更多优质自考资料尽在百度贴吧自考乐园俱乐部
(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,可以直接进入俱乐部
自考数据结构重点(珍藏版)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)