数据结构实验报告-数据结构的程序实现

福建农林大学计算机与信息学院实验报告

数据结构的程序实现

一、 实验目的和要求

1) 进一步了解数据结构的实现策略。 2) 掌握动态结构的静态实现方法。 3) 了解大批量数据的组织策略。 4) 掌握数据结构在问题建模中的应用。 二、 实验内容和原理 实验内容：

编程实现Josephus问题。 实验原理：

【问题描述】设有n个人围坐一圈并由1~n编号。从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数和出列，知道最后一个人出列为止。试设计确定这n个人出列序列的程序。

【解题思路】有问题描述可以很自然地联想到循环列表，用循环列表对Josephus问题建模，可以做到程序世界和问题世界的完全一致性，符合面向对象的设计思想。考虑到反复报数的过程，可选用不带头结点的单循环链表，以避免报数过程中识别头结点的麻烦。由此，程序中可以先构建一个具有n个结点的单循环链表，然后从约定的结点开始1到m计数，计到m时从链表中删除对应结点；接着从被删除结点的下一个结点起计数，知道最后一个结点从链表中删除后结

束。

三、 实验环境 Windows XP系统 visual c++6.0 四、 实验习题：

#include \#include \typedef struct node {int num;

struct node *next; }linklist;

linklist *creat(int n) {linklist*head,*s,*p; int i;

s=(linklist*)malloc(sizeof(linklist)); head=s; s->num=1; p=s;

for(i=2;i<=n;i++)

{s=(linklist*)malloc(sizeof(linklist)); s->num=i; p->next=s; p=s; }

p->next=head; return head; }/*creat*/

linklist *select(linklist *head,int m) {linklist *p,*q; int i,t; p=head;t=1; q=p; do

{p=q->next; t=t+1; if(t==m) {t=0;

printf(\q->next=p->next; free(p); } else q=p;

}while(p->next!=p); head=p;

return(head); }/*select*/ main() {int n,m;

linklist *head;

printf(\scanf(\

printf(\scanf(\head=creat(n);

head=select(head,m);

printf(\}/*main*/

五、 调试过程

六、 实验结果

七、 总结 1） 2） 3）

进一步了解数据结构的实现策略。 掌握动态结构的静态实现方法。 了解大批量数据的组织策略。

4）

掌握数据结构在问题建模中的应用。