数据结构约瑟夫环
实验一 线性表及其应用 一、 实验题目:
线性表及其应用——约瑟夫环
二、 实验内容:
1(设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列,且各自链表内无重复的结点,要求:
(1)建立两个按升序排列的单链表ha和hb。
(2)将单链表ha合并到单链表hb中,且归并后的hb链表内无重复的结点,结点值仍保持从小到大顺序排列。
(3)输出合并后单链表hb中每个结点的数据域值。
2(约瑟夫(Joseph)问题。具体描述是:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新报数,如此下去,直至所有人全部出列为止。试
一个程序求出出列顺序。
要求:利用不带头结点的循环单链表存储结构模拟此过程,按照出列的顺序输出各人的编号。 三、 程序源代码:
1. 实验一源代码及其注释
#include
//定义一个结构体类型
typedef struct A
{
int data ;
A* next;
A* prior;
}stulist;
//对链表进行插入操作
void Insert(stulist * head)
{
int i,j;
bool T=true ;
stulist *p=new stulist;
stulist *q;
cout<<"请输入五个整数"<>j;
q=head->next;
//验证插入的结点是否重复
while (q)
{
第 1 页 共 8 页
if(q->data==j)
{
cout<<"此数已经存在,请重新输入~"<next;
}
while(T)
{ p->data=j;
p->next=head->next;
p->prior=head;
if(head->next)
head->next->prior=p;
else
p->next=NULL;
head->next=p;
T=false;
}
if(i<5)
{p=new stulist;
T=true;
}
}
}
//对链表的所有结点排序
void sort (stulist * head) {
int i, j,temp;
stulist *p=head->next;
for(i=0;i<4;i++)
{ p=head->next;
for(j=0;j<4-i;j++)
{if(p->data>p->next->data)
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
第 2 页 共 8 页
}
//显示链表内所有的结点
void show(stulist * head) {
stulist * p=head->next;
while (p)
{
cout<data<<" ";
p=p->next;
}
cout<next;
q=hb->next;
while(p&&q)
{ //如果ha链表的值小于hb链表的值就把ha的值插入到hb中
if(p->datadata)
{ t=p->next;
p->prior=q->prior;
p->next=q;
q->prior->next=p;
q->prior=p;
p=t;
}
//如果ha链表的值等于hb链表的值,ha链表就指向下一个值进行比较
else if (p->data==q->data)
p=p->next;
//如果ha链表的值大于hb链表的值,hb链表就指向下一个值进行比较
else if(p->data>q->data)
{ r=q;
q=q->next;
}
}
//当hb链表指向最后的结点时,就让ha链表剩下的结点连在hb链表后面
if(q==NULL)
{
r->next=p;
p->prior=r;
第 3 页 共 8 页
}
}
//主函数
void main()
{
stulist ha;
ha.next=NULL;
stulist hb;
hb.next=NULL;
cout<<"请输入ha链表中的数值~"< typedef struct Node {
int number;
int password;
Node * next;
}Stu;
//向链表内插入结点
void IntoData(Stu *lst,int n)
{
Stu *p,*q;
int i;
p= new Stu;
p=lst;
for(i=2;i<=n;i++)
{
q=new Stu;
第 4 页 共 8 页
cout<<"请输入第"<>q->password;
q->number=i;
p->next=q;
p=q;
}
p->next=lst; }
//判断链表中是否只剩下最后一个结点 bool LengthList(Stu * lst)
{
int i=1;
Stu*p=lst->next;
while(p!=lst)
{
i++;
p=p->next;
}
if(i>1)
return true;
else
return false; }
//删除出局结点并输出出局节点的信息 void DelElem(Stu *lst,int n)
{
bool T;
Stu *p,*q,*s;
p=lst;
q=lst;
int m,i,j=1;
cout<<"请输入一个m值:"; cin>>m;
//m=1时,即删除循环链表中的头结点 if(m==1)
{
for(i=1;inext;
}
cout<<"第"<number<<"密码为:"<password<password;
第 5 页 共 8 页
s=p;
q->next=p->next;
p=p->next;
delete s;
}
while(T)
{
for(i=1;inext;
}
cout<<"第"<number<<"密码为:"<password<password;
s=p;
q->next=p->next;
p=p->next;
delete s;
T=LengthList(p);
}
cout<<"最后出局的号码为:"<number<<"密码为:"<password<>n;
if(n<1)
cout<<"您输入的信息有误~"<1)
{
cout<<"请输入第1个人的密码:";
cin>>head->password;
head->number=1;
IntoData(head,n);
DelElem(head,n);
}
//当一个人参加游戏时直接出局
else if(n==1)
{ cout<<"请输入第1个人的密码:";
cin>>head->password;
head->number=1;
cout<<"最后出局的号码为:"<number<<"密码为:"<password<心得体会#、存在的问题及解决问题的
、建议等)
这次上机不仅是对开学以来所学的知识的练习,而且也是很好地锻炼自己的编程能力。在实验过程中发现心中了解的主要算法写出来后与结果不是一回事。
就如第一个题目中总是无法把链表中的重复的数据项结点删除,进过思考后想到在每次输入新结点时就遍历一次链表判断是否有重复值,若存在就重新输入,但是这种方法是比较繁琐的,每次插入新结点就
第 7 页 共 8 页
要遍历一次链表,后来想到用另一种方法就是先输入链表元素,输入完毕后排序时再把重复值删除,但是这种在编程遇到了是链表在输入新结点时无法确定链表的长度,所以我就无法实现这种方法。还有是将两个链表的数值升序后排序到其中一个链表内时,我采用的是双链表结构,很顺利地实现了题目要求。
在第二个题目中采用的是循环单链表结构,但在有人出局时,
信息后删除该结点时,如何判断链表中剩下的结点是否只剩下一个结点(只剩一个结点就不用删除了),我采用的方法是调用函数判断,若是只剩下一个结点时就返回false,否则就返回true;同时在调试过程中出现的错误是如果在第一次输入的m值为 1时,程序就会出错,我现在仍旧不知道是什么原因,我处理的方法是在第一次m等于1时,单独列出来处理,这样结果就正确了。
在实验过程遇到了许多的难题,也使我感到理论知识的重要性。但是我并没有气垒,在实验中发现问题,自己看
,独立思考,最终解决问题。由此通过这次的实验使我不但对理论知识有了更加深的理解,同时对于实际的操作也有了一定的进步。
第 8 页 共 8 页