链表、双向链表、循环链表.ppt

判断题： （1）线性表的逻辑顺序与存储顺序总是一致的。 F T T T F （2）顺序存储的线性表可以按序号随机存取。 （3）在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 （4）在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。 （5）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。 假定建立了以下链表结构，指针p、q分别指向如图所示的结点，则以下可以将q所指结点从链表中删除并释放该结点的语句组是 A) free(q); p-next=q-next; B) (*p).next=(*q).next; free(q); C) q=(*q).next; (*p).next=q; free(q); D) q=q-next;p-next=q;p=p-next; free(p); head 8 4 3 p q date next 练1 练2 head ? E F \0 p date next G s 若已建立如下图所示的单向链表结构,在该链表结构中，指针p、s分别指向图中所示结点，则不能将s所指的结点插入到链表末尾仍构成单向链表的语句组是 A) p =p-next; s-next=p; p-next=s;B) p =p-next; s-next=p-next; p-next=s;C) s-next=NULL; p=p-next; p-next=s;D) p=(*p).next; (*s).next=(*p).next; (*p).next=s; 要点回顾 线性结构(包括表、栈、队、数组）的定义和特点： 仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。 2. 线性表 逻辑结构：“一对一” 或 1:1 存储结构：顺序、链式 运 算 ：修改、插入、删除 3.顺序存储 特征：逻辑上相邻，物理上也相邻； 优点：随机查找快 O(1) 缺点：插入、删除慢 O(n) 改进方案：链表存储结构 循环链表的特点：从任一结点出发均可找到表中其他结点 双向链表的特点：可方便找到任一结点的前驱 4.链式存储 特征：逻辑上相邻，物理上未必相邻； 优点：插入、删除快 O(1) 缺点：随机查找慢 O(n) 5.几种特殊链表的特点： 链表存储结构是一种动态数据结构，其特点是它包含的据对象的个数及其相互关系可以按需要改变，存储空间是程序根据需要在程序运行过程中向系统申请获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储结构所具有的弱点。 * * * AC(B?) AAB ABC BD BD 插入步骤 修改s指针域,使其指向p结点的后继结点:s?next=p?next p B C X s A 修改p指针域, 使其指向新结点s: p?next＝s 后面的结点都将从链表中脱离 它们占用着内存空间，程序却找不到它们了 3 .单链表: (2)单链表删除：不需要移动元素,仅修改指针链接 删除结点 删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可 1.2.3 线性表的链式存储结构 删除步骤 修改q结点指针域 q?next＝p?next C p B A 删除前 删除后 q p C B A free(p); 先找到p的前驱结点q q?next＝q?next?next 单链表结构和顺序存储结构的比对： 假设我们的校园只有单行道 保安沿这条路线巡逻，需要查遍所有地点。有一天，保安先从主教出发，想把以上地点走一遍，此时主管告诉他，不行，你必须从主校门开始走。。。 事实上，把主校门和北门连接起来，形成一个环路，就解决了这个问题。 单链表的尴尬 4.循环链表 特点：表中最后一个结点的指针域指向头结点， 整个链表首尾相连形成一个环。 带头结点的循环链表 1.2.3 线性表的链式存储结构 优点：从表中任一结点出发均可找到表中其它结点。 对带头结点的单循环链表head为空的判定条件是 head-next=head 带头结点的空循环链表 例：假设长度大于1的循环单链表中，既无头结点也无头指针，p指向该链表中某一结点，编写一个算法删除该结点的前驱结点。 单链表只能从头结点开始遍历整个链表，而循环单链表则可以从表中任意结点开始遍历整个链表。 ... a1 a2 an-1 a0 p s=p; while(s.