清华C++语言程序设计：第09章-链表讲课教案.ppt

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

1、清华C+语言程序设计：第09章-链表9.1 9.1 链表的基本概念链表的基本概念 n结构数组结构数组-必须将数组的大小设定成足必须将数组的大小设定成足够大的值够大的值n太浪费太浪费n能否需要多少分配多少？能否需要多少分配多少？n链表链表=动态内存分配动态内存分配+结构结构+指针指针n所有结构形成一条链所有结构形成一条链n可以在任何地方插入或删除元素可以在任何地方插入或删除元素2022/11/1929.2 单向链表单向链表 n自引用结构自引用结构n结构中包含指向同类型结构的指针结构中包含指向同类型结构的指针n通过指针连接成链表，终点是通过指针连接成链表，终点是NULL指针指针(0)2022/11

2、/1939.2.1 单向链表定义单向链表定义n例子：例子：structnodeintdata;node*next;nnext：指向下一个指向下一个node类型的结构，连接类型的结构，连接node 的纽带的纽带head2852296NULL2022/11/194512491249 A A13561356 B B14751475 C C10211021 D DNullNull1 1、链表中的元素称为、链表中的元素称为“结点结点”，每个结点包括两个域：，每个结点包括两个域：数数据域和指针域；据域和指针域；2 2、单向链表通常由一个头指针（、单向链表通常由一个头指针（head)head)，用于指向链表

3、头；，用于指向链表头；3 3、单向链表有一个尾结点，该结点的指针部分指向一个空、单向链表有一个尾结点，该结点的指针部分指向一个空结点结点(NULL)(NULL)。Head 1249 1356 1475 1021结点里的指针是存放下一个结点的地址2022/11/1959.2.1 单向链表定义单向链表定义n存放学生信息的链表节点存放学生信息的链表节点 structstudentintnum;charname20;charsex;floatscore;student*next;n动态申请内存的方法动态申请内存的方法 student*p=(student*)malloc(sizeof(student)

4、;或或student*p=newstudent;2022/11/196#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);建建立立和和输输出

5、出一一个个简简单单链链表表各结点在程序中定义，不是临时开辟的，各结点在程序中定义，不是临时开辟的，始终占有内容始终占有内容不放不放，这种链表称为，这种链表称为“静静态链表态链表”79.2.2 9.2.2 单向链表的操作单向链表的操作 n建立单向链表建立单向链表n声明一个链首指针变量声明一个链首指针变量headhead，并赋初值并赋初值NULL(NULL(包含包含0 0个节点的链表个节点的链表)n动态分配一个新节点，将该节点链入链尾动态分配一个新节点，将该节点链入链尾n重复上一步重复上一步2022/11/198 建立动态链表建立动态链表991019910189.589.5headtemptail

6、1.任务是开辟结点和输入数据任务是开辟结点和输入数据2.2.并建立前后相链的关系并建立前后相链的关系待插入的结点待插入的结点temptemp数据部分初始化数据部分初始化,该该结点被头结点结点被头结点head、尾结点尾结点tail同时指向同时指向.9991019910189.589.5headtail99103991039090temp991019910189.589.5headtail99103991039090temp(a)(b)temp重复申请待插重复申请待插入结点空间，对该入结点空间，对该结点的数据部分赋结点的数据部分赋值（或输入值）值（或输入值）tail-next tail-next

7、指向指向temptemp新开辟的结点。新开辟的结点。10图图11.14head991019910189.589.5temptail99103991039090(c)tailtail指向新结指向新结点点tail=temptail=temp11991019910189.589.5991019910189.589.5tail99107991078585temphead991019910189.589.5991019910189.589.5tail99107991078585temphead(a)(b)129910399103909099107991078585tail0 00 0temphead99

8、1019910189.589.59910399103909099107991078585NULLNULLtail0 00 0temphead991019910189.589.513例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾#includestructnode intdata;node*next;node*createList(intn);intmain()intn;node*listHead=NULL;coutn;if(n0)listHead=createList(n);return0;2022/11/1

9、914例子例子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;2022/11/1915例子例子1 1：建立链表，读入：建立链表，读入n n个整数，每个整数，每个整数作为一个新结点插入到链尾个整数作为一个新结点插入到链尾

10、 for(inti=0;inum;temp=newnode;/为新节点动态分配内存为新节点动态分配内存if(temp=NULL)coutdata=num;temp-next=NULL;tail-next=temp;tail=temp;returnhead;2022/11/1916建立链表过程建立链表过程tailtailtemptempheadheadNULLNULL初始状态初始状态NULLNULLNULLNULL读入读入1 1后后tailtailtemptempheadhead1 1NULLNULL2022/11/1917建立链表过程建立链表过程读入读入2 2后后tailtailtemptem

11、pheadhead1 12 2NULLNULL读入读入3 3后后tailtailtemptempheadhead1 13 3NULLNULL2 22022/11/19189.2.2 9.2.2 单向链表的操作单向链表的操作n遍历链表遍历链表n依次访问链表中的每个节点的信息依次访问链表中的每个节点的信息 head-data=15;head-next-data=15;n一般遍历方法一般遍历方法node*curNode=head;while(curNode)curNode=curNode-next;2022/11/1919例子例子2 2：编写一个函数，输出例：编写一个函数，输出例1 1链表链表中各节

12、点的中各节点的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;

13、2022/11/1922例子例子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)/插入

14、到链表头插入到链表头newNode-next=curNode;returnnewNode;elsepreNode-next=newNode;newNode-next=curNode;returnhead;2022/11/19249.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的的后后继继指指针针指指向向

15、c c的的后后继继节节点点：dptr-next=cptr-nextdptr-next=cptr-next(3)(3)释放释放c c占用的空间占用的空间2022/11/1925例子例子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;/返回链首指针返回链首指针2022/11/1926此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢