本 章 说 明 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.4 循环链表和双向链

Presentation on theme: "本 章 说 明 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.4 循环链表和双向链"— Presentation transcript:

1 本 章 说 明 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.4 循环链表和双向链
2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式存储结构 2.4 循环链表和双向链 2.5 一元多项式的表示及相加 本 章 小 结 返回主目录

2 本章说明 学习目标 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 结合线性表类型的定义增强对抽象数据类型的理解。

3 本章说明 重点和难点 链表是本章的重点和难点。 扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。 知识点 线性表、顺序表、链表、有序表

4 线性结构的特点：在数据元素的非空有限集中
存在唯一的一个被称做“第一个”的数据元素 存在唯一的一个被称做“最后一个”的数据元素 除第一个之外，每个元素都只有一个前驱 除最后一个之外，每个元素都只有一个后继

5 定义：一个线性表是n个数据元素的有限序列。
2.1 线性表的类型定义 1.线性表 定义：一个线性表是n个数据元素的有限序列。 例如：英文字母（A，B，C，……，Z）是一个线性表。表中元素是一个字母。 例如：星期（星期日，星期一，星期二，……，星期六）是一个线性表。表中的数据元素是星期中一天的名称。

6 例如：在稍复杂的线性表中，一个数据元素可以是由若干个数据项组成的记录，含有大量记录线性表称为文件。如，一个学校的学生健康情况登记表。
姓 名 学 号 性别 年龄 班级 健康状况 王小林 790631 男 18 计91 健康 陈 红 790632 女 20 一般 刘建平 790633 21 张立立 790634 17 神经衰弱 ┆ 数据元素

7 2.线性表的结构特性 2.1 线性表的类型定义 综上三个例子，我们可以如下描述线性表：
线性表是n≥0个数据元素a1，a2，…，ai-1，ai，ai+1，…，an的有限序列。 线性表的长度定义为线性表中数据元素的个数n。当n=0时，为空表。n>0时记为（a1，a2，……，an） · ai-1是ai的直接前驱，a1无直接前趋 · ai+1是ai的直接后继，an无直接后继 数据元素同构，相邻数据元素之间存在着序偶关系。所以可将线性表记为 （a1, …, ai-1, ai, ai+1, …an） 数据元素在线性表中的位置只取决于它们自己的序号。数据元素之间的相对位置是线性的

8 3.线性表的基本运算 2.1 线性表的类型定义 表的初始化 求表长 取（或修改）表中的结点 查找结点 插入结点 删除结点。
不是全部操作，不同的问题需要的操作不同。

9 4.抽象数据类型线性表的定义P19 2.1 线性表的类型定义 ADT List{ 数据对象：D={ai|ai∈ElemSet,
i=1,2,…,n,n>=0} 数据关系：R1={<ai-1, ai>|ai-1, ai∈D, i=1,2,…,n } 基本操作： InitList(&L) //创建一个空的线性表L DestroyList(&L) //撤消L

10 4.抽象数据类型线性表的定义P19 ClearList(&L) //将L重置为空表 ListEmpty(L) //判L是否为空? 空为T
2.1 线性表的类型定义 4.抽象数据类型线性表的定义P19 ClearList(&L) //将L重置为空表 ListEmpty(L) //判L是否为空? 空为T ListLength(L) //返回表长度(元素个数) GetElemList(L,I,&e) //用e返回L中第i个数据元素的个数

11 2.1 线性表的类型定义 LocateElem(L, e, compare() )
PriorElem(L, cur_e, &pre_e) //找cur_e并返回其前驱pre_e,否则操作失败,pre_e无定义 NextElem(L, cur_e, &next_e) //找cur_e并返回其后继next_e,否则操作失败,next_e无定义 ListInsert(&L, i, e) ListDelete(&L, i, &e) ListTraverse(L, visit()) //依次对L的元素调用visit(),如visit()失败,则操作失败 }ADT List

12 2.1 线性表的类型定义 例2-1 两个线性表LA、LB，将存在于线性表LB中而不在LA中的数据元素加入到线性表LA中。即LA=LA∪LB 算法思想：逐一取出LB中的元素，判断是否在LA中，若不在,则插入之。 仅已知LA、LB （1）先求出LA、LB长度 （2）取LB中一元素=>e，若LB取空则转（4） （3）如e不在LA中，则插入到LA中，转（2） （4）结束

13 算法2.1实现 2.1 线性表的类型定义 求表长、插入、取元素时间复杂度：O(1) void unin(List &La，List Lb)
{ La_len=(ListLength(La)); Lb_len=(ListLength(Lb)); for (i=1; i<=Lb_len; i++) { GetElem(Lb, i, &e); //取LB中第i个元素 if (!LocateElem(La, e, equal)) ListInsert(&La, ++La_len, e); } //La 中不存在和e 相同的元素，则插入之 } //union 算法的时间复杂度：O(ListLength(LA)×ListLength(LB))

14 算法2.2 2.1 线性表的类型定义 例2-2 线性表LA和LB是非递减有序的，将两表合并成新的线性表LC，且LC也是非递减的。
即（1）LA 、LB均不空，则在LA中取一元素=>a,LB中取一元素=>b, 否则转（3） （2）若a<=b,a=>c,否则b=>c,转（1） （3）若LA不空，则LA剩余部分放到LC尾 （4）若LB不空，则LA剩余部分放到LC尾 void MergeList(List La, List Lb, List &Lc) { InitList(Lc); //建一空表LC i=j=1; k=0; //i，j，k分别指向La，Lb，Lc 初始位置

15 La_len=(ListLength(La)); Lb_len=(ListLength(Lb));
2.1 线性表的类型定义 算法2.2 La_len=(ListLength(La)); Lb_len=(ListLength(Lb)); while (i<=La_len) && (j<=Lb_len) { //La和Lb均非空 GetElem(La,i,ai); GetElem(Lb, j, bj); if(ai<=bj) {ListInsert(Lc, ++k, ai); ++i;} else {ListInsert(Lc, ++k, bj); ++j;} }

16 算法2.2 2.1 线性表的类型定义 while (i<=La_len) { //La还有元素
GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } while (j<=Lb_len) { //Lb还有元素 GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); }//MergeList 时间复杂度：O(ListLength(LA) +ListLength(LB))

17 1.线性表的顺序表示 2.顺序表的特点 3.线性表的动态分配顺序存储结构 4.顺序线性表的操作 5.顺序表的优缺点
2.2 线性表的顺序表示和实现 1.线性表的顺序表示 2.顺序表的特点 3.线性表的动态分配顺序存储结构 4.顺序线性表的操作 5.顺序表的优缺点

18 1.线性表的顺序表示 实现：可用C语言的一维数组实现 2.2 线性表的顺序表示和实现
定义：用一组地址连续的存储单元存储一个线性表的数据元素，称为顺序表。 元素地址计算方法： · LOC(ai+1)=LOC(ai)+L · LOC(ai)=LOC(a1)+(i-1)* L ·其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 实现：可用C语言的一维数组实现

19 typedef int DATATYPE; #define M 1000 DATATYPE data[M];
an 1 n-1 2 n 内存 V数组下标 元素序号 M-1 typedef int DATATYPE; #define M 1000 DATATYPE data[M]; 例 typedef struct card { int num; char name[20]; char author[10]; char publisher[30]; float price; }DATATYPE; DATATYPE library[M]; 备用空间 或动态申请和释放内存 DATATYPE *pData = (DATATYPE *)malloc(M*sizeof(DATATYPE)); free(pData); 数据元素不是简单类型时,可定义结构体数组

20 2.2 线性表的顺序表示和实现 2.顺序表的特点 特点： 实现逻辑上相邻—物理地址相邻 实现随机存取

21 #define LIST_INIT_SIZE 100 #define LISTINCREAMENT 10 type struct
2.2 线性表的顺序表示和实现 3.线性表的动态分配顺序存储结构 用一维数组定义一个线性表 #define LIST_INIT_SIZE 100 #define LISTINCREAMENT 10 type struct { ElemType *elem; //指向线性表起始地址的指针 int length; //线性表实际存放数据长度 int listsize; //线性表申请长度 }SqList

22 顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。 (1)初始化操作 算法思想：构造一个空表。 设置表的起始位置 表长
2.2 线性表的顺序表示和实现 4.顺序线性表的操作 顺序表容易实现访问操作，可随机存取元素。但插入和删除操作主要是移动元素。 (1)初始化操作 算法思想：构造一个空表。 设置表的起始位置 表长 可用空间

23 线性表初始化算法2.3 2.2 线性表的顺序表示和实现 Status InitList_Sq(SqList &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

24 （2）插入 定义：线性表的插入是指在第i（1i  n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表 算法
需将第n至第i,共（n-i+1)个元素后移 算法 Ch2_1.c

25 x X 内存 a1 a2 ai ai+1 an 1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai
1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 内存 a1 a2 ai ai+1 an 1 i-1 V数组下标 n-1 i n 2 元素序号 i+1 n+1 an-1 X x

26 （在表L中的第i个元素之前插入e），见P24 ①判i值的合法性，1≤i≤表长+1； ②判表的空间满否？若满则增加分配（动态分配）；
2.2 线性表的顺序表示和实现 插入算法2.4 （在表L中的第i个元素之前插入e），见P24 ①判i值的合法性，1≤i≤表长+1； ②判表的空间满否？若满则增加分配（动态分配）； ③从表元素n到i，依次后移一个位置； ④将e插入第i个位置，表长度增1。 ＊算法中定义的线性表是L，以结构形式出现

27 2.2 线性表的顺序表示和实现 插入算法2.4实现 Status ListInsert_Sq(SqList &L, int i, ElemType e ) {if (i<1||i>L.length+1) return ERROR; //i不合法 if (L.length>=L.listsize) //当前可用空间已满 { //增加分配 newbase=(ElemType*)realloc(L.elem, (L.listsize+ LISTINCREMENT)sizeof(ElemType)); if (!newbase) exit(OVERFLOW); L.elem=newbase; //新基址 L.listsize+= LISTINCREMENT; }

28 q=&(L.elem[i-1]); //取插入位置 for (p=&(L.elem[L.length-1]); p>=q; --p)
2.2 线性表的顺序表示和实现 插入算法2.4实现 q=&(L.elem[i-1]); //取插入位置 for (p=&(L.elem[L.length-1]); p>=q; --p) { *(p+1)=*p; } //将n~i位置的元素后移 *q=e; //插入e ++L.length; //表长度+1 return OK;

29 插入算法2.4时间复杂度 2.2 线性表的顺序表示和实现 可见插入元素的时间主要花费在移动元素上，而移动元素的个数主要取决于插入的位置。
若在任何位置上插入元素都是等概率 设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时需移动元素的平均次数为

30 算法思想：删除第i个元素，将第（i+1）至第n个元素逐一向前移动一个位置，将长度为n
（3）删除 算法思想：删除第i个元素，将第（i+1）至第n个元素逐一向前移动一个位置，将长度为n }//ListInsert_Sq (a1,a2……ai-1,ai,ai+1……an) 变成长度为n=>n-1的线性表 (a1,a2……ai-1, ai+1……an) 需将第i+1至第n共（n-i)个元素前移 算法 Ch2_1.c

31 删除 内存 a1 a2 ai ai+1 an 1 i-1 V数组下标 n-1 i 2 元素序号 i+1 n 内存 a1 a2 ai+2 1
1 i-1 V数组下标 n-1 i 2 元素序号 i+1 n 内存 a1 a2 ai+2 1 i-1 V数组下标 n-1 i 2 元素序号 i+1 n an ai+1 删除

32 删除算法2.5思想 在表L中删除第i个元素，放入e，见P24 ①判i值的合法性，1≤i≤表长n ②取第i个元素，放入e
2.2 线性表的顺序表示和实现 删除算法2.5思想 在表L中删除第i个元素，放入e，见P24 ①判i值的合法性，1≤i≤表长n ②取第i个元素，放入e ③从i+1到表长n，依次前移 ④表长度减1

33 2.2 线性表的顺序表示和实现 删除算法2.5实现 Status ListDelete_Sq(SqList &L, int i, ElemType &e ) {if ( (i<1) || (i>L.length) ) return ERROR; //i不合法 p=&(L.elem[i-1]); //取被删除元素位置 e=*p; //取插入位置 q=L.elem+L.Length-1; //取表尾元素的位置 for (++p; p<=q; ++p;) { *(p-1)=*p; } //将i+1~n位置的元素前移 --L.length; //表长度+1 return OK; }//ListInsert_Sq

34 删除算法2.5时间复杂度 2.2 线性表的顺序表示和实现 可见删除元素的时间主要花费在移动元素上，而移动元素的个数主要取决于删除的位置。
若在任何位置上插入元素都是等概率 设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为

35 Int LocateElem_Sq(SqList L,ElemType e,
2.2 线性表的顺序表示和实现 查找算法2.6 Int LocateElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType, ElemType)) { //在顺序线性表L中找第一个值与e满足compare()的元素的位序，找到返回位序，否则返回0 i=1; p=L.elem; while (i<=L.length&&!(*compare)(*p++,e)) ++i; if (i<=L.length) return i; else return 0; }// LocateElem_Sq 时间复杂度：O(L.length)

36 Int MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
2.2 线性表的顺序表示和实现 合并算法2.7实现 Int MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { //已知顺序线性表La和Lb的元素非递减排列，归并得到线性表Lc，Lc也是非递减排列 pa=La.elem; pb= Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize* sizeof(ElemType)); if (!Lc.elem) exit (OVERFLOW);

37 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1;
2.2 线性表的顺序表示和实现 合并算法2.7 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while (pa<=pa_last && pb<=pb_last) //归并 { if (*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } while (pa<=pa_last) *pc++=*pa++; //插入La剩余部分 while (pb<=pb_last) *pc++=*pb++; //插入Lb剩余部分 }//MergeList_Sq

38 预先分配空间需按最大空间分配，利用不充分 表容量扩充难
2.2 线性表的顺序表示和实现 5.顺序表的的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量扩充难

39 1.特点 2.3 线性表的链式存储结构 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息（指针），用来表示线性表数据元素的逻辑关系 结点 数据域：元素本身信息 指针域：指示直接后继的存储位置 数据域 指针域 结点

40 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
存储地址 1 7 13 19 25 31 37 43 数据域 指针域 43 头指针 13 31 H 1 NULL 37 7 19 25 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H

41 由n个结点链结成一个链表 ，称为线性链表或单链表。 结点（Node）、数据域、指针域、指针、链、头指针 3. 线性链表的实现
2.3 线性表的链式存储结构 2. 线性链表的定义 由n个结点链结成一个链表 ，称为线性链表或单链表。 结点（Node）、数据域、指针域、指针、链、头指针 3. 线性链表的实现 typedef struct Lnode { ElemType data; struct Lnode *next; }Lnode,*LinkList;

42 2.3 线性表的链式存储结构 LNode *h,*p; (*p)表示p所指向的结点 p->data表示p指向结点的数据域
p->next表示p指向结点的指针域 生成一个LNode型新结点：p=(LNode *)malloc(sizeof(LNODE)); 系统回收p结点：free(p) 带头结点非空表： 空表： data next p 结点（*p） a1 a2 an /\ … L

43 插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。 5.单链表的操作 （1）取第i个元素
2.3 线性表的链式存储结构 4. 链式存储结构的优点 插入、删除操作是不再需要移动大量的元素，但失去了顺序表的可随机存取特点。 5.单链表的操作 （1）取第i个元素 算法思想：单链表是非随机存取结构。每个元素的位置信息都包含在前驱结点的信息中，所以取得第i个元素必须从头指针出发寻找。设置一个指针变量指向第一个结点，然后，让该指针变量逐一向后指向，直到第i个元素。

44 取结点算法2.8 2.3 线性表的链式存储结构 Status GetElem_L(LinkList L, int i, ElemType){
//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR p=L→next; j=1; //p指向第一个结点，j做计数器 while(p && j<i){ //直到p指向第i元素或p为空 p=p→next; ++j; } if(!p || j>i) return ERROR; e=p→data; return OK; }//GetElem_L

45 设p为指向结点a 的指针，s为指向结点x的指针，则修改s、a的指针：
2.3 线性表的链式存储结构 插入结点算法2.9 （2）插入操作： 要在数据元素a和b 之间插入元素x。 算法思想：决定a和b之间的相邻关系是由a的指针决定的。若要实现插入，生成x结点，然后让a的指针指向x 且x的指针指向b。实现三个元a、x和b的逻辑关系。 设p为指向结点a 的指针，s为指向结点x的指针，则修改s、a的指针：

46 s->next=p->next
B … A p X s p->next= s s->next=p->next X s B … A p

47 2.3 线性表的链式存储结构 插入结点算法2.9实现 Status ListInsert_L(ListLInk &L, int i, ElemType e){ //在带头结点的单链表L中第i个位置之前插入元素e p=L; j=0; while(p && j<i-1){p=p→next; ++j;} //找第i个结点 if (!p || j>i-1) return ERROR; //i小于1或大于表长 s=(LinkList)malloc(sizeof(LNode)); s→data=e; s→next=p-next; p→next=s; return OK; }//ListInsert_L

48 p->next=p->next->next
（3）删除操作 B C … A p p->next=p->next->next C … A p

49 2.3 线性表的链式存储结构 删除结点算法2.10实现 Status ListDelete_L(LinkList &L,int i,ElemType &e){ //在带头结点的单链表L中删除第i个元素，并由e返回 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

50 动态建立单链表算法：设线性表n个元素，逆位序输入数据元素建立一个单链表，h为头指针。
动态创建链表算法 动态建立单链表算法：设线性表n个元素，逆位序输入数据元素建立一个单链表，h为头指针。 h 头结点 ^ h 头结点 an ^ h 头结点 an-1 an ^ a2 …... h 头结点 an-1 an ^ h a1 a2 头结点 an ^ …...

51 动态创建链表算法2.11实现 2.3 线性表的链式存储结构 Void CreateList_L(LinkList &L, int n){
//逆位序输入n个元素值，建立带头结点的单链表L L=（LinkList)malloc(sizeof(LNode)); L->next=NULL; for (i=n; i>0; --i){ p=(LinkList)malloc(sizeof(LNode)); scanf(&p->data); p->next=L->next; L->next=p; } }//CreatList_L

52 合并有序链表算法2.12 2.3 线性表的链式存储结构 （4）单链表的合并 例：将两个有序链表合并为一个有序链表。 算法思想：
设立三个指针pa、pb和pc分别用来指向两个有序链表和合并表的当前元素。 比较两个表的当前元素的大小，将小的元素链接到合并表Lc中,让合并表的当前指针指向该元素，然后，修改指针。 在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新建立关系。

53 每次链接pa或pb的一个结点后，便做如下操作： pa=pa->next; pc=pc->next; pa和pc分别后移一个位置
pc-next=pb pa pa pa pa pa 3 5 11 /\ La 8 Lc pc pc pc pc pc 15 2 6 20 /\ 8 9 11 Lb pb pc pb pc pb pc pb pc pb pc->next=pa 每次链接pa或pb的一个结点后，便做如下操作： pa=pa->next; pc=pc->next; pa和pc分别后移一个位置 或pb=pb->next; pc=pc->next; pb和pc分别后移一个位置

54 合并有序链表算法2.12实现 2.3 线性表的链式存储结构
Void MergeList_L(LinkList La, LinkList Lb, LinkList &Lc){ pa=La->next; pb=Lb->next; Lc=pc=La; while (pa && pb) { 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; free(Lb); }//MergeList_L

55 有些高级语言没有指针，我们可以用数组来表示单链表，在数组中以整型游标来代替指针。这种用数组描述的链表称为静态链表。
2.3 线性表的链式存储结构 6.静态单链表 有些高级语言没有指针，我们可以用数组来表示单链表，在数组中以整型游标来代替指针。这种用数组描述的链表称为静态链表。 存储结构： #define MAXSIZE 1000 typedef struct{ ElemType data; int cur; }component, SLinklist[MAXSIZE]; S[i].cur 指示第i+1个结点的位置。 静态链表的操作和动态链表相似，以整型游标代替动态指针。

56 1 ZHAO 2 QIAN 3 SUN 4 LI 5 ZHOU 6 WU 7 8 9 10 1 ZHAO 2 QIAN 3 SUN 4 LI
S[0].cur为头指针，可以遍历整个静态链表 找到插入位置i 1 ZHAO 2 QIAN 3 SUN 4 LI 5 ZHOU 6 WU 7 ZHENG 8 WANG 9 10 1 ZHAO 2 QIAN 3 SUN 4 LI 5 ZHOU 6 WU 7 ZHENG 8 WANG 9 10 1 ZHAO 2 QIAN 3 SUN 4 LI 9 5 ZHOU 6 WU 8 7 ZHENG WANG SHI 10 9 SHI 8 SHI 5 删除ZHENG, s[6].cur=s[7].cur

57 int LocateElem_SL(SLinkList S, ElemType e){ //在静态单链线性表L中查找第1个值为e的元素
2.3 线性表的链式存储结构 算法2.13静态链表查找 int LocateElem_SL(SLinkList S, ElemType e){ //在静态单链线性表L中查找第1个值为e的元素 // 找到返回位序，否则返回0 i=S[0].cur; while (i && S[i].data!=e) i=S[i].cur; return i; //没找到则到链尾，i=0 }//LocateElem_SL

58 假设由终端输入A集合元素并建立静态链表S，然后输入集合B元素在S中查找，若存在和B相同的元素，则从S中删除之，否则插入到S中。
2.3 线性表的链式存储结构 例2-3 运算(A-B)U(B-A) 假设由终端输入A集合元素并建立静态链表S，然后输入集合B元素在S中查找，若存在和B相同的元素，则从S中删除之，否则插入到S中。 算法思想： 将整个数组空间初始化成一个链表 从备用空间取得一个结点 将空闲结点链接到备用链表上

59 Space[0].cur是备用空闲链表的头指针，space[1].cur是链表的头指针
A=(c, b, e, g, f, d), B=(a, b, n, f) 1 2 3 4 5 6 7 8 9 10 3 1 2 c 4 5 6 7 8 9 10 4 1 2 c 3 b 5 6 7 8 9 10 初始化后

60 Space[0].cur是备用空闲链表的头指针，space[1].cur是链表的头指针
A=(c, b, e, g, f, d), B=(a, b, n, f) 5 1 2 c 3 b 4 e 6 7 8 9 10 6 1 2 c 3 b 4 e 5 g 7 8 9 10 7 1 2 c 3 b 4 e 5 g 6 f 8 9 10

61 A=(c, b, e, g, f, d), B=(a, b, n, f) 取B中元素在A中查找，若有与其相同的，则将A中的同元素删除，若没有则在A中插入
删b, space[2].cur 8 1 2 c 3 b 4 e 5 g 6 f 7 d 9 10 9 1 2 c 3 b 4 e 5 g 6 f 7 d 8 a 10 3 1 2 c 4 b 9 e 5 g 6 f 7 d 8 a 10 A输入结束 取a，在A中找，没有插入

62 A=(c, b, e, g, f, d), B=(a, b, n, f) 取B中元素在A中查找，若有与其相同的，则将A中的同元素删除，若没有则在A中插入
删除f，space[5].cur=space[6].cur 3 1 2 c 4 b 9 e 5 g 6 f 7 d 8 a 10 9 1 2 c 4 3 n e 5 g 6 f 7 d 8 a 10 6 1 2 c 4 3 n e 5 g 7 f 9 d 8 a 10 插入n

63 算法2.14 2.15静态链表初始化 2.3 线性表的链式存储结构 void InitSpace_SL(SLinkList &space){
// space[0].cur为头指针，0表示空指针 for (i=0; i<MAXSIZE-1; ++i) space[i].cur=i+1; space[MAXSIZE-1].cur=0; }// InitSpace _SL int Malloc_SL(SLinkList &space){ i=space[0].cur; if (space[0].cur) space[0].cur=space[i].cur; return i; }//Malloc_SL

64 2.3 线性表的链式存储结构 算法 静态链表初始化 void Free_SL(SLinkList &space, int k){ //将下标为k的空闲结点回收到备用链表 space[k].cur=space[0].cur; space[0].cur=k; }// Free _SL (2.16) void differece(SLinkList &space, int &S){ //依次输入集合A和B，在space中建立静态链表，S为头指针 //设space的备用空间足够大，space[0].cur为其头指针， InitSpace_SL(space); //初始化备用空间 S=Malloc_SL(space); //生成S头结点 r=S; scanf(m,n); //r指向表尾元素，输入A,B元素个数

65 算法2.17续 2.3 线性表的链式存储结构 for (j=1; j<=m; ++j) { //建立集合A的链表
i=Malloc_SL(space); //分配结点，i为结点下标 scanf(space[i].data); space[r].cur=i; r=i; //插入到表尾，r指向新表尾 }//for space[r].cur=0; //创建结束，表尾的指针为空 for (j=1; j<=n; ++j) { //输入B中元素，在插入否删除 scanf(b); p=S; k=space[S].cur; //k指向集合A中第一个结点

66 算法2.17续 2.3 线性表的链式存储结构 while (k!=space[r].cur && space[k].data!=b)
{ p=k; k=space[k].cur; } //在当前表中查找 if (k==space[r].cur { i=Malloc_SL(space); space[i].data=b; space[i].cur=space[r].cur; space[i].cur=i }//if else { space[p].cur=space[k].cur; Free_SL(space,k); if (r==k) r=p; }//else }//for }//difference

67 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率
2.4 循环链表和双向链表 1.循环链表： 循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p->next=NULL 循环链表p->next=H 非空表 空表 H

68 在双向链表的结点中有两个指针域，分别指向前驱和后继。双向链表也可以有循环链表。 双向链表的存储结构
2.4 循环链表和双向链表 2.双向链表 在双向链表的结点中有两个指针域，分别指向前驱和后继。双向链表也可以有循环链表。 双向链表的存储结构 typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; } DuLNode, *DuLinklist; prior data next

69 p->prior->next= p= p->next->proir;
L 空双向循环链表： 非空双向循环链表： L a b b c a p p->prior->next= p= p->next->proir;

70 NextElem和PriorElem的执行时间为O(1) 仅需涉及一个方向的指针的操作和线性链表的操作相同
2.4 循环链表和双向链表 双向链表的操作 双指针使得链表的双向查找更为方便、快捷 NextElem和PriorElem的执行时间为O(1) 仅需涉及一个方向的指针的操作和线性链表的操作相同 插入和删除需同时修改两个方向的指针

71 插入算法：在表L中第i个位置之前插入元素e
H a b p x s 设P指针，p=GetElemP-DuL(L,i)，使其指向第i个结点 若p=null，则i不存在；p<>null，则为e申请结点, e赋值 插入 s->prior=p->prior 算法实现 p->prior->next=s s->next=p p->prior=s

72 删除算法：删除表L中第i个元素，赋于e。P37算法2．19
H b c a p 设P指针，p=GetElemP-DuL(L,i)，使其指向第i个结点 p=null，则i不存在；若p<>null，p指向第i个结点，将其赋给e 删除 p->prior->next=p-next p->next->prior=p->prior 算法实现 算法评价：T(n)=O(1)

73 typedef struct {//链表类型 Link head,tail; int len; }LinkList
2.4 循环链表和双向链表 3.带头结点的线性链表类型 类型定义： typedef struct LNode{ ElemType data; struct LNode *next }*Link, *Position; typedef struct {//链表类型 Link head,tail; int len; }LinkList

74 从实际应用出发，重新定义了线性表极其基本操作。 基本操作定义见P37 利用这些基本操作，很容易实现插入和删除操作
2.4 循环链表和双向链表 操作 从实际应用出发，重新定义了线性表极其基本操作。 基本操作定义见P37 利用这些基本操作，很容易实现插入和删除操作

75 2.4 循环链表和双向链表 算法2.20 Status ListInsert_L(LinkList &L, int I, ElemType e) { //在带头结点的单链表L的第i个元素之前插入元素e if ( !LocatePos(L, i-1, &h)) return ERROR; //找第i-1个结点,h指向i-1结点 if ( !MakeNode(s,e)) return ERROR;//结点申请失败 InsFirst(h,s); //h指向头结点,将s插在第一个结点之前 return OK; }//ListInsert_L

76 Status MargeList_L(LinkList &La, LinkList &Lb,
2.4 循环链表和双向链表 Status MargeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, int(*compare)(ElemType,ElemTYpe) ) { if ( !InitList(Lc)) return ERROR; ha=GetHead(La); hb= GetHead(Lb); pa=NextPos(La,ha); pb=NextPos(Lb,hb); while (pa&&pb){ a=GetCurElem(pa); b= GetCurElem(pb); if ((*compare)(a,b)<=0) { //a<=b DelFirst(hb,q); Append(Lc,q); pa=NextPos(La,pa);}

77 DelFirst(ha,q); Append(Lc,q); pa=NextPos(Lb,pb);} }//while
2.4 循环链表和双向链表 else { DelFirst(ha,q); Append(Lc,q); pa=NextPos(Lb,pb);} }//while if (pa) Append(Lc,pa); else Append(Lc,pb); FreeNode(ha); FreeNode(hb); reture OK; }//MergeList_L

78 2.5 一元多项式的表示及相加 一元多项式的表示 可用线性表P表示 但对S(x)这样的多项式浪费空间 一般 其中
用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构，也可以用单链表

79 单链表的结点定义 一元多项式相加 Typedef struct Pnode { float coef; int expn;
struct Pnode *next; }term, ElemType; coef exp next 一元多项式相加 -1 A ^ ^ 22 7 -1 B -1 C ^ 11 1 22 7

80 若p==NULL，将B中剩余部分连到A上即可
运算规则 设p,q分别指向A,B中某一结点，p,q初值是第一结点 p->exp < q->exp: p结点是和多项式中的一项 　　　　　　 p后移,q不动 比较 p->exp与q->exp p->exp > q->exp: q结点是和多项式中的一项 　　　　　　 将q插在p之前,q后移,p不动 0：从A表中删去p, 释放p,q，p,q后移 p->exp = q->exp: 系数相加 0：修改p系数域, 释放q，p,q后移 若q==NULL，结束 直到p或q为NULL 若p==NULL，将B中剩余部分连到A上即可

81 算法描述 q=NULL -1 pa 7 0 11 1 9 8 5 17 ^ pb 8 1 22 7 -9 8 ^ p pre q=NULL
^ pb 22 7 ^ p pre q=NULL -1 pa ^ pb 22 7 ^ p pre q -1 pa ^ pb 22 7 ^ p pre q -1 pa ^ pb 22 7 ^ p pre q -1 pa ^ pb 22 7 ^ p pre q -1 pa ^ pb 22 7 ^ p pre -1 pa 22 7 ^ 算法描述

82 本章小结 线性表是n(n≥0)个数据元素的序列，通常写成 　　　 （a1,…,ai-1,ai,ai+1,…an） 线性表中除了第一个和最后一个元素之外，都只有一个前驱和一个后继。 线性表中每个元素都有自己确定的位置，即“位序”。 n=0时的线性表称为“空表”，在写线性表的操作算法时一定要考虑你的算法对空表的情况是否也正确。

83 本章小结（二） 本章小结 顺序表 是线性表的顺序存储结构的一种别称。 特点是以“存储位置相邻”表示两个元素之间的前驱、后继关系。
优点是可以随机存取表中任意一个元素。 缺点是每作一次插入或删除操作时，平均来说必须移动表中一半元素。 常应用于主要是为查询而很少作插入和删除操作，表长变化不大的线性表。

84 本章小结（三） 本章小结 链表 是线性表的链式存储结构的别称。
特点是以“指针”指示后继元素，因此线性表的元素可以存储在存储器中任意一组存储单元中。 优点是便于进行插入和删除操作。 缺点是不能进行随机存取，每个元素的存储位置都存放在其前驱元素的指针域中，为取得表中任意一个数据元素都必须从第一个数据元素起查询。 由于它是一种动态分配的结构，结点的存储空间可以随用随取，并在删除结点时随时释放，以便系统资源更有效地被利用。这对编制大型软件非常重要，作为一个程序员在编制程序时必须养成这种习惯。

85 基础知识题 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 简述线性表的两种存储结构顺序表和链表的优缺点。 已知 L 是无表头结点的单链表，且 P 是指向表中某个结点的指针，试写出在 P 所指结点之前插入指针 S 所指结点的语句序列。 已知 P 是指向双向链表中某个结点的指针，试写出删除 P 所指结点的前驱结点的语句序列。

86 基础知识题 简述以下算法的功能。 　(1) Status A(LinkedList L) { // L 是无表头结点的单链表 　　　　if (L && L->next){ 　　　　　Q =L; L =L->next; P =L ; 　　　　　while ( P->next) P =P->next ; 　　　　　P->next =Q; Q->next = NULL; 　　　　} 　　　　return OK; 　　　} // A 　(2) void BB(LNode *s, LNode *q ) { 　　　　p =s ; 　　　　while (p->next!=q) p =p->next ; 　　　　p->next =s; 　　　} //BB 　　　void AA(LNode *pa, LNode *pb) { 　　　// pa 和 pb 分别指向单循环链表中的两个结点 　　　　BB(pa, pb); 　　　　BB(pb, pa); 　　　} //AA