清华C++语言程序设计：第09章-链表优秀PPT.ppt

《清华C++语言程序设计：第09章-链表优秀PPT.ppt》由会员分享，可在线阅读，更多相关《清华C++语言程序设计：第09章-链表优秀PPT.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2022/11/31第第1111讲讲 链表简洁介绍链表简洁介绍2022/11/32讲授内容讲授内容n自引用结构、链表的概念自引用结构、链表的概念n内存的动态安排和释放内存的动态安排和释放n单向链表的定义与操作单向链表的定义与操作2022/11/339.1 9.1 链表的基本概念链表的基本概念 n结构数组结构数组-必需将数组的大小设定成足必需将数组的大小设定成足够大的值够大的值n太奢侈太奢侈n能否须要多少安排多少？能否须要多少安排多少？n链表链表=动态内存安排动态内存安排+结构结构+指针指针n全部结构形成一条链全部结构形成一条链n可以在任何地方插入或删除元素可以在任何地方插入或删除元素2022/

2、11/349.2 单向链表单向链表 n自引用结构自引用结构n结构中包含指向同类型结构的指针结构中包含指向同类型结构的指针n通过指针连接成链表，终点是通过指针连接成链表，终点是NULL指针指针(0)2022/11/359.2.1 单向链表定义单向链表定义n例子：例子：structnodeintdata;node*next;nnext：指向下一个指向下一个node类型的结构，连接类型的结构，连接node 的纽带的纽带head2852296NULL2022/11/36612491249 A A13561356 B B14751475 C C10211021 D DNullNull1 1、链表中的元素

3、称为、链表中的元素称为“结点结点”，每个结点包括两个域：，每个结点包括两个域：数数据域和指针域；据域和指针域；2 2、单向链表通常由一个头指针（、单向链表通常由一个头指针（head)head)，用于指向链表头；，用于指向链表头；3 3、单向链表有一个尾结点，该结点的指针部分指向一个空、单向链表有一个尾结点，该结点的指针部分指向一个空结点结点(NULL)(NULL)。Head 1249 1356 1475 1021结点里的指针是存放下一个结点的地址2022/11/379.2.1 单向链表定义单向链表定义n存放学生信息的链表节点存放学生信息的链表节点 structstudentintnum;cha

4、rname20;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;

5、head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do coutnum scorenext;while(p!=NULL);建建立立和和输输出出一一个个简简洁洁链链表表各结点在程序中定义，不是临时开拓的，各结点在程序中定义，不是临时开拓的，始终占有内容不放，这种链表称为始终占有内容不放，这种链表称为“静静态链表态链表”2022/11/399.2.2 9.2.2 单向链表的操作单向链表的操作 n建立单向链表建立单向链表n声明一个链首指针变量声明一个链首指针变量headhead，并赋初值，并赋初值NULL(NULL(包含包含0 0个节点的链表个节点的链表)

6、n动态安排一个新节点，将该节点链入链动态安排一个新节点，将该节点链入链尾尾n重复上一步重复上一步10 建立动态链表建立动态链表991019910189.589.5headtemptail1.任务是开拓结点和输入数据任务是开拓结点和输入数据2.并建立前后相链的关系并建立前后相链的关系待插入的结点待插入的结点temptemp数据部分初始化数据部分初始化,该该结点被头结点结点被头结点head、尾结点尾结点tail同时指向同时指向.11991019910189.589.5headtail99103991039090temp991019910189.589.5headtail99103991039090

7、temp(a)(b)temp重复申请待插重复申请待插入结点空间，对该入结点空间，对该结点的数据部分赋结点的数据部分赋值（或输入值）值（或输入值）tail-next tail-next 指向指向temptemp新开拓的结点。新开拓的结点。12图图11.14head991019910189.589.5temptail99103991039090(c)tailtail指向新结指向新结点点tail=temptail=temp13991019910189.589.5991019910189.589.5tail99107991078585temphead991019910189.589.599101991

8、0189.589.5tail99107991078585temphead(a)(b)149910399103909099107991078585tail0 00 0temphead991019910189.589.59910399103909099107991078585NULLNULLtail0 00 0temphead991019910189.589.52022/11/315例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾#includestructnode intdata;node*next;node*c

9、reateList(intn);intmain()intn;node*listHead=NULL;coutn;if(n0)listHead=createList(n);return0;2022/11/316例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾 node*createList(intn)node*temp,*tail=NULL,*head=NULL;intnum;cinnum;head=newnode;/为为新新节节点点动态动态安排内存安排内存if(head=NULL)coutdata=num;hea

10、d-next=NULL;tail=head;2022/11/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;2022/11/318建立链表过程建立链表过程tailtailtemptempheadheadNULLNULL初始状态初始状态NULLNULLNU

11、LLNULL读入读入1 1后后tailtailtemptempheadhead1 1NULLNULL2022/11/319建立链表过程建立链表过程读入读入2 2后后tailtailtemptempheadhead1 12 2NULLNULL读入读入3 3后后tailtailtemptempheadhead1 13 3NULLNULL2 22022/11/3209.2.2 9.2.2 单向链表的操作单向链表的操作n遍历链表遍历链表n依次访问链表中的每个节点的信息依次访问链表中的每个节点的信息 head-data=15;head-next-data=15;n一般遍历方法一般遍历方法node*cur

12、Node=head;while(curNode)curNode=curNode-next;2022/11/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.nextcp

13、tr-nextaptr-nextaptr-next；(3)(3)把把c c的地址赋给节点的地址赋给节点a a的后继指针的后继指针 aptr-next=cptr;aptr-next=cptr;2022/11/324例子例子4 4：编写一个函数，将输入的整数：编写一个函数，将输入的整数从小到大插入链表从小到大插入链表node*insertData(intn,node*head)node*curNode=head;/指向插入点的后节点指向插入点的后节点node*preNode=NULL;/指向插入点的前节点指向插入点的前节点node*newNode=NULL;/指向新建节点指向新建节点while(c

14、urNode!=NULL)&(curNode-datanext;newNode=newnode;if(newNode=NULL)coutdata=n;if(preNode=NULL)/插入到链表头插入到链表头newNode-next=curNode;returnnewNode;elsepreNode-next=newNode;newNode-next=curNode;returnhead;2022/11/3269.2.2 9.2.2 单向链表的操作单向链表的操作n从链表中删除一个节点从链表中删除一个节点c c n(1)(1)在链表中查找要删除的节点在链表中查找要删除的节点c c，用指，用指针针

15、cptrcptr指向节点指向节点c;c;n(2)(2)假如假如c c有前驱节点有前驱节点(设为设为d,d,用指针用指针dptrdptr指向指向d)d)，则将，则将d d的后继指针指向的后继指针指向c c的后继的后继节点：节点：dptr-next=cptr-nextdptr-next=cptr-nextn(3)(3)释放释放c c占用的空间占用的空间2022/11/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;/返回链首指针返回链首指针