第2章线性表(链表)课件

第第2 2章章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加1线性链表线性链表 将将线线性性表表的的元元素素放放到到一一个个具具有有头头指指针针的的链链表表中，链表中每个结点包含数据域和指针域。中，链表中每个结点包含数据域和指针域。数数据据域域存存放放数数据据，指指针针域域存存放放后后继继结结点点的的地地址址，最最后后一一个个结结点点的的指指针针域域为为空空。逻逻辑辑上上相相邻邻的的数据元素在内存中的物理存储空间不一定相邻。数据元素在内存中的物理存储空间不一定相邻。2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2 上图的线性表为上图的线性表为:ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现3线性链表表示法线性链表表示法:4链表的种类链表的种类单链表单链表循环链表循环链表双向链表双向链表线性链表的基本操作线性链表的基本操作建立链表建立链表求链表长度求链表长度查找链表中指定的结点查找链表中指定的结点插入结点插入结点删除结点删除结点逆转逆转2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现5单链表单链表1 1）每个元素包含两个域：）每个元素包含两个域：数据域数据域(datadata)和指针域和指针域(nextnext)，数据域用来存放元素的值，指针域用来存放后继元素的数据域用来存放元素的值，指针域用来存放后继元素的存储地址。存储地址。2 2）指示链表中第一个结点的指针称为）指示链表中第一个结点的指针称为头指针（头指针（headhead），最最后一个结点没有后继结点，后一个结点没有后继结点，它的指针域为空它的指针域为空(记为记为NULLNULL或或)。如下图：。如下图：2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现63 3）表示方法）表示方法 c c语言定义一种节点类型：语言定义一种节点类型：typedef struct Node datatype data;struct Node*next;LNode,*Linklist;同时定义了两种数据类型：同时定义了两种数据类型：LNode是结点类型，是结点类型，LinkList是指向是指向LNode类型类型结点的指针类型。结点的指针类型。若有若有 LNode L;或者或者struct Node L L为结点类型的变量为结点类型的变量 L.data=x;L.next=NULL;若有若有 LNode*L;L为存储某个结点的地址的指针变量，为存储某个结点的地址的指针变量，(或者或者Linklist L 或者或者struct Node*L）L=(Lnode*)malloc(sizeof(LNode);或者或者 L=(Linklist)malloc(sizeof(LNode);或者或者 L=(struct Node*)malloc(sizeof(struct Node);L-data=x;L-next=NULL;2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现73 3）表示方法）表示方法为了增强程序的可读性，通常将指向为了增强程序的可读性，通常将指向链表的指针链表的指针用用LinkList定定义义:例如：例如：LinkList L;L要么为要么为NULL，表示一个空表；表示一个空表；要么为第一个结点的地址。要么为第一个结点的地址。指向其它节点的指针用指向其它节点的指针用LNode 定义：定义：例如：例如：LNode *p；typedef struct Node datatype data;struct Node*next;LNode,*Linklist;2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现8指针与结点的常见运算指针与结点的常见运算1 1）指针赋值：指针赋值：s=ps=p；q=p-nextq=p-next；ppppsq2 2）指针移动：指针移动：p=p-nextp=p-next；2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现9指针与结点的常见操作指针与结点的常见操作psheadpsheadqpsps3）后插：后插：s-next=p-next；p-next=s；4）前插：前插：q=head；while(q-next!=p)q=q-next;q-next=s；s-next=p；2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现10单链表的基本操作单链表的基本操作 建立单链表建立单链表链表中的每个结点是运行时系统根据需要而生链表中的每个结点是运行时系统根据需要而生成的，建立单链表要从空表开始，每读入一个数据成的，建立单链表要从空表开始，每读入一个数据元素则申请一个结点，然后插入链表中。元素则申请一个结点，然后插入链表中。向链表中插入一个结点的方式有两种：向链表中插入一个结点的方式有两种：(1)(1)头插法：头插法：每次新加入的结点都插在链的头部。每次新加入的结点都插在链的头部。(2)(2)尾插法：尾插法：每次新加入的结点都插在链的尾部。每次新加入的结点都插在链的尾部。2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现11H 建立单链表建立单链表(1)头插法：头插法：LinkList Hcreatlist()Lnode *P,*H=NULL;/P新建节点；新建节点；H：头指针。头指针。int x;scanf(“%d”,&x);while(x!=Flag)P=(Lnode*)malloc(sizeof(Lnode);P-data=x;p-next=H;H=P;scanf(“%d”,&x);return H;a1Pnulla2PHH特点：特点：建立简单，但链表中的顺序与读入的顺序相反。建立简单，但链表中的顺序与读入的顺序相反。12(2)尾插法：尾插法：每次新加入的结点都插在链的尾部。每次新加入的结点都插在链的尾部。方法方法1：Lnode*H=NULL,*T,*P;/P为新加入节点，为新加入节点，T为尾节点为尾节点P-next=NULL;P-data=a;第一个结点：第一个结点：H=P 其它结点：其它结点：T-next=PT=P;aiHTTP解决办法（方法解决办法（方法2）：）：加入一个头结点，加入一个头结点，只是它的数据域中只是它的数据域中不存放线性表的元素，它的指针域指向线性表的第一个元不存放线性表的元素，它的指针域指向线性表的第一个元素。当表空时只有一个头结点，它的指针域为空素。当表空时只有一个头结点，它的指针域为空,如下图：如下图：headhead（空表）（空表）If(H=NULL)H=P;else T-next=Pa113(2)尾插法：尾插法：带头结点算法带头结点算法LinkList TCreatList2()Lnode*H,*T,*P;int x;H=(Lnode*)malloc(sizeof(Lnode);H-next=NULL;T=H;scanf(%d,&x);while(x!=0)P=(Lnode*)malloc(sizeof(Lnode);P-data=x;P-next=NULL;T-next=P;T=P;scanf(%d,&x);return H;a2HTTPTPa114 顺序输出链表顺序输出链表1 1）算法）算法1 1。void PrintList1(LinkList H)Lnode*p=H;while(p!=NULL)printf(%d,p-data);p=p-next;2 2）算法算法2 2（带头结点）带头结点）void PrintList2(LinkList H)Lnode*p=H-next;while(p!=NULL)printf(%d,p-data);p=p-next;2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现15求链表的长度求链表的长度1 1）问题描述：问题描述：根据头指针统计出链表中的节点个数。根据头指针统计出链表中的节点个数。int LengthList(LinkList H)Lnode*p=H;int i=0;while(p-next!=NULL)i+;p=p-next;return i;2 2）算法描述算法描述2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现16查找链表中指定的结点查找链表中指定的结点Lnode*SearchX(LinkList H,Datatype x)Lnode*p=H-next;while(p!=NULL&p-data!=x)p=p-next;return p;2 2）算法描述算法描述 (按内容查找、带头结点按内容查找、带头结点)1 1）查找过程查找过程：根据头指针找到第一个结点检查是否是指定：根据头指针找到第一个结点检查是否是指定结点，若不是根据其结点，若不是根据其nextnext域检查下一结点，以此类推。域检查下一结点，以此类推。2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现17单线性链表的基本操作单线性链表的基本操作 插入运算插入运算 （前插（前插/后插）后插）1 1）问题描述：问题描述：在头节点为在头节点为headhead的链表中，在值为的链表中，在值为a a的结点前的结点前面插入一个值面插入一个值为为x x的结点。若表中无的结点。若表中无a a元素，则将元素，则将x x插入链表末插入链表末尾。尾。x xsq-next=s;q-next=s;s-next=q-next;s-next=q-next;aHeadHead q2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现18插入运算插入运算void InsertList(LNode *H,int a,int x)LNode*s,*q=H;s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=NULL;while(q-next!=NULL&q-next-data!=a)/找到找到a前驱前驱 q=q-next;s-next=q-next;/插入插入 q-next=s;2 2）算法描述算法描述2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现19 删除运算删除运算1 1）问题描述：问题描述：在头指针为在头指针为headhead的链表中，的链表中，将值为将值为a a的结点删除。的结点删除。pp=q-next;p=q-next;q-next=p-next;q-next=p-next;free(p);free(p);qheadhead a必须找到必须找到a a的的前驱结点前驱结点2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现20int DeleteList(LNode*head,int a)LNode*p,*q=head;while(q-next!=NULL&q-next-data!=a)q=q-next;if(q-next!=NULL);/找到，删除找到，删除 p=q-next;q-next=p-next;free(p);return 1;/返回成功返回成功 else return 0;/返回失败返回失败2 2）算法描述算法描述运行一下运行一下2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现21注意注意（1 1）单链表的前插法和删除一个结点时，必须单链表的前插法和删除一个结点时，必须记住其前驱结点。记住其前驱结点。（2 2）单链表是随机存储，顺序访问方式，若访）单链表是随机存储，顺序访问方式，若访问尾结点时，需遍历整个链表才能找到。问尾结点时，需遍历整个链表才能找到。思考：思考：若只知道中间某个结若只知道中间某个结点，如何修改单链表结构，点，如何修改单链表结构，才能访问到所有的节点？才能访问到所有的节点？2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现22 循环链表循环链表特点：特点：表中最后一个结点的指针域不为空，而是指向表头，表中最后一个结点的指针域不为空，而是指向表头，整个链表形成一个环。与一般链表不同之处在于只要给定整个链表形成一个环。与一般链表不同之处在于只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始。如下图：而不必从头指针开始。如下图：anH.a1a2a3思考：思考：如何判断如何判断已到了尾结点？已到了尾结点？H2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现23 循环链表循环链表判断尾结点的方式有三种：判断尾结点的方式有三种：(1)(1)if(P-next=H)if(P-next=H)(2)(2)令头结点令头结点H H的域赋一个标志值的域赋一个标志值flagflag if(p-next-data=flag)if(p-next-data=flag)(3)(3)增加一个指针增加一个指针Tail,Tail,令令TailTail指向链表的尾结点。指向链表的尾结点。If(p=Tail)If(p=Tail)在建立链表时，每插入一个新的结点（后插法）在建立链表时，每插入一个新的结点（后插法）S,S,都都要令要令 Tail=S;S-next=H;Tail=S;S-next=H;循环链表的插入、删除操作与单链表类似循环链表的插入、删除操作与单链表类似anH.a1a2a3思考：思考：循环链表与循环链表与单链表类似同样找单链表类似同样找前驱结点不便。再前驱结点不便。再如何改进？如何改进？2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现24 双向循环链表双向循环链表(简称双链表简称双链表)特点：特点：表中每个结点有两个指针域：一个指向直接后继，表中每个结点有两个指针域：一个指向直接后继，一个指向直接前驱，那么从表中任一结点都可以一个指向直接前驱，那么从表中任一结点都可以随意向前或向后查找。如下图：随意向前或向后查找。如下图：headdatanextbefore一个结点一个结点datanextbefore空表空表H对指向双向对指向双向链表链表任任一结点的指针一结点的指针d，有下面的关系：有下面的关系：d-next-before=d-before-next=d25 问题描述问题描述一个一元多项式可以表示为：一个一元多项式可以表示为：其中每一项由系数其中每一项由系数P Pi i及及x x的指数的指数i i组成。若多项组成。若多项式按升幂排列，则它由式按升幂排列，则它由n+1n+1个系数唯一确定，因个系数唯一确定，因此可以用一个线性表此可以用一个线性表P P表示：表示：其指数其指数i i隐藏在系数隐藏在系数P Pi i的序号内。的序号内。有问题：可能次数很高但又存在大量零系数的项有问题：可能次数很高但又存在大量零系数的项2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加261 1）链式存储结构）链式存储结构：每一个非零项构成链表中的一个结点每一个非零项构成链表中的一个结点,结结点由两个数据域和一个指针域构成点由两个数据域和一个指针域构成,如图：如图：a e nextpi系数系数指数指数2 2）链表结构链表结构：采用带头结点的线采用带头结点的线性链表表示多项式性链表表示多项式A(x)A(x)、B(x)B(x)，A(x)=4xA(x)=4x8080+7x+7x6060+9x+9x5 5+5+5 B(x)=2xB(x)=2x8080-7x-7x6060+3x+3x1212 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加27 问题分析问题分析4 4）运算过程：运算过程：指针指针a a、b b的初始位置分别指向的初始位置分别指向A(x)A(x)、B(x)B(x)中的中的第一项第一项;C(x)C(x)是新的是新的A(x)A(x)；过程为：过程为：比较比较a a、b b所指结点中的指数项。所指结点中的指数项。若：若：a-e a-e b-e b-e，那么那么a a所指的结点为所指的结点为C(x)C(x)中的一项，令中的一项，令p p指指针后移一个结点；针后移一个结点；若：若：a-e a-e e b-e，则则b b所指的结点为所指的结点为C(x)C(x)中的一项，将中的一项，将b b结点结点插入插入a a结点之前，并令结点之前，并令b b指针后移一个结点；指针后移一个结点；若：若：a-e a-e=b-eb-e，则将两个结点中的系数相加，当和不为则将两个结点中的系数相加，当和不为零时，修改零时，修改a a结点中的系数，释放结点中的系数，释放b b结点；否则，删去结点；否则，删去a a结点，结点，同时释放同时释放a a、b b结点。结点。将将B(x)B(x)加到加到A(x)A(x)中，在加的过程中释放已经运算完毕的不中，在加的过程中释放已经运算完毕的不再需要的结点。假设再需要的结点。假设B(x)B(x)和和A(x)A(x)都是已经按照指数排序。都是已经按照指数排序。A(x)=4xA(x)=4x8080+7x+7x6060+9x+9x5 5+5+5 B(x)=2xB(x)=2x8080-7x-7x6060+3x+3x1212 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加285、链式存储结构特点、链式存储结构特点(1)(1)插插入入、删删除除灵灵活活方方便便，不不需需要要移移动动结结点点，只只要要改变结点中指针域的值即可。改变结点中指针域的值即可。(2)(2)适适合合于于线线性性表表是是动动态态变变化化的的,不不进进行行频频繁繁查查找找操操 作作、但但 经经 常常 进进 行行 插插 入入 删删 除除 时时 使使 用用。(3)(3)链表的查找只能从头指针开始顺序查找。链表的查找只能从头指针开始顺序查找。(4)(4)指针占用额外存储空间指针占用额外存储空间2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加29四、顺序表和链表的比较四、顺序表和链表的比较 线性表的长度是否固定线性表的长度是否固定顺序表的存储空间是静态分配的，执行期间上下界顺序表的存储空间是静态分配的，执行期间上下界固定，适用于表长固定的场合；固定，适用于表长固定的场合；链表的存储空间是在执行过程中动态分配的，适用链表的存储空间是在执行过程中动态分配的，适用于表长不固定的场合。于表长不固定的场合。线性表的主要操作是什么线性表的主要操作是什么 顺序表是连续存放的，适用于频繁查找操作的表。顺序表是连续存放的，适用于频繁查找操作的表。链表适用于经常进行插入和删除的表。链表适用于经常进行插入和删除的表。采用的算法语言：采用的算法语言：链表要求指针类型变量。链表要求指针类型变量。2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加30LS28375PR(1)L=P-next;练习练习:对单链表分别执行下列各程序段对单链表分别执行下列各程序段,画出结果示意图画出结果示意图.(2)R-data=P-data;(3)R-data=P-next-data;(4)P-next-next-next-data=P-data;(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-next;2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加31LS28375PR练习练习:对单链表分别执行下列各程序段对单链表分别执行下列各程序段,画出结果示意图画出结果示意图.(6)T=P;while(T-next!=NULL)T-data=(T-data)*2;T=T-next;(7)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加32LS28375PR练习练习:对单链表分别执行下列各程序段对单链表分别执行下列各程序段,画出结果示意图画出结果示意图.(8)T=L;T-next=P-next;free(P);(9)S-next=L;2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加33LS28375PR(1)L=P-next;28375PRSLL答案答案2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加34LS28375PR(2)R-data=P-data;28575PRS2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加35(3)R-data=P-next-data;28775PRSLS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加36(4)P-next-next-next-data=P-data;25375PRSLS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加37(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-next;LS2PR1014616LS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加38(6)T=P;while(T-next!=NULL)T-data=(T-data)*2;T=T-next;LS2PR101468LS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加39(7)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;LS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加40(7)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;PLS28375PRLS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加41(7)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;P10LS28375PRLS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加42(7)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;LS28375RP10LS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加43(7)P=(LNode*)malloc(sizeof(LNode);P-data=10;R-next=P;P-next=S;LS28375RP10LS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加44(8)T=L;T-next=P-next;free(P);LS2837PRT5LS28375PR2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加45p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后谢谢你的到来学习并没有结束，希望大家继续努力Learning Is Not Over.I Hope You Will Continue To Work Hard演讲人：XXXXXX 时 间：XX年XX月XX日