数据结构实验一约瑟夫(Joseph)问题

2011～2012学年 第 二 学期 级 计算机 专业

班级： 学号： 姓名：

实验一 线性表及其应用

一、 实验题目：

线性表及其应用——约瑟夫环 二、 实验内容：

1．设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列，且各自链表内无重复的结点，要求： （1）建立两个按升序排列的单链表ha和hb。

（2）将单链表ha合并到单链表hb中，且归并后的hb链表内无重复的结点，结点值仍保持从小到大顺序排列。

（3）输出合并后单链表hb中每个结点的数据域值。 代码： 实验结果：

struct Node { int data; Node* next; }; typedef Node Slink; void create(Slink* h); void show(Slink* h);

void merge(Slink* ha,Slink* hb); #include void main() {

cout<<\"创建链表ha\"<cout<<\"链表ha的节点排列\"<cout<<\"创建链表hb\"<cout<<\"链表hb的节点排列\"<cout<<\"合并后 链表hb的节点排列\"<第 1 页 共 8 页

void create(Slink* h) {

if(!h) return; int n=0;//节点总数 int j=0;//累计创建结点个数

cout<<\"请输入创建节点的个数\"<>n;

Node* F=h;//F始终指向tou节点

Node* pre=h;//pre始终指向要插入位置的前一个节点 while(jvoid merge(Slink* ha,Slink* hb)

第 2 页 共 8 页

Node* p=new Node;

cout<<\"请输入节点的数据\"<>p->data; //链表为空时 if(!F->next ) { F->next =p; }

//链表不空时 while(pre->next )

{ if(p->data next ->data ) }

if(!pre->next ) { pre->next =p; }

p->next =NULL; j++;

{ p->next =pre->next ; }

else if (p->data ==pre->next ->data)

{ cout<<\"该值已存在，请重新输入\"<pre=pre->next ;

break; pre->next =p; pre=h; j++; break; p->next =NULL; j++; continue;

{ //p遍历ha,q遍历hb

Node * p=ha->next ; Node * q=hb->next ;

//pw始终指向新生成链表的最后一个结点 Node * pw=hb; while(p&&q)

{ if((p->data)<(q->data)) { pw->next=p; p=p->next; pw=pw->next; continue;

}

if((p->data)>(q->data)) { pw->next=q; q=q->next; pw=pw->next; continue; }

if((p->data)==(q->data)) { pw->next=q; p=p->next; q=q->next; pw=pw->next; continue; }

} while(p) { pw->next=p; p=p->next; pw=pw->next;

} while(q) { pw->next=q; q=q->next; pw=pw->next;

}

pw->next=NULL; void show(Slink* h) {

Node* p=h->next ; while(p )

{ cout<data <<\" \"; p=p->next ;

}

第 3 页 共 8 页}

cout<2．约瑟夫（Joseph）问题。具体描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

要求：利用不带头结点的循环单链表存储结构模拟此过程，按照出列的顺序输出各人的编号。

三、 程序源代码：

struct person { int id; };

void show(int n,person* head); #include

第 4 页 共 8 页

int password; person* next;

void main() { person head;

head.next =&head; person* T=&head; //创建节点

cout<<\"请输入创建节点的个数\\n n=\";

int n; cin>>n;

int i;

for(i=0;i{ person* p=new person; }

p->id =i+1;

cout<<\"请输入第\"<>p->password ; p->next =T->next ; T->next =p; T=p;

// if(T->next ==&head) //此句证明T指向最后一个节点

//cout<<\"dddddddddddddddddddddddddddd\"<person* F=head.next ; //F指向第一个节点 ，或者始终指向要删除的节点 T->next =F; //T指向最后一个节点 或者指向要删除节点的前一个节点 //报数输出

person* q=NULL; //始终指向要删除的节点

int j=1; int count;

while(j{ cout<<\"请输入第一个节点的上限\"<cin>>count;

cout<<\"报数出列序列为 ：\"<//当密码为1时，即上限为1时

if(count==1) { q=F;

第 5 页 共 8 页

T->next =F->next ; F=T->next ;

count=q->password ; cout<id<<\" \" ; delete q; j++; continue;

}

//当只剩一个节点时 if(j==n)

{ cout<id ; break;

}

//当密码大于1时，即每次报数上限大于1时 }

void show(int n,person* head) { person* T=head; int h=n;

cout<<\"节点ID\"<<\" \"<<\"对应密码\"<{ cout<next ->id <<\" \"<next ->password <next ;

h--; }

cout<for(int k=1;count>k;k++) { T=F;F=F->next ; } q=F;

T->next =F->next ; F=T->next ;

count=q->password ; cout<id<<\" \"; delete q; j++;

} }

第 6 页 共 8 页

四、 测试结果：

五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）

注：内容一律使用宋体五号字，单倍行间距

通过本次试验，我更加熟悉结构体定义，使用，和指针使用。

在做实验过程中，一定要有清晰的思路，即算法要心里想明白。

此外，还有做到代码简练，实现简单，步骤容易看懂。这是我的缺点，在今后编程中我一定会勤加练习，尽量用简单的代码实现较多的功能。

第 7 页 共 8 页

第 8 页 共 8 页