链表及其应用.ppt

1、1,回顾： 顺序表的特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑 缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先分配空间需按最大空间分配，利用不充分;表容量难以扩充。 讨论：在线性排列的一组数据元素中插入和删除数据元素时可不可以不移动元素？ 答：可以！引入另一种数据结构链表。,2,第3章 链表及其应用, 3.1 链表的基本概念 3.2 单链表的数据结构 3.3 单链表的基本运算实现 3.4 循环链表 3.5 链表的应用,3,3.1 链表的基本概念, 3.1.1 什么是链表 3.1.2 链表的逻辑结构 3.1.3

2、链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算,4, 什么是链表 链表是满足下列条件的一种数据结构： 是有限个具有相同数据类型的数据元素的集合， D = ai | i=1，2，n，n0 ，ai为数据元素 数据元素之间的关系R = | ai-1, aiD i=2，3，n，n0； 数据元素ai-1、 ai（i=2，3，n，n0）在存储器中占用任意的、连续或不连续物理存储区域 。,5,3.1 链表的基本概念,3.1.1 什么是链表 3.1.2 链表的逻辑结构 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算,6, 链表的逻辑结构 同一

3、链表中所有数据元素的数据类型必须相同。 链表中相邻的元素ai-1、ai间存在序偶关系，即对于非空的链表，ai-1是ai的唯一直接前驱，ai1是ai的唯一直接后继；而a1无前驱，an无后继 链表属于线性逻辑结构。,7,3.1 链表的基本概念,3.1.1 什么是链表 3.1.2 链表的逻辑结构 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算,8, 链表的存储结构 用一组任意的存储单元来存放表中的元素，这使得链表中数据元素的逻辑顺序与其物理存储顺序不一定相同； 为确保表中数据元素间的线性逻辑关系，在存储每一个数据元素的同时，存储其逻辑后继的存储地址；,9, 链

4、表的存储结构 ai的值与ai1的存储地址共同组成了链表中的一个结点：,其中：data域是数据域，用来存放数据元素ai的值； next域是指针域，用来存放ai的直接后继ai1的存储地址。 链表正是通过每个结点的指针域将表中n个数据元素按其逻辑顺序链接在一起的。,10,【例】设有一组线性排列的数据元素（zhao, qian, sun, li, zhou, wu, zheng, wang），其链接存储形式如图所示：,11,讨论：在该存储方式下，如何找到表中任一元素？ 答：在链接存储方式下（链表中），每一个数据元素的存储地址是存放在其直接前驱结点的next域中，只要知道第一个数据元素（结点）zhao的

5、存储地址，就可以“顺藤摸瓜”找到其后续的所有结点。 另外：链表中的最后一个数据元素无后继，则最后一个结点（尾结点）的指针域为空。,12,通常情况下，我们用箭头来表示指针域中的指针，忽略每一个结点的实际存储位置，而重点突出链表中结点间的逻辑顺序，将链表直观地画成用箭头链接起来的结点序列。,13,3.1 链表的基本概念,3.1.1 什么是链表 3.1.2 链表的逻辑结构 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算,14,静态链表 静态链表是用地址连续的存储空间(一般使用计算机语言中的“数组”)存储链表中的元素，及其逻辑后继在数组中的位置。 与顺序表不同的

6、是，在静态链表中逻辑位置相邻的元素其物理位置不一定相邻。,15,【例】 如图所示的静态链表。该链表存储在一个数组空间中，该数组为结构类型，每一个数组元素包括两个分量(也可以是多个分量)：存放表中元素值的data分量和存放该元素直接后继位置的next分量。,16,我们可以用结构体来定义静态链表的节点数据类型： typedef struct Datatype data； int next； node； 一个静态链表可以描述为： #define maxsize 100 node nodepoolmaxsize；/存放链表的数组 int head；/放头指针的head 在静态链表中进行插入与删除操作不

7、需要移动元素，只需改变被插入(删除)元素的直接前驱的next域中的值。,17, 动态链表 由于静态链表需要事先估计表中数据元素的个数，通常情况下，我们可以为链表中的每一个数据元素分配相应的存储空间. 该存储空间中存放有该数据元素的值(data域)和其直接后继的存储空间地址(next域)，数据元素之间的逻辑关系由每一个这样的存储空间中所存储的地址来维系。 我们称这样的链表为动态链表。 我们在本章后续所讨论的链表都是动态链表。,18,3.1 链表的基本概念,3.1.1 什么是链表 3.1.2 链表的逻辑结构 3.1.3 链表的存储结构 3.1.4 静态链表和动态链表 3.1.5 链表的基本运算,1

8、9,我们可以定义链表的以下6种基本运算： （1）置空表LLsetnull ( L ) 运算的结果是将链表L置成空表。 （2）求表长LLlength ( L ) 运算结果是输出链表中数据元素的个数。 （3）按序号取元素LLget (L ,i ) 当1ilength ( L )时，输出链表L中第i个结点的值或其地址。,20,（4）按值查找（定位）LLlocate ( L , x ) 当链表L中存在值为 x 的结点时，输出该元素的地址。若表L中存在多个值为x 的结点，则依次输出它的所有地址；当表中不存在值为x 的结点时，则输出空指针。 （5）插入LLinsert (L , i ,x) 在链表L中的第

9、i位置插入值为x的结点，表长由n变为n+1。,21,（6）删除 LLdelete (L , i ) 在链表L中删除第i个结点，表长由n变为n-1。 在解决具体问题时，所需要的运算可能仅是上述运算中的一部分，也可能需要更为复杂的运算。对于复杂运算，可通过上述6种基本运算的组合来实现。,22,第3章 链表及其应用,3.1 链表的基本概念 3.2 单链表的数据结构 3.3 单链表的基本运算实现 3.4 循环链表 3.5 链表的应用,23,定义 单链表是满足下列条件的一种数据： 是有限个具有相同数据类型的数据元素组成的链表； 该链表的每个结点只有一个指针域。,24,单链表中的每一个结点包括两个域： 存

10、储该结点所对应的数据元素信息的data域 数据域 存储其直接后继的存储位置的next域 指针域,25,该结点的数据类型用C语言描述为： typedef struct node DataType data; struct node *next; LinkList ； 可以定义一个该类型的指针变量：LinkList *H；,26,称 H为该单链表的头指针。 若已知单链表的头指针，则可以搜索到表中任一结点；也就是说，单链表由头指针唯一确定。 因此，单链表可以用头指针的名字来命名。 上图所示的单链表可称为单链表H。,若有：,27,注意：严格区分指针变量和结点变量 对于上例，H为指针变量；若它的值非空，

11、则它的值为linklist类型的某结点的地址； 若H非空，*H为LinkList类型的结点变量，它有两个分量：(*H).data 和 (*H).next 或者写成H-data和H-next 其中：(*H).data为DataType类型的变量，若它的值非空，其值为该数据元素ai的值； (*H).next是与H同类型的指针变量，其值为ai的直接后继ai+1的地址。,28,上图所示的单链表H，表中各结点的地址及数据元素值分别表示为： 结点1的地址：H 数据元素a1值：H-data 结点2的地址：H-next 数据元素a2值：H-next -data 若令p = H-next ： 则数据元素a2值为

12、：p -data 结点3的地址：p-next；,29,再令p = p-next， 数据元素a3值：p -data 结点4的地址：p-next；,30,再令p = p-next 数据元素a4值：p -data 结点5的地址：p-next；,再令p = p-next， 数据元素a5值：p -data 结点5无后继结点，则p-next = NULL。,31, 可以看出：若有LinkList *pH-next（或LinkList *pH），则除第一个结点外，其余结点的地址、数据元素值均有一致的表述方式，分别为 p-next p -data 为使单链表中所有结点都有一致的描述方式，不妨在第一个结点之前加

13、一个同类型的结点，并称该结点为头结点。,32, 头结点的data域中不存放任何内容，或者存放表长信息； 头结点的next域中存放第一个数据元素结点的地址，而指针H记录头结点的地址。 我们称这样的单链表为带头结点的单链表。 在带头结点的单链表中，我们称第一个数据元素结点为首元素结点，称最后一个数据元素结点为尾结点。,头指针,头结点,首元素结点,尾结点,33,何谓头指针、头结点和首元结点？,头指针是指向链表中第一个结点（或为头结点或为首元素结点）的指针。 单链表可由一个头指针唯一确定。 头结点是在链表的首元素结点之前附设的一个结点；数据域内只放空表标志和表长等信息; 首元素结点是指链表中存储线性表

14、第一个数据元素a1的结点。,34,答：,讨论1. 在链表中设置头结点有什么好处？,讨论2. 如何表示空表？,头结点即在链表的首元素结点之前附设的一个结点，该结点的数据域中不存储数据元素的值，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元素结点进行统一处理，编程更方便。,答：,无头结点时，当头指针的值为空时表示空表； 有头结点时，当头结点的指针域为空时表示空表。,35,第3章 链表及其应用,3.1 链表的基本概念 3.2 单链表的数据结构 3.3 单链表的基本运算实现 3.4 循环链表 3.5 链表的应用,36,3.3 单链表的基本运算实现, 3.3.1 带头结点的单链表的基本

15、运算实现 3.3.2 单链表的运算效率分析 3.3.3 单链表的建立和输出,37,1、置空表 LLsetnull ( L ),没有元素，仅有头结点 即：L-next = NULL (空）,算法： LinkList *LLsetnull (LinkList *L) L-next = NULL; return ( L); ,38,2、求表长 LLlength ( L),难点分析：每个数据元素在内存中是“零散”存放的，怎么查询数据元素的个数？,实现思路：从头结点开始，顺着各个结点next域中记录的地址，依次访问各结点，直到遇到某结点的next的值为空（NULL）为止。,39,流程图：,p=Lnext

16、,n=0,n=n+1,p=pnext,40,int LLlength(LinkList *L) /求带头结点的单链表L的长度 LinkList *p; int n; p=L-next; n=0; /用来存放单链表的长度 while(p!=NULL) p=p-next; n+; return n; ,算法描述如下：,41,3、取第 i 个元素 LLget(L,i）,思路：要取第i个数据元素，关键是要先找到该结点的指针p， 然后输出该结点的地址p，或输出该数据元素的值p-data均可。,难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取 。,42,方法： 从单链表的头指

17、针L出发，从首元素结点 （L-next）开始顺着链域扫描， 用指针p指向当前扫描到的结点, 初值指向首元素结点，用j做计数器，累计当前扫描过的结点数（初值为1）， 当j = i 时， 指针p所指的结点就是要找的第i个结点。,43,流程图：,p = p next；j + + ;,所找的结点不存在,44,算法描述：,LinkList *Get (LinkList *L, int i) /在带头结点的单链表L中查找第i个结点， 若找到(1in)， 则返回该结点的存储位置; 否则返回NULL int j； LinkList *p； p=L-next ； j=1； / 从首元素结点开始扫描 while

18、(p! =NULL p=L-next; / 从表中第一个结点比较 while (p!=NULL) if (p-data ! =x) p=p-next; else break; / 找到值为x的结点， 退出循环 return p; ,48,5. 单链表的插入LLinsert (L, i , x),在链表中插入一个元素的示意图如下：,插入步骤（即核心语句）：,Step 1：s-next=p-next; Step 2：p-next=s ；,p-next,s-next,元素x结点应预先生成： S=(LinkList)malloc(m); S-data=x;,49,插入条件： 1 i n + 1 即：可

19、在a1前，或an后插入 也就是说，要求第 i1位置 不空 即：get (L, i- 1) NULL (空）,50,流程图：,S=malloc(sizeof(linklist) Sdata = x Snext = pnext Pnext = S,51,void LLinsert(LinkList *L, int i, DataType x) /在带头结点的单链表L中第i个位置插入值为x的新结点 LinkList *p, *s; p = get(L , i-1) ; / 在第i个元素之前插入， 则先找到第i-1个数据元素的存储位置, 使指针p指向它 if (p!=NULL ) s = malloc

20、(sizeof(LinkList); / 为e申请一个新的结点并由s指向它 s-data = x; / 将待插入结点的值x赋给s的数据域 s-next=p-next; /完成插入操作 p-next=s; ; ,52,6. 单链表的删除 LLdelete (L , i ),在链表中删除某元素的示意图如下：,删除步骤（即核心语句）：,q = p-next; /*保存b的指针，靠它才能指向c*/ p-next=q-next; /* a、c两结点相连*/ free(q) ； /* 删除b结点，彻底释放*/,p-next,思考： 省略free(q)语句行不行？,(p-next) - next,53,删除

21、条件: 1 i n 即：结点ai-1不空，且不是尾结点。 即：若 pget (L, i-1)，则 pNULL 且 p-nextNULL,54,void LLdelete(LinkList *L, int i) /在带头结点的单链表L中删除第i个结点 LinkList *p, *q; p = get(L , i-1) ; / 删除第i个结点， 则先找到第i-1个结点的存储位置, 使指针p指向它 if (p!=NULL free(q) ； ,55,3.3 单链表的基本运算实现,3.3.1 带头结点的单链表的基本运算实现 3.3.2 单链表的运算效率分析 3.3.3 单链表的建立和输出,56,链表的

22、运算效率分析,（1）查找 包括按序号查找LLget( )和按值查找LLlocate( )，因单链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。, 时间效率分析,（2）插入和删除 因单链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。,但在单链表中进行插入或删除操作时，要调用LLget( )函数，该函数的时间复杂度为O(n)，这使得插入或删除操作所耗时间复杂度为 O(n)。,57, 空间效率分析,单链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。,58,3.3 单链表的基本运算实现,3.3.1 带头结点的单链表的

23、基本运算实现 3.3.2 单链表的运算效率分析 3.3.3 单链表的建立和输出,59,1、头插法建立单链表,实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？,实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将该结点插入到头结点后（首元素结点前）。,60,建表过程如图所示:,L= malloc(sizeof(LinkList); L-next = NULL;,61,scanf(“%d”, ,62,L-next = S;,63,while( 条件 ) s

24、canf(“%d”, ,64,LinkList *SetList( ) /字母链表的生成，要一个一个链入 LinkList *L, *S; int i; L= malloc(sizeof(LinkList); S= malloc(sizeof(LinkList); L-next = S; S-next = NULL; for(i=0;idata=z-i; / 倒数第一个结点值为字符z S= malloc(sizeof(LinkList); S-next = L-next; L-next = S; S-data=z-i; / 插入第一个结点字符a return L; ,65,2. 单链表的输出,

25、实现思路：顺着头指针，从第一个结点开始，“顺藤摸瓜”，直到最后一个结点（其next域为空）。,算法：void display(LinkList *head) /字母链表的输出 p=head-next; while (p!=NULL) printf (%c,p-data); p=p-next; /只要没到最后一个元素，就不停地向后搜索 ,66,第3章 链表及其应用,3.1 链表的基本概念 3.2 单链表的数据结构 3.3 单链表的基本运算实现 3.4 循环链表 3.5 链表的应用,67,3.4 循环链表, 3.4.1 单循环链表 3.4.2 双向循环链表,68,讨论1： 单链表能不能首尾相连？怎

26、样实现？,答：能。只要将表中最后一个结点的指针域指向头结点即可 (P-next= L;) 。这种形成环路的单链表称为单循环链表。,69,特别地：带头结点的空循环链表样式,单循环链表的特点： 1、从任一结点出发均可找到表中其他结点。 2、操作仅有 一 点与单链表不同：结束循环的条件 单链表 - p = NULL 或 p -next =NULL 循环链表- p= L 或 p-next = L,这时：Lnext = L,70,带尾指针的单循环链表：,空表：,这时：Rnext = R,这时： 头指针为： Rnext,71,例：两个带尾指针的循环链表首尾相接,思路: (1) 将b1的地址存放在an的ne

27、xt域中，同时注意不可以丢 掉链表A的头指针； (2) 应记录完成后的链表的头指针或尾指针。,实现: (1) 用指针变量u记录链表A的头指针； (2) 将b1的地址存放在an的next域中； (3) 记下链表B的尾指针，并释放其头结点。,72,(A),步骤: (1)u = Anext (2) Anext = Bnextnext (3) free (Bnext) (4) Bnext = u (5) A = B,73,3.4 循环链表,3.4.1 单循环链表 3.4.2 双向循环链表,74,讨论2： 单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？,答：能。只要把单链表再多开一个指针域

28、即可。,这种有两个指针的链表称为双向链表。,75, 双向链表中的指针域next和prior分别记录其前驱、后继结点的地址。, 结点数据类型描述：,typedef struct dnode datatype data; struct dnode *prior, *next; Dlinklist;,76, 带头结点的空双向链表样式：,这时： Lnext = Lprior = L, 双向链表中的运算，基本上同单链表。这里，重点介绍插入和删除运算：,插入：包括 前插 和 后插 前插：在 *p 结点前插入新结点 后插：在 *p 结点后插入新结点,77,后插：,插入方法同单链表。,插入过程：,78,(4)

29、 pprior = s,(3) ppriornext = s,(1) sprior = pprior,(2) snext = p,前插：,79,删除：删除结点*p,pprior next = pnext;,pnext prior = pprior;,free (p);,80,第3章 链表及其应用,3.1 链表的基本概念 3.2 单链表的数据结构 3.3 单链表的基本运算实现 3.4 循环链表 3.5 链表的应用,81,3.5 链表的应用, 3.5.1 多项式相加问题 3.5.2 两个链表的归并问题 3.5.3 链表在字符处理方面的应用 链串,82, 一元多项式的表示 通常，一个n次一元多项式P

30、(x)可按升幂的形式写成： P(x) = a0 + a1x + a2x2 + + anxn 它实际上包含n+1项，由n+1个系数唯一确定。在计算机内，我们可以用一个链表来表示一个一元多项式。 为了节省存储空间，我们只存储多项式中系数非0 的项。链表中的每一个节点存放多项式的一个系数非0项，它包含三个域，分别存放该项的系数、指数以及指向下一多项式项节点的指针。,83,下图所示为该节点的结构：,该节点的数据类型如下： typedef struct Pnode int coef； int exp； struct Pnode *next； Polynode；,84,例如：多项式P = 3 + 4x +

31、 6x3 + 8x7+ 23x21的单链表表示形式如下图所示 ：,为方便以后的运算，我们也在该单链表中增加了头节点，并给定指数值为-1。,85, 两个一元多项式相加,两个多项式相加的法则是： 两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多项式”中的一项；所有指数不同的项均直接移位至“和多项式”中。,86,【例】 两个一元多项式A (x)=2+ 5x+9x8 +5x17， B(x) = 10 x + 22x6 - 9x8，分别用单链表表示，试描述其相加的过程。,指针p、q指向多项式链表A、B的首元素结点， 并令指针pre=A;,87,p-exp exp，指针p、pre后移： 即：p

32、re = p , p=p-next,此时p-exp = q-exp，则将*p和*q结点的系数相加： p-coef = p-coef + q-coef,若约定相加的结果用单链表A表示，则free(B)，且B=q；,88,15,指针q后移，即：q=q-next，同时free(B)，且B=q；,p-exp exp，指针p、pre后移： 即：pre = p , p=p-next,89,15,p-exp q-exp，应将*q插入到*p结点前： q=q-next； B-next=p； pre-next = B； pre = B； B=q；,90,此时p-exp = q-exp，则将*p和*q结点的系数相加

33、： p-coef = p-coef + q-coef,91,但相加后p-coef = 0；需要将结点*p从链表A中删除： pre-next = p-next ； free(p)； p = pre-next ；,指针q后移，即：q=q-next，同时free(B)，且B=q；,此时q = NULL，算法结束。,92,综合以上分析，两个一元多项式相加的算法如下： Polynode *polyadd(Polynode *A，Polynode *B) /两个多项式相加，将和多项式存放在多项式A中，并将多项式B删除 Polynode *p，*q，*temp，*pre； int sum； p = A-ne

34、xt ； q = B-next / p和q分别指向A和B多项式链表中的第一个节点 pre = A ； /pre指向*p的前趋节点 free (B)；/释放多项式B的头节点空间 ,93,while (p! =NULL int curlen ; link_string; link_string *ST ;,为便于操作，我们为块链串增加一个尾指针。块链的结构描述为：,108,以下是第2、3章的补充（综合）知识。,109, 线性表的概念,线性表(Linear List)是由n (n0)个类型相同的数据元素a1, a2, ， an组成的有限序列，有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 记作（a1, a2, ，ai-1，ai，ai+1， ，an）,110,（a1, a2, a