《数据结构与算法设计》
实验报告
——实验一
学院：
班级：
学号：
姓名：
一、实验目的
第一题利用单向环表实现约瑟夫环。
第二题归并顺序表。
二、实验内容
第一题采用单向环表实现约瑟夫环。
请按以下要求编程实现：
①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。
②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。
例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。
第二题选作：归并顺序表。
请按以下要求编程实现：
①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。
②将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka 和linkb为空表。输出linkc。
③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。
例如：linka输入为：10 20 30 40 50 0
linkb输入为：15 20 25 30 35 40 45 50 0
归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50
删除重复后的linkc为：10 15 20 25 30 35 40 45 50
三、程序设计
1、概要设计
第一题为了实现程序功能，应当建立单向环表来寄存信息及结点，通过查找结
点来完成相应的操作。顺序是：输入数据--建立头结点--建立环表--循环输出和删除结点。
程序流程
开始
输入数据（m，s，n）
创建环表
计算处理
输出环表
结束
第二题为了实现程序功能，应当建立单向链表来寄存信息及结点，顺序是：输入数据--建立头结点--建立链表--合并链表--输出链表--删除重复数据--输出链表。
程序流程
开始
输入链表a和链表b
创建链表
合并链表
输出链表c
删除重复数据
输出链表c
结束
2、详细设计
第一题
#include
#include
//定义结构体
typedef struct LNode {
int data;
struct LNode *next;
}LNode,*LinkList;
//创建具有m个结点的单向环表
void Create(LinkList &l,int m){
LinkList p;
l=(LinkList)malloc(sizeof(LNode));
l->next=NULL;l->data=1;
for(int i=m;i>1;i--){
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(i==m) p->next=l;
else p->next=l->next;
l->next=p;
}
}
//主函数
int main ()
{
int m,s,n,i;
LNode *l,*p,*q;
printf("请输入m s n\n");
scanf("%d %d %d",&m,&s,&n);
Create(l,m);
for(i=1,p=l;i p=p->next; while (m--){ for(i=1;i q=p->next; printf("%d ",q->data); p->next=q->next; //将该结点从环表中消除 p=p->next; free(q); } return 0; } 第二题 #include #include typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //从键盘输入升序排列的整数序列，序列以输入0为结束标记。 void create(LinkList &head){ LinkList p,q; int n; head=(LinkList)malloc(sizeof(LNode)); head->next=NULL; scanf("%d",&n); p=(LinkList)malloc(sizeof(LNode)); p=head; while(n!=0){ q=(LinkList)malloc(sizeof(LNode)); q->data=n; q->next=p->next; p->next=q; p=q; scanf("%d",&n); } } //将链表La和Lb归并为Lc，Lc仍然为升序排列 void paixu(LinkList &La,LinkList &Lb,LinkList &Lc) { LinkList pa,pb,pc,p,q; pa=La->next; pb=Lb->next; Lc=(LinkList)malloc(sizeof(LNode)); Lc->next=NULL; pc=Lc; while(pa&&pb) { if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; } else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; } //对c进行处理，保持升序不变，删除其中重复的整数，对重复的整数保留一个void shanchu(LinkList &c){ LinkList p,q; p=(LinkList)malloc(sizeof(LNode)); q=(LinkList)malloc(sizeof(LNode)); p=c->next; while(p->next!=NULL){ if(p->data==p->next->data){ q=p->next; p->next=q->next; } else p=p->next; } } //输出链表c void output(LinkList &c){ LinkList p; p=(LinkList)malloc(sizeof(LNode)); p=c->next; while(p->next!=NULL){ printf("%d ",p->data); p=p->next; } printf("%d\n",p->data); } //主函数 int main() { LNode *a,*b,*c; printf("请输入整数序列linka：\n");create(a); printf("请输入整数序列linkb：\n");create(b); paixu(a,b,c); free(a); free(b); //归并完成后，a和b为空表 output(c); shanchu(c); output(c); return 0; } 四、程序调试分析 第一题计数到第n个结点时应定位在n-1个节点，这样才能删除第n个节点。第二题将链表a和链表b合并时易出错，需要理好关系，可以借助画图试思路更清晰。 体会当程序运行出现问题的时候，一定要仔细一步步去调试，很有可能一个很小的漏洞就导致整个程序的错误。 五、程序运行结果与分析 第一题 测试用例1 输入：10 5 4 输出：8 2 6 1 7 4 3 5 10 9 测试用例2 输入：15 3 4 输出：6 10 14 3 8 13 4 11 2 12 7 5 9 1 15 第二题 测试用例1 输入：10 20 30 40 0 10 15 20 25 30 0 输出：10 10 15 20 20 25 30 30 40 10 15 20 25 30 40 测试用例2 输入：100 200 300 400 0 150 200 300 350 400 0 输出：100 150 200 200 300 300 350 400 400 100 150 200 300 350 400 六、用户使用说明书 第一题 1、本程序的运行环境为Windows操作系统下的DEV c++。 2、在VC环境下打开程序后，按要求键入m,s,n的值，敲击“回车符”，即可以显示要求的结果。 第二题 1、本程序的运行环境为Windows操作系统下的DEV c++。 2、在VC环境下打开程序后，从键盘输入两个升序排列的整数序列a和b，每个序列以输入0为结束标记，敲击“回车符”，即可以显示要求的结果。 七、程序清单 第一题注释见程序详细设计。 第二题注释见程序详细设计。
相关主题
文本预览