数据结构与算法设计实验一

1、精选优质文档-倾情为你奉上数据结构与算法设计实验报告实验一学院：班级：学号：姓名：1、 实验目的第一题 利用单向环表实现约瑟夫环。第二题 归并顺序表。二、实验内容 第一题 采用单向环表实现约瑟夫环。 请按以下要求编程实现： 从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，m。 从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 例如，

2、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 归并后的l

3、inkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50 3、 程序设计1、 概要设计第一题 为了实现程序功能，应当建立单向环表来寄存信息及结点，通过查找结点来完成相应的操作。顺序是：输入数据-建立头结点-建立环表-循环输出和删除结点。 程序流程开始输入数据（m，s，n）创建环表计算处理 输出环表结束 第二题 为了实现程序功能，应当建立单向链表来寄存信息及结点，顺序是：输入数据-建立头结点-建立链表-合并链表-输出链表-删除重复数据-输出链表。程序流程开始输入链表a和链表b创建链表合

4、并链表 输出链表c删除重复数据 输出链表c结束2、 详细设计第一题#include <stdio.h>#include <stdlib.h>/定义结构体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=(L

5、inkList)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 nn");scanf("%d %d %d",&m,&s,&n);Create(l,m);for(i=1,p=l;i<s;i+) /寻找起始结点s p=p->next;while (m-)for(i=1;i

6、<n-1;i+) /计数到第n个结点时，输出该第n结点对应的编号 p=p->next; q=p->next;printf("%d ",q->data);p->next=q->next; /将该结点从环表中消除p=p->next;free(q);return 0;第二题#include <stdio.h>#include <stdlib.h>typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;/从键盘输入升序排列的整数序列，序列以输入0

7、为结束标记。 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("

8、%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=p

9、a->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

10、;p->next=q->next;else p=p->next;/输出链表cvoid 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("%dn",p->data);/主函数int main() LNode *a,*b,*c;printf("请输入整数序列linka：n"

11、;);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;4、 程序调试分析 第一题 计数到第n个结点时应定位在n-1个节点，这样才能删除第n个节点。第二题 将链表a和链表b合并时易出错，需要理好关系，可以借助画图试思路更清晰。体会 当程序运行出现问题的时候，一定要仔细一步步去调试，很有可能一个很小的漏洞就导致整个程序的错误。五、程序运行结果与分析第一题 测试用例1 输入

12、：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