清华C++语言程序设计第09章 链表.ppt

《清华C++语言程序设计第09章 链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、de类型的结构，连接node的纽带head2852296NULL2021/9/1559.2.1单向链表定义存放学生信息的链表节点structstudent{intnum;charname[20];charsex;floatscore;student*next;};动态申请内存的方法student*p=(student*)malloc(sizeof(student));或student*p=newstudent;2021/9/1569.2.2单向链表的操作建立单向链表声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)动态分配一个新节点，将

3、该节点链入链尾重复上一步2021/9/157例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾#includestructnode{intdata;node*next;};node*createList(intn);intmain(){intn;node*listHead=NULL;cout<<"Pleaseenterthenumberofnodes:";cin>>n;if(n>0)listHead=createList(n);return0;}2021/9/158例子1：建立链表，读入n个整数，每个整数作为一个新结

4、点插入到链尾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;}2021/9/159例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾for(inti=0;i>num;temp=

5、newnode;//为新节点动态分配内存if(temp==NULL){cout<<"Nomemoryavailable!";returnhead;}else{temp->data=num;temp->next=NULL;tail->next=temp;tail=temp;}}returnhead;}2021/9/1510建立链表过程tailtempheadNULL初始状态NULLNULL读入1后tailtemphead1NULL2021/9/1511建立链表过程读入2后tailtemphead12NULL读入3后tailtemphead13NULL220

6、21/9/15129.2.2单向链表的操作遍历链表依次访问链表中的每个节点的信息head->data=15;head->next->data=15;一般遍历方法node*curNode=head;while(curNode)curNode=curNode->next;2021/9/1513例子2：编写一个函数，输出例1链表中各节点的data成员的值voidoutputList(node*head){cout<<"List:";node*curNode=head;while(curNode){cout<data;if(curNode->

7、next)cout<<"->";curNode=curNode->next;}cout<data==n){cout<<"Find"<next;}cout<<"Can'tfind"<

8、nthelist."<