数据结构课程设计 猴子选大王 joseph环 飞机订票 文章编辑

1、课 程 设 计课程名称：数据结构题目名称：数据结构课程设计专业班级：*计算机系*班学生姓名：田龙学 号：指导教师：张艳二一一年十二月二十二日目录引言3一、课程设计目的与要求41课程设计的目的42课程设计的根本要求4二、猴子选大王51提出问题52概要设计53调试分析6二、joseph环71提出问题72概要设计721 算法设计722 存储结构设计73调试分析8三、文章编辑91提出问题92概要设计93调试分析11四、飞机订票系统121提出问题122概要设计1221 算法设计1221 存储结构设计133调试分析14附录一：猴子选大王源程序17附录二：joseph环源程序19附录三：文章编辑源程序22附

2、录四：飞机订票系统源程序27引言课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。?数据结构?是一门实践性强的课程，其中对算法设计和程序编写的掌握尤其重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，要求学生编写的程序结构清楚和正确易读，符合软件工程的标准，能够为今后从事计算机开发与应用打下根底。需要学生具有丰富科学知识、独立解决实际问题、有创造能力，这也是该课程设计的最终

3、目的。通过本课程设计，使自己更加系统地理解和掌握数据结构的根本概念；能自如地根据实际要求，设计相应的数据结构，并运用C语言实现所设计的算法，编写较大型的程序，分析和解决实际应用问题，进一步加深、稳固所学专业课程的根本理论知识，理论联系实际，进一步培养自己综合分析问题和解决问题的能力。掌握C语言独立的编写、调试应用程序和进行其它相关设计的技能。此工程主要是考察我们对结构体、数组、文件等具体操作，以及对C语言语法的掌握，所以做成此工程要求比拟高的设计要求，对整体有很熟悉的概括，同时调试过程也是很重要的，对程序界面的要求也比拟高，要设计的合理同时也要美观一点，能够人性化的描述清楚你的各个功能，一目了

4、然，对其他用户使用本程序简单易懂，这才能本钱程序或本系统是成功的。这个设计能够练习我们的理解和运用结构化程序设计的思想和方法，掌握开发一个小型实用系统的根本方法，学会调试一个比拟长的程序的根本方法，同时掌握书写程序设计开发文档的能力。一、课程设计目的与要求1课程设计的目的课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。?数据结构?是一门实践性强的课程，其中对算法设计和程序编写的掌握尤其重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综

5、合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，要求学生编写的程序结构清楚和正确易读，符合软件工程的标准，能够为今后从事计算机开发与应用打下根底。需要学生具有丰富科学知识、独立解决实际问题、有创造能力，这也是该课程设计的最终目的。2课程设计的根本要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般标准进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、设计的题目要求到达一定

6、工作量，并具有一定的深度和难度。6、编写出课程设计说明书，说明书不少于15页不包括代码。二、猴子选大王1提出问题任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子m个按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，那么该猴子为大王。要求：输入数据：输入m,n m,n 为整数，n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 2概要设计根据任务描述可知，编号是1，2，3n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m

7、值，为保证m<n，用一个while( )语句实现，如果输错，报错，再输入。用for循环实现猴子编号。从1开始数到m的猴子出列，即用指针移动查找法将计数器数到m的指针指向的内容变为0，用for循环，直到只有一个元素不为0时，最后不为0的元素的值即为大王。实现这个程序功能需3个模块，一个模块用数组指针实现猴子编号，一个模块用指针移动查找法实现猴子出局，最后主模块将前两个模块要用到的函数，数组定义。具体步骤如下：第一步 建立数组，填入猴子编号及猴子出局时报的数第二步 从第一个猴子报数第三步 数到m让指针指向元素变为0第四步 继续报数，重复第三步猴子的存放采用链式存储结构，利用循环链表来实现建立

8、的，其表示方法是递归定义的：typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList;根据题目要求，要让这M只猴子顺序围坐一圈，那就得用循环链表，只须将单循环链表的尾指针的NEXT域指向头指针。它的判空条件是L=L->next =NULL； 非空表 空表 单循环链表3调试分析二、joseph环1提出问题任务：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码正整数。一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为

9、新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,那么正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列。2概要设计21 算法设计利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方

10、向围坐一圈，每个人只有一个密码正整数内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。22 存储结构设计密码和序号的存放采用链式存储结构，利用循环链表来实现建立的，其表示方法是递归定义的。要让这M个人顺序围坐一圈，那就得用循环链表，只须将单循环链表的尾指针的NEXT域指向头指针。3调试分析三、文章编辑1提出问题任务：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求：1分别统计出其中英文字母数和空格数及整篇文章总字数；2统计某一字符

11、串在文章中出现的次数，并输出该次数；3删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；4输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：1分行输出用户输入的各行字符；2分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"3输出删除某一字符串后的文章。2概要设计1定义结构体 struct line，文本行采用顺序存储，行与行之间采用链式存储。2主要函数：int FindString(LINE * &head,char *s

12、tr) /*统计str在文章中出现的次数*/查找第一个字符，如果有第一个字符即p->datai=str0，设计数器k=0；查找这个字符后面的字符与要查找的字符串是否匹配即p->datai+j=strj，如果匹配k+；重复第二步，如果k=len2，那么查找到，count+；如果没查找到，重新进行第一步。void delstringword(char *s,char *str) /*删除字符串*s中的字符串*str*/实现思想：从字符串s中寻找str第一次出现的位置 *p=strstr(s,str);len=strlen(s);i=len-strlen(p)即前i项恰好不含要删除的字符

13、串，将前i项复制到tmp中j=i+strlen(str) 即要删除的字符串在i+1和j之间，将j之后的字符串复制到tmp中将tmp赋给串s，返回s3调试分析四、飞机订票系统1提出问题任务：通过此系统可以实现如下功能：录入：可以录入航班情况数据可以存储在一个数据文件中，数据结构、具体数据自定查询：可以查询某个航线的情况如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓；订票：订票情况可以存在一个数据文件中，结构自己设定可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，订票数量及航班情况，订单要有编号。修改航班

14、信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。 2概要设计21 算法设计每个模块的算法设计说明如下：1录入模块： 查找单链表的链尾，在链尾插入一个“航班信息的新结点。可以进行新增航班信息、删除航班信息等操作。2查询模块：提供查方式顺着单链表查找，查找出所有航班的信息和订票信息。3订票模块：查找乘客要订的航班号，判断此航班是否有空位，有那么输入乘客有关信息，订票成功，否那么失败。4退票模块：输入要退票的乘客姓名，查找乘客资料的链表中是否有这位乘客，有那么删去此结点，并在空位加上1，无那么退票失败。21 存储结构设计航班的信息：

15、为了便于查找和修改，航班的情况存储结构采用单链表，每个元素表示一个航班的情况，包括航班号、飞机编号、目的地、时间、总座位和空座六个数据项：航班号飞机编号目的地时间总座位空座单链表如下：hD1D2D3每个结点包括数据域和指针域：数据域指针域C语言描述如下：typedef struct airline /飞机编号结构体/ char air_num8; /*航班号*/ char plane_num8; /*飞机编号*/ char end_place20;/*目的地*/ char time_plane16;/*时间*/ int total; /*总座位*/ int left; /*空座*/ struc

16、t airline *next; /*指向下个结点*/airline; 旅客的资料：为了便于插入、删除和修改，其采用单链表存储结构，每个数据元素包括姓名、航班号和座位号四个数据项：旅客姓名航班号座位号每个结点包括数据域和指针域：数据域指针域C语言描述如下：typedef struct customer /乘客编号结构体/ char name8; char air_num8; int seat_num; struct customer *next; customer; 3调试分析附录一：猴子选大王源程序源程序：#include "stdio.h"#include "

17、process.h"#include "malloc.h"#define ture 1#define false 0#define ok 1#define error 0#define infeasible -1#define overflow -2#define list_init_size 100#define listincrement 10typedef int Status;typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/

18、创立循环链表void CreateList_L(LinkList &L,int n)/创立一个n单元的循环链表int i; struct LNode *p,*q;L=(LinkList) malloc (sizeof(LNode);L->next=NULL;L->data=1;q=L;for(i=2;i<=n;i+)p=(LinkList)malloc(sizeof(LNode);p->data=i;q->next=p;p->next=L;q=q->next;/链表删除操作Status ListDelete_L(LinkList &L,

19、int i,ElemType &e)int j;LNode *p,*q;p=L;j=1;while ( j<i-1)p=p->next; +j;q=p->next; p->next =q->next;e=q->data; free(q);L=p->next;return ok;void main() printf("n *n"); printf(" * 班级： * n"); printf(" * 姓名： 田 龙 * n"); printf(" * 学号： * n")

20、; printf("n *n"); printf(" * * n"); printf(" * 猴子选大王 * n"); printf(" * * n"); printf(" *nn");LinkList L; int m,n,i;ElemType e;printf("n 请输入猴子的个数:");scanf("%d",&m);CreateList_L(L,m);printf(" 所有猴子的编号为:n");for(i=0;i<

21、m;i+) printf("%3d",L->data); L=L->next;printf("n");printf("n 请输入猴子要数的数:");scanf("%d",&n);printf("n 猴子依次离开的序号:n");for (i=1;i<m;i+)ListDelete_L(L,n,e);printf("%3d",e);printf("n");printf("n 猴子选出的大王是:");printf(&

22、quot;%2dnn",L->data);附录二：joseph环源程序源程序：#include "stdio.h"#include "process.h"#include "malloc.h"#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef int Status;#include "defineHeader.h"typedef structint name

23、;intsno;ElemType;typedef struct LNodeElemTypedata;struct LNode *next;LNode,*LinkList;/逆位序输入n个人的密码，建立带表头结点的单链表Lvoid CreateList_L(LinkList &L,int n)int i;LinkList p;L=(LinkList)malloc(sizeof (LNode);L->next=NULL;for(i=n;i>0;-i)p=(LinkList)malloc(sizeof (LNode);p->=i;scanf("%

24、d",&p->data.sno);p->next=L->next;L->next=p;/查找元素值Status GetElem_L(LinkList L,int i,ElemType &e)LNode *p;int j;p=L->next;j=1;while(p&&j<i)p=p->next;+j;if(!p|j>i)return ERROR;e=p->data;return OK;/在带头结点的单链表L中第i个位置之前插入元素eStatus ListInsert_L(LinkList &L

25、,int i,ElemType e)LNode *p,*s;int j=0;p=L;while(p&&j<i-1)p=p->next;+j;/寻找第i-1个结点if(!p|j>i-1) return ERROR;s=(LinkList)malloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;return OK;/在带头结点的单链表L中删除第i个元素，并用e返回其值Status ListDelete_L(LinkList &L,int i,ElemType &e)L

26、Node *p,*q;int j=0;p=L;while(p->next&&j<i-1)p=p->next;+j;if(!(p->next)|j>i-1)return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;void OutPut(LinkList &L,int m,int n,ElemType &e)int i,k,cun,cun1=0;/从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新

27、的m值if(cun=m%n)=0)cun=n;ListDelete_L(L,cun,e);k=n-cun;m=e.sno;printf("%4d:%d |",,e.sno);/从上一个报m的人在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。for(i=n-1;i>0;i-)if(cun1=m%i)=0)cun1=i;if(cun1<=k)ListDelete_L(L,(cun1+cun-1),e);k=i-(cun1+cun-1);cun=cun1+cun-1;else ListDelete_L(L,(cun1-k),e);

28、cun=cun1-k;k=i-(cun1-k);m=e.sno;printf("%4d:%d |",,e.sno);/printf("n"); void main()int i,m,n;ElemType e;LinkList L;printf("n *n"); printf(" * 班级： * n"); printf(" * 姓名： 田 龙 * n"); printf(" * 学号： * ");printf("n *n");printf(&qu

29、ot;n"); printf(" * Joseph环 * n"); printf("*n"); printf("请输入“m的初值：");scanf("%d",&m);printf("请输入一个数表示有“n个人：");scanf("%d",&n);printf("n请输入这“%d个人的密码，按Enter键确认n",n);CreateList_L(L,n);printf("n这“%d个人的密码为：n",n);for

30、(i=1;i<=n;i+)GetElem_L(L,i,e);printf("%5d:%d | ",,e.sno);printf("nn");/*一开始任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。*/printf("n这“%d个人的出列顺序为：n",n);OutPut(L,m,n,e);printf("nn");附录三：文章编辑源程序源程

31、序：#include<iostream.h>#include <string.h>#include <stdio.h> /*文本每行以字符串形式存储，行与行之间以链表存储*/typedef struct line char *data; struct line *next;LINE; /*创立一链表，同时向里面输入文本数据*/void Create(LINE * &head) printf ("请输入一页文章，以Ctrl+E(E)为结尾(每行最多输入80字符!):n");LINE *p=new LINE; /*首先为链表 建立一个

32、附加表头结点*/ head=p; /*将p付给 表头指针*/ char tmp100; while(1) gets(tmp); /*输入字符串！*/ if(strlen(tmp)>80) printf("每行最多输入80字符"); break; if(tmp0=5)break; /*如果发现输入 E，那么退出输入*/ p=p->next=new LINE; p->data=new charstrlen(tmp)+1; /*为结点分配空间 */ strcpy(p->data,tmp); if(tmpstrlen(tmp)-1=5) /*除去最后一个控制

33、符 E */ p->datastrlen(tmp)-1='0' break; p->next=NULL; /*最后的一个指针为空 */ head=head->next;/*统计字母数*/int CountLetter(LINE * &head) LINE *p=head; int count=0;do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<Len;i+)if(p->datai>='a'&&p->datai

34、<='z')|(p->datai>='A'&&p->datai<='Z') /*计算字母数*/count+; while(p=p->next)!=NULL); /*遍历 链表*/return count; /*返回文章的字母总数*/*统计数字数*/int CountNumber(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=

35、0;i<Len;i+) if(p->datai>=48 && p->datai<=57)count+;/*计算数字数，ASCII码*/ while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计空格数*/int CountSpace(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p->data); /*计算当前 data 里的数据元素的个数*/ for(int i=0;i<Len;i+) if(p->

36、datai=32)count+; /*计算空格数，空格ASCII码为32*/ while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计文章的总字数*/int CountAll(LINE * &head) LINE *p=head; /*保存链表的首地址*/ int count=0; do /*计算总字符数*/ count+=strlen(p->data); while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*统计str在文章中出现的次数*/int FindString(LI

37、NE * &head,char *str) LINE *p=head; int count=0; int h=0; int len1=0; /*保存当前行的总字符数*/ int len2=strlen(str); /*待统计字符串的长度*/ int i,j,k; do len1=strlen(p->data); /*当前行的字符数*/for(i=0;i<len1;i+) /*字符匹配*/ if(p->datai=str0)k=0; for(j=0;j<len2;j+) if(p->datai+j=strj) k+;if(k=len2)count+;i=i+

38、k-1; while(p=p->next)!=NULL); /*遍历 链表*/ return count;/*删除指定的字符串*/void delstringword(char *s,char *str) /* *s为输入的字符串，*str为将要删除的字符*/char *p=strstr(s,str); /*从字符串s中寻找str第一次出现的位置*/ char tmp80; int len=strlen(s); int i=len-strlen(p); int j=i+strlen(str); int count=0; for(int m=0;m<i;m+)tmpcount+=sm

39、; for(int n=j;n<len;n+)tmpcount+=sn; tmpcount='0' strcpy(s,tmp); /*返回新的字符串*/void DelString(LINE * &head,char *str) LINE *p=head; do if(strstr(p->data,str)!=NULL)delstringword(p->data,str);while(p=p->next)!=NULL); /*遍历 链表*/*向屏幕输出文章*/void OutPut(LINE * &head) LINE *p=head;

40、do printf("%sn",p->data); while(p=p->next)!=NULL); /*遍历 链表*/void main() LINE *head; printf("n *n"); printf(" * 班级： * n"); printf(" * 姓名： 田 龙 * n"); printf(" * 学号： * ");printf("n *n");printf("n"); printf(" * 文章编辑 * n&quo

41、t;);printf("*n"); Create(head); printf("输入的文章为:n"); OutPut(head); printf("n"); printf("全部字母数：%d n",CountLetter(head); printf("数字个数：%d n",CountNumber(head); printf("空格个数: %d n",CountSpace(head); printf("文章总字数: %d n",CountAll(head);

42、 char str120,str220; printf("n"); printf("请输入要统计的字符串:"); scanf("%s",str1); printf("%s出现的次数为:%d n",str1,FindString(head,str1); printf("n"); printf("请输入要删除的某一字符串："); scanf("%s",str2); DelString(head,str2); printf("删除%s后的文章为:n&q

43、uot;,str2); OutPut(head); 附录四：飞机订票系统源程序源程序：#include <stdio.h> #include <string.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef struct airline /飞机编号结构体/ char air_num8; char plane_num8; char end_place20; char time_plane16; int total; int left; struct airline *next; airlin

44、e; typedef struct customer /乘客编号结构体/ char name8; char air_num8; int seat_num; struct customer *next; customer; airline *start_air() airline *a; a=(airline*)malloc(sizeof(airline); if(a!=NULL)a->next=NULL; return a; customer *start_cus() customer *c; c=(customer*)malloc(sizeof(customer); if(c!=NUL

45、L)c->next=NULL; return c; airline *modefy_airline(airline *l,char *air_num) airline *p; p=l->next; for(;p!=NULL;p=p->next) if(strcmp(air_num,p->air_num)=0) p->left+; return l; printf(" 对不起，没有该航班!"); return 0; /增加飞机信息int insert_air(airline *p,char *air_num,char *plane_num,cha

46、r *end_place,char *time_plane,int total,int left) airline *q; q=(airline*)malloc(sizeof(airline); strcpy(q->air_num,air_num); strcpy(q->plane_num,plane_num); strcpy(q->end_place,end_place); strcpy(q->time_plane,time_plane); q->total=total; q->left=left; q->next=NULL; (*p)->next=q; (*p)=(*p)->next; /printf(" 添加航线成功！"); return OK; /添加航线airline *add_air(airline *p,char *air_num,char *plane_num,char *end_place,char *time_plane,int total,int left) airline *q,*pt; pt=p; q=(airline*)malloc(sizeof(airline)