数据结构-课件-链表部分.ppt

1、回顾上次课内容回顾上次课内容n数据结构的相关概念n数据的存储结构逻辑结构存储结构集合集合线性结构线性结构树形结构树形结构图状结构或网图状结构或网状结构状结构顺序存储结构顺序存储结构链接存储结构链接存储结构n 算法分析方法第二章第二章 线性表线性表主要内容：l 线性表的类型定义线性表的类型定义l 线性表的顺序表示和实现线性表的顺序表示和实现l 线性表的链式表示和实现线性表的链式表示和实现l 线性表的应用举例线性表的应用举例 存在惟一的一个开始结点，称做存在惟一的一个开始结点，称做“第一个第一个”的数据元素的数据元素存在惟一的一个终端结点，称做存在惟一的一个终端结点，称做“最后一个最后一个”的数据

2、元素的数据元素除第一个外，每个数据元素只有一个前驱除第一个外，每个数据元素只有一个前驱除最后一个外，每个数据元素只有一个后继除最后一个外，每个数据元素只有一个后继 线性表是由线性表是由n (n=0)个数据元素个数据元素(结点结点)a1,a2,.,ai,.,an组成的有限序列。其中，数据元素的个数组成的有限序列。其中，数据元素的个数n定义为表长。定义为表长。当当n=0时称为空表，非空的线性表时称为空表，非空的线性表(n0)记为：记为： (a1,a2,.,ai,.,an) 1.数据元素数据元素ai是一个抽象的符号是一个抽象的符号 2. ai可取各种数据类型可取各种数据类型 3. 同一线性表中的元素

3、必定具有相同的特性，属于同一数同一线性表中的元素必定具有相同的特性，属于同一数 据对象据对象 4. 相邻数据元素之间存在序偶关系相邻数据元素之间存在序偶关系 5. i是数据元素是数据元素ai在线性表中的位序在线性表中的位序 (1i n) ：仅有一个开始结点和一个终端结点，并且所有结：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个前驱和一个后继点都最多只有一个前驱和一个后继2.1 线性表的类型定义线性表的类型定义二、抽象数据类型线性表的定义二、抽象数据类型线性表的定义ADT List 数据对象：数据对象：D=aiai Elemset, i=1,2,n , n0数据关系：数据关系：R1

4、= ai-1 , ai D, i=2, ,n基本操作：基本操作：构造、销毁、置空、判空、获取元素、插入、删除、构造、销毁、置空、判空、获取元素、插入、删除、定位等。定位等。ADT Listna1是第一个元素，有且仅有一个直接后继元素是第一个元素，有且仅有一个直接后继元素a2；nan是最后一个元素，有且仅有一个直接前趋元素是最后一个元素，有且仅有一个直接前趋元素an-1 ；n其余其余ai(1in)有且仅有一个直接前趋有且仅有一个直接前趋ai-1，有且仅有一，有且仅有一个直接后继个直接后继ai+1一一顺序表示（存顺序表示（存储）：储）：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这

5、种存储形式存储的线性表称其为顺序表顺序表。线性表顺序存储结构示意图线性表顺序存储结构示意图2.2 线性表的顺序表示和实现线性表的顺序表示和实现n数据元素存储位置表示数据元素存储位置表示设设 a的存储地址为的存储地址为Loc(a)，每个数据元素占，每个数据元素占l l个存储地址，则第个存储地址，则第i个数据元素的地址为：个数据元素的地址为： Loc(ai)=Loc(a)+(i-1)* l l ，1inn逻辑上相邻的逻辑上相邻的ai和和ai+1以相邻的存储位置。以相邻的存储位置。n确定起始位置后，顺序表中任一数据元素都可确定起始位置后，顺序表中任一数据元素都可随机存取。随机存取。n顺序表是一种随机

6、存取的存储结构。顺序表是一种随机存取的存储结构。n 高级语言中一般用数组来描述顺序存储。高级语言中一般用数组来描述顺序存储。#include#define MAXSIZE 100typedef int ElemType;typedef structElemType aMAXSIZE;int length;Sqlist;因为线性表长度可变，且所需最大空间随问题不同因为线性表长度可变，且所需最大空间随问题不同而不同，所以用动态分配的一维数组而不同，所以用动态分配的一维数组(P22)。为使得。为使得算法简明扼要，暂使用静态数组。算法简明扼要，暂使用静态数组。线性表的建立、输出算法线性表的建立、输出算

7、法初始化初始化void initlist(Sqlist *L) L-length=0;建立顺序表建立顺序表void creat_sqlist(Sqlist &L) int i,n; coutn; L.length=n; for (i=0; iL.ai;void initlist(Sqlist &L) L.length=0;Sqlist Sl;initlist(&Sl);Sqlist Sl;initlist(Sl);输出顺序表输出顺序表void outputl(Sqlist L) int i; coutList length L.lengthendl; for (i=0; iL.length;

8、i+) coutL.ai ;if (i+1)%10=0) coutendl; coutendl; (a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的长度加11. 插入：在线性表第插入：在线性表第i （1i n+1）个位置上插入元）个位置上插入元素素e线性表主要操作的实现线性表主要操作的实现注意：注意：C语言中的数组下标从语言中的数组下标从“0”开始，因此，若开始，因此，若L是是Sqlist类型的顺序表，则表中第类型的顺序表，则表中第i个元素是个元素是L.ai-1。void

9、 insert_sq(Sqlist &L, int i, ElemType e)int j;if (L.length=MAXSIZE) coutERROR! endl;elseif (iL.length+1) coutERROR! i-1; j-)L.aj=L.aj-1;L.ai-1=e;L.length+; 这里的问题规模是表的长度，设它的值为这里的问题规模是表的长度，设它的值为n。该算。该算法的时间主要花费在循环的元素后移语句上，所需移法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位动元素的次数不仅依赖于表的长度，而且还与插入位置有关。置有关。i

10、位置位置 移动次数移动次数 1n 2 n-1 i n-i+1 n 1 n+10插入操作时间复杂度分析插入操作时间复杂度分析n最好情况下：T(n)=O(1)n最坏情况下：T(n)=O(n)n平均时间复杂度： 长度为n的顺序表中，插入一个结点，令E(n)表示移动结点的期望值(移动平均次数)，在表中第i个位置插入一个结点移动的次数为n-i+1.其中pi表示在表中第i位置插入结点的概率。Pi1/(n+1)计算得 E(n)=n/2，所以平均时间复杂度为O(n)11)1(*)(niiinpnE (a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an

11、) （1 i n）ai+1 an表的长度减1a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 2.2.删除：在线性表中删除第删除：在线性表中删除第i i个元素，使个元素，使ElemType delete_sq(Sqlist &L, int i)int x,j;if (L.length=0)coutERROR! endl;return(-1);else if (iL.length)coutERROR!“endl;return(-1);else x=L.ai-1;for (j=i; j0)，否则返回，否则返回-1，表示未找到。，表示未找到。int locate_sq(Sqlist L

12、, ElemType e)int i;i=0;while (i=L.length-1 & L.ai!=e) i+;if (i=L.length-1) return (i+1);return(-1);4. 合并：两表分别非递减有序合并：两表分别非递减有序(递增或等值递增或等值)，合并后，合并后仍然非递减有序。仍然非递减有序。void merge_list(Sqlist a, Sqlist b, Sqlist &c)int i,j,k;i=j=k=0;c.length=a.length+b.length;while (i=a.length-1 & j=b.length-1)if (a.ai=b.a

13、j) c.ak=a.ai; i+; k+;else c.ak=b.aj; j+; k+;while (i=a.length-1) c.ak=a.ai; i+; k+; while (jdata 表示数据域表示数据域p-next 表示指针域表示指针域函数函数mallocfree(p);访问结点访问结点P=(LNode*) malloc(sizeof(LNode);产生一个产生一个Lnode类型结点，把首地址送给类型结点，把首地址送给P变量变量系统回收系统回收P所指向的结点（若干字节），所指向的结点（若干字节），P中无中无所指向所指向Lnode *p, s;p-data=20; p-next=nu

14、ll;(s.data=20; s.next=null; 用的少用的少) 指针指向结点指针指向结点 p=qq p指针指向后继指针指向后继 p=q-next指针移动指针移动 p=p-nextqppppqp-next =qp-next =q-nextpq1. 创建链表创建链表单链表的基本运算单链表的基本运算void creat_list() ElemType x;LNode *ptr,*p;p=head;coutx;while (x!=999)ptr=new LNode;ptr-data=x;ptr-next=NULL;p-next=ptr;p=ptr;coutx;调用语句：head=new LNo

15、de;head-next=NULL;creat_list();定义定义head 为全局变量为全局变量void create(LNode *L)int i,n;LNode *s,*p;p=L;coutn;for (i=1; i=n; i+) s=new LNode;couts-data;p-next=s;p=s;p-next=NULL;调用语句：head=new LNode;head-next=NULL;create(head);定义定义head 为局部变量为局部变量LNode *Creat_L(int n)int i;LNode *L,*p;L=new LNode;L-next=NULL;fo

16、r (i=n; i=1; i-)p=new LNode;coutp-data; p-next=L-next;L-next=p;return(L);调用语句：head=Creat_L(5);定义定义head 为全局变量为全局变量2. 输出链表输出链表void out_list()LNode *q;q=head-next;if (q=NULL) coutEmpty list!n;elsewhile (q!=NULL)coutdatanext;coutnext;j=1;while(p & jnext; j+;if (!p | ji) return(-1);else return(p-data);调用

17、语句：coutGetElem is GetElem(head,4)endl;语句频度：语句频度：in，n次次平均为平均为n数量级，故数量级，故T(n)=O(n)4. 在带头结点的单链表在带头结点的单链表L中第中第i结点之前插入元素结点之前插入元素evoid Insert_L(LNode *L, int i, ElemType e)LNode *p,*s;int j;p=L;j=1;while (p!=NULL & jnext; j+;if (p=NULL | ji) coutERROR!data=e;s-next=p-next;p-next=s;5. 删除带头结点的单链表删除带头结点的单链表L

18、中第中第i个结点，其数据元素由函个结点，其数据元素由函数名返回数名返回ElemType delete_list(LNode *L, int i)LNode *p,*q;int j;ElemType e;p=L;j=0;while (p-next!=NULL & jnext; j+; if (p-next=NULL | ji-1) coutERROR!next;e=q-data;p-next=q-next;delete(q);return(e);void listdelete_L(LNode *L,ElemType x)LNode *p,*q;p=L;while( p-next & p-next

19、-data!=x) /找找x的前驱的前驱p=p-next;if(!p-next) coutNot find elementnext; p-next=q-next; delete(q); /删除删除x结点结点6.在带头结点的单链表在带头结点的单链表L中，查找值中，查找值x的元素，删除之。的元素，删除之。（假设（假设L中元素不重复）中元素不重复）7. 链表合并链表合并La,Lb有序递增，合并为有序递增，合并为Lc，仍非递减有序，仍非递减有序LNode *merge_list(LNode *La, LNode *Lb)LNode *Lc,*pa,*pb,*pc;Lc=La; pc=La; /以以La

20、链为基础链为基础pa=La-next; pb=Lb-next;while (pa!=NULL & pb!=NULL)if (pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; if (pa!=NULL) pc-next=pa;else pc-next=pb;delete(Lb); return(Lc);T(n)=O(m+n) （1）a1,ai+1地址可不连续；地址可不连续； （2）不能直接存取，需先移动指针到）不能直接存取，需先移动指针到ai ； （3）插入、删除时，不需大量移动元素。）

21、插入、删除时，不需大量移动元素。n最后一个结点的指针域的指针又指回第一个结最后一个结点的指针域的指针又指回第一个结点的链表点的链表和单链表的差别仅在于，和单链表的差别仅在于，判别判别链表中最后一个结链表中最后一个结点的点的条件条件不再是不再是“后继是否为空后继是否为空”，而是，而是“后后继是否为头结点继是否为头结点”。a1a2anH (a) H (b)单循环链表p =A next ; A next =B next next ;B next=p; A=B; 操作和线性链表基本一致，有时在循环链表中设立尾指针操作和线性链表基本一致，有时在循环链表中设立尾指针可使操作简化。见下图可使操作简化。见下图

22、 ABAB/- /- 线性表的双向链表存储结构线性表的双向链表存储结构 -typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;双向链表双向链表a1a2anai-1aies-prior = p-prior; psai-1ai插入插入p- prior - next = s;s-next = p;p-prior = s;ai-1删除删除aiai+1p-prior-next = p-next;

23、p-next-prior = p-prior;free( p);pai-1n 本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点： (1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。 但它也有两个缺点： 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。 链表的优缺点恰好与顺序表相反。n 基于存储的考虑基于存储的考虑 对线性表的长

24、度或存储规模难以估计时，不宜采用顺序表；链表不用事对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。先估计存储规模，但链表的存储密度较低。n 基于运算的考虑基于运算的考虑 如果经常做的运算是按序号访问数据元素，顺序表优于链表；如果经常做的运算是按序号访问数据元素，顺序表优于链表； 在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优

25、于前者。度考虑后者优于前者。n 基于环境的考虑基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。针的，相对来讲前者简单些，也是用户考虑的一个因素。n 总之，两种存储结构各有长短，选择那一种由实际问总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常题中的主要因素决定。通常“较稳定较稳定”的线性表选择顺的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。选择链式存储。

26、nnnxpxpxppxp.)(2210在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P = (p0, p1, ，pn)一、一元多项式的表示一、一元多项式的表示但是对于形如但是对于形如 S(x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？2.4 线性表的应用线性表的应用_一元多项式相加一元多项式相加 一般情况下的一元稀疏多项式一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：其中：pi 是指数为ei 的项的非零系数， 0 e1 e2 exp=q-exp则将两结点中的系

27、数相加，则将两结点中的系数相加，当和不为零时修改当和不为零时修改p结点中的系数域，将结点中的系数域，将p所指结点加入所指结点加入C; p、q后移。后移。2、若、若p-expexp 则将则将p所指结点加入所指结点加入C 。 p后移。后移。3、若、若p-expq-exp 则则q所指结点加入所指结点加入C。 q后移。后移。typedef struct poly float coef; /系数系数 int exp; /指数指数 struct poly *next; poly;结点的数据元素类型定义为:poly *add_poly(poly *La, poly *Lb) poly *Lc,*pa,*pb

28、,*pc,*s1,*s2;int x;Lc=La; pc=La; /以以La链为基础链为基础pa=La-next; pb=Lb-next; delete(Lb);while (pa & pb)if (pa-expexp) pc-next=pa; pc=pa; pa=pa-next; else if (pa-exppb-exp) pc-next=pb; pc=pb; pb=pb-next; else x=pa-coef+pb-coef;if (x=0) s1=pa; s2=pb; pc-next=pa-next; pa=pa-next; pb=pb-next; delete(s1); delet

29、e(s2);else s2=pb; pc-next=pa; pa-coef=x; pc=pa; pa=pa-next; pb=pb-next; delete(s2);本章小结本章小结1.1.了解线性表的逻辑结构特性是数据元素之间了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。用后者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描

30、述方法，以及熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。线性表的各种基本操作的实现。思考题P29 算法 2.8，若L不是带头结点的单链表，要如何调整程序？想一想，增加头结点的目的是什么？实验：实验：有一个单链表的第一个结点指针为有一个单链表的第一个结点指针为head,编写一个编写一个函数将该单链表逆置函数将该单链表逆置,即最后一个结点变成第一个结即最后一个结点变成第一个结点点,原来倒数第二个结点变成第二个结点。在逆置中原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表不能建立新的单链表调试好后，老师检查，计入实验成绩。上机后写实调试好后，老师检查，计入实验成绩。上机后写实验报告。验报告。编程环境：编程环境：VC6.0+