《清华大学课件-链表的用法-PPT(全)》由会员分享，可在线阅读，更多相关《清华大学课件-链表的用法-PPT(全)（35页珍藏版）》请在金锄头文库上搜索。
1、2017/11/27,1,第9章 链表,2017/11/27,2,讲授内容,自引用结构、链表的概念内存的动态分配和释放单向链表的定义与操作双向链表的定义与操作,2017/11/27,3,9.1 链表的基本概念,结构数组-必须将数组的大小设定成足够大的值太浪费能否需要多少分配多少？链表 = 动态内存分配 + 结构 + 指针所有结构形成一条链可以在任何地方插入或删除元素,2017/11/27,4,9.2 单向链表,自引用结构结构中包含指向同类型结构的指针通过指针连接成链表，终点是NULL指针 (0),2017/11/27,5,9.2.1 单向链表定义,例子：struct node int data
2、; node * next; ; next：指向下一个node类型的结构，连接node 的纽带,2017/11/27,6,9.2.1 单向链表定义,存放学生信息的链表节点 struct student int num; char name20; char sex; float score; student * next;动态申请内存的方法 student *p=(student*) malloc(sizeof(student); 或student * p = new student;,2017/11/27,7,9.2.2 单向链表的操作,建立单向链表声明一个链首指针变量head，并赋初值NUL
3、L(包含0个节点的链表)动态分配一个新节点，将该节点链入链尾重复上一步,2017/11/27,8,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,#include struct node int data; node * next;node * createList(int n);int main() int n; node * listHead = NULL; cout n; if (n 0) listHead = createList(n); return 0;,2017/11/27,9,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,node *cre
4、ateList(int n) node *temp, *tail = NULL, *head = NULL ; int num; cin num; head = new node ; / 为新节点动态分配内存 if (head = NULL) cout data = num; head-next = NULL; tail = head; ,2017/11/27,10,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,for ( int i = 0; i num; temp = new node ; / 为新节点动态分配内存 if (temp = NULL) cout data
5、= num; temp-next = NULL; tail-next = temp; tail = temp; return head ;,2017/11/27,11,建立链表过程,2017/11/27,12,建立链表过程,2017/11/27,13,9.2.2 单向链表的操作,遍历链表依次访问链表中的每个节点的信息 head-data = 15; head-next-data = 15;一般遍历方法 node * curNode = head; while (curNode ) curNode = curNode-next;,2017/11/27,14,例子2：编写一个函数，输出例1链表中各
6、节点的data成员的值,void outputList(node * head) cout List: ; node *curNode = head; while ( curNode ) cout data; if (curNode -next)cout ; curNode = curNode -next; cout data = n) coutFind n in the list.next; coutCant find n in the list.nextaptr-next；(3) 把c的地址赋给节点a的后继指针 aptr-next=cptr;,2017/11/27,17,例子4：编写一个函
7、数，将输入的整数从小到大插入链表,node * insertData(int n, node * head) node *curNode = head;/ 指向插入点的后节点 node *preNode = NULL;/ 指向插入点的前节点 node *newNode = NULL;/ 指向新建节点 while (curNode!=NULL)&(curNode-datanext; newNode = new node ; if (newNode = NULL) cout data = n; if (preNode = NULL) /插入到链表头 newNode-next = curNode;
8、return newNode; else preNode-next = newNode; newNode-next = curNode; return head; ,2017/11/27,19,9.2.2 单向链表的操作,从链表中删除一个节点c (1)在链表中查找要删除的节点c，用指针cptr指向节点c;(2)如果c有前驱节点(设为d,用指针dptr指向d)，则将d的后继指针指向c的后继节点：dptr-next=cptr-next(3)释放c占用的空间,2017/11/27,20,例子5：编写一个函数，删除链表中包含指定整数的节点,node * deleteData(int n, node *
9、 head) node *curNode = head;/ 指向当前节点 node *preNode = NULL;/ 指向当前节点的前驱节点 while (curNode & curNode-data != n) preNode = curNode; / 当前节点变为前驱节点 curNode = curNode-next; if (curNode = NULL) coutCant find n in the listnext; else preNode-next = curNode-next; delete curNode; return head;/ 返回链首指针,2017/11/27,2
10、1,9.3 双向链表,单向链表：有利于从链首向链尾遍历有些时候双向遍历是需要的双向链表,2017/11/27,22,9.3.1 双向链表的定义,定义双向链表的节点：struct node int data; node * next; /指向后续节点 node * pre; /指向前面的节点 ;,2017/11/27,23,9.3.1 双向链表的定义,双向链表的例子：双向链表一般也由头指针唯一确定双向链表首尾相接可以构成双向循环链表,2017/11/27,24,9.3.2 双向链表的操作,建立双向链表新节点链入链尾原链尾节点的后继指针指向新节点新节点的前驱指针指向原链尾节点新链尾节点的后继指针置
11、为空指针将新节点链入链头原链头节点的前驱指针指向新节点新节点的后继指针指向原链头节点新链头节点的前驱指针置为空指针,2017/11/27,25,例子6：编写一个函数，按数据输入的顺序建立双向链表,node *createBidirList (int n) node *temp, *tail = NULL, *head = NULL ; int num; cin num; head = new node ; / 为新节点动态分配内存 if (head = NULL) cout data = num; head-next = NULL; head-pre = NULL; tail = head; ,2017/11/27,26,例子6：编写一个函数，按数据输入的顺序建立双向链表,for ( int i = 0; i num; temp = new node ; / 为新节点动态分配内存 if (temp = NULL) cout data = num; temp-next = NULL; temp-pre = tail; tail-next = temp; tail = temp; return head ;,
