数据结构速成攻略.docx

《数据结构速成攻略.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》速成攻略考试题型：选择、填空、简答、算法。第1章绪论1、存储结构（物理结构）：顺序存储结构（特点：只存数据不存关系，其关系体现在存储位置上）和链式存储结构（特点：需存数据及其关系）2、逻辑结构：集合、线性结构、树型结构、图型结构（其中树和图属于非线性结构）3、数据类型:原子类型（非结构，可分解）、结构类型（不可分解）4、算法的时间复杂度（一个算法的时间耗费的数量级）、空间复杂度与问题规模n有关Eg：for（i=0；i

2、顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。△设每个元素需占用L个存储单元，则第i个数据元素ai的存储位置为Loc（ai）=Loc（ai）+L*（i-1）。△当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上，移动元素的个数取决于插入或删除元素的位置。△若表长为n，则插入、删除操作平均移动个元素，算法时间复杂度为O（n）。△优点：存储密度大（＝1），存储空间利用率高，便于访问。缺点：插入或删除元素时不方便。△宜做查找这样的静态操作。若线性表长度变化不大（插入、删除等操作在表尾进行）

3、，且主要操作是查找，则采用顺序表。2、线性表的链式存储结构（顺序存取）：△链式存储时，相邻数据元素可随意存放（逻辑相邻物理不一定相邻），但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。△每个元素由结点（Node）构成，它至少包括两个域，数据域（data）：存储数据元素信息；指针域（link）：存储直接后继存储位置（指示数据元素之间的逻辑关系）。△整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点的存储位置。最后一个数据元素没有直接后继，现行链表中最后一个结点的指针为“空”（NULL）。△优点：插入或删除元素时很方便，使用灵活。缺点：存储

4、密度小（<1），存储空间利用率低。△宜做插入、删除等动态操作。若线性表长度变化较大，且主要操作是插入、删除则采用链表。3、单链表△插入操作(核心语句)：s->next=p->next;p->next=s;△删除操作(核心语句)：q=p->next;p->next=q->next;free(q);△在单链表中，除了首元结点外，任意结点内的存储位置由前驱结点的后继指针指示。△在单链表中设置头结点的作用是简化链表操作。4、L为指向表头结点的指针，p为指向表尾结点的指针，p满足的条件（判断是哪类链表）：单链表p->next==NULL循环链表（表中最后一个结点的指针域指向头结点，整个

5、链表形成一个环）p->next==L双向链表（结点中有两个指针域，其一指向直接后继，另一指向直接前驱）p->next==NULL双向循环链表 p->next==NULL 5、L为指向表头结点的指针，链表为空，应满足条件：单链表L->next==NULL循环链表L->next==L双向链表L->next==NULL双向循环链表 L->next==NULL&&L->prior==NULL  第3章  栈和队列1、栈 △栈是限定仅在表尾进行插入（进栈Push）或删除（出栈Pop）操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。△栈的修改是按后进先出的原则进行的

6、。2、队列△队列是一种先进先出的线性表。△队列只允许在表的一端进行插入，而在另一端删除元素。允许插入的一端叫做队尾，允许删除的一端则称为对头。3、栈和队列的顺序存储和链式存储 △顺序栈（栈的顺序存储结构）是利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。（以栈顶指针top=0表示空栈）△顺序栈中入栈操作需判断栈满，出栈操作需判断栈空。△链栈（栈的链式存储结构）是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。△链栈中指针方向指向前驱结点。△链栈入栈操作（不需判断栈满）：p->data=x;//设置新结点的值

7、p->next=top;//将新元素插入栈中top=p；//将新元素设置为栈顶△链栈出栈操作（需判断栈空）：p->top;//指向被删除的栈top=top->next;//修改栈顶指针free（p）；4、循环队列，队空、队满的条件△设数组维数M，两个指针front（队头指针）、rear（队尾指针）队空：front==rear队满：（rear+1）%M=front入队列：rear=（rear+1）%M出队列：front=（front+1）%M△循环队列中是否能插入下一个元素与队头指针与队尾指针有关。△循环