数据结构实验报告约瑟夫环.docx
《数据结构实验报告约瑟夫环.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告约瑟夫环.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构实验报告约瑟夫环
数据结构实验报告
专业:
计算机科学与技术
班级:
计算机09-2
姓名:
林嘉俊
学号:
31
评分:
指导老师:
许波
完成时间：
2011/3/14
实验一：
约瑟夫问题
1.问题描述：
设有编号为1、2，…,n（n>0）的n个人围成一圈，从约定编号k（1如此反复下去，直到所有人出圈。
当任意给定n和m时，设计算法求n个人出圈的次序。
2.基本要求：
（1）建立模型，确定存储结构
（2）对任意n个人,密码为m，起始报数人为k，实现约瑟夫问题。
（3）输入：
m、n、k可在程序中定义，或以交互式从键盘输入。
（4）输出：
m、n、k的值及出圈序列。
3.源程序：
#include
usingnamespacestd;
structLinkNode
{
intpwd;//每个人手中的密码，即轮到谁就按手中的密码排除
intNum;//对每个人进行编号
structLinkNode*next;
};
intmain（）
{
inti=0;intn,k;
cout<<"请输入人数n=";
cin>>n;
cout<<"请输入初始报数编号k=";
cin>>k;
cout<<"请依次输入每个人的密码（多少个人就多少个密码）：
"<<"\n";
inta[100];
for（i=0;icin>>a[i];
LinkNode*L,*p;
L=newLinkNode;
L->next=NULL;
for（i=n;i>0;i--）
{p=newLinkNode;
p->pwd=a[i-1];
p->Num=i;
p->next=L->next;
L->next=p;
}
p=L;
cout<cout<<"人数n为：
"<cout<cout<<"起始报数人k="<cout<cout<<"每人的密码为";
for（i=0;icout<cout<cout<cout<<"最后结果为：
"<while（n>0）
{
for（i=1;i{
p=p->next;
if（p->next==NULL）
{
p->next=L->next;
}
}
LinkNode*temp;
temp=p->next;
cout<Num<<" ";
p->next=temp->next;
k=temp->pwd;
free（temp）;
n--;
}
cout<return0;
}
4.运行结果：
实验二：
有序表合并
1.问题描述：
把两个有序表归并为一个有序表。
2.基本要求：
（1）设计表的存储结构
（2）设计归并算法
（3）输入：
可以程序定义或键盘输入
（4）输出：
显示两个有序表和归并后的有序表
3.源程序：
#include
usingnamespacestd;
structnode//链表节点
{
intvalue;
node*next;
};
voidinsertNode（node*head,intvalue）//向链表添加节点
{
node*p=head->next;
if（p==NULL）
{
p=newnode;
p->value=value;
p->next=NULL;
head->next=p;
return;
}
while（p->next!
=NULL）
{
p=p->next;
}
node*tmp=newnode;
tmp->value=value;
tmp->next=NULL;
p->next=tmp;
}
voidprint（node*head）//输出链表节点
{
node*p=head->next;
while（p!
=NULL）
{
cout<value<<"";
p=p->next;
}
cout<}
node*formalMerge（node*headA,node*headB）//合并有序表
{
node*head=newnode;
head->next=NULL;
node*p=headA->next;
node*q=headB->next;
if（p==NULL）
{
returnheadB;
}
if（q==NULL）
{
returnheadA;
}
while（（p!
=NULL）&&（q!
=NULL））
{
if（p->value==q->value）
{
insertNode（head,p->value）;
insertNode（head,q->value）;
p=p->next;
q=q->next;
}
elseif（p->valuevalue）
{
insertNode（head,p->value）;
p=p->next;
}
elseif（p->value>q->value）
{
insertNode（head,q->value）;
q=q->next;
}
}
while（p!
=NULL）
{
insertNode（head,p->value）;
p=p->next;
}
while（q!
=NULL）
{
insertNode（head,q->value）;
q=q->next;
}
returnhead;
}
voidchg2sort（node*head,node*&p）
{
if（head->next==NULL）//没有节点，直接返回
{
return;
}
node*s=head;
while（s->next!
=p）//s指向p的前一个节点
{
s=s->next;
}
//下面的一段找到第一个大于p节点值的节点
node*q=p;
node*r=q;
while（q!
=NULL）
{
if（q->value<=p->value）
{
r=q;//r始终指向q的前一个节点
q=q->next;
}
else
{
break;
}
}
//下面调整指针，其实可以统一写出来，为了阅读清晰把q为NULL和非NULL分开写出来
if（q==NULL）
{
r->next=p;
s->next=p->next;
p->next=NULL;
}
elseif（q!
=NULL）
{
s->next=p->next;
r->next=p;
p->next=q;
}
//由于链表进行了调换，当前链表指针也需要改变
p=s->next;
}
/*两个有序链表进行合并*/
node*merge（node*head1,node*head2）
{
node*head;//合并后的头指针
node*p=head1->next;
node*q=head2->next;
//有一个链表为空的情况，直接返回另一个链表
if（p==NULL）
{
head=head2;
returnhead;
}
elseif（q==NULL）
{
head=head1;
returnhead;
}
//两个都不为空,先确定哪个链表作为合并后的链表
if（（p!
=NULL）&&（q!
=NULL））
{
if（p->valuevalue）
{
head=head1;
}
else
{head=head2;
}
}
node*p_prior;//始终指向p节点的前一个节点
node*q_prior;
while（（p!
=NULL）&&（q!
=NULL））
{
if（p->valuevalue）
{
if（head==head1）
{
p_prior=p;
p=p->next;
}
elseif（head==head2）
{
//进行当前节点值的交换
inttmp=p->value;
p->value=q->value;
q->value=tmp;
chg2sort（head1,p）;//交换元素后的调整
q_prior=q;
q=q->next;
}
}
elseif（p->value==q->value）
{
p_prior=p;
p=p->next;
q_prior=q;
q=q->next;
}
elseif（p->value>q->value）
{
if（head==head1）
{
inttmp=p->value;
p->value=q->value;
q->value=tmp;
chg2sort（head2,q）;
p_prior=p;
p=p->next;
}
elseif（head==head2）
{
q_prior=q;
q=q->next;
}
}
}
if（p!
=NULL）
{
q_prior->next=p;
}
if（q!
=NULL）
{
p_prior->next=q;
}
returnhead;
}
intmain（）
{
inta[5]={1,5,8,11,19};//建立有序链表A
node*headA=newnode;
headA->next=NULL;
for（inti=0;i<5;++i）
{
insertNode（headA,a[i]）;
}
cout<<"有序表a为：
"<print（headA）;
intb[3]={3,4,6};//建立有序链表B
node*headB=newnode;
headB->next=NULL;
for（intj=0;j<3;++j）
{
insertNode（headB,b[j]）;
}
cout<<"有序表b为：
"<print（headB）;
node*head=formalMerge（headA,headB）;
head=merge（headA,headB）;
cout<<"合并后的有序表为：
"<print（head）;
return0;
}
4.运行结果：
实验心得：
约瑟夫问题开始比较难理解，通过算法来转换为程序有一定的困难，需要认真分析每一步。
第二个程序比较长，打起来都比较费时，平时应该加强练习打代码。
升级会员 