没有合适的资源?快使用搜索试试~ 我知道了~
北京理工大学数据结构与算法设计课程结课实验报告
需积分: 0 2 下载量 35 浏览量
2023-08-05
17:44:44
上传
评论 1
收藏 111KB DOCX 举报
温馨提示
试读
49页
共包括四个实验,实验一:采用单向环表实现约瑟夫环;实验二:实现简单计算器;实验三:遍历二叉树与按层次遍历二叉树;实验四:输入 10 个数,编程实现插入排序、快速排序、选择排序三类算法。
资源推荐
资源详情
资源评论
《数据结构与算法设计》实验报告
——实验一
1. 需求分析
采用单向环表实现约瑟夫环。
请按以下要求编程实现:
① 从键盘输入整数 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。
2. 概要设计
数据类型
struct node{
int data;
struct node* next;
}; //定义一个链表结点
typedef struct node NODE;//NODE 为结点
typedef struct node* PNODE;//PNODE 为结点指针
基本函数
PNODE creat(PNODE head,int num);//以head为指针建立一个环
表,并且有 num 个数据
2. void outlist(PNODE head,int s,int n,int num);//将第 s 个数作为 1,向后
数 n 位输出该节点所对应的数值 并释放该结点,然后将下一个结点看作
1,一直循环输出直到没有数据
主程序流程
开始
输入数据
调用函数 1 建立环
表
调用函数 2 输出数
据
结束
3. 详细设计
数据类型
struct node{
int data;
struct node* next;
}; //定义一个链表结点
typedef struct node NODE;//NODE 为结点
typedef struct node* PNODE;//PNODE 为结点指针
自定义函数部分
PNODE creat(PNODE head,int num){
PNODE q,p;
p=(PNODE)malloc(sizeof(NODE));//申请一块空间
p=head;//让 p 指向 head 所指位置
int i;
for(i=1;i<=num;i++){
q=(PNODE)malloc(sizeof(NODE));//申请一块空间
q->data=i;//赋值为 i
q->next=NULL;//下一个结点为空指针
head->next=q;//将 q 指针放在 head 之后
head=head->next;//head 后移
}
head->next=p->next;//将链表环接起来
}//建立一个数据为 1..num 的环表
void outlist(PNODE head,int s,int n,int num){
int i,j;
PNODE p;
head=head->next;
for(i=1;i<s-1;i++){
head=head->next;
}//使 head 结点指向 s 的前一个结点
for(j=1;j<=num;j++){//每次输出一个数循环 num 次
for(i=1;i<n;i++){
head=head->next;
}//后移 n-1 位
printf("%d ",head->next->data);//输出该结点后一个结点所指数据
p=(PNODE)malloc(sizeof(NODE));//申请一块空间
p=head->next;//p 指向需要删除的结点
head->next=p->next;//将需要删除的结点前后连接起来
free(p);//释放 p 结点空间
}}//将第 s 个数作为 1,向后数 n 位输出该节点所对应的数值 并释放该结点,
然后将下一个结点看作 1,一直循环输出直到没有数据
主函数
int main(){
int num,s,n;
scanf("%d ",&num);
PNODE head;
head=(PNODE)malloc(sizeof(NODE));//申请一块头指针的空间
head->data=-1;
head->next=NULL;//初始化头指针
creat(head,num);//以 head 为指针建立一个环表,并且有 num 个数据
scanf("%d%d",&s,&n);
outlist(head,s,n,num);//将第 s 个数作为 1,向后数 n 位输出该节点所对应的
数值 并释放该结点,然后将下一个结点看作 1,一直循环输出直到没有数据
}
4. 调试分析
在编写程序过程中,发现输出数据除了第一个数据对的上之外,每个数据都
和标准答案有差别,所以就 debug 调试发现,第一次到 s 数之后把他当成 1 了
然后每次都往后走 n-1 个输出出来对应的数据,所以将程序改了一下使其输出的
数据为其指向结点的后一位,程序输出正确结果。
5. 测试结果
输入:10 3 4
输出:6,10,4,9,5,2,1,3,8,7。
输入:20 4 8
输出:11 19 7 16 5 15 6 18 10 3 20 14 13 17 2 9 8 1 12 4
输入: 15 4 5
输出:8 13 3 9 15 6 14 7 2 12 11 1 5 10 4
剩余48页未读,继续阅读
资源评论
haxy685
- 粉丝: 1
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功