清华大学课件-链表的用法-PPT(全)学习资料.ppt

《清华大学课件-链表的用法-PPT(全)学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学课件-链表的用法-PPT(全)9.1链表的基本概念结构数组--必须将数组的大小设定成足够大的值太浪费能否需要多少分配多少？链表=动态内存分配+结构+指针所有结构形成一条链可以在任何地方插入或删除元素2021/7/2929.2单向链表自引用结构结构中包含指向同类型结构的指针通过指针连接成链表，终点是NULL指针(0)2021/7/2939.2.1单向链表定义例子：structnode{intdata;node*next;};next：指向下一个node类型的结构，连接node的纽带head2852296NULL2021/7/2949.2.1单向链表定义存放学生

2、信息的链表节点structstudent{intnum;charname[20];charsex;floatscore;student*next;};动态申请内存的方法student*p=(student*)malloc(sizeof(student));或student*p=newstudent;2021/7/2959.2.2单向链表的操作建立单向链表声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)动态分配一个新节点，将该节点链入链尾重复上一步2021/7/296例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾#include<

3、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;}2021/7/297例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾node*createList(intn){node*temp,*tail=NULL,*head=NULL;intnum;ci

4、n>>num;head=newnode;//为新节点动态分配内存if(head==NULL){cout<<"Nomemoryavailable!";returnNULL;}else{head->data=num;head->next=NULL;tail=head;}2021/7/298例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾for(inti=0;i>num;temp=newnode;//为新节点动态分配内存if(temp==NULL){cout<<"Nomemoryavailable!";returnhead;}e

5、lse{temp->data=num;temp->next=NULL;tail->next=temp;tail=temp;}}returnhead;}2021/7/299建立链表过程tailtempheadNULL初始状态NULLNULL读入1后tailtemphead1NULL2021/7/2910建立链表过程读入2后tailtemphead12NULL读入3后tailtemphead13NULL22021/7/29119.2.2单向链表的操作遍历链表依次访问链表中的每个节点的信息head->data=15;head->next->data=15;一般遍历方法no

6、de*curNode=head;while(curNode)curNode=curNode->next;2021/7/2912例子2：编写一个函数，输出例1链表中各节点的data成员的值voidoutputList(node*head){cout<<"List:";node*curNode=head;while(curNode){cout<data;if(curNode->next)cout<<"->";curNode=curNode->next;}cout<

7、找包含指定整数的节点node*findData(intn,node*head){node*curNode=head;while(curNode){if(curNode->data==n){cout<<"Find"<next;}cout<<"Can'tfind"<