DS02线性表讲解.ppt

free()函数 原型：extern void free(void *p);??用法：#include alloc.h??功能：释放指针p所指向的的内存空间。??说明：p所指向的内存空间必须是用calloc,malloc,realloc所分配的内存。 循环链表的应用——约瑟夫问题(Josephus) 典型题目是猴子选大王。 题目描述：n只猴子要选大王，选举方法如下：所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第1 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。 输入数据：猴子总数num，出局数字m 输出数据：猴子的出队序列和猴子大王的编号 循环链表的应用——约瑟夫问题(Josephus) （1）算法设计 思想：创建循环链表，结点数值由1到num; 循环链表的应用——约瑟夫问题(Josephus) （1）算法设计 关键步骤： ① 创建循环链表：1-2-3-4-5-……-num-1 ② 设置计数器counter=1,从1开始计数，到m前一个节点m-1处停止计数。 ③ 删除第m个节点，输出被淘汰猴子的号码。 ④ 重复②③操作，直到剩余一个结点为止。输出最后一个结点的编号即为“大王”。 循环链表的应用——约瑟夫问题(Josephus) 循环链表的应用——约瑟夫问题(Josephus) 从表中任一结点出发均可找到表中其它结点。 讨论：在循环链表中多采用尾指针？为什么？ 结论：如果采用尾指针，则查找第一个结点和最后一个结点都容易。 循环链表的优点 a1 a2 … an head 循环链表 4、基本操作——循环链表的合并 （1）算法设计 （2）算法 p=RA-next; RA-next = RB-next-next; free(RB-next); RB-next=p; a1 an RA b1 bn RB a1 an b1 bn RB （3）算法分析——时间复杂度 该算法的时间复杂度为：O(1) 设两个链表La=(a1,a2,...,an)和Lb=(b1,b2,...bm)，讨论如下问题： (1) La、Lb都是带头结点的单链表，如何实现将Lb接在La之后？时间复杂度是多少？ (2) La、Lb都是带头结点头指针的单循环链表，如何实现将Lb接在La之后还形成一个循环链表？时间复杂度是多少？ (3) La、Lb都是带头结点尾指针的单循环链表，如何实现将Lb接在La之后还形成一个循环链表？时间复杂度是多少？ 单链表和循环链表操作比较 结论： (1) La、Lb都是带头结点的单链表，Lb接在La之后，时间复杂度是 O(length(La))。 (2) La、Lb都是带头结点头指针的单循环链表，实现将Lb接在La之后还形成一个循环链表，时间复杂度是多少 O(length(La)+length(Lb))。 (3) La、Lb都是带头结点尾指针的单循环链表，实现将Lb接在La之后还形成一个循环链表，时间复杂度是 O(1)。 单链表和循环链表操作比较 //单链表的创建 LinkList Creat_LinkList(int n ) { LNode *s,*r;int i ; LinkList H = (LinkList) malloc(sizeof(LNode)); H-next = NULL; r=H; for(i=1;i=n;i++) { s = (LinkList) malloc(sizeof(LNode)); s-data=i; s-next = r-next; r-next = s; r=s; } r-next=H; return r; } 链表 一、线性链表（单链表） 1、构造思想 结点由存放信息的的数据域和存放其直接后继的地址的指针域组成。 data link 结点 a1 a2 a3 an an-1 ^ … list 链表 li 250 zhen 165 qian 240 wu 120 zhao 130 wang NULL shun 110 zhou 140 存储地址 数据域 指针域 110 120 130 140 160 165 240 250 160 头指针