数 2-线性表.ppt

Transcription

1 数据结构华中科技大学计算机学院

2 第二章 2.1 线性表的定义 线性表 线性表的逻辑结构 1. 线性表 : 由 n(n 0) 个数据元素 (a 1,a 2,..., a n ) 构成的有限序列 记作 : L=(a 1,a 2,...,a n ) a 1 首元素 a n 尾元素 2. 表的长度 ( 表长 ) 线性表中数据元素的数目 3. 空表 不含数据元素的线性表 2

3 线性表举例 : 例 1. 字母表 L1=(A,B,C,...,Z) 表长 26 例 2. 姓名表 L2=( 李明, 陈小平, 王林, 周爱玲 ) 表长 4 例 3. 图书登记表 序号 书 名 作 者 单价 ( 元 ) 数量 ( 册 ) 1 程序设计语言 李 明 数据结构 陈小平 n DOS 使用手册 周爱玲 表长 n 3

4 线性表的特征 : 对于 L=(a 1,a 2,...,a i-1,a i,a i+1,...,a n ) 1.a i-1 在 a i 之前, 称 a i-1 是 a i 的直接前驱, (1<i n) 2.a i+1 在 ai 之后, 称 a i+1 是 a i 的直接后继 (1 i<n) 3.a 1 没有前驱 4.a n 没有后继 5.a i (1<i<n) 有且仅有一个直接前驱和一个直接后继 4

5 2.1.2 抽象数据类型线性表的定义 ADT List { 数据对象 :D={a i a i ElemSet,i=1,2,,...n,n>=0} 数据关系 :R1={<a i-1,a i > a i-1,a i D,i=2,,...n} 基本操作 : 1.IniList(&L) // 构造空表 L 2.ListLength(L) 3.GetElem(L,i,&e) // 求表 L 的长度 // 取元素 ai, 由 e 返回 ai 4.PriorElem(L,ce,&pre_e) // 求 ce 的前驱, 由 pre_e 返回 5.ListInsert(&L,i,e) 6.ListDelete(&L,i,&e) 7.ListEmpty (L)... }ADT List // 在元素 ai 之前插入新元素 e // 删除第 i 个元素 // 判断 L 是否为空表 5

6 说明 1. 删除 L 中第 i 个数据元素 (1<=i<=n), 记作 : ListDelete(&L,i,&e) L=(a 1,a 2,...,a i-1,a i,a i+1,...,a n ) 指定序号 i, 删除 a i L=(a 1,a 2,...,a i-1,a i+1,...,a n ) 2. 指定元素值 x, 删除表 L 中的值为 x 的元素, 记作 : DeleteElem(&L,x) 3. 在元素 ai 之前插入新元素 e(1<=i<=n+1) L=(a 1,a 2,...,a i-1,a i,...,a n ) 插入 e L=(a 1,a 2,...,a i-1,e, a i,...,a n ) 4. 查找 ---- 确定元素值 ( 或数据项的值 ) 为 e 的元素 给定 : L=(a 1,a 2,...,a i,...,a n ) 和元素 e 若有一个 a i =e, 则称 查找成功,i=1,2,...,n 否则, 称 查找失败 6

7 5. 排序 ---- 按元素值或某个数据项值的递增 ( 或递减 ) 次序重新排列表中各元素的位置 例. 排序前 : L=(90,60,80,10,20,30) 排序后 : L=(10,20,30,60,80,90) L 变为有序表 6. 将表 La 和表 Lb 合并为表 Lc 例. 设有序表 : La=(2,14,20,45,80) Lb=(8,10,19,20,22,85,90) 合并为表 Lc=(2,8,10,14,19,20,20,22,45,80,85,90) 7. 将表 La 复制为表 Lb La= (2,14,20,45,80) Lb= (2,14,20,45,80) 7

8 可利用现有基本操作组成更复杂的操作 : 例 : 将线性表 Lb 中的, 且不在线性表 La 数据元素合并到线性表 La 中 void union(list &La, List &Lb) { La_len=ListLength (La); // 求线性表 La 的长度 Lb_len=ListLength (Lb); // 求线性表 Lb 的长度 for (i=1; i<= Lb_len; i++) { GetElem(Lb, i, e); // 取 Lb 的的第 i 个数据元素赋给 e // 即依次取出 Lb 中的所有元素 if (!LocateElem(La, e, equal)) // 判断 e 在 La 中是否存在 ListInsert(La, ++La_len, e); // 不存在则插入 } } 8

9 2.2 线性表的顺序表示 ( 顺序存储结构 ) 顺序分配 将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中, 这种分配方式称为顺序分配或顺序映像 由此得到的存储结构称为顺序存储结构或向量 ( 一维数组 ) 例. 线性表 :a=(30,40,10,55,24,80,66) 内存状态 a 1 a 2 a 3 a 4 a 5 a 6 a 7 C 语言中静态一维数组的定义 : int a[11]; // 两种存储方式 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

10 (a 1,a 2,...a n ) 顺序存储结构的一般形式 序号存储状态存储地址 1 b 2 b+l i n maxleng a 1 a 2... a i... a n // // // b+(i-1)*l b+(n-1)*l 自由区 b+(maxleng-1)*l 其中 : b---- 表的首地址 / 基地址 / 元素 a1 的地址 l----1 个数据元素所占存储单元的数目 maxleng---- 最大长度, 为某个常数 10

11 2.2.2 线性表顺序结构在 C 语言中的定义 例 1. 分别定义元素所占空间 表长 尾元素的位置 或 : #define maxleng 100 { ElemType la[maxleng+1];// 下标 :0,1,,maxleng } int length; int last; // 当前长度 //an 的位置 a1 a2... ai... an 0 1 i 1 n-1 n maxleng last=length-1=n-1 a1 a2... ai... an i n maxleng last=length=n 结论 : last 和 length 二取一 11

12 线性表顺序结构在 C 语言中的定义 ( 静态分配 ) 例 2. 元素所占空间和表长合并为 C 语言的一个结构类型 : #define maxleng 100 typedef struct { ElemType elem[maxleng];// 下标 :0,1,...,maxleng-1 int length; // 表长 } SqList; SqList La;... 其中 :typedef--- 别名定义,SqList---- 结构类型名 La---- 结构类型变量名 La.length--- 表长 La.elem[0]----a1 La.elem[La.length-1]---an 12

13 讨论 : q 顺序表的存储结构是一维数组, 如果插入若干元素 后元素总个数超过数组定义的长度怎么办? 采用动态分配的一维数组 q 在 C 语言中如何实现动态数组? 利用 C 中几个库函数 ( 在 <stdlib.h> 中 ): sizeof(x):c 中的单目操作符, 计算变量 x 的长度 ( 字节数 ); malloc(m) : 开辟 m 字节长度的地址空间, 并返回这段空间的 首地址 ; realloc(*p, newsize) : 新开一片大小为 newsize 的连续空间, 并把以 *p 为首址的原空间数据都复制进去 free(p) : 释放指针 p 所指变量的存储空间 13

14 线性表顺序结构在 C 语言中的定义 ( 动态分配 ) #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem;// 存储空间基地址 int length; // 表长 ( 表中有多少个元素 ) int listsize; } SqList; SqList Lb; // 当前分配的存储容量 //( 以 sizeof(elemtype) 为单位 其中 :typedef--- 别名定义,SqList---- 结构类型名 Lb---- 结构类型变量名 Lb.length--- 表长 Lb.elem[0]----a1 Lb.elem[Lb.length-1]---a n 14

15 2.2.3 顺序存储结构的寻址公式 a1 a2... ai... an // // // i= i... n 地址 = b b+1*l b+(i-1)l b+(n-1)l 假设 : 线性表的首地址为 b, 每个数据元素占 l 个存储单元, 则表中任意元素 ai(1 i n) 的存储地址是 : LOC(i)=LOC(1)+(i-1)*l =b+(i-1)*l 例 : 假设 b=1024,l=4,i=35 LOC(i)=b+(i-1)*l =1024+(35-1)*4 = *4 =1160 (1 i n) 15

16 Status InitList_Sq( SqList &L) { // 构造一个空的线性表 L, 利用动态顺序存储结构 L.elem= (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (! L.elem) exit(overflow); // 存储分配失败 L.length = 0; L.listsize= LIST_INIT_SIZE; return OK; //?? } // InitList_Sq 算法时间复杂度 : O(1) 16

17 2.2.4 插入算法实现举例 设 L.elem[0..maxleng-1] 中有 legth 个元素, 在 L.elem[i-1] 之前插入新元素 e,1<=i<=length 例.i=3,e=6,length=6 插入 6 之前 : // // // ,30,20,8 依次后移一个位置插入 6 之后 : // //

18 在线性表 L=(a 1,a 2,...,a i-1,a i,a i+1,...,a n ) 中的第 i 个元素前插入元素 x a 1 a 2 a i a i+1 a n /// ///. /// 0 1 i-1 i n-1... n maxleng-1 a 1 a 2 a i a i a i+1 a n ///. /// 0 1 i-1 i n-1 n maxleng-1 移动元素下标范围 : x i-1 ~ n-1 或 i-1 ~ L.length-1 18

19 算法 1:( 用指针指向被操作的线性表, 静态分配 ): // 设 L.elem[0..maxleng-1] 中有 length 个元素, 在 L.elem[i-1] 之前插入新元素 e,(1<=i<=length+1) int Insert1(SqList *L,int i,elemtype e) { if (i<1 i>l->length+1) return ERROR //i 值不合法 if (L->length>=maxleng) return OVERFLOW // 溢出?? for (j=l->length-1;j>=i-1;j--;) L->elem[j+1]=L->elem[j]; // 向后移动元素 L->elem[i-1]=e; // 插入新元素 L->length++; // 长度变量增 1 return OK // 插入成功 } 19

20 算法 2:( 用引用参数表示被操作的线性表, 静态分配 ) : // 设 L.elem[0..maxleng-1] 中有 length 个元素, 在 L.elem[i-1] 之前插入新元素 e,(1<=i<=length+1) Status Insert2(SqList &L,int i,elemtype e) { if (i<1 i>l.length+1) return ERROR //i 值不合法 if (L.length>=maxleng) return OVERFLOW // 溢出 for (j=l.length-1;j>=i-1;j--;) L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; // 向后移动元素 // 插入新元素 L.length++; // 长度变量增 1 return OK // 插入成功 } 20

21 算法 2.4 ( 动态分配线性表空间, 用引用参数表示被操作的线性表 ) int ListInsert_Sq(SqList &L,int i, ElemType e) {int j; if (i<1 i>l.length+1) //i 的合法取值为 1 至 n+1 return ERROR; if (L.length>=L.listsize) /* 溢出时扩充 */ { ElemType *newbase; newbase=(elemtype *) realloc(l.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if (newbase==null) return OVERFLOW; // 扩充失败 L.elem=newbase; L.listsize+=LISTINCREMENT; } 21

22 // 向后移动元素, 空出第 i 个元素的分量 elem[i-1] for(j=l.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; /* 新元素插入 */ L.length++; /* 线性表长度加 1*/ return OK; } 22

23 2.2.5 插入操作移动元素次数的分析 在 (a 1,a 2,...,a i,...a n ) 中 a i 之前插入新元素 e ( 1<=i<=n+1 ) a 1 a 2.. a i.. a n 0 1 i-1 n-1 当插入点为 : 1 2 i n-1 n n+1 需移动元素个数 : n n-1 n-i 假定 p i 是在各位置插入元素的概率, 且 p 1 =p 2 =...=p n =p n+1 =1/(n+1), 则插入一个元素时移动元素的平均值是 : n+1 E is = p i (n-i+1)=1/(n+1)*[n+(n-1) ]=n/2 i=1 23

24 2.2.6 删除操作及移动元素次数的分析 线性表操作 ListDelete(&L, i, &e) 的实现 : 分析 : 删除元素时, 线性表的逻辑结构发生什么变化? 24

25 (a 1,, a i-1, a i, a i+1,, a n ) 改变为 (a 1,, a i-1, a i+1,, a n ) <a i-1, a i >, <a i, a i+1 > <a i-1, a i+1 > a 1 a 2 a i-1 a i a i+1 a n a 1 a 2 a i-1 a i+1 a n 表的长度减少 25

26 Status ListDelete_Sq (SqList &L, int i, ElemType &e) { if ((i < 1) (i > L.length)) return ERROR; p = &(L.elem[i-1]); e = *p; q = L.elem+L.length-1; // 删除位置不合法 // p 为被删除元素的位置 // 被删除元素的值赋给 e // 表尾元素的位置 for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移元素左移 --L.length; // 表长减 1 return OK; } // ListDelete_Sq 26

27 a 1 a 2 a i-1 a i a i+1 a n // // 0 1 i-2 i-1 i n-1 a 1 a 2 a i-1 a i+1 a n // // // 当 i= i... n 移动元素个数 = n-1 n-2... n-i... 0 假定 q i 是在各位置删除元素的概率, 且 : q 1 =q 2 =...=q n =1/n 则删除一个元素时移动元素的平均值是 : E = q ( n E dl = 1 n ( n i) n i= 1 = n 1 2 算法时间复杂度为 : O(n) dl n i= 1 i i) 27

28 2.2.7 顺序存储结构的评价 1. 优点 : (1) 是一种随机存取结构, 存取任何元素的时间是一个常数, 速度快 ; (2) 结构简单, 逻辑上相邻的元素在物理上也是相邻的 ; (3) 不使用指针, 节省存储空间 2. 缺点 : (1) 插入和删除元素要移动大量元素, 消耗大量时间 ; (2) 需要一个连续的存储空间 ; (3) 插入元素可能发生 溢出 ; (4) 自由区中的存储空间不能被其它数据占用 ( 共享 ) 内存 : 2k 占用 5k 占用 3k 28

29 2.3 线性表的链式存储结构 链式存储结构特点 : 其结点在存储器中的位置是随意的, 即逻辑上相邻的数据元素在物理上不一定相邻 如何实现? 通过指针指针来实现! 让每个存储结点都包含两部分 : 数据域和指针域链式存储有关的术语 : 结点 : 数据元素的存储映像 由数据域和指针域两部分组成 链表 : n 个结点由指针链组成一个链表 它是线性表的链式存储映像, 称为线性表的链式存储结构 单链表 双链表 多链表 循环链表 29

30 2.3.1 单链表 1. 单链表的一般形式 : (1) 不带表头结点的单链表 : data next head --- a1 --- a an 头指针 首结点 尾结点 其中 :data 称为数据域,next 称为指针域 / 链域 当 head==null, 为空表 ; 否则为非空表 30

31 (2) 带表头结点的单链表 : a. 非空表 : data next head --- /// -- a an 头指针表头结点首结点尾结点 b. 空表 : data next head --- /// 头指针表头结点 其中 :head 指向表头结点, head->data 不放元素, head->next 指向首结点 a1, 当 head->next==null, 为空表 ; 否则为非空表 31

32 头指针 头结点和首元结点的区别 示意图如下 : a 1 head a 2 info a n ^ 头指针头结点首元结点 头指针是指向链表中第一个结点 ( 或为头结点 或为首元结点 ) 的指针 头结点是在链表的首元结点之前附设的一个结点 ; 数据域内只放空表标志和表长等信息, 它不计入表长度 首元结点是指链表中存储线性表第一个数据元素 a 1 的结点 32

33 讨论 1. 在链表中设置头结点有什么好处? 头结点即在链表的首元结点之前附设的一个结点, 该结点的数据域可以为空, 也可存放表长度表长度等附加信息, 其作用是为了对链表进行操作时, 可以对空表 非空表的情况以及对首元结点进行统一处理, 编程更方便 讨论 2. 如何表示空表? 无头结点时, 当头指针的值为空时表示空表 ; 有头结点时, 当头结点的指针域为空时表示空表 头指针 头指针 头结点 ^ ^ 无头结点 有头结点 头结点不计入链表长度! 33

34 线性表的逻辑结构 : 线性表 由 n(n 0) 个数据元素 (a 1,a 2,..., a n ) 构成的有限序列 记作 : L=(a 1,a 2,...,a n ) 线性表顺序存储结构 ( 静态分配 ) #define maxleng 100 typedef struct { ElemType elem[maxleng];// 下标 :0,1,...,maxleng-1 int length; // 表长 } SqList; SqList L; 34

35 线性表顺序存储结构 ( 动态分配 ) #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem;// 存储空间基地址 int length; // 表长 ( 表中有多少个元素 ) int listsize; } SqList; SqList L; a1 // 当前分配的存储容量 //( 以 sizeof(elemtype) 为单位 a2... ai... an // // // LOC(i)=LOC(1)+(i-1)*l =b+(i-1)*l (1 i n) Status ListInsert_Sq(SqList &L,int i, ElemType e) Status ListDelete_Sq (SqList &L, int i, ElemType &e) 顺序表 ( 占用连续存储空间 ) 是一种随机存取结构, 存取速度快 ; 但插入与删除元素要移动大量数据元素, 时间复杂性为 O(n). 35

36 线性表的链式存储结构 (1) 不带表头结点的单链表 : data next head --- a1 --- a an 头指针 首结点 尾结点 (2) 带表头结点的单链表 : a. 非空表 : data next head --- /// -- a an 头指针表头结点首结点尾结点 b. 空表 : data next head --- /// 头指针表头结点 注意 : 头指针 头结点和首元结点的区别 36

37 2 单链表的结点结构 例 1 C 语言的 结构 类型 : struct Lnode { ElemType data; //data 为抽象元素类型 struct Lnode *next; //next 为指针类型 }; 指向结点的指针变量 head,p,q 说明 : struct Lnode *head,*p,*q; 例 2 用 typedef 定义指针类型 : typedef struct Lnode { ElemType data; //data 为抽象元素类型 struct Lnode *next; //next 为指针类型 } Lnode, *Linklist; 指针变量 head,p,q 的说明 : Linklist head,p,q; 37

38 3. 单链表操作和算法举例 : (1) 生成单链表例 1 输入一列整数, 以 0 为结束标志, 生成 先进先出 单链表 若输入 :1,2,3,4,5 则生成 : head - /// ^ #define LENG sizeof(struct Lnode) // 结点所占的字节数 struct Lnode // 定义结点类型 { int data; //data 为整型, 数据域 struct Lnode *next; //next 为指针类型, 指针域 }; 38

39 输入 1: head 初始化 :head //// ^ //// tail 2 p tail ^ 输入 2: head 3 tail 每次输入新元素后 : 1 生成新结点 ;p=malloc( 结点大小 );p->data=e; p->next=null; 2 添加到表尾 ;tail->next=p; 3 设置新表尾 tail=p; //// 1 2 p 1 2 ^ 39

40 先进先出表的产生过程 (1,2,3,4,5,0): tail tail tail tail tail tail head /// 头指针头结点 p p p p p ^ head=malloc(sizeof(struct Lnode)) tail=head p=malloc(sizeof(structlnode)) tail->next=p tail=p p=malloc(sizeof(structlnode)) tail->next=p tail=p tail->next=null; 40

41 算法 : 生成 先进先出 单链表 ( 链式队列 ) struct Lnode *creat1( ) { struct Lnode *head,*tail,*p; // 变量说明 int e; head=(struct Lnode *)malloc(leng); // 生成表头结点 tail=head; // 尾指针指向表头 scanf( %d,&e); // 输入第一个数 while (e!=0) // 不为 0 { p=(struct Lnode *)malloc(leng);// 生成新结点 p->data=e; // 装入输入的元素 e tail->next=p; // 新结点链接到表尾 tail=p; // 尾指针指向新结点 scanf( %d,&e); // 再输入一个数 } tail->next=null; // 尾结点的 next 置为空指针 return head; // 返回头指针 } 41

42 例 2 生成 后进先出 单链表 ( 链式栈 ) 输入 :1,2,3,4,0 生成 : head - /// p 1 3 初始化 : head //// ^ 输入 1: head //// 1 ^ 输入 2: head //// p 1 ^ 2 每次输入新元素后 : 1 生成新结点 ; p=malloc( 结点大小 ); p->data=e; 2 新结点指针指向 首元素 ;p->next=head->next; 3 新结点作为首元素 : head->next=p; 42

43 例 2 生成 后进先出 单链表 ( 链式栈 ) 算法 : struct Lnode *creat2( ) // 生成 后进先出 单链表 { struct Lnode *head,*p; head=(struct Lnode *)malloc(leng); // 生成表头结点 head->next=null; // 置为空表 scanf( %d,&e); // 输入第一个数 while (e!=0) // 不为 0 { p=(struct Lnode *)malloc(leng);// 生成新结点 p->data=e; // 输入数送新结点的 data p->next=head->next; // 新结点指针指向原首结点 head->next=p; // 表头结点的指针指向新结点 scanf( %d,&e); // 再输入一个数 } return head; // 返回头指针 } 43

44 单链表的建立和输出 (Slides from Prof. Liu Yu s Lecture) 例 : 用单链表结构来存放 26 个英文字母组成的线性表 (a,b,c,,z), 请写出 C 语言程序 实现思路 : 先开辟头指针, 然后陆续为每个结点开辟存储 空间并及时赋值, 后继结点的地址要提前送给前面的指针 先挖 坑, 后种 萝卜! 44

45 将全局变量及函数提前说明 : #include<stdio.h stdio.h> #include<stdlib.h stdlib.h> typedef struct Lnode{ char data; struct Lnode *next; }Lnode; Lnode *p,*q,*head; int n ; int m=sizeof(lnode); // 一般需要 3 个指针变量 // 数据元素的个数 /* 结构类型定义好之后, 每个变量的长度就固定了,m 求一次即可 */ 45

46 void build( ) { inti; head=(lnode*)malloc(m); p=head; for( i=1; i<26; i++) 特别容易忘记!! //m=sizeof(node) 前面已求出 // 因尾结点要特殊处理, 故 i 26 { p->data=i+ a -1; // 无头结点, 首结点值为字符 a p->next=(lnode*)malloc(m); // 为后继结点 挖坑! p=p->next;} p->data=i+ a -1; // 字母链表的生成 要一个个慢慢链入 // 让指针变量 P 指向后一个结点 // 最后一个元素要单独处理 p->next=null ;} // 单链表尾结点的指针域要置空! 46

47 void display() /* 字母链表的输出 */ {p=head; while (p) sum=0; // 当指针不空时循环, 仅限于无头结点的情况 {printf("%c",p->data); } } p=p->next; // 让指针不断 顺藤摸瓜 sum++; 讨论 : 要统计链表中数据元素的个数, 该如何改写? 47

48 单链表的修改 ( 或读取 ) 思路 : 要修改第 i 个数据元素, 必须从头指针起一直找到该结点的指针 p, 然后才能执行 p->data=new_value 读取第 i 个数据元素的操作函数可写为 : Status GetElem_L(LinkList L, int i, ElemType &e) // 带头结点的链表 L {p=l->next; j=1; while(p&&j<i){p=p->next; ++j;} if(!p j>i ) return ERROR; // if i<1? p->data =e; // 若是读取则为 :e=p->data; return OK;}//GetElem_L 缺点 : 寻找单链表中第 i 个元素, 只能从头指针开始逐一查询 ( 顺藤摸瓜 ), 无法随机存取 48

49 (2) 插入一个结点 例 1: 在已知 p 指针指向的结点后插入一个元素 x a b p x f 执行 : f=(struct Lnode *)malloc(leng); f->data=x; f->next=p->next; p->next=f; // 生成 // 装入元素 x // 新结点指向 p 的后继 // 新结点成为 p 的后继 思考 : 最后两条语句能互换么? 49

50 例 2: 在已知 p 指针指向的结点前插入一个元素 x q p a b 执行 : x f f=(struct Lnode *)malloc(leng); f->data=x; f->next=p; q->next=f; // 生成 // 装入元素 x // 新结点成为 p 的前趋 // 新结点成为 p 的前趋结点的后继 50

51 例 3: 输入一列整数, 以 0 为结束标志, 生成递增有序单链表 ( 不包括 0) 递增有序单链表的两种形式 : head ^ head ///// ^ 51

52 分析 : 假定有一个无表头结点的递增排序的链表, 插入一个 新结点, 使其仍然递增 f 7 基本步骤 : 1 定位 ; 2 准备新结点 ; 3 修改指针 head ^ f->next=p; q ^ qp pq p q->next=f; p, q 可能为 NULL 1 (p, q 同时空 ) 空表插入 ; 2 ( 仅 p 为空 ) 尾部插入 ; 3 ( 仅 q 为空 ) 首部插入 ; 52

53 e 为新元素值 插入算法 NULLŁq headłp p!=null&& e>p->data 真 płq p->nextłp 1 空表插入 ; 2 尾部插入 ; 3 首部插入 ; 4 一般插入 假 q==null 真 new(f) ełf->data NULLŁf->next 真 假 p==null 返回 head 假 q==null 真 不带头结点算法 fłhead fłq->next płf->next fłq->next fłhead płf->next 假 53

54 算法 1: 在不带头结点的递增有序单链表中插入元素 e ( 不包括 0) struct Lnode * creat3_1(struct Lnode *head,int e) { q=null; p=head; //q,p 扫描, 查找插入位置 while (p && e>p->data) // 未扫描完, 且 e 大于当前结点 { q=p; p=p->next;} //q,p 后移, 查下一个位置 f=(struct Lnode *)malloc(leng); // 生成新结点 f->data=e; // 装入元素 e if (p==null){ f->next=null; if (q==null) //(1) 对空表的插入 head=f; else q->next=f;} //(2) 作为最后一个结点插入 else if (q==null) //(3) 作为第一个结点插入 {f->next=p; head=f;} else {f->next=p; q->next=f;} //(4) 一般情况插入新结点 return head; } 54

55 e 为新元素值 插入算法 NULLŁq headłp new(f) ełf->data NULLŁf->next p!=null&& e>p->data 假 1 真 q==null 2 假 真 płq fłhead fłq->next p->nextłp płf->next 1 作为第一元素或首元素插入 ; 2 一般插入或作为尾元素插入 ; 返回 head 55

56 main() { struct Lnode *head; head=null; scanf( %d,&e); while (e!=0) { head=creat3_1(head,e); scanf( %d,&e); } } // 定义头指针 // 置为空表 // 输入整数 // 不为 0, 未结束 // 插入递增有序单链表 // 输入整数 56

57 分析 : 假定有一个有表头结点的递增排序的链表, 插入一个 新结点, 使其仍然递增 f 7 基本步骤 : 1 定位 ; 2 准备新结点 ; 3 修改指针 head /// f->next=p; q qp pq p q->next=f; q 不可能为空 57

58 带头结点算法 插入算法 : Begin headłq head->nextłp p!=null&& e>p->data 真 płq p->nextłp 假 1 定位 new(f) ełf->data fłq->next płf->next 2 准备新结点位 3 修改指针 return 58

59 算法 2: 生成带头结点的递增有序单链表 ( 不包括 0) void creat3_2(struct Lnode *head,int e) { q=head; p=head->next; //q,p 扫描, 查找插入位置 } while (p && e>p->data) // 未扫描完, 且 e 大于当前结点 { q=p; p=p->next; //q,p 后移, 查下一个位置 } f=(struct Lnode *)malloc(leng); // 生成新结点 f->data=e; // 装入元素 e f->next=p; q->next=f; // 插入新结点 59

60 main() { head=(struct Lnode *)malloc(leng);// 生成表头结点 head->next=null; // 置为空表 scanf( %d,&e); // 输入整数 while (e!=0) // 不为 0, 未结束 { creat3_2(head,e); // 插入递增有序单链表 head scanf( %d,&e); // 输入整数 } } 60

61 算法 3: 在单链表的指定位置 ( 结点 i 之前 ) 插入新元素 输入 : 头指针 L 位置 i 数据元素 e 输出 : 成功返回 OK, 否则 ERROR p p p p L /// a 1 a 2 a i-1 a i a n ^ 执行 :p=l 当 p 不为空执行 :p=p->next 定位到第 i-1 个结点 i-1 次 当 i<1 或 p 为空时插入点错 否则新结点加到 p 指向结点之后 61

62 算法 3 程序 : Status ListInsert_L(Linklist &L,int i, ElemType e) {p=l; j=1; while (p && j<i) { p=p->next; //p 后移, 指向下一个位置 j++;} if (i<1 p==null) // 插入点错误 return ERROR; f=(linklist) malloc(leng); // 生成新结点 f->data=e; // 装入元素 e f->next=p->next; p->next=f; // 插入新结点 return OK; }//ListInsert_L 62

63 (3) 在单链表中删除一个结点 q p data next next A B C q p 删除 B 1 执行 :q->next=p->next; //A 的 next 域 =C 的地址 (B 的 next 域 ) A B C 执行 :free(p);// 释放 p 所指向的结点空间 q p A C

64 算法 1: 在带表头结点的单链表中删除元素值为 e 的结点 int Delete1(Linklist head, ElemType e) { struct Lnode *q,*p; q=head; p=head->next; //q,p 扫描 while (p && p->data!=e) // 查找元素为 e 的结点 { q=p; // 记住前一个结点 p=p->next; // 查找下一个结点 } if (p) // 有元素为 e 的结点 { q->next=p->next; // 删除该结点 free(p); // 释放结点所占的空间 return YES; } else return NO; // 没有删除结点 } 64

65 算法 2(2.9): 在单链表中删除指定位置的元素 输入 : 头指针 L 位置 i 输出 : 成功返回 OK, 否则 ERROR p p p p L /// a 1 a 2 a i-1 a i a n ^ 执行 :p=l 当 p->next 不为空 执行 :p=p->next 定位到第 i-1 个结点 i-1 次 当 i<1 或 p->next 为空时删除点错 否则 p 指向结点的后继跳过原后继 65

66 Status ListDelete_L(LinkListL, int i, ElemType &e) { // 删除以 L 为头指针 ( 带头结点 ) 的单链表中第 i 个结点 p = L; j = 0; while (p->next && j < i-1) { p = p->next; ++j; } // 寻找第 i 个结点, 并令 p 指向其前趋 if (!(p->next) j > i-1) return ERROR; // 删除位置不合理 q = p->next; p->next = q->next; // 删除并释放结点 e = q->data; free(q); return OK; } // ListDelete_L 算法 2.9 的时间复杂度为 : O(ListLength(L)) 66

67 (4) 将两个有序单链表 La 和 Lb 合并为有序单链表 Lc: ( 该算法利用原单链表的结点 ) pa pa : La /// 2 5 pc pc pc Lb /// pb pb La ///

68 算法设计 : 算法主要包括搜索 比较 插入三个操作 : 搜索 : 需要设立三个指针来指向 La Lb 和 Lc 链表 ; 比较 : 比较 La 和 Lb 表中结点数据的大小 ; 插入 : 将 La 和 Lb 表中数据较小的结点插入新链表 Lc 请注意链表的特点, 仅改变指针便可实现数据的移动, 即 数据不动, 指针动 68

69 算法实现 :P31 算法 2.12 Void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { // 已知单链线性表 La 和 Lb 的元素按值非递减排列 free(lb); } //MergeList_L 归并为 Lc 后也按值非递减排列 pa=la->next; pb=lb->next; Lc=pc=La; while(pa&&pb) // 用 La 的头结点作为 Lc 的头结点 // 将 pa pb 结点按大小依次插入 Lc 中 { if (pa->data<=pb->data) {pc->next=pa; pc=pa; pa=pa->next;} else {pc->next=pb; pc=pb; pb=pb->next} } pc->next = pa? pa: pb ; // 插入非空表的剩余段 // 释放 Lb 的头结点 69

70 4. 静态链表 ---- 用一维数组描述的链表 head - // 1 A 2 B 3 C 4 D 5 E 头指针表头结点首结点尾结点 若某种高级语言没有指针 类型, 能否实现链式存储 结构和运算? 如何实现? 序号 data cur 0 // 1 1 A 2 2 B 3 3 C 4 4 D 5 5 E 0 6 // // 7 // // 指示域或 游标 70

71 动态链表样式 : 静态链表样式 : 数据 数据 数据 指针 指针 指针 数据 数据 数据 数据 数据 指示 指示 指示 指示 指示 数组中每个元素都至少有两个分量, 属于结构型数组 常用于无指针类型的高级语言中 静态单链表的类型定义如下 : #define MAXSIZE 1000 // 预分配最大的元素个数 ( 连续空间 ) typedef struct { ElemType data ; // 数据域 int cur ; // 指示域 }component, SLinkList[MAXSIZE] ; // 一维结构型数组 71

72 一线性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ), 用静态链表如何表示? 教材 P32 例题 i data 头结点 ZHAO LI cur 说明 1: 假设 S 为 SLinkList 型变量, 则 S[MAXSIZE] 为一个静态链表 ; S[0].cur 则表示第 1 个结点在数组中的位置 QIAN WU ZHOU SUN 说明 2: 如果数组的第 i 个分量表示链表的第 k 个结点, 则 : S[i].data 表示第 k 个结点的数据 ; S[i].cur 表示第 k+1 个结点 ( 即 k 的直接后继 ) 的位置

73 说明 : 静态链表的插入与删除操作与普通链表一样, 不需要移动元素, 只需修改指示器就可以了 例如 : 在线性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU ) 的 QIAN, SUN 之间插入新元素 LIU, 可以这样实现 : i data 头结点 ZHAO LI QIAN WU ZHOU SUN cur LIU 6 Step1: 将 QIAN 的游标值存入 LIU 的游标中 : S[7].cur = S[3].cur; Step2: 将 QIAN 的游标换为新元素 LIU 的下标 : S[3].cur = 7 73

74 线性链表小结 线性链表是线性表的一种链式存储结构 线性链表的特点 1 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系 ; 2 插入删除操作通过修改结点的指针实现 ; 3 不能随机存取元素 74

75 2.3.2 循环链表 : 最后一个结点的指针域的指针又指回头结点的链表 1. 一般形式 (1) 带表头结点的非空循环单链表 H - // a 1 a 2... a n 头指针表头结点首结点尾结点 有 :H->next H, H NULL (2) 带表头结点的空循环单链表 H - // 头指针 表头结点 有 :H->next==H, H NULL 和单链表的差别仅在于 : 判别链表中最后一个结点的条件不再 是 后继是否为空, 而是 后继是否为头结点 75

76 2. 只设尾指针的循环链表 (1) 非空表 /// a 1 a 2... a n tail 表头结点首结点尾结点尾指针 有 : tail 指向表尾结点 tail->data==an tail->next 指向表头结点 (2) 空表 tail->next->next 指向首结点 tail->next->next->data== a1 /// tail 有 :tail->next==tail 表头结点 尾指针 76

77 例 : 两循环链表首尾相连 head1 head2 ///// ///// 时间复杂度 : O(m+n) p2 tail1 tail2 (1) p2=tail2->next; (2) tail2->next=tail1->next; ///// ///// (3) tail1->next=p2->next; (4) free(p2); 时间复杂度 : O(1) 77

78 3. 循环链表算法举例例. 求以 head 为头指针的循环单链表的长度, 并依次输出结点的值 算法如下 : int length(struct Lnode *head) { int leng=0; // 长度变量初值为 0 struct Lnode *p; p=head->next; //p 指向首结点 while (p!=head) //p 未移回到表头结点 { printf( %d,p->data);// 输出 leng++; p=p->next;} return leng; } // 计数 //p 移向下一结点 // 返回长度值 78

79 2.3.4 双向链表 1. 双向链表的结点结构 : prior data next 前驱 a(i-1) ai 后继 a(i+1) 双向链表的存储结构类型定义如下 : typedef struct DuLNode{ ElemType data; // 数据域 structdulnode *prior; // 前驱指针域 structdulnode *next; // 后继指针域 } DuLNode, *DuLinkList ; 79

80 2. 双向链表的一般形式 (1) 非空表 prior data next L // a1 a2... an 表头结点首结点尾结点 有 :L 为头指针,L 指向表头结点,L->next 指向首结点 L->next->data==a1 L->prior 指向尾结点, L->prior->data==an L->next->prior== L->prior->next==NULL (2) 空表 L // 表头结点 有 :L->next==L->prior==NULL 80

81 3. 双向循环链表 (1) 空表 L // 有 :L->next==L->prior==L 表头结点 (2) 非空表 prior data next L // a1... an 表头结点 p 尾结点 设 p 指向 a1, 有 : p->next 指向 a2, p->next->prior 指向 a1, 所以,p==p->next->prior 同理 :p==p->prior->next 81

82 (3) 已知指针 p 指向结点 B, 删除 B p A B C 执行 : p->prior->next=p->next; // 结点 A 的 next 指向结点 C p->next->prior=p->prior; // 结点 C 的 prior 指向结点 A free(p); // 释放结点 B 占有的空间 82

83 (4). 已知指针 p 指向结点 C, 在 A C 之间插入结点 B p A C f B 执行 : 1 f->prior=p->prior; 2 f->next=p; 3 p->prior->next=f; 4 p->prior=f; // 结点 B 的 prior 指向结点 A // 结点 B 的 next 指向结点 C // 结点 A 的 next 指向结点 B // 结点 C 的 prior 指向结点 B 83

84 用单链表实现线性表的操作时, 存在的问题 : 1. 单链表的表长是一个隐含的值 ; 2. 在单链表的最后一个元素之后插入元素时, 需遍历整个链表 ; 3. 在链表中, 元素的 位序 概念淡化, 结点的 位置 概念加强 改进链表的设置 :Page 增加 表长 表尾指针 和 当前位置的 指针 三个数据域 ; 2. 将基本操作中的 位序 i 改变为 指针 p 84

85 线性表的两种存储结构的比较 具体要求 基于空间 顺序表 链表 适于线性表长适于当线性表长度变化大, 难以估度变化不大, 计其存储规模时采用 易于事先确定其大小时采用 基于时间 由于顺序表是一种随机存储结构, 当线性表的操作主要是查找时, 宜采用 链表中对任何位置进行插入和删除都只需修改指针, 所以这类操作为主的线性表宜采用链表做存储结构 若插入和删除主要发生在表的首尾两端, 则宜采用尾指针表示的单循环链表 85

86 讨论如下问题 : q 线性表的两种存储结构各有哪些优缺点? q 对于线性表的两种存储结构, 如果有 n 个表同时并存, 且处理过程中各表的长度会动态发生变化, 表的总数也可能自动改变, 在此情况下应选用哪种存储表示? 为什么? q 若表的总数基本稳定, 且很少插入和删除, 但要求以最快速度存取表中元素, 这时应采用哪种存储表示? 为什么? q 顺序表与链表进行插入操作时, 有什么不同? 86

87 2.4 一元多项式的表示与相加 一元多项式 2 p ( x) = p + p x + p x n p n x n 在计算机中, 可以用一个线性表来表示 : P = (p 0, p 1,,p n ) 但是对于如下形式的多项式, 上述表示方法是否合适? S(x) = 1 + 3x x

88 一般情况下的一元稀疏多项式可写成 P n (x) = p 1 x e1 + p 2 x e2 + + p m x em 其中 :p i 是指数为 e i 的项的非零系数, 0 e 1 < e 2 < < e m = n 可以下列线性表表示 : ((p 1, e 1 ), (p 2, e 2 ),, (p m,e m ) ) 例如 : P 999 (x) = 7x 3-2x 12-8x 999 可用线性表表示为 ( (7, 3), (-2, 12), (-8, 999) ) 88

89 抽象数据类型一元多项式的定义如下 : ADT Polynomial { 数据对象 : D={ a i a i TermSet, i=1,2,...,m, m 0 TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 } 数据关系 : R1={ <a i-1,a i > a i-1,a i D, i=2,...,n, 且 a i-1 中的指数值 <a i 中的指数值 } 89

90 基本操作 : CreatPolyn( &P, m ) 操作结果 : 输入 m 项的系数和指数, 建立一元多项式 P DestroyPolyn( &P ) 初始条件 : 一元多项式 P 已存在 操作结果 : 销毁一元多项式 P PrintPolyn( &P ) 初始条件 : 一元多项式 P 已存在 操作结果 : 打印输出一元多项式 P 90

91 PolynLength( P ) 初始条件 : 一元多项式 P 已存在 操作结果 : 返回一元多项式 P 中的项数 AddPolyn( &Pa, &Pb) 初始条件 : 一元多项式 Pa 和 Pb 已存在 操作结果 : 完成多项式相加运算, 即 : Pa = Pa+Pb, 并销毁一元多项式 Pb SubtractPolyn( &Pa, &Pb) } ADT Polynomial 91

92 多项式的链表表示 A 12 (x)=1+3x 5-7x 12 coef expn next pa A // ^ B 17 (x)=6+3x 3-3x 5 +12x 17 pb B // ^ C(x)=A(x)+B(x) pc C // ^ 多项式相加与两个有序单链表的归并有何不同? 92

93 C(x)=A(x)+B(x) 的算法步骤 : 对比参考第 43 页的算法 pa pb 分别指向首元素结点, 产生 C(x) 的空链表,pc 指向头结点 ; 2. pa 不为空并且 pb 不为空, 重复下列操作 : 2-1 pa->expn 等于 pb->expn (a)pa->coef+pb->coef 不等于零 : 产生新结点, 添加到 pc 后, pc 指向新结点 pa pb 后移 (b)pa->coef+pb->coef 等于零 : pa pb 后移 2-2 pa->expn 小于 pb->expn: 由 pa 产生新结点, 添加到 pc 后, pc 指向新结点, pa 后移 2-3 pa->expn 大于 pb->expn: 由 pb 产生新结点, 添加到 pc 后, pc 指向新结点, pb 后移 3. pa 为空, 取 pb 剩余结点产生新结点 ; pb 为空, 取 pa 剩余结点产生新结点, 依次添加到 pc 的后面 93

94 运算效率分析 : (1) 系数相加 0 加法次数 min(m, n) 其中 m 和 n 分别表示表 A(x) 和表 B(x) 的结点数 (2) 指数比较极端情况是表 A 和表 B 没有一项指数相同, 比较次数最多为 m+n-1 (3) 新结点的创建极端情况是产生 m + n 个新结点合计时间复杂度为 O(m+n) 94

95 本章小结 1. 线性结构 ( 包括表 栈 队 数组 ) 的定义和特点 : 仅一个首 尾结点, 其余元素仅一个直接前驱和一个直接后继 2. 线性表 逻辑结构 : 一对一 或 1:1 存储结构 : 顺序 链式运算 : 修改 插入 删除 [ 查找和排序另述 ] 3. 顺序存储 特征 : 逻辑上相邻, 物理上也相邻 ; 优点 : 随机查找修改快 O(1) 缺点 : 插入 删除慢 O(n) 改进方案 : 链表存储结构 95

96 4. 链式存储 特征 : 逻辑上相邻, 物理上未必相邻 ; 优点 : 插入 删除快 O(1) 缺点 : 随机查找修改慢 O(n) 5. 几种特殊链表的特点 : 静态链表的特点 : 不用指针也能实现链式存储和运算 循环链表的特点 : 从任一结点出发均可找到表中其他结点 双向链表的特点 : 可方便找到任一结点的前驱 96

97 经典问题 : 例 1: 试用 C 或类 C 语言编写一个高效算法, 将一循环单链表就地逆置 ( 微软亚洲研究院招聘笔试题 ) 操作前 :(a 1, a 2, a i-1, a i, a i+1,, a n ) 操作后 :( a n, a i+1, a i, a i-1,, a 2, a 1 ) 分析 : 要想让 a n 指向 a n-1, a 2 指向 a 1, 一般有两种算法 : 1 替换法 : 扫描 a 1 a n, 将每个 a i-1 的指针域送入 a i+1 的指针域 2 插入法 : 扫描 a 1 a n, 思路 : 后继变前驱 将每个 a i 插入到链表首部即可 head a 1 ^ 思路 : 头部变尾部 a 2 97

98 替换法的核心语句 : 插入法的核心语句 : q=head; p=head->next; // 有头结点 while(p!=head) // 循环单链表 { r=p->next; p->next=q; // 前驱变后继 q=p; p=r; } // 准备处理下一结点 head->next=q; // 以 a n 为首 p=head->next; // 有头结点 if(p!=head){q=p->next; p->next =head;p=q}; // 处理 a 1 while(p!=head) // 循环单链表 { q=p ->next // 保存原后继 p ->next= head->next; head->next=p; p=q;} // 准备处理下一结点 q p r head a 1 head a i-1 a i a i+1 请上机验证并分析效率! p a 2 q 98

99 例 2: 试用 C 或类 C 语言编写一高效算法, 将一顺序存储的线性表 ( 设元素均为整型量 ) 中所有零元素向表尾集中, 其他元素则顺序向表头方向集中 华为公司招聘面试题 (a 1, a 2, a i-1, a i, a i+1,, a n ) 常见做法 : 1 从前往后扫描, 见到 0 元素则与尾部非 0 元素互换 ; 2 从后往前扫描, 见到 0 元素则后面元素统统前移 ; 3 从前往后扫描, 见到 0 元素先计数, 再将后续的一个非 0 元素前移, 全部扫完后再把后续部分 ( 长度为 0 元素的个数 ) 清 0 99

100 解 : void SortA(SqList &L) { int i=0, zerosum =0; if(l.length= =0) return(0); else { for( i=1; i<=l.length; i++) } // 空表则结束 {if (L.elem[i]<>0) L.elem[i-zerosum]= L.elem[i]; else zerosum++; } for( i= L.length-zerosum+1; i<=l.length; i++) L.elem[i]=0; // 表的后部补 0 return(ok); }// SortA 若表完全不空, 也要移动 n 次? 100

101 若考虑表完全非空的情况, 则程序要变长很多 解 : void SortA(SqList&L) { int i=0, zerosum =0; } if(l.length= =0) return(0); for ( i=1; i<=l.length; i++) {if (L.elem[i]<>0) // 空表则不执行 if(zerosum!=0) L.elem[i-zerosum]= L.elem[i]; else zerosum++ }; // 适当移动非零元素, 是零则增加计数 for ( i= L.length-zerosum+1; i<=l.length; i++) L.elem[i]=0; // 表的后部补 0 return(ok); 101

102 讨论 1: 已知带头结点的单链表, 其头指针为 head, 在不改 变链表的情况下, 设计一高效算法输出链表中倒数第 k 个结 点数据域的值 ( 用 C,C++ 或 JAVA 语言实现 ) 2009 年统考题 a 1 head a 2 a n ^ 讨论 : 如何设计算法? 讨论 2: 一个长度为 n(n 1) 的升序序列 L, 处在第 n/2 的数称为 L 的中位数 两个序列的中位数是含它们所有元素的升序序列的中位数 现有两个等长的升序序列 A 和 B, 试设计一时空高效算法求出两个升序序列 A 和 B 的中位数 ( 用 C,C++ 或 JAVA 语言实现 ) 2011 年统考题例 :(11,13,15,17,19) (2,4,6,8,20) 这两个序列的中位数是

103 习 题 一 填空题 (1) 链表中逻辑上相邻的元素的物理位置 相连 (2) 在单链表中除首结点外, 任意结点的存储位置都由 结点中的指针指示 (3) 线性表的元素长度为 4, 在顺序存储结构下 LOC(a i )=2000, 则 LOC(a i+1 )= (4) 线性表的元素长度为 L, 在顺序存储结构下 Loc(a i )=Loc(a 1 )+ 103

104 (5) 已带表头结点的单链表 L, 指针 p 指向 L 链表中的一个结点, 指针 q 是指向 L 链表外的一个结点, 则 : v 1 在指针 p 所指结点后插入 q 所指结点的语句序列是 ; v2 在指针 p 所指结点前插入 q 所指结点的语句序列是 ; v3 将 q 所指结点插入在链表首结点的语句序列是 ; v4 将 q 所指结点插入在链表尾结点的语句序列是 104

105 (6) 已知带表头结点的单链表 L, 指针 p 指向 L 链表中的一个结点 ( 非首结点. 非尾结点 ), 则 : 1 删除指针 p 所指结点的直接后继结点的语句是 ; 2 删除指针 p 所指结点的直接前驱结点的语句序列是 ; 3 删除指针 p 所指结点的语句序列是 ; 4 删除首结点的语句序列是 ; 5 删除尾结点的语句序列是 105

106 (7) 已知指针 p 指向双向链表中的一个结点 ( 非首结点, 非尾结点 ), 则 : 1 将结点 s 插入在指针 p 所指结点的直接后继位置的语句是 ; 2 将结点 s 插入在指针 p 所指结点的直接前驱位置的语句是 ; 3 删除指针 p 所指结点的直接后继结点的语句序列是 ; 4 删除指针 p 所指结点的直接前驱结点的语句序列是 ; 5 删除指针 p 所指结点的语句序列是 106

107 (8) 在下图所示的链表中, 若在指针 p 所指的结点之后插入数据字段相继为 a 和 b 的两个结点, 则可用下列两个语句实现该操作, 它们依次是 和 107

108 二 单选题 (1) 下列说法正确的是 : A. 线性表的逻辑顺序和存储顺序总是一致的 B. 线性表的链式存储结构中, 内存中可用的存储单元可以是连续的, 也可以不连续 C. 线性表的顺序存储结构优于链式存储结构 D. 每种数据结构都具有插入 删除和查找三种基本操作 (2) 线性表中哪些元素只有一个直接前驱和一个直接后继 A. 首元素 B. 尾元素 C. 中间的元素 D. 所有的元素 108

109 v (3) 指针 p 指向带头结点循环单链表的首结点的条件是 : A.p==L B.p->next==L C.L->next==p D.p->next==NULL v (4) 指针 p 指向双向循环链表的尾结点的条件是 : A.p==L B.p==NULL C.p->prior==L D.p->next==L 109

110 本章作业 选做 : 课外编程练习 先建立一个整型数的单链表, 然后统计单链表中数据元素为 0 的个数 110