清华C++语言程序设计：第09章-链表.ppt
2023/3/31第第1111讲讲 链表简单介绍链表简单介绍2023/3/32讲授内容授内容n自引用自引用结构、构、链表的概念表的概念n内存的内存的动态分配和分配和释放放n单向向链表的定表的定义与操作与操作2023/3/339.1 9.1 链表的基本概念链表的基本概念 n结构数构数组-必必须将数将数组的大小的大小设定成足定成足够大的大的值n太浪太浪费n能否需要多少分配多少？能否需要多少分配多少？n链表表=动态内存分配内存分配+结构构+指指针n所有所有结构形成一条构形成一条链n可以在任何地方插入或可以在任何地方插入或删除元素除元素2023/3/349.2 单向链表单向链表 n自引用自引用结构构n结构中包含指向同构中包含指向同类型型结构的指构的指针n通通过指指针连接成接成链表，表，终点是点是NULL指指针(0)2023/3/359.2.1 单向链表定义单向链表定义n例子：例子：structnodeintdata;node*next;nnext：指向下一个指向下一个node类型的型的结构，构，连接接node 的的纽带head2852296NULL2023/3/36612491249 A A13561356 B B14751475 C C10211021 D DNullNull1 1、链表中的元素称为、链表中的元素称为“结点结点”，每个结点包括两个域：，每个结点包括两个域：数数据域和指针域；据域和指针域；2 2、单向链表通常由一个头指针（、单向链表通常由一个头指针（head)head)，用于指向链表头；，用于指向链表头；3 3、单向链表有一个尾结点，该结点的指针部分指向一个空、单向链表有一个尾结点，该结点的指针部分指向一个空结点结点(NULL)(NULL)。Head 1249 1356 1475 1021结点里的指针是存放下一个结点的地址2023/3/379.2.1 单向链表定义单向链表定义n存放学生信息的存放学生信息的链表表节点点 structstudentintnum;charname20;charsex;floatscore;student*next;n动态申申请内存的方法内存的方法 student*p=(student*)malloc(sizeof(student);或或student*p=newstudent;8#include struct student long num;float score;struct student *next;main()struct student a,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do coutnum scorenext;while(p!=NULL);建建立立和和输输出出一一个个简简单单链链表表各结点在程序中定义，不是临时开辟的，各结点在程序中定义，不是临时开辟的，始终占有内容始终占有内容不放不放，这种链表称为，这种链表称为“静静态链表态链表”2023/3/399.2.2 9.2.2 单向链表的操作单向链表的操作 n建立建立单向向链表表n声明一个声明一个链首指首指针变量量headhead，并并赋初初值NULL(NULL(包含包含0 0个个节点的点的链表表)n动态分配一个新分配一个新节点，将点，将该节点点链入入链尾尾n重复上一步重复上一步10 建立动态链表建立动态链表991019910189.589.5headtemptail1.任务是开辟结点和输入数据任务是开辟结点和输入数据2.2.并建立前后相链的关系并建立前后相链的关系待插入的结点待插入的结点temptemp数据部分初始化数据部分初始化,该该结点被头结点结点被头结点head、尾结点尾结点tail同时指向同时指向.11991019910189.589.5headtail99103991039090temp991019910189.589.5headtail99103991039090temp(a)(b)temp重复申请待插重复申请待插入结点空间，对该入结点空间，对该结点的数据部分赋结点的数据部分赋值（或输入值）值（或输入值）tail-next tail-next 指向指向temptemp新开辟的结点。新开辟的结点。12图图11.14head991019910189.589.5temptail99103991039090(c)tailtail指向新结指向新结点点tail=temptail=temp13991019910189.589.5991019910189.589.5tail99107991078585temphead991019910189.589.5991019910189.589.5tail99107991078585temphead(a)(b)149910399103909099107991078585tail0 00 0temphead991019910189.589.59910399103909099107991078585NULLNULLtail0 00 0temphead991019910189.589.52023/3/315例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾#includestructnode intdata;node*next;node*createList(intn);intmain()intn;node*listHead=NULL;coutn;if(n0)listHead=createList(n);return0;2023/3/316例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾 node*createList(intn)node*temp,*tail=NULL,*head=NULL;intnum;cinnum;head=newnode;/为新节点动态分配内存为新节点动态分配内存if(head=NULL)coutdata=num;head-next=NULL;tail=head;2023/3/317例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾 for(inti=0;inum;temp=newnode;/为新节点动态分配内存为新节点动态分配内存if(temp=NULL)coutdata=num;temp-next=NULL;tail-next=temp;tail=temp;returnhead;2023/3/318建立链表过程建立链表过程tailtailtemptempheadheadNULLNULL初始状初始状态NULLNULLNULLNULL读入入1 1后后tailtailtemptempheadhead1 1NULLNULL2023/3/319建立链表过程建立链表过程读入入2 2后后tailtailtemptempheadhead1 12 2NULLNULL读入入3 3后后tailtailtemptempheadhead1 13 3NULLNULL2 22023/3/3209.2.2 9.2.2 单向链表的操作单向链表的操作n遍遍历链表表n依次依次访问链表中的每个表中的每个节点的信息点的信息 head-data=15;head-next-data=15;n一般遍一般遍历方法方法node*curNode=head;while(curNode)curNode=curNode-next;2023/3/321例子例子2 2：编写一个函数，输出例：编写一个函数，输出例1 1链表链表中各节点的中各节点的datadata成员的值成员的值voidoutputList(node*head)coutList:;node*curNode=head;while(curNode)coutdata;if(curNode-next)cout;curNode=curNode-next;coutdata=n)coutFindninthelist.next;coutCantfindninthelist.nextcptr-nextaptr-nextaptr-next；(3)(3)把把c c的地址的地址赋给节点点a a的后的后继指指针 aptr-next=cptr;aptr-next=cptr;2023/3/324例子例子4 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;2023/3/3269.2.2 9.2.2 单向链表的操作单向链表的操作n从从链表中表中删除一个除一个节点点c c(1)(1)在在链表表中中查找找要要删除除的的节点点c c，用用指指针cptrcptr指向指向节点点c;c;(2)(2)如如果果c c有有前前驱节点点(设为d,d,用用指指针dptrdptr指指向向d)d)，则将将d d的的后后继指指针指指向向c c的的后后继节点点：dptr-next=cptr-nextdptr-next=cptr-next(3)(3)释放放c c占用的空占用的空间2023/3/327例子例子5 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;/返回返回链首指首指针
