1、数据结构实验实验一、约瑟夫环问题 实验目的 1)掌握线性表的存储结构; 2)学会利用线性表解决实际问题。实验内容 编号为 1,2,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个密码 m,从第一个人开始按顺时针方向自 1 开始顺序报数,报到 m 时停止报数。报 m 的人出列,将他的密码作为新的 m 值,从他在顺时针方向上的下一个人开始重新从 1 顺序报数,如此下去,直到所有人全部出列为止。实验要求 1)建立模型模拟约瑟夫环问题,确定存储结构,用单链表实现; 2)输入 m 的初值,人数 n,输入每个人的密码;出圈的顺序请依次输出。数据结构分析 由于约瑟夫环问题本身
2、具有循环性质,考虑采用循环链表。链表的每个结点有两个域,分别是序号和其所持有的密码。建立单链表后,根据算法找到相应的结点,对找到的结点进行输出,并把该结点从链表中删除,再释放该结点空间。实验程序 #include / 实验 数据: 总人数:6 初始密码:18 个人密码:2,1,4,2,4,8 #include / 出圈顺序:6,3,2,4,1,5 typedef struct LNode int id,password;struct LNode *next; LNode, *LinkList;void main() int n,m,e,i,Flag=1;LinkList L,p,q,s;pri
3、ntf(“请输入总人数 n:n”);scanf(“%d”,&n);printf(“请输入初始密码 m:n”);scanf(“%d”,&m);for(i=1;i1 链接结点 printf(“请输入第%d 个人的密码:n”,i);scanf(“%d”,&e);s-id=i;s-passwoed=e;p-next=s;p=s; s-next=L;/ 构成循环链表 p=q=L;/约瑟夫环问题-报数,依次出列 while(Flag) printf(“出圈顺序依次为:n”);for(i=1;inext; /搜索第 m 个人 if(p=q)Flag=0;/表示全部查找完毕 s=p;/ 找到第 m 个人出列
4、q-next=p-next;p=p-next;/ 指出下一次第一个要报数的人 m=s-password;/ 更新 m 值 printf(“第%d 个人出列,密码:%dn”,s-id,s-password);free(s);实验二、数制转换和汉诺塔 实验目的 1)掌握栈的逻辑结构和物理存储结构; 2)学会利用栈的特点解决实际问题。实验内容 1)将一个非负的十进制数 n 转换成 d(范围 236)进制数。2)实现 m(不超过 10)层的三柱汉诺塔移动方案。实验要求 1)输入 n 和 d,确定存储结构,输出 d 进制数,大于 10 的数,用对应的英文字母表示; 2)输入 m 值,输出汉诺塔移动步骤。数据结构分析 上述两个问题,可以利用栈的后进先出特性解决,用递归法来编写程序。实验程序 #include void conversion(int n,int d)/ 十进制转换为 d 进制 if(n=0)return;conversion(n/d,d);if(n%d 10)printf(“%d”,n%d);else printf(“%c”,(char)(n%d+55); void main() int n,d;printf(“请输入一个非负十进制数n”);scanf(“%d”,&n);printf(“请输入需要转换的进制数n”);scanf(“%d”,&d);printf(“十进
《数据结构实验.doc》由会员分享,可在线阅读,更多相关《数据结构实验.doc(5页范文模板文档)》请在优智文库上查找。