《链表及其应用》PPT课件

,第3章 链表及其应用,*,合肥学院 计算机科学与技术系“数据结构与算法”课程建设组（2007-11-20）,回顾：,顺序表的特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；,优点：可以随机存取表中任一元素O(1)；存储空间使用紧凑,缺点：在插入，删除某一元素时，需要移动大量元素O(n);预先分配空间需按最大空间分配，利用不充分;表容量难以扩充,。,讨论：,在线性排列的一组数据元素中插入和删除数据元素时可不可以不移动元素？,答：可以！引入另一种数据结构链表。,1,第3章 链表及其应用,3.1 链表的基本概念,3.2 单链表的数据结构,3.3 单链表的基本运算实现,3.4 循环链表,3.5 链表的应用,2,3.1 链表的基本概念,3.1.1 什么是链表,3.1.2 链表的逻辑结构,3.1.3 链表的存储结构,3.1.4 静态链表和动态链表,3.1.5 链表的基本运算,3, 什么是链表, 链表是满足下列条件的一种数据结构：, 是有限个具有相同数据类型的数据元素的集合，,D = a,i,| i=1，2，n，n0 ，a,i,为数据元素, 数据元素之间的关系R = | a,i-1, a,i,D i=2，3，n，n0；, 数据元素a,i-1,、 a,i,（i=2，3，n，n0）在存储器中占用任意的、连续或不连续物理存储区域 。,4,3.1 链表的基本概念,3.1.1 什么是链表,3.1.2 链表的逻辑结构,3.1.3 链表的存储结构,3.1.4 静态链表和动态链表,3.1.5 链表的基本运算,5,链表的逻辑结构, 同一链表中所有数据元素的数据类型必须相同。, 链表中相邻的元素a,i-1,、a,i,间存在序偶关系，即对于非空的链表，a,i-1,是a,i,的唯一直接前驱，a,i1,是a,i,的唯一直接后继；而a,1,无前驱，a,n,无后继, 链表属于,线性逻辑结构,。,6,3.1 链表的基本概念,3.1.1 什么是链表,3.1.2 链表的逻辑结构,3.1.3 链表的存储结构,3.1.4 静态链表和动态链表,3.1.5 链表的基本运算,7,链表的存储结构,用一组任意的存储单元来存放表中的元素，这使得,链表中数据元素的逻辑顺序与其物理存储顺序不一定相同,；,为确保表中数据元素间的线性逻辑关系，在存储每一个数据元素的同时，存储其逻辑后继的存储地址；,8,链表的存储结构,a,i,的值与a,i1,的存储地址共同组成了链表中的一个结点,：,data next,其中：,data域是数据域，用来存放数据元素a,i,的值；,next域是指针域，用来存放a,i,的直接后继a,i1,的存储地址。,链表正是通过每个结点的指针域将表中n个数据元素按其逻辑顺序链接在一起的。,9,【例】设有一组线性排列的数据元素（zhao, qian, sun, li, zhou, wu, zheng, wang），其链接存储形式如图所示：,存储地址,数据域,指针域,zhao,li,zhou,zheng,qian,wang,100,sun,wu,160,170,200,210,220,310,320,320,210,160,310,200,220,100,10,讨论：,在该存储方式下，如何找到表中任一元素？,答：在链接存储方式下（链表中），每一个数据元素的存储地址是存放在其直接前驱结点的next域中，只要知道第一个数据元素（结点）zhao的存储地址，就可以“顺藤摸瓜”找到其后续的所有结点。,另外：,链表中的最后一个数据元素无后继，则最后一个结点（尾结点）的指针域为空。,11,通常情况下，我们,用箭头来表示指针域中的指针,，忽略每一个结点的实际存储位置，而重点突出链表中结点间的逻辑顺序，,将链表直观地画成用箭头链接起来的结点序列,。,zhao,zhou,zheng,qian,li,sun,wu,wang,12,3.1 链表的基本概念,3.1.1 什么是链表,3.1.2 链表的逻辑结构,3.1.3 链表的存储结构,3.1.4 静态链表和动态链表,3.1.5 链表的基本运算,13,静态链表,静态链表是用地址连续的存储空间(一般使用计算机语言中的“数组”)存储链表中的元素，及其逻辑后继在数组中的位置。,与顺序表不同的是，在静态链表中逻辑位置相邻的元素其物理位置不一定相邻。,14,【例】 如图所示的静态链表。该链表存储在一个数组空间中，该数组为结构类型，每一个数组元素包括两个分量(也可以是多个分量)：存放表中元素值的data分量和存放该元素直接后继位置的next分量。,15,我们可以用结构体来定义静态链表的节点数据类型：,typedef struct,Datatype data；,int next；,node；,一个静态链表可以描述为：,#define maxsize 100,node nodepoolmaxsize；/存放链表的数组,int head；/放头指针的head,在静态链表中进行插入与删除操作不需要移动元素，只需改变被插入(删除)元素的直接前驱的next域中的值。,16,动态链表,由于静态链表需要事先估计表中数据元素的个数，通常情况下，我们可以为链表中的每一个数据元素分配相应的存储空间.,该存储空间中存放有该数据元素的值(data域)和其直接后继的存储空间地址(next域)，数据元素之间的逻辑关系由每一个这样的存储空间中所存储的地址来维系。,我们称这样的链表为,动态链表,。,我们在本章后续所讨论的链表都是动态链表。,17,3.1 链表的基本概念,3.1.1 什么是链表,3.1.2 链表的逻辑结构,3.1.3 链表的存储结构,3.1.4 静态链表和动态链表,3.1.5 链表的基本运算,18,我们可以定义链表的以下6种基本运算：,（1）置空表,LLsetnull ( L ),运算的结果是将链表L置成空表。,（2）求表长,LLlength ( L ),运算结果是输出链表中数据元素的个数。,（3）按序号取元素,LLget (L ,i ),当1ilength ( L )时，输出链表L中第i个结点的值或其地址。,19,（4）按值查找（定位）,LLlocate ( L , x ),当链表L中存在值为 x 的结点时，输出该元素的地址。若表L中存在多个值为x 的结点，则依次输出它的所有地址；当表中不存在值为x 的结点时，则输出空指针。,（5）插入,LLinsert (L , i ,x),在链表L中的第i位置插入值为x的结点，表长由n变为n+1。,20,（6）删除,LLdelete (L , i ),在链表L中删除第i个结点，表长由n变为n-1。,在解决具体问题时，所需要的运算可能仅是上述运算中的一部分，也可能需要更为复杂的运算。对于复杂运算，可通过上述6种基本运算的组合来实现。,21,第3章 链表及其应用,3.1 链表的基本概念,3.2 单链表的数据结构,3.3 单链表的基本运算实现,3.4 循环链表,3.5 链表的应用,22,定义,单链表是满足下列条件的一种数据：, 是有限个具有相同数据类型的数据元素组成的链表；, 该链表的每个结点只有一个指针域。,23,单链表中的每一个结点包括两个域：,存储该结点所对应的数据元素信息的data域,数据域,存储其直接后继的存储位置的next域,指针域,data next,24,该结点的数据类型用C语言描述为：,typedef struct node, DataType data;,struct node *next;, LinkList ；,可以定义一个该类型的指针变量：LinkList *H；,data next,25,zhao,zhou,qian,li,sun,zheng,wu,wang,H,称 H为该单链表的头指针。,若已知单链表的头指针，则可以搜索到表中任一结点；也就是说，,单链表由头指针唯一确定,。,因此，单链表可以用头指针的名字来命名。,上图所示的单链表可称为,单链表H,。,若有：,26,注意：,严格区分,指针变量,和,结点变量,对于上例，,H,为,指针变量,；若它的值非空，则它的值为linklist类型的某结点的地址；,若H非空，,*H,为LinkList类型的,结点变量,，它有两个分量：(*H).data 和 (*H).next,或者写成H-data和H-next,其中：(*H).data为DataType类型的变量,，若它的值非空，其值为该数据元素a,i,的值；,(*H).next是与H同类型的指针变量,，其值为a,i,的直接后继a,i+1,的地址。,27,上图所示的单链表H，表中各结点的地址及数据元素值分别表示为：,结点1的地址：H 数据元素a1值：H-data,结点2的地址：H-next,数据元素a2值：H-next -data,若令,p = H-next,：,则数据元素a2值为：p -data,结点3的地址：p-next；,p,a,1,a,2,a,4,a,5,a,3,H,28,再令,p = p-next,，,数据元素a3值：p -data,结点4的地址：p-next；,p,a,1,a,2,a,4,a,5,a,3,H,p,29,再令,p = p-next,数据元素a4值：p -data,结点5的地址：p-next；,p,a,1,a,2,a,4,a,5,a,3,H,再令,p = p-next,，,数据元素a5值：p -data,结点5无后继结点，则p-next = NULL。,p,a,1,a,2,a,4,a,5,a,3,H,p,30,可以看出：若,有LinkList *pH-next（或LinkList *pH），则除第一个结点外，其余,结点的地址,、,数据元素值,均有一致的表述方式，分别为,p-next,p -data,为使单链表中所有结点都有一致的描述方式，不妨在第一个结点之前加一个同类型的结点，并称该结点为,头结点,。,a,n,a,i,a,i+1,a,i-1,a,1,a,2,H,31,a,n,a,i,a,i+1,a,i-1,a,1,a,2,H,头结点的data域中不存放任何内容，或者存放表长信息；,头结点的next域中存放第一个数据元素结点的地址，而指针H记录头结点的地址。,我们称这样的单链表为,带头结点的单链表,。,在带头结点的单链表中，我们称第一个数据元素结点,为首元素结点,，称最后一个数据元素结点为,尾结点,。,头指针,头结点,首元素结点,尾结点,32,何谓,头指针、头结点和首元结点,？,头指针,是指向链表中第一个结点（或为,头结点,或,为首元素结点,）的指针。,单链表可由一个头指针唯一确定。,头结点,是在链表的,首元素结点,之前,附设,的一个结点；数据域内只放空表标志和表长等信息;,首元素结点,是指链表中存储线性表第一个数据元素,a,1,的结点。,头指针,头结点,首元素结点,a,1,33,答：,讨论1,. 在链表中设置,头结点,有什么好处？,讨论2,. 如何表示,空表,？,头结点,即在链表的首元素结点之前附设的一个结点，该结点的数据域中不存储数据元素的值，其作用是为了对链表进行操作时，可以对,空表、非空表,的情况以及对,首元素结点,进行统一处理，编程更方便。,答：,无头结点时，,当头指针的值为空,时表示空表；,有头结点时，,当头结点的指针域为空,时表示空表。,头指针,头指针,头结点,无头结点,有头结点,34,第3章 链表及其应用,3.1 链表的基本概念,3.2 单链表的数据结构,3.3 单链表的基本运算实现,3.4 循环链表,3.5 链表的应用,35,3.3 单链表的基本运算实现,3.3.1 带头结点的单链表的基本运算实现,3.3.2 单链表的运算效率分析,3.3.3 单链表的建立和输出,36,1、置空表 LLsetnull ( L ),L,没有元素，仅有头结点,即：L-next = NULL (空）,算法：,LinkList *LLsetnull (LinkList *L) ,L-next = NULL;,return ( L);,37,2、求表长 LLlength ( L),a,1,a,2,a,3,a,n,L,P,难点分析：,每个数据元素在内存中是“零散”存放的，怎么查询数据元素的个数？,实现思路：,从头结点开始，顺着各个结点next域中记录的地址，依次访问各结点，直到遇到某结点的next的值为空（NULL）为止。,38,流程图：,p=Lnext,n=0,n=n+1,p=pnext,Y,p=NULL,N,a,1,a,2,a,3,a,n,L,P,39,int LLlength(LinkList *L) ,/求带头结点的单链表L的长度,LinkList *p; int n;,p=L-next; ,n=0;,/用来存放单链表的长度,while(p!=,NULL,) ,p=p-next; ,n+; ,return n; ,算法描述如下：,40,3、取第 i 个元素 LLget(L,i）,思路：,要取第i个数据元素，关键是要先找到该结点的指针p， 然后输出该结点的地址p，或输出该数据元素的值p-data均,可。,难点：,单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取 。,a,1,a,2,a,3,a,n,L,P,41,方法：,从单链表的头指针L出发，从首元素结点 （L-next）开始,顺着链域扫描,， 用,指针p指向当前扫描到的结点, 初值指向首元素结点，用,j做计数器,，累计当前扫描过的结点数（初值为1），,当j = i 时， 指针p所指的结点就是要找的第i个结点,。,a,1,a,2,a,3,a,n,L,P,42,流程图：,j = i,p =,NULL,N,p = p next；j + + ;,N,p=Lnext ；j =1;,Y,Y,所找的结点不存在,返回p,a,1,a,2,a,3,a,n,L,P,43,算法描述：,LinkList *Get (LinkList *L, int i) ,/在带头结点的单链表L中查找第i个结点， 若找到(1in)， 则返回该结点的存储位置; 否则返回NULL ,int j； LinkList *p；, p=L-next ； j=1；,/ 从首元素结点开始扫描,while (p! =NULL&jnext；,/ 扫描下一结点,j+；,/ 已扫描结点计数器,if（i= =j） return p；,/ 找到了第i个结点,else return NULL；,/ 找不到， i0或in,44,4 、查找 LLlocate (L,x),在表L中查找值为 x 的结点的地址,思路：,从单链表的头指针指向的头结点出发（或者从首元素结点出发），顺着链逐个将结点的值和给定值x作比较。若有结点值等于x的结点，则返回首次找到的其值为x的结点的存储位置，否则返回NULL。,a,1,a,2,a,3,a,n,L,P,45,流程图：,p = NULL,p-data =,x,N,p = p next,N,p=Lnext,Y,Y,返回p,a,1,a,2,a,3,a,n,L,P,所找的结点不存在,46,算法描述：,LinkList *LLlocate( LinkList *L, DataType x) ,/在带头结点的单链表L中查找其结点值等于X的结点， 若找到则返回该结点的位置p；否则返回NULL ,LinkList *p; ,p=L-next;,/ 从表中第一个结点比较,while (p!=NULL),if (p-data ! =x) p=p-next;,else break;,/ 找到值为x的结点， 退出循环,return p; ,47,5. 单链表的插入LL,insert (L, i , x),在链表中插入一个元素的示意图如下：,x,s,b,a,p,a,b,p,插入步骤（即核心语句）：,Step 1：,s-next=p-next;,Step 2：,p-next=s ；,p-next,s-next,元素x结点应预先生成：,S=(LinkList)malloc(m);,S-data=x;,48,插入条件：,1 i n + 1,即：可在a1前，或an后插入,也就是说，要求第 i1位置 不空,即：,get (L, i- 1) NULL (空）,49,流程图：,p=get (L,i 1),p =NULL,S=malloc(sizeof(linklist),Sdata = x,Snext = pnext,Pnext = S,N,Y,50,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(sizeof(LinkList);,/ 为e申请一个新的结点并由s指向它,s-data = x;,/ 将待插入结点的值x赋给s的数据域,s-next=p-next;,/完成插入操作,p-next=s; ; ,51,6. 单链表的删除,LLdelete (L , i ),在链表中删除某元素的示意图如下：,c,a,b,p,删除步骤（即核心语句）：,q = p-next;,/*,保存,b,的指针，靠它才能指向c*/,p-next=q-next;,/*,a、c两结点相连,*/,free(q) ；,/*,删除b结点，彻底释放,*/,p-next,思考： 省略,free(q)语句,行不行？,(p-next) - next,52,删除条件:,1 i n,即：结点,a,i-1,不空，且不是尾结点。,即：,若 pget (L, i-1)，则 pNULL,且 p-nextNULL,53,void LLdelete(LinkList *L, int i) ,/在带头结点的单链表L中删除第i个结点, LinkList *p, *q; , p = get(L , i-1) ;,/ 删除第i个结点， 则先找到第i-1个结点的存储位置, 使指针p指向它, if (p!=NULL&p-next !=NULL) ,/第 i-1个结点和第i个结点均存在,q = p-next;,p-next=q-next;,free(q) ； ,54,3.3 单链表的基本运算实现,3.3.1 带头结点的单链表的,基本运算实现,3.3.2 单链表的运算效率分析,3.3.3 单链表的建立和输出,55,链表的运算效率分析,（1）,查找 包括按序号查找,LLget( ),和按值查找,LLlocate( ),，因单链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为,O,(n),。,时间效率分析,（2）,插入和删除 因单链表不需要移动元素，只要修改指针，一般情况下时间复杂度为,O,(1),。,但在单链表中进行插入或删除操作时，要调用,LLget( ),函数，该函数的时间复杂度为O,(n),，这使得插入或删除操作所耗时间复杂度为 O(n)。,56,空间效率分析,单链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为,O,(n),。,57,3.3 单链表的基本运算实现,3.3.1 带头结点的单链表的基本运算实现,3.3.2 单链表的运算效率分析,3.3.3 单链表的建立和输出,58,1、头插法建立单链表,实例,：,用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C语言程序。,难点分析：,每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？,实现思路：,先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将该结点插入到头结点后（首元素结点前）。,59,建表过程如图所示:,L= malloc(sizeof(LinkList);,L-next = NULL;,60,scanf(“%d”, ,S= malloc(sizeof(LinkList);,S-data = x;,S-next = NULL;,61,L-next = S;,62,while(,条件,),scanf(“%d”, ,S= malloc(sizeof(LinkList);,S-data = x;,S-next = L-next;,L-next = S;,63,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;,64,2. 单链表的输出,实现思路：,顺着头指针，从第一个结点开始，“顺藤摸瓜”，直到最后一个结点（其next域为空）。,算法：,void display(LinkList *,head,) ,/字母链表的输出,p=head-next;,while (p!=NULL) printf (%c,p-data);,p=p-next;,/只要没到最后一个元素，就不停地向后搜索,65,第3章 链表及其应用,3.1 链表的基本概念,3.2 单链表的数据结构,3.3 单链表的基本运算实现,3.4 循环链表,3.5 链表的应用,66,3.4 循环链表,3.4.1 单循环链表,3.4.2 双向循环链表,67,讨论1： 单链表能不能首尾相连？怎样实现？,答：能。只要将表中最后一个结点的指针域指向头结点即可 (,P-next= L;,) 。这种形成环路的单链表称为,单循环链表,。,a,1,L,a,n,a,i,p,68,特别地：,带头结点的,空,循环链表样式,单循环链表的特点：,1、从任一结点出发均可找到表中其他结点。,2、操作仅有 一 点与单链表不同：,结束循环的条件,单链表 - p = NULL 或 p -next =NULL,循环链表- p= L 或 p-next = L,L,这时：Lnext = L,69,带尾指针的单循环链表：,a,1,a,n,a,i,R,R,空表：,这时：Rnext = R,这时： 头指针为： Rnext,70,例：两个带尾指针的循环链表首尾相接,思路:,(1) 将,b,1,的地址,存放在,a,n,的next域,中，同时注意不可以丢,掉链表A的头指针；,(2) 应记录完成后的链表的头指针或尾指针。,a,1,a,i,a,n,A,b,1,b,i,b,n,B,实现:,(1) 用,指针变量u,记录链表A的头指针；,(2) 将,b,1,的地址,存放在,a,n,的next域,中；,(3) 记下链表B的尾指针，并释放其头结点。,u,71,a,1,a,i,a,n,A,b,1,b,i,b,n,B,u,(A),步骤:,(1)u = Anext,(2) Anext = Bnextnext,(3) free (Bnext),(4) Bnext = u,(5) A = B,72,3.4 循环链表,3.4.1 单循环链表,3.4.2 双向循环链表,73,讨论2： 单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？,答：能。只要把单链表再多开一个指针域即可。,这种有两个指针的链表称为,双向链表,。,L,a,1,a,n,a,i,74,双向链表中的指针域,next,和,prior,分别记录其前驱、后继结点的地址。,prior,data,next, 结点数据类型描述：,typedef,struct dnode,datatype data;,struct dnode *prior, *next;,Dlinklist;,75,带头结点的,空,双向链表样式：,L,这时：,Lnext = Lprior = L,双向链表中的运算，基本上同单链表。这里，重点介绍插入和删除运算：,插入：,包括 前插 和 后插,前插：,在 *p 结点前插入新结点,后插：,在 *p 结点后插入新结点,76,后插：,a,i-1,p,a,i,a,i+1,插入方法同单链表。,x,s,x,插入过程：,a,i+1,a,i,p,a,i-1,77,(4) pprior = s,(3) ppriornext = s,(1) sprior = pprior,(2) snext = p,x,s,p,a,i-1,a,i,a,i+1,p-prior,前插：,78,删除：,删除结点*p,p,a,i,a,i+1,a,i-1,pprior next = pnext;,pnext prior = pprior;,free (p);,pprior,pnext,79,第3章 链表及其应用,3.1 链表的基本概念,3.2 单链表的数据结构,3.3 单链表的基本运算实现,3.4 循环链表,3.5 链表的应用,80,3.5 链表的应用,3.5.1 多项式相加问题,3.5.2 两个链表的归并问题,3.5.3 链表在字符处理方面的应用,链串,81, 一元多项式的表示,通常，一个n次一元多项式P(x)可按升幂的形式写成：,P(x) = a,0,+ a,1,x + a,2,x,2,+ + a,n,x,n,它实际上包含n+1项，由n+1个系数唯一确定。在计算机内，我们可以用一个链表来表示一个一元多项式。,为了节省存储空间，我们只存储多项式中系数非0 的项。链表中的每一个节点存放多项式的一个系数非0项，它包含三个域，分别存放该项的系数、指数以及指向下一多项式项节点的指针。,82,下图所示为该节点的结构,：,该节点的数据类型如下： ,typedef struct Pnode ,int coef；,int exp；,struct Pnode *next；, Polynode；,83,例如：,多项式P = 3 + 4x + 6x,3,+ 8x,7,+ 23x,21,的单链表表示形式如下图所示 ：,为方便以后的运算，我们也在该单链表中增加了头节点，并给定指数值为-1。,84,两个一元多项式相加,两个多项式相加的法则是：,两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多项式”中的一项；所有指数不同的项均直接移位至“和多项式”中。,85,【例】,两个一元多项式A (x)=2+ 5x+9x,8,+5x,17,，,B(x) = 10x + 22x,6,- 9x,8,，分别用单链表表示，试描述其相加的过程。,A,-1,0,2,8,9,1,5,17,5,p,B,-1,1,10,6,22,8,-9,q,指针p、q指向多项式链表A、B的首元素结点，,并令指针pre=A;,pre,86,A,-1,0,2,8,9,1,5,17,5,p,B,-1,1,10,6,22,8,-9,q,p,p-exp,exp，指针p、pre后移：,即：pre = p , p=p-next,此时p-exp,=,q-exp，则将*p和*q结点的系数相加：,p-coef = p-coef + q-coef,pre,pre,B,若约定相加的结果用单链表A表示，则free(B)，且B=q；,87,A,-1,0,2,8,9,1,17,5,B,1,10,6,22,8,-9,q,p,15,q,B,指针q后移，即：q=q-next，同时free(B)，且B=q；,pre,p-exp,exp，指针p、pre后移：,即：pre = p , p=p-next,p,pre,88,A,-1,0,2,8,9,1,17,5,6,22,8,-9,15,q,B,p-exp,q-exp，应将*q插入到*p结点前：,q=q-next；,B-next=p；,pre-next = B；,pre = B；,B=q；,p,pre,q,B,pre,89,8,9,17,5,6,22,8,-9,A,-1,0,2,1,15,B,p,pre,q,此时p-exp,=,q-exp，则将*p和*q结点的系数相加：,p-coef = p-coef + q-coef,90,8,0,17,5,6,22,8,-9,A,-1,0,2,1,15,B,p,pre,q,但相加后p-coef = 0；需要将结点*p从链表A中删除：,pre-next = p-next ；,free(p)；,p = pre-next ；,指针q后移，即：q=q-next，,同时free(B)，且B=q；,q,B,p,此时q =,NULL,，算法结束。,91,综合以上分析，两个一元多项式相加的算法如下：,Polynode *polyadd(Polynode *A，Polynode *B),/两个多项式相加，将和多项式存放在多项式A中，并将多项式B删除,Polynode *p，*q，*temp，*pre；,int sum；,p = A-next ；,q = B-next / p和q分别指向A和B多项式链表中的第一个节点,pre = A ； /pre指向*p的前趋节点,free (B)；/释放多项式B的头节点空间 ,92,while (p! =NULL & q !=NULL) ,/ 当两个多项式均未扫描结束时,if(p-expexp),pre = p；p = p-next；,/ 如果p指向的多项式项的指数小于q的指数，指针p后移,else,if ( p-exp = = q-exp)/ 若指数相等，则相应的系数相加 sum = p-coef + q-coef ；,if (sum! =0),p-coef = sum；B = q；pre = p；,p = p-next；q = q-next；,free (B)；/释放原先的*q节点空间 ,93,else,temp = p；p = p-next；pre-next = p；free(temp)；,B = q；q = q-next；free (B)；,/若系数和为零，则删除节点*p与*q，并将指针指向下一个节点,else,/ 若p-exp q-exp，将*q节点插入到多项式A中*p节点前 B = q；q =q-next；B-next = p；pre-next = B；,pre=pre-next；,94,if ( q! = NULL) pre-next = q；,/ 若多项式B中还有剩余，则将剩余的节点加入到和多项式A中 ,return (A)；,若多项式A有n项，多项式B有m项，则上述算法的时间复杂度为,95,3.5 链表的应用,3.5.1 多项式相加问题,3.5.2 两个链表的归并问题,3.5.3 链表在字符处理方面的应用,链串,96,两个链表的归并,若将多项式链表A、B中的每个节点的系数域去掉，并修改上节中的一元多项式相加算法，则可形成两个链表的归并操作算法,。,97,【例】有两个有序表A = (0, 1, 8, 17)，B = (1, 6, 8)，将它们归并为一个有序表。,0,p-datadata，令指针p后移；,1,17,8,1,8,6,B,A,p,q,p,p-dataq-data，应将*q节点插入到链表A中的*p节点之前,q,p,q,q,p-datadata，令指针p后移,p-dataq-data，应将*q节点插入到链表A中的*p节点之前,p-data=q-data，应将*q节点插入到链表A中的*p节点之前,q = NULL，则链表A即归并后的链表,98,算法分析：,算法主要包括：搜索、比较、插入三个操作：,搜索：需要,两个指针,搜索两个链表；,比较：比较结点数据域中数据的大小；,插入：将两个结点中数据,小的结点插入新链表,。,99,两个有序链表归并的算法可以描述为：,LinkList *Lmerge(LinkList *A，LinkList *B),LinkList *p，*q，*pre；,p = A-next；,q=B-next；/ p和q分别指向链表A和B中的第一个节点,pre=A；/pre指向*p的前趋节点,free (B)；/释放链表B的头节点空间,while (p!=NULL & q!=NULL)/当两个链表均未扫描结束时,if(p-datadata) pre=p；p=p-next；,/如果*p节点的data值小于*q的data值，指针p后移,100,else /否则，将*q节点插入到链表A中*p节点前,B=q；q=q-next；,B-next=p；pre-next=B；pre=pre-next；,if(q!=NULL) pre-next=q；,/若链表B中还有剩余，则将剩余的节点插入到链表A的表尾,return (A)；,101,3.5 链表的应用,3.5.1 多项式相加问题,3.5.2 两个链表的归并问题,3.5.3 链表在字符处理方面的应用,链串,102,链串是满足下列条件的一种数据结构：, 由0个或多个字符组成的有限序列；一般记为：S=“a,1,.a,i,.a,n,”，i=1，2，n。, 字符之间的关系R = | a,i,，a,i1,S。, 相邻字符a,i,、 a,i1,在存储器中不一定占用相邻的物理存储单元。,其中a,i,(1in)是单个字符，可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度。,链串的概念,：,103,在许多系统中，当一个字符占用一个字节空间的情况时，而链表节点中指针域要占用多个字节存储空间。这样，普通链串(如图所示的每个节点只有一个字符的链串)空间利用率非常低。其节点类型可描述为：,typedef struct node,char data； struct node *next；,LinkString,；,链串的存储结构,：,104,为了提高存储密度，可以让每个节点存放多个字符，也称这种存储结构为块链结构，相应的链串称为块链串，而块链串中每个节点最多能存放的字符的个数称为节点的大小。下图所示的是节点大小为4的块链串。,105,块链结构中，结点类型描述为：,#define Block_Size 4,typedef struct node,char chBlock_Size；,struct node *next；,Node；,106,ST,curlen,tail,head,typedef,struct,cnode *head , *tail ;,int curlen ;,link_string;,link_string *ST ;,为便于操作，我们为块链串增加一个尾指针。,块链的结构描述为：,107,以下是第2、3章的补充（综合）知识。,108,线性表的概念,线性表(Linear List)是由n (n0)个类型相同的数据元素a,1, a,2, ， a,n,组成的有限序列，有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。,记作（a,1, a,2, ，a,i-1,，a,i,，a,i+1,， ，a,n,）,109,（,a,1, a,2, ,a,i-1,，,a,i,a,i1,，,a,n,）,n=0时称为,数据元素,线性起点,a,i,的直接前趋,a,i,的直接后继,下标，,是元素的序号，表示元素在表中的位置,n,为元素总个数，即表长,空表,线性终点,110,可以看出：,（1）线性表是具有线性逻辑结构的数据；,（2）可以定义在线性表上的运算有：置空表、求表长、查找、插入和删除等。,这些运算的实现必须要在为线性表找到一个合适的存储方法之后。,在计算机中存储一个线性表可以,顺序存储,（,顺序表,），也可以,链接存储,（,链表,）。,111,串的堆分配存储,以一组地址连续的存储单元存储串，但这些,存储空间是,在程序的执行过程中动态分配而得（,由malloc ( ) 函数申请而得,）。,C语言中称由malloc ( ) 函数和free( )函数管理的自由存储区为 “堆” ，则,称串的这种存储方式为 堆分配存储。,使用堆分配存储，对每个串可由该串的,首地址,和,串长,唯一指定。,112,描述为：,typedef,struct, char *ch ;,int length ;,hstring ;,hstring *H ;,堆分配存储结构的串，既有顺序结构存储处理方便的特点，操作中又对串长没有限制更显灵活。,ch,length,串,H,113,对于该图:,串的首地址,为：,(*H).ch,或：,Hch,串的首字符,为变量,*(Hch),的值,串长,为：,(*H).length,或：,Hlength,ch,length,串,H,114,例：,生成一个串，并输出它的第一、第二个字符。,#include “alloc.h”,#include “stdio.h”,main( ), hstring *H ;,H = malloc ( sizeof(hstring) ) ;,scanf ( “%s” , Hch) ;,putchar( *(Hch) ) ;,(Hch) + + ;,putchar ( * (Hch) ) ; ,115,习题：,1,、在单链表中，除了首元结点外，任一结点的存储位置由,指示。,2,、 在n个结点的单链表中要删除已知结点*p，需找到它的,，其时间复杂度为,。,3,、,试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？,4,、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？,116,5、设链表A、B分别表示一个集合，设计算法以判断集合A是否是B的子集,6,、若单链表没有头节点，如何实现其插入和删除算法？,7、编写程序，在单循环链表上实现线性表的6种运算。,8、设计算法复制链表A中的内容到B表中。,9、写出求两个递增有序链表表示的集合的交集的算法。,10、设计算法，实现在递增有序的链表中插入元素x后，仍保持链表递增有序。,117,The end,118,