清华大学-链表的用法-(全)PPT课件

2020/4/30,-,1,第9章链表,2020/4/30,-,2,讲授内容,自引用结构、链表的概念内存的动态分配和释放单向链表的定义与操作双向链表的定义与操作,2020/4/30,-,3,9.1链表的基本概念,结构数组-必须将数组的大小设定成足够大的值太浪费能否需要多少分配多少？链表=动态内存分配+结构+指针所有结构形成一条链可以在任何地方插入或删除元素,2020/4/30,-,4,9.2单向链表,自引用结构结构中包含指向同类型结构的指针通过指针连接成链表，终点是NULL指针(0),2020/4/30,-,5,9.2.1单向链表定义,例子：structnodeintdata;node*next;next：指向下一个node类型的结构，连接node的纽带,2020/4/30,-,6,9.2.1单向链表定义,存放学生信息的链表节点structstudentintnum;charname20;charsex;floatscore;student*next;动态申请内存的方法student*p=(student*)malloc(sizeof(student);或student*p=newstudent;,2020/4/30,-,7,9.2.2单向链表的操作,建立单向链表声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)动态分配一个新节点，将该节点链入链尾重复上一步,2020/4/30,-,8,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,#includestructnodeintdata;node*next;node*createList(intn);intmain()intn;node*listHead=NULL;coutn;if(n0)listHead=createList(n);return0;,2020/4/30,-,9,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,node*createList(intn)node*temp,*tail=NULL,*head=NULL;intnum;cinnum;head=newnode;/为新节点动态分配内存if(head=NULL)coutdata=num;head-next=NULL;tail=head;,2020/4/30,-,10,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,for(inti=0;inum;temp=newnode;/为新节点动态分配内存if(temp=NULL)coutdata=num;temp-next=NULL;tail-next=temp;tail=temp;returnhead;,2020/4/30,-,11,建立链表过程,2020/4/30,-,12,建立链表过程,2020/4/30,-,13,9.2.2单向链表的操作,遍历链表依次访问链表中的每个节点的信息head-data=15;head-next-data=15;一般遍历方法node*curNode=head;while(curNode)curNode=curNode-next;,2020/4/30,-,14,例子2：编写一个函数，输出例1链表中各节点的data成员的值,voidoutputList(node*head)coutdata;if(curNode-next)cout;curNode=curNode-next;coutdata=n)coutnext;coutCantfindninthelist.next；(3)把c的地址赋给节点a的后继指针aptr-next=cptr;,2020/4/30,-,17,例子4：编写一个函数，将输入的整数从小到大插入链表,node*insertData(intn,node*head)node*curNode=head;/指向插入点的后节点node*preNode=NULL;/指向插入点的前节点node*newNode=NULL;/指向新建节点while(curNode!=NULL),2020/4/30,-,18,例子4：编写一个函数，将输入的整数从小到大插入链表,newNode-data=n;if(preNode=NULL)/插入到链表头newNode-next=curNode;returnnewNode;elsepreNode-next=newNode;newNode-next=curNode;returnhead;,2020/4/30,-,19,9.2.2单向链表的操作,从链表中删除一个节点c(1)在链表中查找要删除的节点c，用指针cptr指向节点c;(2)如果c有前驱节点(设为d,用指针dptr指向d)，则将d的后继指针指向c的后继节点：dptr-next=cptr-next(3)释放c占用的空间,2020/4/30,-,20,例子5：编写一个函数，删除链表中包含指定整数的节点,node*deleteData(intn,node*head)node*curNode=head;/指向当前节点node*preNode=NULL;/指向当前节点的前驱节点while(curNode/返回链首指针,2020/4/30,-,21,9.3双向链表,单向链表：有利于从链首向链尾遍历有些时候双向遍历是需要的双向链表,2020/4/30,-,22,9.3.1双向链表的定义,定义双向链表的节点：structnodeintdata;node*next;/指向后续节点node*pre;/指向前面的节点;,2020/4/30,-,23,9.3.1双向链表的定义,双向链表的例子：双向链表一般也由头指针唯一确定双向链表首尾相接可以构成双向循环链表,2020/4/30,-,24,9.3.2双向链表的操作,建立双向链表新节点链入链尾原链尾节点的后继指针指向新节点新节点的前驱指针指向原链尾节点新链尾节点的后继指针置为空指针将新节点链入链头原链头节点的前驱指针指向新节点新节点的后继指针指向原链头节点新链头节点的前驱指针置为空指针,2020/4/30,-,25,例子6：编写一个函数，按数据输入的顺序建立双向链表,node*createBidirList(intn)node*temp,*tail=NULL,*head=NULL;intnum;cinnum;head=newnode;/为新节点动态分配内存if(head=NULL)coutdata=num;head-next=NULL;head-pre=NULL;tail=head;,2020/4/30,-,26,例子6：编写一个函数，按数据输入的顺序建立双向链表,for(inti=0;inum;temp=newnode;/为新节点动态分配内存if(temp=NULL)coutdata=num;temp-next=NULL;temp-pre=tail;tail-next=temp;tail=temp;returnhead;,2020/4/30,-,27,9.3.2双向链表的操作,双向链表的遍历有链首节点，则可以沿着后继指针从头至尾遍历有链尾节点，则可以沿着前驱指针从尾向头遍历,2020/4/30,-,28,例子7：编写一个函数，输出双向链表中各节点的data成员的值,voidoutputBidirList(node*head)coutpre)coutdata;if(curNode-next)cout;curNode=curNode-next;coutnext=curNode;newNode-pre=NULL;if(curNode!=NULL)curNode-pre=newNode;returnnewNode;if(curNode=NULL)/链尾newNode-pre=preNode;preNode-next=newNode;newNode-next=NULL;returnhead;,2020/4/30,-,32,例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大),else/链中preNode-next=newNode;newNode-next=curNode;newNode-pre=preNode;curNode-pre=newNode;returnhead;,2020/4/30,-,33,例子9：编写函数，在双向链表中查找并删除指定,node*deleteData(intn,node*head)node*curNode=head;/指向当前节点while(curNode,2020/4/30,-,34,例子9：编写函数，在双向链表中查找并删除指定,if(curNode-pre=NULL)head=head-next