计算机数据结构课程设计报告

1、. . . . 数据结构课程设计报告题目一：约瑟夫环题目二：停车场管理题目一： 约瑟夫环一、问题描述：约瑟夫问题的一种描述是：编号为1，2···，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从它的顺时针方向的下一个人开始重新从1报数，如此下去，直至全部人出列为止。最后按照出列的顺序印出各人的编号。二、数据结构：其主要的数据类型为无头结点的单向循环链表，如下：typedef struct Nodeint data;

2、 /存储人数int password; /存储的每人所对应的密码struct Node *next;Node, *LinkList;三、大致的程序流程：1. 函数之间的调用关系图： mainPersonNumberFirstValueCreatLinkListInitLinkListOutputOrderprintResultPassword2.主要模块的流程图：开始输出界面输入人数目输入初始上限值输入第1人密码···输入第n人密码退出系统 结束3主程序A）以下两个函数作用是构建并初始化一个单循环链表，初始化时将链表*L赋值给链表*q,（*q）为头指针，并赋值p&

3、gt;data为第一人的编号，赋值p>password为此人对应的密码。再通过for（）循环，以链表q为过渡，依次给p>next赋值q。最后令p>next等于链表L的头指针(*L)。void CreatLinkList(LinkList *L)/*构建单链表*/(*L) = (LinkList)malloc(sizeof(Node);if (*L) = NULL)printf("memory allocation failed");exit(1);void InitLinkList(LinkList *L, int personNumber)/*初始化单链

4、表*/Node *p, *q;int i ;p = (*L);p->data = 1;p->password = Password();for (i = 2; i <= personNumber; i+)q = (LinkList)malloc(sizeof(Node);if (q = NULL)printf("memory allocation failed");exit(1);q->password = Password();q->data = i;p->next = q;p = q;p->next = (*L); B）以下三个

5、函数的作用分别是确定输入人数，确定每人密码，确定开始的上限制。他们都是通过库函数scanf（）来接受用户输入的数据，并且数据类行为整型（int）。其中用户输入的人数必须在0MAXPERSONNUMBER之间，密码必须在0MAXPASSWORDVALUE之间 ，开始查找的上限值必须在0MAXFIRSTVALUE之间。如果用户输入数值大于上限值或小于0，则返回重新输入。此过程是通过while（）函数实现的。如果while运行说明输入数据不合要求，重新输入。/*确定需要处理的人数*/int PersonNumber()int personNumber;printf("请输入需要输入人的数目

6、:");scanf("%d",&personNumber);while (personNumber > MAXPERSONNUMBER | personNumber < 0)printf("n你输入的数字无效,请输入在0到%d的整数",MAXPERSONNUMBER);scanf("%d",&personNumber);printf("最终确定的人数为%dn",personNumber);return personNumber;/*给每个人赋密码*/int Password()

7、int password;static int count = 1;printf("n请输入第%d的密码:",count);scanf("%d",&password);while (password > MAXPASSWORDVALUE | password < 0)printf("您输入的数字无效，请输入在0到%d的整数:",MAXPASSWORDVALUE);scanf("%d",&password);printf("第%d个人的密码为%d",count,pass

8、word);count+;return password; /*确定开始的上限值*/int FirstValue()int firstValue;printf("请输入初始的上限值");scanf("%d",&firstValue);while (firstValue > MAXFIRSTVALUE | firstValue < 0)printf("n你输入的数字无效,请输入在0到%d的整数",MAXFIRSTVALUE);scanf("%d",&firstValue);printf(&

9、quot;最终的上限值为%d",firstValue);return firstValue;C）以下此函数为关键函数，它决定着整个约瑟夫环程序的功能，通过此函数可以输出按出列顺序得到的各人的编号。整个函数是在满足personnumber大于0的前提下进行的，通过while (personNumber)函数实现。紧跟着通过循环while (count != reportValue)给count赋初值1，当countreportValue（也就是firstValue）时停止循环，此时p>data即为保数到reportvalue时所对应的人的编号，将其赋值到数组array，并将此人对

10、应的密码赋值给reportValue，令q的下一个指针指向p>next用来保存p>next的位置之后，释放p的存储空间，再令p指向q>next，得到被输出编号下一个编号的存储位置。之后人数减1，继续while (personNumber)循环，直到personNumber0返回array 。/*得到出队顺序*/void OutputOrder(LinkList *L, int personNumber, int reportValue, int arrayMAXPERSONNUMBER)Node *p, *q;int count = 1, i = 0;p = (*L);whi

11、le (personNumber)while (count != reportValue)q = p;p = p->next;count+;arrayi+ = p ->data;reportValue = p->password;q->next = p->next;free(p);p = q->next;count = 1;personNumber-;D）此函数功能就是在主函数调用时通过for（）循环打印出数组array 的值。/*输出结果*/void printResult(int array,int personNumer)int i;printf(&q

12、uot;n出队的顺序为:");for(i = 0; i < personNumer; i+)printf("%-3d",arrayi);printf("n");E）此函数通过调用各自定义函数，使各模块协调统一起来，以达到实现约瑟夫环程序功能的作用。/*主函数*/int main(void)LinkList L;int personNumber, reportValue;int arrayMAXPERSONNUMBER;personNumber = PersonNumber();reportValue = FirstValue();Crea

13、tLinkList(&L);InitLinkList(&L, personNumber);OutputOrder(&L, personNumber, reportValue, array);printResult(array, personNumber);return 0;四、调试分析A）程序的功能：按照出列的顺序印出各人的编号。数据类型： 全为整型（int）时间复杂度： 遍历O(n)，插入O(1)。B）主要的难点：线程控制，使程序达到参数即时可控，同时提高程序的健壮性。上机过程中遇到过一些错误，主要是语法错误经过我的再三排查终于改正了错误。五、用户手册1）输入要操作的

14、人的数目，输入数目必须在030之间，界面如下：2)输入初始上限值，输入值在010之间，界面如下：3）输入第一到第n人的密码，并输出出队顺序，密码在020之间，界面如下：4）按任意键退出界面。六、测试结果 第一组：输入数据：人数：4 初始上限：8 密码1：4 密码2：6 密码3：5 密码4：2输出数据：4 2 1 3第二组：输入数据：人数：5 初始上限：11（错误） 初始上限：7 密码1：3 密码2：7 密码3：2 密码4：9 密码5：5输出数据：4 2 1 3七、附录约瑟夫环源程序如下：#include"stdio.h"#include"stdlib.h"

15、;#define MAXPASSWORDVALUE 20#define MAXPERSONNUMBER 30#define MAXFIRSTVALUE 10typedef struct Nodeint data;int password;struct Node *next;Node, *LinkList;/*函数的声明*/void CreatLinkList(LinkList *);void InitLinkList(LinkList *,int );int GetPassword();int GetPersonNumber();int GetFirstCountValue();void Ge

16、tOutputOrder(LinkList* , int, int, int* );void printResult(int * ,int );/*构建单链表*/void CreatLinkList(LinkList *L)(*L) = (LinkList)malloc(sizeof(Node);if (*L) = NULL)printf("memory allocation failed");exit(1);/*初始化单链表*/void InitLinkList(LinkList *L, int personNumber)Node *p, *q;int i ;p = (*

17、L);p->data = 1;p->password = GetPassword();for (i = 2; i <= personNumber; i+)q = (LinkList)malloc(sizeof(Node);if (q = NULL)printf("memory allocation failed, goodbye");exit(1);q->password = GetPassword();q->data = i;p->next = q;p = q;p->next = (*L);/*确定需要处理的人数*/int Get

18、PersonNumber()int personNumber;printf("请输入需要输入人的数目:");scanf("%d",&personNumber);while (personNumber > MAXPERSONNUMBER | personNumber < 0)printf("n你输入的数字无效,请输入在0到%d的整数",MAXPERSONNUMBER);scanf("%d",&personNumber);printf("最终确定的人数为%dn",pers

19、onNumber);return personNumber;/*给每个人赋密码*/int GetPassword()int password;static int count = 1;printf("n请输入第%d的密码:",count);scanf("%d",&password);while (password > MAXPASSWORDVALUE | password < 0)printf("您输入的数字无效，请输入在0到%d的整数:",MAXPASSWORDVALUE);scanf("%d"

20、;,&password);printf("第%d个人的密码为%d",count,password);count+;return password;/*确定开始的上限值*/int GetFirstValue()int firstValue;printf("请输入初始的上限值");scanf("%d",&firstValue);while (firstValue > MAXFIRSTVALUE | firstValue < 0)printf("n你输入的数字无效,请输入在0到%d的整数",M

21、AXFIRSTVALUE);scanf("%d",&firstValue);printf("最终的上限值为%d",firstValue);return firstValue;/*得到出队顺序*/void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int arrayMAXPERSONNUMBER)Node *p, *q;int count = 1, i = 0;p = (*L);while (personNumber)while (count != reportVa

22、lue)q = p;p = p->next;count+;arrayi+ = p ->data;reportValue = p->password;q->next = p->next;free(p);p = q->next;count = 1;personNumber-;/*输出结果*/void printResult(int array,int personNumer)int i;printf("n出队的顺序为:");for(i = 0; i < personNumer; i+)printf("%-3d",ar

23、rayi);printf("n");/*主函数*/int main(void)LinkList L;int personNumber, reportValue;int arrayMAXPERSONNUMBER;personNumber = GetPersonNumber();reportValue = GetFirstValue();CreatLinkList(&L);InitLinkList(&L, personNumber);GetOutputOrder(&L, personNumber, reportValue, array);printRes

24、ult(array, personNumber);system("pause");return 0;题目二： 停车场管理一、问题描述：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车辆到达时间的先后顺序，依次由北向南排列，若车场已停满n辆汽车，则后来的汽车必须在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场某辆车要离开始，在它之后进入的车必须先退出车场为他让路，待该车开出大门外，其他车再按原次序进入车场，每辆停放在车场的车在它离开车场时必须按它停留的时间长短交纳费用。二、数据结构主要的数据类型为栈的顺序存储结构，

25、队列的链表存储结构，存储时间的链表结构。如下所示;/*时间结点*/ typedef struct time int hour; int min; Time; /*车辆信息结点*/typedef struct node char num10; Time reach; Time leave; CarNode; /*模拟车站*/typedef struct NODE CarNode *stackMAX+1; int top; SeqStackCar; /*车道结点*/typedef struct car CarNode *data; struct car *next; QueueNode; /*模拟

26、通道*/ typedef struct Node QueueNode *head; QueueNode *rear; LinkQueueCar;三、大致的程序流程1. 函数之间的调用关系图： mainInitStackInitQueueArrivalLeaveflushallPRINT2.主要模块的流程图：开始输出界面选择操作是输入数据选择1否是选择2输入数据否否选择3是退出系统结束3主程序： A）以下两个函数分别初始化了一个栈和一个队列。对于栈，数据服从先进后出关系。对于队列，数据服从先进先出规则。用栈来模拟一停车场，用队列模拟一便道。/*初始化栈*/void InitStack(SeqSt

27、ackCar *s) int i; s->top=0; for(i=0;i<=MAX;i+) s->stacks->top=NULL; /*初始化便道*/int InitQueue(LinkQueueCar *Q) Q->head=(QueueNode *)malloc(sizeof(QueueNode); if(Q->head!=NULL) Q->head->next=NULL; Q->rear=Q->head; return(1); else return(-1); B）此函数主要起到显示出站车信息的作用。包括显示车进入停车场的时

28、间，出车场的时间，车牌号，和应收取的费用。公式(B1-A1)*60+(B2-A2)*price用来计算费用，price为0.1元，单位为每分钟。/*打印出站车的信息*/void PRINT(CarNode *p,int room) int A1,A2,B1,B2; printf("nplease input thedepart time:/*:*/"); scanf("%d:%d",&(p->leave.hour),&(p->leave.min); printf("nthe number of the car:&qu

29、ot;); puts(p->num); printf("nthe time the car arrive: %d:%d",p->reach.hour,p->reach.min); printf("the depart time: %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("nthe fee: %2.1f元&qu

30、ot;,(B1-A1)*60+(B2-A2)*price); free(p); C）此函数实现的功能是实现汽车进停车场的操作。第一步操作是确定要进停车场车的车牌号，然后通过函数if(Enter->top<MAX)来判断栈是否已满，未满则执行if（）函数，令栈顶加1，视为一辆车进入停车场，并输入此时时间，用p->reach.hour,p->reach.min存储。若车场已满则进入便道，由队列实现。/*车辆到达*/int Arrival(SeqStackCar *Enter,LinkQueueCar *W) CarNode *p; QueueNode *t; p=(CarN

31、ode *)malloc(sizeof(CarNode); flushall(); printf("ninput the number of the car(例:1234):"); gets(p->num); if(Enter->top<MAX) /*车场未满，车进车场*/ Enter->top+; printf(" nthe place of the car: %d ",Enter->top); printf("nthe time thecar arrive:/*:*/"); scanf("%

32、d:%d",&(p->reach.hour),&(p->reach.min); Enter->stackEnter->top=p; return(1); else /*车场已满，车进便道*/ printf("n该车须在便道等待."); t=(QueueNode *)malloc(sizeof(QueueNode); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); D）此函数实现的功能是实现车出停车场时的操作。包括显示

33、车的位置，车进、出停车场的时间，得出应交纳的费用。然后便道上等候的车进入停车场。通过函数if(Enter->top>0)来判断栈是否为空，如不为空，则执行if（）函数。之后第一个while（1）函数的作用是确定出停车场车的位置。第二个while(Enter->top>room)函数作用是令存储在栈选定位置上方的数据存入临时栈Temp，令选定位置处于栈的顶端。之后取出栈顶元素。取出之后再用第三个while(Temp->top>=1)函数将临时栈Temp中数据依次返回停车场栈中。之后当停车场中留出空位，执行函数if(W->head!=W->rear)

34、&&Enter->top<MAX)将便道中车存入停车场栈中。/*车辆离开*/void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) int room; CarNode *p,*t; QueueNode *q; /*判断车场是否有车*/ if(Enter->top>0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf("n请输入车在车场的位置/1-%d/：",Enter->top); scanf("%d",&am

35、p;room); if(room>=1&&room<=Enter->top) break; while(Enter->top>room) /*车辆离开*/ Temp->top+; Temp->stackTemp->top=Enter->stackEnter->top; Enter->stackEnter->top=NULL; Enter->top-; p=Enter->stackEnter->top; Enter->stackEnter->top=NULL; Enter->

36、;top-; while(Temp->top>=1) Enter->top+; Enter->stackEnter->top=Temp->stackTemp->top; Temp->stackTemp->top=NULL; Temp->top-; PRINT(p,room); /*判断通道上是否有车与车站是否已满*/ if(W->head!=W->rear)&&Enter->top<MAX) /*便道的车辆进入车场*/ q=W->head->next; t=q->data; E

37、nter->top+; printf("n便道的%s号车进入车场第%d位置.",t->num,Enter->top); printf("n请输入现在的时间/*:*/:"); scanf("%d:%d",&(t->reach.hour),&(t->reach.min); W->head->next=q->next; if(q=W->rear) W->rear=W->head; Enter->stackEnter->top=t; free(q);

38、 else printf("n便道里没有车.n"); else printf("n车场里没有车."); /*没车*/ E）主函数实现了用户界面。并通过调用各自定义函数，实现了停车场管理系统的模拟。void main() SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(&Enter); /*初始化停车场*/ InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) printf(&

39、quot;n*");printf("n 1. the car arrive"); printf(" 2. the car leave"); printf(" 3. quitn"); printf("*n"); while(1) scanf("%d",&ch); if(ch>=1&&ch<=4)break; else printf("nplease choose： 1|2|3"); switch(ch) case 1:Arrival

40、(&Enter,&Wait);break; /*车辆到达*/ case 2:Leave(&Enter,&Temp,&Wait);break; /*车辆离开*/ case 3:exit(0); /*退出程序*/ default: break; 四、调试分析此程序输入输出的数据都为整型（int）。线程控制，使程序达到参数即时可控，同时提高程序的健壮性。上机过程中遇到过一些错误，主要是语法错误经过我的再三排查终于改正了错误。程序功能：模拟停车场管理系统，一狭长结构停车场，一次只允许一辆车进出。当停车场未满时，车进停车场，当满时，车进便道。当停车场某辆车要离开时

41、，在它之后进入的车必须先退出车场为他让路，待该车开出大门外，其他车再按原次序进入车场，每辆停放在车场的车在它离开车场时必须按它停留的时间长短交纳费用。五、用户手册1 输入进站车信息，界面：2输入出站信息，界面：3便道车入站，界面：六测试结果第一组：输入数据：1 车牌号：1234 到达时间12：12 2 离开车位置：1 离开时间 12：34输出数据：出站车牌号 1234 到达时间 12：12 离开时间：12：34 收费：4.4元第二组：输入数据：1 车牌号：1234 到达时间 12：12 输入数据：1 车牌号：1122 到达时间 13：01 2 离开车位置：1 离开时间 14：00输出数据：出站

42、车牌号 1234 到达时间 12：12 离开时间：14：00 收费：10.08元七、附录停车场管理源代码：#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 2 /*车库容量*/ #define price 0.1 /*每车每分钟费用*/*-定义数据类型-*/ /*时间结点*/ typedef struct time int hour; int min; Time; /*车辆信息结点*/typedef struct node char num10; Time reach; T

43、ime leave; CarNode; /*模拟车站*/typedef struct NODE CarNode *stackMAX+1; int top; SeqStackCar; /*车道结点*/typedef struct car CarNode *data; struct car *next; QueueNode; /*模拟通道*/ typedef struct Node QueueNode *head; QueueNode *rear; LinkQueueCar; /*-预定义函数-*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQ

44、ueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ /*-自定义函数-*/ /*初始化栈*/void InitStack(SeqStackCar *s) int i; s->top=0; for(i=0;i<=MAX;i+) s->stacks->top=NULL; /*初始化便道*/int InitQueue(LinkQueu

45、eCar *Q) Q->head=(QueueNode *)malloc(sizeof(QueueNode); if(Q->head!=NULL) Q->head->next=NULL; Q->rear=Q->head; return(1); else return(-1); /*打印出站车的信息*/void PRINT(CarNode *p,int room) int A1,A2,B1,B2; printf("nplease input thedepart time:/*:*/"); scanf("%d:%d",&a

46、mp;(p->leave.hour),&(p->leave.min); printf("nthe number of the car:"); puts(p->num); printf("nthe time the car arrive: %d:%d",p->reach.hour,p->reach.min); printf("the depart time: %d:%d",p->leave.hour,p->leave.min); A1=p->reach.hour; A2=p->

47、;reach.min; B1=p->leave.hour; B2=p->leave.min; printf("nthe fee: %2.1f元",(B1-A1)*60+(B2-A2)*price); free(p); /*车辆到达*/int Arrival(SeqStackCar *Enter,LinkQueueCar *W) CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode); flushall(); printf("ninput the number of the car(例:

48、1234):"); gets(p->num); if(Enter->top<MAX) /*车场未满，车进车场*/ Enter->top+; printf(" nthe place of the car: %d ",Enter->top); printf("nthe time thecar arrive:/*:*/"); scanf("%d:%d",&(p->reach.hour),&(p->reach.min); Enter->stackEnter->to

49、p=p; return(1); else /*车场已满，车进便道*/ printf("n该车须在便道等待."); t=(QueueNode *)malloc(sizeof(QueueNode); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); /*车辆离开*/void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) int room; CarNode *p,*t; QueueNode *q; /*判断车场是否有车*/ if(Enter->top>0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf("n请输入车在车场的位置/1-%d/：",Enter->top