数据结构实验报告电梯模拟.doc

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.05M 资料格式：doc 举报版权申诉

zhucyalfer-2107168-4744300845170849570.doc.pdf-第1页.png

第1页 / 共6页

zhucyalfer-2107168-4744300845170849570.doc.pdf-第2页.png

第2页 / 共6页

zhucyalfer-2107168-4744300845170849570.doc.pdf-第3页.png

第3页 / 共6页

zhucyalfer-2107168-4744300845170849570.doc.pdf-第4页.png

第4页 / 共6页

zhucyalfer-2107168-4744300845170849570.doc.pdf-第5页.png

第5页 / 共6页

zhucyalfer-2107168-4744300845170849570.doc.pdf-第6页.png

第6页 / 共6页

文本预览

数据结构实验报告班级：通信工程 0805 姓名：鲁勤学号：U200813004

题目：约瑟夫环摘要：编号为 1，2，……，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。该程序用单向循环链表存储结构模拟此过程来求出列顺序，并按照出列的顺序印出各人的编号。思路和原理：定义一个结点结构体代表一个人，该结构体分为三部分，其中两个数据域用来存储结点序号和结点密码（均为正整数），最后一个指针域用来存储该结点所指向的下一个结点的位置，将 n（人数）个结点通过指针域连接起来形成单向循环链表。报数时，一开始，指针指向队尾，当指定一个报数上限值 m 时，通过 m-1 次指针赋值循环将指针移动到报数为 m-1 的结点位置上，也就是要求出列的结点的前一个结点，然后输出指针所指结点的下一个结点的序号并将其对应的密码赋给 m；然后将要求出列的结点的下个指针位置赋给当前指针所指位置，这样该结点就不在链表里面了，同时链表长度即人数 n 减一。当链表里至少有两个结点时继续循环 n-1 次，每次均模仿上述过程，直至循环链表里只剩下一个结点时，循环退出，直接输出该结点的序号即可，这样约瑟夫环的建立和报数过程就完成了。算法设计： 1. 单向循环链表结点存储结构的定义： typedef int DataType; typedef struct linknode { DataType data1; DataType data2; linknode * next; }Node; 2. 单向循环链表的建立： Node *head, *p, *q,*r; int i,x,n; printf("input the number of people:"); scanf("%d",&n); head=p=(Node *)malloc(sizeof(Node)); if(p==NULL) { printf("no enough memory"); exit(1);

} printf("input the password of each person:"); scanf("%d",&x); p->data1=1; p->data2=x; for(i=0;idata1=i+2; q->data2=x; p->next=q; p=q; } p->next=head; 3.报数过程： int m,j; printf("input the origin value of upper limit:"); scanf("%d",&m); r=p; while(r->next !=r) { for(j=0;jnext; } printf("%d\t",r->next->data1); m=r->next->data2; r->next =r->next ->next ; n--; } printf("%d\n",r->data1); 具体实现： #include #include typedef int DataType; typedef struct linknode

{ DataType data1; DataType data2; linknode * next; }Node; void main() { Node *head, *p, *q,*r; int i,x,n; printf("input the number of people:"); scanf("%d",&n); head=p=(Node *)malloc(sizeof(Node)); if(p==NULL) { printf("no enough memory"); exit(1); } printf("input the password of each person:"); scanf("%d",&x); p->data1=1; p->data2=x; for(i=0;idata1=i+2; q->data2=x; p->next=q; p=q; } p->next=head; int m,j; printf("input the origin value of upper limit:"); scanf("%d",&m); r=p; while(r->next !=r) { for(j=0;j

{ r=r->next; } printf("%d\t",r->next->data1); m=r->next->data2; r->next =r->next ->next ; n--; } printf("%d\n",r->data1); } 实验结果：测试数据：m 的初值为 20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4，首先 m 的值为 6（正确的出列顺序应为 6，1，4，7，2，3，5）分析： 1. 时间复杂度：单向循环链表建立过程中循环了 n-1 次；报数过程中，有 n-1 次报数，每次报数指针赋值的操作要循环 m-1 次；这两部分相加得到 m（n-1）次基本循环体，则该程序的时间复杂度为 O（mn）。 2. 空间复杂度：一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量、和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息和辅助空间。对于本程序输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，而该程序没有用到额外的辅助空间，所以，这个程序的空间复杂度为 0。结论：

通过约瑟夫环的实习，我们掌握了线性表的基本操作在链式存储结构上的实现，同时也了解到指针的强大作用。这个程序是用单向循环链表结构来实现的参考文献： 1.《数据结构（C 语言版）》严蔚敏吴伟民编著 2.《标准 C 语言程序设计及应用》周纯杰刘正林何顶新周凯波编著

分享到：

赞收藏

资料库

数据结构实验报告电梯模拟.doc

相关推荐

开发技术

热门标签

最新资料