第6讲 链表设计及应用.ppt

1、第6讲 链表设计及其应用,一、知识准备 1、结构 结构-构造的数据类型 定义结构 struct node /node为结构类型名 int x; /成员1,占内存4字节(Visual c+编译器中) float y; /成员2,占内存4字节 char a10; / 成员3,占内存10字节 float *b; /成员4,占内存 ? 字节 ; /此种数据类型或该类型的变量占内存 ?字节 void main() / node的定义方式为全局定义 node s，m10，*p；/定义局部结构变量s和m,指针p ;,s.x=12; /一般变量形式访问 s.y=7.86; strcpy(s.a,”LiMing

2、”); coutx=20; /指针形式访问成员 p-y=11.89; strcpy(s-a,”LiMing”); 指针形式访问成员,按正常写法应当是 (*p).x=20; 但这个写法复杂,所以D.Ritche推荐了指针形式另一种写法,即: p-x=20;,2、指针 （1）一种变量，存放其它变量的地址,主要是近指针,所以指针的值非负。变量的地址通过是允许的。问在C中，*p是多少？ （3）指针可能进行的运算 若p是指针，则p+n或p-n(n是整数)允许； 若p、q是同类型指针，则p-q可以，也可做关系运算。,3、预约存储空间(malloc()/free()，new/delete) （1）什么情况下

3、要预约存储空间？ int x=8,*p; p=*x;/p有初值 *p=12; cout“*p=”*p“x=”xendl; 如果有如下程序： int *p; *p=12; /p还未有初值，编译器将出现警告错误！ 解决办法： （2）二种预约存储空间的方法 方法一：,/预约1个整型单元，p指在其首地址上 在C语言中 int *p; p=(int *)malloc(1*sizeof(int); *p=12; 在C+语言中，上述语句可写为 int *p; p=new int; *p=12;,/预约8个整型单元，p指在第1个单元的首地址上 /从键盘输入8个数依次存放在这些单元中 在C语言中 int *p;

4、 p=(int *)malloc(8*sizeof(int); for(i=0;i*(p+i);/或cinpi; 在C+语言中，上述语句可写为 int *p; p=new int8; for(i=0;i*(p+i);/或cinpi; 从内存中清除掉（也称为释放）这些单元，在C语言中用free(p);在C+语言中用delete p(1个单元)或delete p（多个单元）,二、链表的引入 1、康熙的“八宝箱” 2、排序过的数据插入新数据的平均移动次数分析 3、动态数据处理,三、单链表的有关操作 （1）建立单链表 定义结点类型结构如下： struct chain int data; chain *

5、 next; ; 建立如下具有n结点的单链表，要求编写函数 chain *crechain(int *a,int n)，返回为首地址head。 head,chain *crechain(int *a,int n) int i; chain *t; /先建表尾结点 t=new chain ; /预约存储空间 t-data=an-1; t-next=NULL; /表尾结点建立完毕 /下面开始从尾向头，逐个建立结点,for(i=n-2;i=0;i-) /建立后续结点 chain *p; /创建指针 p= new chain; /预约存储空间 p-data=ai; /设置结点数据 p-next=t;

6、t=p; return t; ,（2）将上述单链表改为单循环链表 编写circulachain函数内容。 chain * cir-chain(chain *head)， head为单链表首地址 返回仍为首地址head。 chain *cir-chain(chain *head) chain *p; p=head; while(p-next!=NULL) p=p-next; p-next=head; return head; ,（3）在单循环链表中插入新的结点 void addcirculachain (chain * head,int m,int k ) chain *p,*q,*t; p=h

7、ead,q=p-next; while(q!=head ,(4)在已建好的单链表中删除结点 由学生自己设计函数完成,七、应用举例 例6-1约瑟夫问题 有n个人，围坐一圈，对他们从1开始编号，即1，2，3，.，n，如果从某一个人开始报数，他报数1，按顺时针进行，紧挨的人报数2，再往下的人跟着报3， .，一直报到k，凡报到k的人出列，再往下，继续从1 开始报数，2，3，.，一直报到k，凡报到k的人出列。试输出该问题中顺序出列的人的编号。,我们先用一般方法思想求解本问题，然后再用单循环链表求解本问题。 （1）一般方法 分析：该问题的轮廓是. 设计： void joseph(char *a,int n

8、,int b,int k)；其中，为了简便，数组a存放每个 人的编号，采用a1=1,a2=2,a3=3,.，n为最后一个人的编号， b为开始报数的人的位置， k是每次最后的报数号。,void joseph( char *a,int n,int b,int k) int i; while(n) b=（b+k-1)%n; if(b=0) printf(%c ,_); b=1; else printf(%c ,ab); b=_; for(i=_;i=n;i+)ai-1=a_; n=_; ,（2）链表方法求解 a、建立一个该问题的单循环链表； 确定基本结点的结构类型 struct chain char

9、 code2; chain * next; ; 用函数buildchain将单循环链表建立好后，返回首地址head b 、设计自定义函数 void joseph(chain *head,int n,int b,int k) 输出head为首地址的人圈中、从b开始喊号到k出列的人的编号。因为预先已将人的编号都已建立在单循环链表中，所以形参只需要首地址。,#define count 4 #include #include typedef struct node char data; struct node *link; jd; void main() jd *h,*p,*q; int i; void joseph(jd *); / 单循环链表将生成 h=(jd *)malloc(sizeof(jd); /首结点 h-data=65; /65是A的ASCII值 q=h;,for(i=74;i=66;i-) p=(jd *)malloc(sizeof(jd); p-data=i,p-link=q; q=p; h-link=p; /*cicle the list*/ joseph(h); ,void joseph(jd *head) jd *p,*q,*t1,*t2; int i; p=