清华大学链表的用法全

2024/4/81第9章链表2024/4/82讲授内容自引用结构、链表的概念内存的动态分配和释放单向链表的定义与操作双向链表的定义与操作2024/4/839.1链表的基本概念结构数组--必须将数组的大小设定成足够大的值太浪费能否需要多少分配多少？链表=动态内存分配+结构+指针所有结构形成一条链可以在任何地方插入或删除元素2024/4/849.2单向链表自引用结构结构中包含指向同类型结构的指针通过指针连接成链表，终点是NULL指针(0)2024/4/859.2.1单向链表定义例子：structnode{intdata;node*next;};

next：指向下一个node类型的结构，连接node的纽带head2852296NULL2024/4/869.2.1单向链表定义存放学生信息的链表节点structstudent{intnum;charname[20];charsex;floatscore;student*next;};动态申请内存的方法student*p=(student*)malloc(sizeof(student));或student*p=newstudent;2024/4/879.2.2单向链表的操作建立单向链表声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)动态分配一个新节点，将该节点链入链尾重复上一步2024/4/88例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾#include<iostream.h>structnode{ intdata; node*next;};node*createList(intn);intmain(){intn;node*listHead=NULL;cout<<"Pleaseenterthenumberofnodes:";cin>>n;if(n>0) listHead=createList(n);

return0;}2024/4/89例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾node*createList(intn){node*temp,*tail=NULL,*head=NULL;intnum;

cin>>num;head=newnode;//为新节点动态分配内存

if(head==NULL){

cout<<"Nomemoryavailable!";returnNULL; } else{head->data=num;head->next=NULL;tail=head;}2024/4/810例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾

for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//为新节点动态分配内存

if(temp==NULL){

cout<<"Nomemoryavailable!";returnhead;}else {temp->data=num;temp->next=NULL;tail->next=temp;tail=temp;}} returnhead;}

2024/4/811建立链表过程tailtempheadNULL初始状态NULLNULL读入1后tailtemphead1NULL2024/4/812建立链表过程读入2后tailtemphead12NULL读入3后tailtemphead13NULL22024/4/8139.2.2单向链表的操作遍历链表依次访问链表中的每个节点的信息head->data=15;head->next->data=15;一般遍历方法node*curNode=head;while(curNode)curNode=curNode->next;2024/4/814例子2：编写一个函数，输出例1链表中各节点的data成员的值voidoutputList(node*head){cout<<"List:";node*curNode=head;while(curNode){cout<<curNode->data;if(curNode->next) cout<<"->";curNode=curNode->next;}cout<<endl;return;}2024/4/815例子3：编写一个函数，在例1的链表中查找包含指定整数的节点node*findData(intn,node*head){node*curNode=head;while(curNode){if(curNode->data==n){cout<<"Find"<<n<<"inthelist."<<endl;returncurNode;}curNode=curNode->next;}cout<<"Can'tfind"<<n<<"inthelist."<<endl;returnNULL;}2024/4/8169.2.2单向链表的操作在链表中节点a之后插入节点c(1)指针cptr指向节点c,aptr指向节点a；(2)把a后继节点的地址赋给节点c的后继指针

cptr->next＝aptr->next；(3)把c的地址赋给节点a的后继指针aptr->next=cptr;2024/4/817例子4：编写一个函数，将输入的整数从小到大插入链表node*insertData(intn,node*head){node*curNode=head;//指向插入点的后节点

node*preNode=NULL;//指向插入点的前节点

node*newNode=NULL;//指向新建节点while((curNode!=NULL)&&(curNode->data<n)){preNode=curNode;//后节点变为前节点

curNode=curNode->next;}newNode=newnode;

if(newNode==NULL){

cout<<"Nomemoryavailable!"; returnhead; }2024/4/818例子4：编写一个函数，将输入的整数从小到大插入链表newNode->data=n;if(preNode==NULL)//插入到链表头{

newNode->next=curNode;

returnnewNode;}

else{preNode->next=newNode;newNode->next=curNode;

returnhead;}}2024/4/8192024/4/8209.2.2单向链表的操作从链表中删除一个节点c(1)在链表中查找要删除的节点c，用指针cptr指向节点c;(2)如果c有前驱节点(设为d,用指针dptr指向d)，则将d的后继指针指向c的后继节点：dptr->next=cptr->next(3)释放c占用的空间2024/4/821例子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){cout<<"Can'tfind"<<n<<"inthelist"<<endl;returnhead;}if(preNode==NULL)//删除链首节点

head=head->next;else

preNode->next=curNode->next;deletecurNode;returnhead; //返回链首指针}

2024/4/8229.3双向链表单向链表：有利于从链首向链尾遍历有些时候双向遍历是需要的——双向链表2024/4/8239.3.1双向链表的定义定义双向链表的节点：structnode{intdata; node*next;//指向后续节点 node*pre;//指向前面的节点};2024/4/8249.3.1双向链表的定义双向链表的例子：双向链表一般也由头指针唯一确定双向链表首尾相接可以构成双向循环链表head28NULL52296NULL2024/4/8259.3.2双向链表的操作建立双向链表新节点链入链尾原链尾节点的后继指针指向新节点新节点的前驱指针指向原链尾节点新链尾节点的后继指针置为空指针将新节点链入链头原链头节点的前驱指针指向新节点新节点的后继指针指向原链头节点新链头节点的前驱指针置为空指针2024/4/826例子6：编写一个函数，按数据输入的顺序建立双向链表node*createBidirList(intn){node*temp,*tail=NULL,*head=NULL; intnum;

cin>>num;head=newnode;//为新节点动态分配内存

if(head==NULL) {

cout<<"Nomemoryavailable!";returnNULL;}else{head->data=num;head->next=NULL;head->pre=NULL;tail=head;}2024/4/827例子6：编写一个函数，按数据输入的顺序建立双向链表for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//为新节点动态分配内存

if(temp==NULL){

cout<<"Nomemoryavailable!";returnhead;}else{temp->data=num;temp->next=NULL;temp->pre=tail;tail->next=temp;tail=temp;}}returnhead;}2024/4/8289.3.2双向链表的操作双向链表的遍历有链首节点，则可以沿着后继指针从头至尾遍历有链尾节点，则可以沿着前驱指针从尾向头遍历2024/4/829例子7：编写一个函数，输出双向链表中各节点的data成员的值voidoutputBidirList(node*head){cout<<"List:";node*curNode=head;while(curNode){if(curNode->pre)cout<<"<-";cout<<curNode->data;if(curNode->next)cout<<"->";curNode=curNode->next;}cout<<endl;return;}2024/4/8309.3.2双向链表的操作在双向链表中插入和删除一个节点优点：获取插入节点或被删除节点的前驱和后继节点比较方便注意点：需要维护的指针较多2024/4/831例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大)node*insertData(intn,node*head){ node*curNode=head; //指向插入点的后节点

node*preNode=NULL; //指向插入点的前节点

node*newNode=NULL; //指向新建节点 //寻找插入位置

while((curNode!=NULL)&&(curNode->data<n)){ preNode=curNode; curNode=curNode->next; } newNode=newnode;//为新节点动态分配内存

if(newNode==NULL){//内存分配不成功

cout<<"Notmemoryavailable!"; returnhead; }2024/4/832例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大) newNode->data=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/833例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大) else {//链中

preNode->next