- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
北理工数据结构实验报告1
《数据结构与算法设计》
实验报告
——实验一
学院:自动化学院
班级:__
学号:__
姓名:____ ____
一、实验目的
1、熟悉VC环境,学习使用C语言实现链表的存储结构。
2、通过编程、上机调试,进一步理解线性表、链表、环表的基本概念。
3、锻炼动手编程,独立思考的能力。
二、实验内容
采用单向环表实现约瑟夫环。
请按以下要求编程实现:
① 从键盘输入整数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。
三、程序设计
1、概要设计
为实现上述程序功能,应用单向环表寄存数字序列。为此,需要单向环表的抽象数据结构。
(1)、单项环表的抽象数据类型定义为:
ADT Joseph{
数据对象:D=
数据关系:R1=
基本操作:
create(J, n)
操作结果:构造一个有n个结点的单向环表J。
show(J)
初始条件:单向环表J已存在。
操作结果:按顺序在屏幕上输出J的数据元素。
calculate( J,s,n)
初始条件:单向环表J已存在,s0,n0,s环表结点数。
操作结果:返回约瑟夫环的计算结果。
}ADT Joseph
(2)、宏定义
#define OK 1
#define ERROR 0
(3)、主程序流程
主程序首先调用create(J,m)函数创建含有m个结点的单向环表J,随后调用show(J)函数显示创建的环表内容,最后调用calculate(J,s,n)函数计算结果并在屏幕上打印。
(4)、模块调用关系:
由主函数模块调用创建模块,显示模块与计算模块。
由计算模块将结果输出。
(5)、流程图
2、详细设计
(1)、数据类型设计
typedef int ElemType; //元素类型
typedef struct {
ElemType data;
struct Joseph *next;
}Joseph, *LinkList,*p; //结点类型,指针类型
(2)、操作算法设计
Status create(LinkList J,int n){
//创建一个有n个结点的单向环表
if(n=0)
return ERROR; //n0错误
J=(LinkList)malloc(sizeof(J));
J-data=1;
J-next=J;//建立第一个结点
for(int i=n;i1;--i){
p=(LinkList)malloc(sizeof(J));
p-data=i;
p-next=J-next;J-next=p;//插入到表头
}
return OK;
}//create
void show(LinkList J){
//顺序输出环表J的结点
p=J;
printf(%d ,p-data);
p=p-next;
while(p!=J){ //循环终止条件
printf(%d ,p-data);
p=p-next;
}
}//show
void calculate(LinkList J,int s,int n){
p=J;
Joseph *head=p; //声明结点
while(p-data!=s){
p=p-next;
head=p;
}//寻找起始结点
while(p-next!=p){ //终止条件
for(int i=0;in-1;i++){
head=p; //保存前置节点
p=p-next;
}
printf(%d ,p-data);
head-next=p-next; //删除已输出结点
p=head-next;
}
if(n!=1)
printf(%d\n,p-data);
else
printf(\n);
}//calculate
(3)、主函数设计
int main()
{
//主函数
Joseph *J;int m,s,n;
printf(The num of node is:);
scanf(%d,m);
create(J,m); //创建单向环表J
show(J); //输出J的数据
printf(\n);
printf(T
您可能关注的文档
最近下载
- 山东省聊城市东阿县2022-2023学年四年级下学期期中英语试卷.docx VIP
- 基坑工程技术标准DG TJ08-61-2018上海(1).pdf
- 2020-2021学年粤教版三年级科学下册教学计划.docx VIP
- 安永-达芙妮预算管控框架设计v2.6-201209.pptx VIP
- 涉密软件项目实施过程必威体育官网网址管理.pdf
- 内部控制与风险管理-全套PPT课件.pptx
- 附件-1二级医疗机构安全生产标准化评定标准.doc
- 必威体育精装版教科版小学二年级科学下册《全册》教案板书反思教学设计.docx VIP
- 质量保证承诺书.docx VIP
- 2025年公文筐测试题汇总(附答案).pdf VIP
文档评论(0)