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

1、2020/9/4,1,第9章 链表,2020/9/4,2,讲授内容,自引用结构、链表的概念 内存的动态分配和释放 单向链表的定义与操作 双向链表的定义与操作,2020/9/4,3,9.1 链表的基本概念,结构数组-必须将数组的大小设定成足够大的值 太浪费 能否需要多少分配多少？ 链表 = 动态内存分配 + 结构 + 指针 所有结构形成一条链 可以在任何地方插入或删除元素,2020/9/4,4,9.2 单向链表,自引用结构 结构中包含指向同类型结构的指针 通过指针连接成链表，终点是NULL指针 (0),2020/9/4,5,9.2.1 单向链表定义,例子： struct node int dat

2、a; node * next; ; next：指向下一个node类型的结构，连接node 的纽带,2020/9/4,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;,2020/9/4,7,9.2.2 单向链表的操作,建立单向链表 声明一个链首指针变量head，并赋初值N

3、ULL(包含0个节点的链表) 动态分配一个新节点，将该节点链入链尾 重复上一步,2020/9/4,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; ,2020/9/4,9,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,node

4、 *createList(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; ,2020/9/4,10,例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾,for ( int i = 0; i num; temp = new node ; / 为新节点动态分配内存 if (temp = NULL) cout da

5、ta = num; temp-next = NULL; tail-next = temp; tail = temp; return head ; ,2020/9/4,11,建立链表过程,2020/9/4,12,建立链表过程,2020/9/4,13,9.2.2 单向链表的操作,遍历链表 依次访问链表中的每个节点的信息 head-data = 15; head-next-data = 15; 一般遍历方法 node * curNode = head; while (curNode ) curNode = curNode-next;,2020/9/4,14,例子2：编写一个函数，输出例1链表中各节点

6、的data成员的值,void outputList(node * head) cout data; if (curNode -next) cout ; curNode = curNode -next; cout endl; return; ,2020/9/4,15,例子3：编写一个函数，在例1的链表中查找包含指定整数的节点,node * findData(int n, node * head) node *curNode = head; while ( curNode ) if ( curNode-data = n) coutnext; coutCant find n in the list.

7、endl; return NULL; ,2020/9/4,16,9.2.2 单向链表的操作,在链表中节点a之后插入节点c (1) 指针cptr指向节点c,aptr指向节点a； (2) 把a后继节点的地址赋给节点c的后继指针 cptr-nextaptr-next； (3) 把c的地址赋给节点a的后继指针 aptr-next=cptr;,2020/9/4,17,例子4：编写一个函数，将输入的整数从小到大插入链表,node * insertData(int n, node * head) node *curNode = head;/ 指向插入点的后节点 node *preNode = NULL;/

8、指向插入点的前节点 node *newNode = NULL;/ 指向新建节点 while (curNode!=NULL) ,2020/9/4,18,例子4：编写一个函数，将输入的整数从小到大插入链表,newNode-data = n; if (preNode = NULL) /插入到链表头 newNode-next = curNode; return newNode; else preNode-next = newNode; newNode-next = curNode; return head; ,2020/9/4,19,9.2.2 单向链表的操作,从链表中删除一个节点c (1)在链表中查

9、找要删除的节点c，用指针cptr指向节点c; (2)如果c有前驱节点(设为d,用指针dptr指向d)，则将d的后继指针指向c的后继节点：dptr-next=cptr-next (3)释放c占用的空间,2020/9/4,20,例子5：编写一个函数，删除链表中包含指定整数的节点,node * deleteData(int n, node * head) node *curNode = head;/ 指向当前节点 node *preNode = NULL;/ 指向当前节点的前驱节点 while (curNode / 返回链首指针 ,2020/9/4,21,9.3 双向链表,单向链表：有利于从链首向链

10、尾遍历 有些时候双向遍历是需要的双向链表,2020/9/4,22,9.3.1 双向链表的定义,定义双向链表的节点： struct node int data; node * next; /指向后续节点 node * pre; /指向前面的节点 ;,2020/9/4,23,9.3.1 双向链表的定义,双向链表的例子： 双向链表一般也由头指针唯一确定 双向链表首尾相接可以构成双向循环链表,2020/9/4,24,9.3.2 双向链表的操作,建立双向链表 新节点链入链尾 原链尾节点的后继指针指向新节点 新节点的前驱指针指向原链尾节点 新链尾节点的后继指针置为空指针 将新节点链入链头 原链头节点的前驱

11、指针指向新节点 新节点的后继指针指向原链头节点 新链头节点的前驱指针置为空指针,2020/9/4,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; ,2020/9/4,26,例子6：编写一

12、个函数，按数据输入的顺序建立双向链表,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 ; ,2020/9/4,27,9.3.2 双向链表的操作,双向链表的遍历 有链首节点，则可以沿着后继指针从头至尾遍历 有链尾节点，则可以沿着前驱指针从尾向头遍历,2020/9/4,28,例子7：编写一个函数，输出双向链表中各节点

13、的data成员的值,void outputBidirList(node * head) cout pre) cout data; if (curNode -next) cout ; curNode = curNode -next; cout endl; return; ,2020/9/4,29,9.3.2 双向链表的操作,在双向链表中插入和删除一个节点 优点：获取插入节点或被删除节点的前驱和后继节点比较方便 注意点：需要维护的指针较多,2020/9/4,30,例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大),node * insertData(int n, node * he

14、ad) node *curNode = head;/ 指向插入点的后节点 node *preNode = NULL;/ 指向插入点的前节点 node *newNode = NULL;/ 指向新建节点 /寻找插入位置 while(curNode != NULL) ,2020/9/4,31,例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大),newNode-data = n; if(preNode=NULL) /链头 newNode-next = curNode; newNode-pre = NULL; if (curNode != NULL) curNode-pre = newN

15、ode; return newNode; if (curNode = NULL) / 链尾 newNode-pre = preNode; preNode-next = newNode; newNode-next = NULL; return head; ,2020/9/4,32,例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大),else /链中 preNode-next = newNode; newNode-next = curNode; newNode-pre = preNode; curNode-pre = newNode; return head; ,2020/9/4,33,例子9：编写函数，在双向链表中查找并删除指定,node * deleteData(int n, node * head) node *curNode = head;/ 指向当前节点 while ( curNode ,2020/9/4,34,例子9：编写函数，在双向链表中查找并删除指定,if