数据结构上机实验报告1.doc

广东工业大学实验报告 ___自动化 _学院___网络工程__专业_3__班 学号_3111001381_姓名__何宇航 ___ 成绩评定_______ 教师签名 许亮 实验__一__题目___约瑟夫环_______________ 课程名称 数据结构A PAGE PAGE 1 一．实验目的 1.利用单向循环链表存储结构模拟循环过程，按照出列的顺序输出各个人的编号。 2.测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，8，4，输出结果。 二．实验内容 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 三．实验步骤（可选） 输入数据：建立输入处理输入数据，输入m的初值n ，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的序列输出。 详细设计代码：#includeiostream using namespace std; #define N 7 typedef struct node { int data; int sercet; struct node *next; }ListNode; typedef ListNode *LinkList; LinkList InitRing (int n,LinkList R,int a[N]) //建立单循环链表的函数 { ListNode *p,*q; int i; R=q=(ListNode *)malloc(sizeof(ListNode)); for(i=0;in-1;i++) { p=(ListNode *)malloc(sizeof(ListNode)); q-data=i+1; q-sercet=a[i]; q-next=p; q=p; } p-data=n; p-sercet=a[n-1]; p-next=R; R=p; return R; } LinkList Delete(int n,LinkList R,int k) //删除数到预设号码的人 { int i,j; ListNode *p,*q; p=R; for(i=1;in;i++) { for(j=1;jk;j++) p=p-next; q=p-next; p-next=q-next; coutq-data ; k=q-sercet; free(q); } R=p; coutthe last is :p-data; return R; } void main() //主函数 { LinkList R; int n,i,m; coutinput the number of the man :; cinn; coutinput m:; cinm; int a[N]; cout请输入密码依次为:endl; for(i=0;in;i++) cina[i]; cout被删除的顺序是：; R=InitRing (n,R,a); R=Delete(n,R,m); coutendl; } 四．实验的结果及分析。 实验输出值满足预期。 五．实验中出现的问题、解决方法和心得体会 1.建立单向循环链表时没为链表分配初始的存储空间时R=q=(ListNode *)malloc(sizeof(ListNode)); 2.要注意空表和非空表的界限。