计算机数据结构课程设计报告.docx
- 文档编号:11038009
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:35
- 大小:172.04KB
计算机数据结构课程设计报告.docx
《计算机数据结构课程设计报告.docx》由会员分享,可在线阅读,更多相关《计算机数据结构课程设计报告.docx(35页珍藏版)》请在冰点文库上搜索。
计算机数据结构课程设计报告
数据结构课程设计报告
题目一:
约瑟夫环
题目二:
停车场管理
班级:
计算机科学与技术系1班
姓名:
学号:
指导教师:
完成日期:
2007年7月12日
题目一:
约瑟夫环
一、问题描述:
约瑟夫问题的一种描述是:
编号为1,2···,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。
报m的人出列,将它的密码作为新的m值,从它的顺时针方向的下一个人开始重新从1报数,如此下去,直至全部人出列为止。
最后按照出列的顺序印出各人的编号。
二、数据结构:
其主要的数据类型为无头结点的单向循环链表,如下:
typedefstructNode
{
intdata;//存储人数
intpassword;//存储的每人所对应的密码
structNode*next;
}Node,*LinkList;
三、大致的程序流程:
1.函数之间的调用关系图:
main
PersonNumberFirstValueCreatLinkListInitLinkListOutputOrderprintResult
Password
2.主要模块的流程图:
·
·
·
3.主程序
A)以下两个函数作用是构建并初始化一个单循环链表,初始化时将链表*L赋值给链表*q,(*q)为头指针,并赋值p->data为第一人的编号,赋值p->password为此人对应的密码。
再通过for()循环,以链表q为过渡,依次给p->next赋值q。
最后令p—>next等于链表L的头指针(*L)。
voidCreatLinkList(LinkList*L)
{/*构建单链表*/
(*L)=(LinkList)malloc(sizeof(Node));
if((*L)==NULL)
{
printf("memoryallocationfailed");
exit
(1);
}
}
voidInitLinkList(LinkList*L,intpersonNumber)
{/*初始化单链表*/
Node*p,*q;
inti;
p=(*L);
p->data=1;
p->password=Password();
for(i=2;i<=personNumber;i++)
{
q=(LinkList)malloc(sizeof(Node));
if(q==NULL)
{
printf("memoryallocationfailed");
exit
(1);
}
q->password=Password();
q->data=i;
p->next=q;
p=q;
}
p->next=(*L);
}
B)以下三个函数的作用分别是确定输入人数,确定每人密码,确定开始的上限制。
他们都是通过库函数scanf()来接受用户输入的数据,并且数据类行为整型(int)。
其中用户输入的人数必须在0~MAXPERSONNUMBER之间,密码必须在0~MAXPASSWORDVALUE之间,开始查找的上限值必须在0~MAXFIRSTVALUE之间。
如果用户输入数值大于上限值或小于0,则返回重新输入。
此过程是通过while()函数实现的。
如果while运行说明输入数据不合要求,重新输入。
/*确定需要处理的人数*/
intPersonNumber()
{
intpersonNumber;
printf("请输入需要输入人的数目:
");
scanf("%d",&personNumber);
while(personNumber>MAXPERSONNUMBER||personNumber<0)
{
printf("\n你输入的数字无效,请输入在0到%d的整数",MAXPERSONNUMBER);
scanf("%d",&personNumber);
}
printf("最终确定的人数为%d\n",personNumber);
returnpersonNumber;
}
/*给每个人赋密码*/
intPassword()
{
intpassword;
staticintcount=1;
printf("\n请输入第%d的密码:
",count);
scanf("%d",&password);
while(password>MAXPASSWORDVALUE||password<0)
{
printf("您输入的数字无效,请输入在0到%d的整数:
",MAXPASSWORDVALUE);
scanf("%d",&password);
}
printf("第%d个人的密码为%d",count,password);
count++;
returnpassword;
}
/*确定开始的上限值*/
intFirstValue()
{
intfirstValue;
printf("请输入初始的上限值");
scanf("%d",&firstValue);
while(firstValue>MAXFIRSTVALUE||firstValue<0)
{
printf("\n你输入的数字无效,请输入在0到%d的整数",MAXFIRSTVALUE);
scanf("%d",&firstValue);
}
printf("最终的上限值为%d",firstValue);
returnfirstValue;
}
C)以下此函数为关键函数,它决定着整个约瑟夫环程序的功能,通过此函数可以输出按出列顺序得到的各人的编号。
整个函数是在满足personnumber大于0的前提下进行的,通过while(personNumber)函数实现。
紧跟着通过循环while(count!
=reportValue)给count赋初值1,当count=reportValue(也就是firstValue)时停止循环,此时p->data即为保数到reportvalue时所对应的人的编号,将其赋值到数组array[],并将此人对应的密码赋值给reportValue,令q的下一个指针指向p->next用来保存p->next的位置之后,释放p的存储空间,再令p指向q->next,得到被输出编号下一个编号的存储位置。
之后人数减1,继续while(personNumber)循环,直到personNumber=0返回array[]。
/*得到出队顺序*/
voidOutputOrder(LinkList*L,intpersonNumber,intreportValue,intarray[MAXPERSONNUMBER])
{
Node*p,*q;
intcount=1,i=0;
p=(*L);
while(personNumber)
{
while(count!
=reportValue)
{
q=p;
p=p->next;
count++;
}
array[i++]=p->data;
reportValue=p->password;
q->next=p->next;
free(p);
p=q->next;
count=1;
personNumber--;}}
D)此函数功能就是在主函数调用时通过for()循环打印出数组array[]的值。
/*输出结果*/
voidprintResult(intarray[],intpersonNumer)
{
inti;
printf("\n出队的顺序为:
");
for(i=0;i { printf("%-3d",array[i]); } printf("\n");} E)此函数通过调用各自定义函数,使各模块协调统一起来,以达到实现约瑟夫环程序功能的作用。 /*主函数*/ intmain(void) { LinkListL; intpersonNumber,reportValue; intarray[MAXPERSONNUMBER]; personNumber=PersonNumber(); reportValue=FirstValue(); CreatLinkList(&L); InitLinkList(&L,personNumber); OutputOrder(&L,personNumber,reportValue,array); printResult(array,personNumber); return0;} 四、调试分析 A)程序的功能: 按照出列的顺序印出各人的编号。 数据类型: 全为整型(int) 时间复杂度: 遍历O(n),插入O (1)。 B)主要的难点: 线程控制,使程序达到参数即时可控,同时提高程序的健壮性。 上机过程中遇到过一些错误,主要是语法错误经过我的再三排查终于改正了错误。 五、用户手册 1)输入要操作的人的数目,输入数目必须在0~30之间,界面如下: 2)输入初始上限值,输入值在0~10之间,界面如下: 3)输入第一到第n人的密码,并输出出队顺序,密码在0~20之间,界面如下: 4)按任意键退出界面。 六、测试结果 第一组: 输入数据: 人数: 4初始上限: 8密码1: 4密码2: 6密码3: 5密码4: 2 输出数据: 4213 第二组: 输入数据: 人数: 5初始上限: 11(错误)初始上限: 7密码1: 3密码2: 7密码3: 2密码4: 9密码5: 5 输出数据: 4213 七、附录 约瑟夫环源程序如下: #include"stdio.h" #include"stdlib.h" #defineMAXPASSWORDVALUE20 #defineMAXPERSONNUMBER30 #defineMAXFIRSTVALUE10 typedefstructNode { intdata; intpassword; structNode*next; }Node,*LinkList; /**************************************** 函数的声明 ****************************************/ voidCreatLinkList(LinkList*); voidInitLinkList(LinkList*,int); intGetPassword(); intGetPersonNumber(); intGetFirstCountValue(); voidGetOutputOrder(LinkList*,int,int,int*); voidprintResult(int*,int); /*构建单链表*/ voidCreatLinkList(LinkList*L) { (*L)=(LinkList)malloc(sizeof(Node)); if((*L)==NULL) { printf("memoryallocationfailed"); exit (1);}} /*初始化单链表*/ voidInitLinkList(LinkList*L,intpersonNumber) { Node*p,*q; inti; p=(*L); p->data=1; p->password=GetPassword(); for(i=2;i<=personNumber;i++) { q=(LinkList)malloc(sizeof(Node)); if(q==NULL) { printf("memoryallocationfailed,goodbye"); exit (1); } q->password=GetPassword(); q->data=i; p->next=q; p=q; } p->next=(*L);} /*确定需要处理的人数*/ intGetPersonNumber() { intpersonNumber; printf("请输入需要输入人的数目: "); scanf("%d",&personNumber); while(personNumber>MAXPERSONNUMBER||personNumber<0) { printf("\n你输入的数字无效,请输入在0到%d的整数",MAXPERSONNUMBER); scanf("%d",&personNumber); } printf("最终确定的人数为%d\n",personNumber); returnpersonNumber;} /*给每个人赋密码*/ intGetPassword() { intpassword; staticintcount=1; printf("\n请输入第%d的密码: ",count); scanf("%d",&password); while(password>MAXPASSWORDVALUE||password<0) { printf("您输入的数字无效,请输入在0到%d的整数: ",MAXPASSWORDVALUE); scanf("%d",&password); } printf("第%d个人的密码为%d",count,password); count++; returnpassword;} /*确定开始的上限值*/ intGetFirstValue() { intfirstValue; printf("请输入初始的上限值"); scanf("%d",&firstValue); while(firstValue>MAXFIRSTVALUE||firstValue<0) { printf("\n你输入的数字无效,请输入在0到%d的整数",MAXFIRSTVALUE); scanf("%d",&firstValue); } printf("最终的上限值为%d",firstValue); returnfirstValue;} /*得到出队顺序*/ voidGetOutputOrder(LinkList*L,intpersonNumber,intreportValue,intarray[MAXPERSONNUMBER]) { Node*p,*q; intcount=1,i=0; p=(*L); while(personNumber) { while(count! =reportValue) { q=p; p=p->next; count++; } array[i++]=p->data; reportValue=p->password; q->next=p->next; free(p); p=q->next; count=1; personNumber--;}} /*输出结果*/ voidprintResult(intarray[],intpersonNumer) { inti; printf("\n出队的顺序为: "); for(i=0;i { printf("%-3d",array[i]); } printf("\n"); /*主函数*/ intmain(void) { LinkListL; intpersonNumber,reportValue; intarray[MAXPERSONNUMBER]; personNumber=GetPersonNumber(); reportValue=GetFirstValue(); CreatLinkList(&L); InitLinkList(&L,personNumber); GetOutputOrder(&L,personNumber,reportValue,array); printResult(array,personNumber); system("pause"); return0;} 题目二: 停车场管理 一、问题描述: 设停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。 汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列,若车场内已停满n辆汽车,则后来的汽车必须在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开始,在它之后进入的车必须先退出车场为他让路,待该车开出大门外,其他车再按原次序进入车场,每辆停放在车场的车在它离开车场时必须按它停留的时间长短交纳费用。 二、数据结构 主要的数据类型为栈的顺序存储结构,队列的链表存储结构,存储时间的链表结构。 如下所示; /*时间结点*/ typedefstructtime{ inthour; intmin; }Time; /*车辆信息结点*/ typedefstructnode{ charnum[10]; Timereach; Timeleave; }CarNode; /*模拟车站*/ typedefstructNODE{ CarNode*stack[MAX+1]; inttop; }SeqStackCar; /*车道结点*/ typedefstructcar{ CarNode*data; structcar*next; }QueueNode; /*模拟通道*/ typedefstructNode{ QueueNode*head; QueueNode*rear; }LinkQueueCar; 三、大致的程序流程 1.函数之间的调用关系图: main InitStackInitQueueArrivalLeave flushallPRINT 2.主要模块的流程图: 3.主程序: A)以下两个函数分别初始化了一个栈和一个队列。 对于栈,数据服从先进后出关系。 对于队列,数据服从先进先出规则。 用栈来模拟一停车场,用队列模拟一便道。 /*初始化栈*/ voidInitStack(SeqStackCar*s) { inti; s->top=0; for(i=0;i<=MAX;i++) s->stack[s->top]=NULL;} /*初始化便道*/ intInitQueue(LinkQueueCar*Q) { Q->head=(QueueNode*)malloc(sizeof(QueueNode)); if(Q->head! =NULL) { Q->head->next=NULL; Q->rear=Q->head; return (1); } elsereturn(-1);} B)此函数主要起到显示出站车信息的作用。 包括显示车进入停车场的时间,出车场的时间,车牌号,和应收取的费用。 公式((B1-A1)*60+(B2-A2))*price用来计算费用,price为0.1元,单位为每分钟。 /*打印出站车的信息*/ voidPRINT(CarNode*p,introom) { intA1,A2,B1,B2; printf("\npleaseinputthedeparttime: /**: **/"); scanf("%d: %d",&(p->leave.hour),&(p->leave.min)); printf("\nthenumberofthecar: "); puts(p->num); printf("\nthetimethecararrive: %d: %d",p->reach.hour,p->reach.min); printf("thedeparttime: %d: %d",p->leave.hour,p->leave.min); A1=p->reach.hour; A2=p->reach.min; B1=p->leave.hour; B2=p->leave.min; printf("\nthefee: %2.1f元",((B1-A1)*60+(B2-A2))*price); free(p);} C)此函数实现的功能是实现汽车进停车场的操作。 第一步操作是确定要进停车场车的车牌号,然后通过函数if(Enter->top 若车场已满则进入便道,由队列实现。 /*车辆到达*/ intArrival(SeqStackCar*Enter,LinkQueueCar*W) { CarNode*p; QueueNode*t; p=(CarNode*)malloc(sizeof(CarNode)); flushall(); printf("\ninputthenumberofthecar(例: 1234): "); gets(p->num); if(Enter->top { Enter->top++; printf("\ntheplaceofthecar: %d",Enter->top); printf("\nthetimethecararrive: /**: **/"); scanf("%d: %d",&(p->reach.hour),&(p->reach.min)); Enter->stack[Enter->top]=p; return (1); } else/*车场已满,车进便道*/ { printf("\n该车须在便道等待."); t=(QueueNode*)malloc(sizeof(QueueNode)); t->data=p; t->next=NULL;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 数据结构 课程设计 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)