更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
14.单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。判断空链表的条件是head==head->next;
15. 仅设尾指针的单循环链表: 用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear==rear->next;
16.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。
具体算法：
LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针 LinkList p=A->next;//①保存A表的头结点位置
A->next=B->next->next;//②B表的开始结点链接到A表尾 free(B->next);//③释放B表的头结点 B->next=p;//④
return B;//返回新循环链表的尾指针
循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
17. 双向链表: 双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来，为双（向）循环链表。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
18.双向链表的前插和删除本结点操作 ①双链表的前插操作
void DInsertBefore(DListNode *p,DataType x){//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
DListNode *s=malloc(sizeof(DListNode));//① s->data=x;//②
s->prior=p->prior;//③ s->next=p;//④
p->prior->next=s;//⑤ p->prior=s;//⑥ }
②双链表上删除结点*p自身的操作
void DDeleteNode(DListNode *p)
{//在带头结点的双链表中，删除结点*p，设*p为非终端结点 p->prior->next=p->next;//① p->next->prior=p->prior;//② free(p);//③ }
与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。
19. 存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即,存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
20.顺序表和链表比较
顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑： 顺序表 分配方式 静态分配。程序执行之前必须明确规定存储规模。若线性表长度n变化较大，则存储规模难于预先确定估计过大将造成空间浪费，估计太小又将使空间溢出机会增多。 存储密度 为1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。 链表 动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。 <1 存取方式 随机存取结构，对表中任一结点都可在O顺序存取结构，链表中的结点，需从头指针（1）时间内直接取得线性表的操作主要起顺着链扫描才能取得。 是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。 插入删除操作 在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。 在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜 第三章 栈 1. 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。 (2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中\最新\的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
2.顺序栈：栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 ①顺序栈中元素用向量存放
②栈底位置是固定不变的，可设置在向量两端的任意一个端点
③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 3. 进栈操作：进栈时，需要将S-＞top加1， ①S-＞top==StackSize-1表示栈满
②\上溢\现象--当栈满时，再做进栈运算产生空间溢出的现象。 退栈操作：退栈时，需将S-＞top减1 ①S-＞top<0表示空栈
②\下溢\现象--当栈空时，做退栈运算产生的溢出现象。 下溢是正常现象，常用作程序控制转移的条件。 4. 两个栈共享同一存储空间:
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
当Top1=Top2-1时，栈满 ════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
5. 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。 链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算
6. 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。 允许删除的一端称为队头（Front），允许插入的一端称为队尾（Rear），当队列中没有元素时称为空队列，队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
7. 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
顺序队列的基本操作
①入队时：将新元素插入rear所指的位置，然后将rear加1。
②出队时：删去front所指的元素，然后将front加1并返回被删元素。 当头尾指针相等时，队列为空。
在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 8. 顺序队列中的溢出现象：
①当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 ②当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
③\假上溢\现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为\假上溢\现象。
9.循环队列：为充分利用向量空间，克服\假上溢\现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://m.cmpx.com.cn//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： ① 方法一：
if(i+1==QueueSize) //i表示front或rear i=0; else i++;
② 方法二--利用\模运算\ i=(i+1)%QueueSize；
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是\空\还是\满\。 解决这个问题的方法至少有三种：
① 另设一布尔变量以区别队列的空和满； ② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③ 使用一个计数器记录队列中元素的总数（即队列长度）。
10.循环队列的基本运算: ① 置队空:
Q->front=Q->rear=0; Q->count=0; ② 判队空:
return Q->count==0; ③ 判队满:
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
自考数据结构重点（珍藏版）
