数据结构第二章线性表要点.ppt

习题 例如 ： LA=(3,5,8,11) LB=(2,6,8,9,11,15,20) 则 LC=(2,3,5,6,8,8,9,11,11,15,20) 算法分析: 3 5 8 11 2 6 8 9 11 15 20 LA LB LC i j 2 j 3 i 5 i 顺序表情况 习题 4. 简述下列术语：线性表，顺序表，链表。 5. 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么? 6. 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素? 习题 7. 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 8. 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 习题 9 写一求单链表的结点数目ListLength(L)的算法。 10 写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 11 写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 习题 12 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。 第二章内容到此结束… 从本章开始，学习最简单的也是最常用的数据结构--线性结构，包括：线性表、栈、队列和串。 本章学习线性表，第三章和第四章分别讨论栈、队列和串。 本章的重点和难点：链表 单链表（线性链表）：前三点 循环链表和双向链表的特点：第四点 线性结构的特点是：在数据元素的非空集合中，（1）~（4）。第一个元素又称为开始元素，最后一个称为终端元素。 同一性：又称均匀性。 举例： La = (2, 5, 7, 9) Lb = (4, 5, 6, 7) 合并结果: La = (2, 5, 7, 9, 4, 6) 举例： La = (3, 5, 8, 11) Lb=(2, 6, 8, 9, 11, 15, 20) 归并结果: Lc=(2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) * 数据元素之间的逻辑关系通过结点中的指针来指示的，指针作为元素之间逻辑关系的映像，逻辑上相邻的两个元素其存储的位置可以不相邻，这种结构称为链式存储结构，或者是非顺序映像。单链表由头指针唯一确定。 * * 循环链表中尾指针的应用 考虑如何实现将带有尾指针的两个循环链表合并为一个？ an A a2 a1 an a2 a1 B p=A-next; A=B-next-next; free(B-next); B-next=p; A=B; 带尾指针的循环链表 rear 31 48 15 57 22 如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。 在表尾插入，时间复杂性 O(1) 在表尾删除，时间复杂性 O(n) 在表头插入，相当于在表尾插入 在表头删除，时间复杂性 O(1) 2.3.3 双向链表 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点有两个指针域, 结构如下： 双向链表通常采用带头结点的循环链表形式。 前驱方向 ? ? 后继方向 prior data next 双向链表的C语言定义 typedef struct DuLNode { ElemType data; struct DuLNode *prior,*next; } DuLNode ,*DuLinkList; prior data next 空双向循环链表： 非空双向循环链表： L L A B 结点指向 p-prior-next == p == p-next-prior p-prior p-next p prior next 双向链表中插入操作 s=(DuLNode *)malloc(sizeof(DuLNode )); s-data=e; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; e s b a p 双向链表的插入操作算法: Status ListInsert_DuL ( DuLinkList L, int i, ElemType e ) { if