清华大学链表的用法全.ppt

2024/4/21 周日1第9章链表2024/4/21周日2讲授内容n自引用结构、链表的概念n内存的动态分配和释放n单向链表的定义与操作n双向链表的定义与操作2024/4/21周日39.1链表的基本概念n结构数组-必须将数组的大小设定成足够大的值n太浪费n能否需要多少分配多少？n链表=动态内存分配+结构+指针n所有结构形成一条链n可以在任何地方插入或删除元素2024/4/21周日49.2单向链表n自引用结构n结构中包含指向同类型结构的指针n通过指针连接成链表，终点是NULL指针(0)2024/4/21周日59.2.1单向链表定义n例子：structnodeintdata;node*next;nnext：指向下一个node类型的结构，连接node的纽带head2852296NULL2024/4/21周日69.2.1单向链表定义n存放学生信息的链表节点structstudentintnum;charname20;charsex;floatscore;student*next;n动态申请内存的方法student*p=(student*)malloc(sizeof(student);或student*p=newstudent;2024/4/21周日79.2.2单向链表的操作n建立单向链表n声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)n动态分配一个新节点，将该节点链入链尾n重复上一步2024/4/21周日8例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾#includestructnodeintdata;node*next;node*createList(intn);intmain()intn;node*listHead=NULL;coutn;if(n0)listHead=createList(n);return0;2024/4/21周日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;2024/4/21周日10例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾for(inti=0;inum;temp=newnode;/为新节点动态分配内存if(temp=NULL)coutdata=num;temp-next=NULL;tail-next=temp;tail=temp;returnhead;2024/4/21周日11建立链表过程tailtailtemptempheadheadNULLNULL初始状态初始状态NULLNULLNULLNULL读入读入1 1后后tailtailtemptempheadhead1 1NULLNULL2024/4/21周日12建立链表过程读入读入2 2后后tailtailtemptempheadhead1 12 2NULLNULL读入读入3 3后后tailtailtemptempheadhead1 13 3NULLNULL2 22024/4/21周日139.2.2单向链表的操作n遍历链表n依次访问链表中的每个节点的信息head-data=15;head-next-data=15;n一般遍历方法node*curNode=head;while(curNode)curNode=curNode-next;2024/4/21周日14例子2：编写一个函数，输出例1链表中各节点的data成员的值voidoutputList(node*head)coutList:;node*curNode=head;while(curNode)coutdata;if(curNode-next)cout;curNode=curNode-next;coutdata=n)coutFindninthelist.next;coutCantfindninthelist.nextaptr-next；(3)把c的地址赋给节点a的后继指针aptr-next=cptr;2024/4/21周日17例子4：编写一个函数，将输入的整数从小到大插入链表node*insertData(intn,node*head)node*curNode=head;/指向插入点的后节点node*preNode=NULL;/指向插入点的前节点node*newNode=NULL;/指向新建节点while(curNode!=NULL)&(curNode-datanext;newNode=newnode;if(newNode=NULL)coutdata=n;if(preNode=NULL)/插入到链表头newNode-next=curNode;returnnewNode;elsepreNode-next=newNode;newNode-next=curNode;returnhead;2024/4/21 周日周日192024/4/21周日209.2.2单向链表的操作n从链表中删除一个节点c(1)在链表中查找要删除的节点c，用指针cptr指向节点c;(2)如果c有前驱节点(设为d,用指针dptr指向d)，则将d的后继指针指向c的后继节点：dptr-next=cptr-next(3)释放c占用的空间2024/4/21周日21例子5：编写一个函数，删除链表中包含指定整数的节点node*deleteData(intn,node*head)node*curNode=head;/指向当前节点node*preNode=NULL;/指向当前节点的前驱节点while(curNode&curNode-data!=n)preNode=curNode;/当前节点变为前驱节点curNode=curNode-next;if(curNode=NULL)coutCantfindninthelistnext;elsepreNode-next=curNode-next;deletecurNode;returnhead;/返回链首指针2024/4/21周日229.3双向链表n单向链表：有利于从链首向链尾遍历n有些时候双向遍历是需要的双向链表2024/4/21周日239.3.1双向链表的定义n定义双向链表的节点：structnodeintdata;node*next;/指向后续节点 node*pre;/指向前面的节点;2024/4/21周日249.3.1双向链表的定义n双向链表的例子：n双向链表一般也由头指针唯一确定n双向链表首尾相接可以构成双向循环链表headhead2828NULLNULL52522 29696NULLNULL2024/4/21周日259.3.2双向链表的操作n建立双向链表n新节点链入链尾n原链尾节点的后继指针指向新节点n新节点的前驱指针指向原链尾节点n新链尾节点的后继指针置为空指针n将新节点链入链头n原链头节点的前驱指针指向新节点n新节点的后继指针指向原链头节点n新链头节点的前驱指针置为空指针2024/4/21周日26例子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;2024/4/21周日27例子6：编写一个函数，按数据输入的顺序建立双向链表for(inti=0;inum;temp=newnode;/为新节点动态分配内存if(temp=NULL)coutdata=num;temp-next=NULL;temp-pre=tail;tail-next=temp;tail=temp;returnhead;2024/4/21周日289.3.2双向链表的操作n双向链表的遍历n有链首节点，则可以沿着后继指针从头至尾遍历n有链尾节点，则可以沿着前驱指针从尾向头遍历2024/4/21周日29例子7：编写一个函数，输出双向链表中各节点的data成员的值voidoutputBidirList(node*head)coutpre)cout-;coutdata;if(curNode-next)cout;curNode=curNode-next;coutdatanext;newNode=newnode;/为新节点动态分配内存if(newNode=NULL)/内存分配不成功coutdata=n;if(preNode=NULL)/链头newNode-next=curNode;newNode-pre=NULL;if(curNode!=NULL)curNode-pre=newNode;returnnewNode;if(curNode=NULL)/链尾newNode-pre=preNode;preNode-next=newNode;newNode-next=NULL;returnhead;2024/4/21周日33例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大)else/链中preNode-next=newNode;newNode-next=curNode;newNode-pre=preNode;curNode-pre=newNode;returnhead;2024/4/21周日34例子9：编写函数，在双向链表中查找并删除指定node*deleteData(intn,node*head)node*curNode=head;/指向当前节点while(curNode&curNode-data!=n)curNode=curNode-next;if(curNode=NULL)coutCantfindnpre=NULL)head=head-next;head-pre=NULL;elsecurNode-pre-next=curNode-next;if(curNode-next!=NULL)curNode-next-pre=curNode-pre;deletecurNode;returnhead;/返回链首指针2024/4/21周日36学习目的检测n理解自引用结构和链表的含义n掌握通过动态分配和释放内存来建立和维护链表2024/4/21 周日周日37