《C语言综合实验》3链表.ppt

《《C语言综合实验》3链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言综合实验结构体与链表结构体应用举例N个孩子围成一圈，并给他们依次编号，老师指定从第start个孩子开始报数，报到第m个孩子出列；然后从下一个孩子再开始报数，依次重复下去，直到所有的孩子都出列。试求孩子出列的顺序，即约瑟夫（Josephus）问题。分析：由于问题本身的数据构成一个闭合的环，用结构体数组来构成一个静态环行链来表示此闭合环。structchildren{intnum;charnext;}link[MAX];孩子自身的号码下一个孩子的号码解题方法：只需沿着next连接成的环行链不带重复计数到m，使对应的num所在的节点从环行链中摘下（出列）；

2、当环中的num成员的值为0时，表示该节点摘下，以后不再参加计数，直至节点全部摘完为止。数据结构：Num和next一起构成一个整体，成为环行链中的一个节点（即结构体数组link中的一个元素）#include#defineMAX100voidmain(){intcount,i,k,m,n,start;structchildren{intnum;charnext;}link[MAX];printf("请输入参加游戏孩子的人数(1~%d)：",MAX-1);scanf("%d",&n);printf("请输入起始号码：");scanf

3、("%d",&start);printf("请输入每次所数人数：");scanf("%d",&m);/*建立闭合环*/for(i=1;i<=n;i++){link[i].num=i;if(i==n)link[i].next=1;elselink[i].next=i+1;}/*确定第一个参加计数的前一个孩子的号码*/if(start==1)k=n;elsek=start-1;printf("孩子出列顺序为：");for(count=0;count

4、数的孩子的号码*/if(link[k].num!=0)++i;/*已出列的孩子不参加计数*/}printf(“%5d”,link[k].num);/*输出应出列的孩子的号码*/link[k].num=0;/*标明其已出列*/}}利用结构体和指针处理动态链表若用户使用引用自身的结构体，就可以形成一个动态链，真正做到摘去一个节点。动态结构体中的每一个节点由两部分构成：数据项和指针项。数据项存放有关节点自身的数据，指针项存放与该节点有关的其他节点的地址。通过指针将若干个同类结构体连接起来。structchildren{intnum;structchildren*

5、next;};链表的表示和实现（1）链表的表示（2）链表的实现1)链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率（1）链表的表示例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）链表存放示意图如下：结点：数据元素的存储映像。由数据域和指针域

6、两部分组成；链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head2)与链式存储有关的术语：头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据

7、域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。示意图如下：答：讨论.如何表示空表？无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHO

8、U25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一