《数据结构》课件第3章(链表).ppt

1、第三章第三章 链链 表表 线性链表线性链表 链栈、链队链栈、链队 循环链表循环链表 多重链表多重链表 线性链表线性链表 a1Heada2a3 a4a5a6a7a8地址地址 数据数据 指针指针6462149594327901137991a24212743495990a1a3a7 a6a4a5a86499027594321Head线性表的链式存储结构：线性表的链式存储结构：用一组用一组地址任意地址任意的存储单元存放线性表中的数据元素的存储单元存放线性表中的数据元素结点结点(表示数据元素表示数据元素)=元素元素(数据元素的映象数据元素的映象)+指针指针(指示后继元素存储位置指示后继元素存储位置)链表

2、：链表：以以“结点的序列结点的序列”表示的线性表表示的线性表。ABCD E F G H头结点头结点数据数据域域 指针域指针域链表结点链表结点头指针：头指针：指向链表中第一个结点的指针。指向链表中第一个结点的指针。首元结点首元结点表结点表结点头指针头指针Head1)1)其头指针是指向头结点的非空指针，无论链表是否为其头指针是指向头结点的非空指针，无论链表是否为 空，头指针始终保持值不变，因此头指针的处理方法空，头指针始终保持值不变，因此头指针的处理方法 对空表和非空表的操作是一致的，这与不带头结点的对空表和非空表的操作是一致的，这与不带头结点的 单链表为空时头指针为空不同。单链表为空时头指针为空

3、不同。2)2)首元结点的地址存放在头结点的指针域中，对该结点首元结点的地址存放在头结点的指针域中，对该结点 的操作与其它结点的操作一致，无需进行特殊处理的操作与其它结点的操作一致，无需进行特殊处理(如如 删除首元结点时，对不带头结点的单链表要修改头指删除首元结点时，对不带头结点的单链表要修改头指 针针)。单链表上基本运算的实现单链表上基本运算的实现1)Init_Link(&Head):初始化一个单链表初始化一个单链表void Init_Link(Pointer&Head);Head=new Node;Head-next=null;单链表的类型定义如下：单链表的类型定义如下：typedef st

4、ruct Node ElemType data;struct Node*next;*Pointer;2)Length_Link(Head):返回单链表中所含表结点的个数。返回单链表中所含表结点的个数。int Length_Link(Pointer Head)p=Head;j=0;while(p-Next!=null)p=p-next;j=j+1;return(j);3)Find_Link(Head):返回指向线性表第返回指向线性表第i个结点的指针。个结点的指针。Pointer Find_Link(Pointer Head,int i)p=Head;j=0;while(p-next!=null)

5、&(jnext;j=j+1;if(i=j)return(p);else return(null);4)Locate_Link(Head,x):在单链表中查找值等于在单链表中查找值等于x的结点，的结点，返回指向该结点的指针。返回指向该结点的指针。Pointer Locate_Link(Pointer Head,ElemType x)p=Head-next;while(p!=null)&(p-data!=x)p=p-next;return(p);ABCD x=CHeadp5)Insert_Link(Head,x,i):在单链表的第在单链表的第i个结点之前插入值个结点之前插入值 等于等于x的结点。的

6、结点。void Insert_Link(Pointer&Head,ElemType x,int i)p=Find_Link(Head,i-1);if(p=null)Error(“Without”)else s=new Node;s-data=x;s-next=p-next;p-next=s;ABCD x=F i=3HeadpF S6)Delete_Link(Head,i):删除单链表的第删除单链表的第i个结点。个结点。void Delete_Link(Pointer&Head,int i)p=Find_Link(Head,i-1);if(p!=null)&(p-next!=null)q=p-n

7、ext;p-next=q-next;delete q;else Error(“Without”);ABCD i=3Headp7)Create_Link(Head):建立一个单链表。建立一个单链表。void Create_Link_1(Pointer&Head)Init_Link(Head);scanf(“%c”,&x);i=1;while(x!=*)Insert_Link(head,x,i);i=i+1;scanf(“%c”,&x);void Create_Link_2(Pointer&Head)/顺序顺序 Init_Link(Head);p=Head;scanf(“%c”,&x);while

8、(x!=*)q=new Node;q-data=x;p-next=q;p=q;scanf(“%c”,&x);p-next=null;void Create_Link_3(Pointer&Head)/逆序逆序 p=null;scanf(“%c”,&x);while(x!=*)q=new Node;q-data=x;q-next=p;p=q;scanf(“%c”,&x);Head=new Node;Head-next=p;线性表的链式存储结构的优缺点：线性表的链式存储结构的优缺点：优点：优点：1)1)存储空间动态分配，可以按需要使用；存储空间动态分配，可以按需要使用；2)2)插入插入/删除结点操作

9、时，只需要修改指针，删除结点操作时，只需要修改指针，不必移动数据元素。不必移动数据元素。缺点：缺点：1)1)每个结点需加一指针域，存储密度降低；每个结点需加一指针域，存储密度降低；2)2)非随机存储结构，查找定位操作需要从非随机存储结构，查找定位操作需要从 头指针出发顺着链表扫描。头指针出发顺着链表扫描。单链表的应用示例：单链表的应用示例：例例1.1.将一个单链表逆置将一个单链表逆置void Invert_Link_1(Pointer&Head)/不带头结点不带头结点 p=Head;Head=null;while(p!=null)s=p;p=p-next;s-next=Head;Head=s;

10、Procedure Invert_Link_2(Pointer&Head)/带头结点带头结点 p=Head-next;h=null;while(p!=null)s=p;p=p-next;s-next=h;h=s;Head-next=h;例例2.2.设有带头结点的链表，每个结点有三个域：设有带头结点的链表，每个结点有三个域：datadata，Next,SortNext,Sort，其中，其中，datadata为整型值域，为整型值域，nextnext和和sortsort 均为指针，现所有结点已由均为指针，现所有结点已由nextnext域链接起来，构域链接起来，构 成单链表，试编写利用成单链表，试编写

11、利用sortsort域把所有结点按照值的域把所有结点按照值的 大小链接起来的算法。大小链接起来的算法。算法的思想：算法的思想：1)先构造以先构造以sort域为链表的空表；域为链表的空表；2)依次扫描以依次扫描以next域链接的单链表上的每个结域链接的单链表上的每个结 点，并根据其值将其插入到以点，并根据其值将其插入到以sort域链接的域链接的 链表的合适位置。链表的合适位置。数据类型定义如下：数据类型定义如下：typedef struct Snode int data;Snode*next,sort;*Slist;void LinkList_sort(Slist&Head)Head-sort=

12、null;q=Head-next;while(q!=null)pre=Head;p=pre-sort;while(p!=null)&(q-datap-data)pre=p;p=p-sort;q-sort=p;pre-sort=q;q=q-next;例例2 2：一元多项式的表示及相加。：一元多项式的表示及相加。一元多项式的表示：一元多项式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用线性表可用线性表P P表示为：表示为：200001000231)(xxxS 但是对于如下多项式：但是对于如下多项式：一般一般emmnxPxPxPxPee2121)(其中其中为非零系数）（iP

13、emee210用数据域含两个数据项的线性表表示：用数据域含两个数据项的线性表表示：emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表。其存储结构可以用顺序存储结构，也可以用单链表。则非常浪费存储空间。则非常浪费存储空间。17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 可以采用链式存储结构来表示线性表：可以采用链式存储结构来表示线性表：typedef struct node float coef;int e

14、xp;struct node*next;*polynom;设设p,qp,q分别指向分别指向A,BA,B中某一结点，中某一结点，p,qp,q初值是第一结点初值是第一结点比较比较p-exp与与q-expp-exp exp:p结点是和多项式中的一项结点是和多项式中的一项 p后移后移,q不动不动p-exp q-exp:q结点是和多项式中的一项结点是和多项式中的一项 将将q插在插在p之前之前,q后移后移,p不动不动p-exp=q-exp:系数相加系数相加0：从：从A表中删去表中删去p,释放释放p,q，p,q后移后移 0：修改：修改p系数域系数域,释放释放q，p,q后移后移直到直到p或或q为为NULL 若

15、若q=NULL，结束结束 若若p=NULL，将将B中剩余部分连到中剩余部分连到A上即可上即可运算规则运算规则算法描述如下：算法描述如下：void Polyadd(polynom&pa,polynom&pb,polynom&pc)/pa,pb和和pc分别表示多项式分别表示多项式A,B及它们的和及它们的和C的带表头的头指针的带表头的头指针 p=pa-next;q=pb-next;s=pa;pc=pa;/s指向指向p的直接前驱的直接前驱 while(p!=null)&(q!=null)switch(p-exp)case p-expexp:s=p;p=p-next;break;case p-exp=q

16、-exp:x=p-coef+q-coef;if(x!=0)p-coef=x;s=p;else s-next=p-next;delete p;p=s-next;u=q;q=q-next;delete u;break;case p-expq-exp:u=q-next;q-next=p;s-next=q;s=q;q=u;break;if(q!=null)s-next=q;delete pb;例：求多项式的微商问题例：求多项式的微商问题void Differential_coefficient(polynom&L);q=L;while (q-next!=null)q=q-next;if(q-exp0)

17、q-coef=q-coef*q-exp;q-exp=q-exp-1;else p=q;q-next=q-next-next;delete p;练习练习1 若已知非空线性链表第一个结点的指针为若已知非空线性链表第一个结点的指针为list，请请 写一个算法，写一个算法，将该链表中数据域值最小的那个将该链表中数据域值最小的那个 结点移到链表的最前端。结点移到链表的最前端。list356718658271521014list356718658271521014qpqs void Remove(Pointer&list)/q,s用以保存数据值最小的节点及其前趋节点所在的位置用以保存数据值最小的节点及其前

18、趋节点所在的位置 q=list;p=list-next;r=list;while (p!=null)if (p-data data)s=r;q=p;r=p p=p-next;/找到值最小的那个结点找到值最小的那个结点，地址由，地址由q记录记录 if (q!=list)/若值最小的结点不是链表最前面那个结点若值最小的结点不是链表最前面那个结点 s-next=q-next;q-next=list;list=q;链栈和链队链栈和链队栈的链式存储结构栈的链式存储结构 链栈就是用一个线性链表来实现一个栈结构链栈就是用一个线性链表来实现一个栈结构,同时同时设置一个指针变量设置一个指针变量(这里不妨仍用这里

19、不妨仍用 top表示表示)指出当前栈指出当前栈顶元素所在链结点的位置。当栈为空时，有顶元素所在链结点的位置。当栈为空时，有top=null。在一个初始为空的链接堆栈中依次插入数据元素在一个初始为空的链接堆栈中依次插入数据元素 A,B,C,D以后以后,栈的状态为栈的状态为DCBAtop栈顶元素栈顶元素itemptop.二二.插入插入(进栈进栈)算法算法void Push_link_stack(Pointer&top,ElemType item)p=new Node;/申请一个新结点申请一个新结点 p-data=item;/将将item送新结点数据域送新结点数据域 p-next=top;/将新结点

20、插在链表最前面将新结点插在链表最前面 top=p;/修改栈顶指针的指向修改栈顶指针的指向算法算法topitem.pitem三三.删除删除(退栈退栈)算法算法void Pop_link_stack(Pointer&top,ElemType&item)if (top=null)Error(“Stack is empty!”)；else p=top;/暂时保存栈顶结点的地址暂时保存栈顶结点的地址 item=top-data;/保存被删栈顶的数据信息保存被删栈顶的数据信息 top=top-next;/删去栈顶结点删去栈顶结点 delete p;/释放被删结点释放被删结点算法算法队列的链式存储结构队列的

21、链式存储结构一一.构造原理构造原理 队列的链式存储结构是用一个线性链表表示队列的链式存储结构是用一个线性链表表示一个队列，一个队列，指针指针 front 与与rear 分别指向分别指向实际队头实际队头元素所在位置的前一个位置和实际队尾元素所在的位元素所在位置的前一个位置和实际队尾元素所在的位置置。front rear空队空队 空队对应的链表为空链表，空队的标志是空队对应的链表为空链表，空队的标志是 front=rear 在一个初始为空的链接队列中依次插入数据元素在一个初始为空的链接队列中依次插入数据元素 A,B,C,D以后以后,队列的状态为队列的状态为ABCDfrontrear 1)队列初始化

22、队列初始化 void InitQueue(Pointer&front,Pointer&rear)/构造一个空队列构造一个空队列Q p=new Node;p-next=null;front=p;rear=p;二二.基本运算的实现基本运算的实现front rearfrontrear2）插入算法）插入算法pitemvoid Inqueue(Pointer&front,Pointer&rear,ElemType item)p=new node;/申请一个链结点申请一个链结点 p-data=item;p-next=null;rear-next=p;rear=p;frontrearvoid Delqueu

23、e(Pointer&front,Pointer&rear,ElemType&item)/删除队头元素删除队头元素,并将数据域信息保存在变元并将数据域信息保存在变元item中中 if (front=rear)Error(“Queue is empty!”);else q=front-next;front-next=q-next;item=q-data;if(q-next=null)rear=front;delete q;算算 法法3）删除算法）删除算法 循环链表循环链表 是指链表中最后那个链结点的指是指链表中最后那个链结点的指针域存放指向链表最前面那个结点的指针，整个针域存放指向链表最前面那个结

24、点的指针，整个链表形成一个环。链表形成一个环。循环链表循环链表list 线性链表线性链表list带头结点的循环链表带头结点的循环链表循环链表的特点循环链表的特点1.只要给出表中任何一个结点的位置，则由此出发就可以访只要给出表中任何一个结点的位置，则由此出发就可以访问表中其他所有结点。问表中其他所有结点。2.对循环链表，若在它的第一个结点之前设立一个特殊的称对循环链表，若在它的第一个结点之前设立一个特殊的称为表头的结点，它的数据域可以按需要设定。使这样的链为表头的结点，它的数据域可以按需要设定。使这样的链表中任何时候都至少有一个结点存在，这样就可以把对空表中任何时候都至少有一个结点存在，这样就可

25、以把对空表和非空表的处理统一起来。表和非空表的处理统一起来。3.当需要将整个链表中所有结点归还给可用空间栈时，用循当需要将整个链表中所有结点归还给可用空间栈时，用循环链表比用普通链表要方便的多。环链表比用普通链表要方便的多。HavavHavav单链表单链表循环链表循环链表 双向链表双向链表1.双向链表的构造双向链表的构造2.双向链表的插入与删除双向链表的插入与删除1.1.双向链表的构造双向链表的构造 所谓所谓双向链表双向链表是指链表的每一个结点中除了数据是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向

26、结点的直接后继结点。驱结点，另外一个指向结点的直接后继结点。链结点的实际构造可以形象地描述如下：链结点的实际构造可以形象地描述如下：llinkdata rlink其中，其中，data 为数据域为数据域 llink,rlink 分别为指向该结点的直接前驱结点分别为指向该结点的直接前驱结点 与直接后继结点的指针域与直接后继结点的指针域双向链表的几种形式双向链表的几种形式list不带头结点的双向链表不带头结点的双向链表list不带头结点的双向循环链表不带头结点的双向循环链表list带头结点的双向循环链表带头结点的双向循环链表2.双向链表的插入双向链表的插入 功能功能：在带有头结点的非空双向循环链表中

27、第一在带有头结点的非空双向循环链表中第一 个数据域的内容为个数据域的内容为x 的链结点右边插入一的链结点右边插入一 个数据信息为个数据信息为item 的新结点。的新结点。list1.找到满足条件的结点。找到满足条件的结点。2.若找到，申请一个新的链结点。若找到，申请一个新的链结点。3.将新结点插到满足条件的结点后面。将新结点插到满足条件的结点后面。需要做的工作需要做的工作itemp插入前插入前xq插入后插入后q-rlink=pq-rlink-llink=pp-llink=qp-rlink=q-rlink q=list-rlink;/q 初值时指向头结点的下一个结点初值时指向头结点的下一个结点

28、while (qlist)&(q-datax)q=q-rlink;/寻找满足条件的链结点寻找满足条件的链结点 /if (q=list)printf(“There is no this node!”);return;/没有找到满足条件的结点没有找到满足条件的结点void insert(Pointer&list,ElemType x,ElemType item)p=new Node;/申请一个新的结点申请一个新的结点 /p-data=item;q-rlink=p;p-llink=q;q-rlink-llink=p;p-rlink=q-rlink;算法算法xitemq 3.双向链表的删除双向链表的删

29、除1.找到满足条件的结点。找到满足条件的结点。2.若找到，删除并释放该结点。若找到，删除并释放该结点。list 功能功能：删除带有头结点的非空双向循环链表中第删除带有头结点的非空双向循环链表中第 一个数据域的内容为一个数据域的内容为x 的链结点。的链结点。需要做的工作需要做的工作删除前删除前删除后删除后q-llink-rlink=q-rlinkq-rlink-llink=q-llinkq q=list-rlink;/q初值时指向头结点的下一个结点初值时指向头结点的下一个结点 while (qlist)&(q-datax)q=q-rlink;/找满足条件的链结点找满足条件的链结点 if (q=list)then printf(“There is no this node”);return;/没有找到满足条件的结点没有找到满足条件的结点 void delete(Pointer&list,ElemType x)delete q;/释放被删除的结点的存储空间释放被删除的结点的存储空间 q-rlink-llink=q-llink;q-llink-rlink=q-rlink;算法算法xq