数据结构实验

1、本文格式为word版，下载可任意编辑数据结构实验 试验一、约瑟夫环问题 试验目的 1）把握线性表的存储结构； 2）学会利用线性表解决实际问题。 试验内容 编号为 1，2，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开头任选一个密码 m，从第一个人开头按顺时针方向自 1 开头挨次报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开头重新从 1 挨次报数，如此下去，直到全部人全部出列为止。 试验要求 1）建立模型模拟约瑟夫环问题，确定存储结构，用单链表实现； 2）输入 m 的初值，人数 n，输入每个人的密码；出圈的挨次请依

2、次输出。 数据结构分析 由于约瑟夫环问题本身具有循环性质，考虑采纳循环链表。链表的每个结点有两个域，分别是序号和其所持有的密码。建立单链表后，依据算法找到相应的结点，对找到的结点进行输出，并把该结点从链表中删除，再释放该结点空间。 试验程序 #include malloc.h / 试验 数据: 总人数：6 初始密码：18 个人密码：2,1,4,2,4,8 #include stdio.h / 出圈挨次：6,3,2,4,1,5 typedef struct lnode int id,password; struct lnode *next; lnode, *linklist; void main

3、() int n,m,e,i,flag=1; linklist l,p,q,s; printf("请输入总人数 n：n'); scanf("%d',n); printf("请输入初始密码 m：n'); scanf("%d',m); for(i=1;i=n;i+) / 创建循环单链表 s=(linklist)malloc(sizeof(struct lnode); / 申请存放一个结点的空间 if (i=1) l=s; p=s; / i=1 创建结点，i1 链接结点 printf("请输入第%d 个人的密码：n&#

4、39;,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;im;i+) q=p; p=p-next; /搜寻第 m 个人 if (p=q) flag=0; /表示全部查找完毕 s=p; / 找到第 m 个人出列 q-next=p-next; p=p-next; / 指出下一次第一个要报数的人 m=s-password; / 更新 m

5、值 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 值，输出汉诺塔移动步骤。 数据结构分析 上述两个问题，可以利用栈的后进先出特性解决，用递归法来编写程序。 试验程序

6、 #include stdio.h 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(&

7、quot;%d',d); printf ("十进制%d 转换%d 进制的结果是：',n,d); conversion(n,d); _ #include stdio.h void hanoi(int m,char x,char y,char z) / 汉诺塔，将塔座 x 上 m 个圆盘按规章， / 通过塔座 y，搬动到塔座 z。 if (n=1) printf("把%d 号圆盘从塔座%c 移到塔座%cn',1,x,z); else hanoi(n-1,x,z,y); printf("把%d 号圆盘从塔座%c 移到塔座%cn',n,x,

8、z); hanoi(n-1,y,x,z); void main() int m; char x=x, y=y, z=z ; printf ("请输入汉诺塔圆盘数目，不超过 10n'); scanf("%d',m); hanoi(m,x,y,z); 试验三、串的模式匹配 试验 目的 1）熟识和理解串的规律结构和物理存储结构； 2）学会利用 kmp 算法验证字符串的模式匹配。 试验内容 输入主串 s 和模式串 t，用堆安排存储方式存储串，并将串 s 和串 t 输出；然后计算模式串 t 的 next 函数，并将计算结果输出；最终进行模式匹配，输出从主串 s 的第

9、1 个字符起，主串 s 和模式串 t 首次匹配的字符位置。 试验要求 1）输入主串 s 和模式串 t； 2）采纳克努特莫里斯普拉特（简称 kmp 算法），实现模式匹配。 数据结构分析 当主串 s 中第 i 个字符与模式串 t 中第 j 个字符"失配'时，考虑主串中第 i 个字符（i指针不回溯）应与模式串 t 中哪个字符比较。通过对模式匹配过程特点的分析，对模式串 t构造 next 函数，设模式串中某个字符的 next 函数值为 k，则当"失配'发生时，匹配仅需从模式中第 k 个字符与主串 s 中第 i 个字符比较起连续进行。 试验程序 #include st

10、dio.h #include string.h int index_kmp(char *s, char *t, int pos) int i,j,next20; i=0; j=-1; next0=0; while(istrlen(t) if (j=-1 | ti=tj) i+; j+; if (ti=tj) nexti=nextj; else nexti=j; else j=nextj; i=pos; j=0; while(si tj) if (j=-1 | si=tj) i+; j+; / 连续比较后续字符 else j=nextj; / 模式串向右移动 if (jstrlen(t) return i-strlen(t); else return -1; / 匹配胜利，返回位置；否则返回-1 void main() char s100,t20; int pos; printf("请输入主串 s：n')