数据结构课程设计报告56212new

1、数据结构课程设计报告班 级： 姓 名： 序 号： 指导老师： 日 期: 目 录一、课程设计目的3二、课程设计要求3三、需求分析4四、逻辑设计5五、详细设计8六、程序编码10七、程序调试与测试31八、结果分析.32九、心得体会.36一、课程设计目的数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。课程设计是加强学生实践能力的一个强有力手段。本课程设计的目的就是要达到理论与实际应用相结合，使学生深化理解书本知识，获取上机实践经验，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养软件工作者所需的动手

2、能力、独立解决问题的能力。该课程设计侧重软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，以至一整套软件工作规范的训练和科学作风的培养。通过该课程设计的操作与实践，使学生真正掌握数据结构相关算法的实现及应用方法，在一定程度上提高使用数据结构相关算法的综合设计能力，具体掌握的基本能力如下：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软

3、件工作者所应具备的科学的工作方法和作风。二、课程设计要求学生必须仔细阅读数据结构课程设计方案，认真主动完成课程设计的要求。通过设计一个完整的程序，使学生掌握数据结构的应用，算法的编写。要求如下：1. 做好上机准备：要充分认识课程设计对自己的重要性，认真做好设计前的各项准备工作。每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。2. 既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。3. 独立思考，独立

4、完成：课程设计中各项任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。在设计过程中，要严格要求自己，树立严肃，严密，严谨的科学态度，必须按时，按质，按量完成课程设计。不得弄虚作假，不准抄袭他人内容。4. 设计的题目要求达到一定工作量(1000行以上代码)，并具有一定的深度和难度。 编写出课程设计说明书，说明书不少于2000字(代码不算)。5. 课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。课程设计期间，无故缺席按旷课处理。6. 按照任意性（用户任意给定输入，系统能够完成正确的计算），友好性

5、（界面要友好，输入有提示，尽量展示人性化），可读性（源程序代码清晰、有层次），健壮性（用户输入非法数据时，系统要及时给出警告信息），结构性（应用程序具有良好的程序结构）要求分析设计实现。整个系统只能有一个执行程序，各项内容分别以不同文件存放，功能尽量模块化。三、需求分析：1.线性表的操作（1）该程序主要考查线性链表的基本操作（2）程序的功能为：创建链表，删除结点，插入结点，遍历，计算链表的长度（3）生成线性表时，可以键盘上读取元素2.表达式求值 （1）该程序主要考查栈的基本操作 （2）程序功能有：进栈，出栈，求表达式的值 （3）表达式以字符序列的形式从键盘输入不含变量的整数。3. 二叉树的遍历

6、、线索及应用（1）该程序主要考查二叉树的应用（2）程序的功能有：先序遍历法创建二叉树，先序、中序、后序遍历二叉树。4.二叉排序树的操作（1）该程序主要考查二叉排序树的应用（2）程序的功能有：创建二叉排序树，插入，遍历，删除等操作5.订票系统（1）该程序是以链表的形式读取文件，将各航班的信息赋给链表的各个结点（2）程序的功能主要有：通过文件读取航班信息，查询各个航班的信息，订票，退票等功能四、逻辑设计：Main_Linklist（）链表的主函数Inite_Linklist（L）链表初始化Menu_Linklist（L）菜单Print_List( L)遍历Delete_List(L, i)删除In

7、sert_List(L, i);插入Inite_List(L)创建Length_List(L)长度图1.链表的函数调用关系图Main_Expression()表达式求值主函数Menu_Expression(exp)表达式求值菜单CalExp(exp)表达式求值InitStack(s)栈初始化IsOperator(expcur)是否运算符Calculate(a, expcur,b)计算Pop(s)出栈Push(s,c)进栈图2.表达式求值函数调用关系图Main_BiTree()二叉树主函数Inite_BiTree(T)二叉树初始化Menu_BiTree(T)菜单CalculateLeaf(T)计

8、算叶子结点数PostOrderTraverse(T)后序遍历InOrderTraverse(T)中序遍历PreOrderTraverse(T)先序遍历Create_BiTree(T)创建图3.二叉树的应用函数调用关系图MainSortTree()排序树主函数 IniteSortTree(T)初始化MenuSortTree(T)菜单PrintSortTree(T)遍历SearchSortTree(T,e)查找并删除InsertSortTree(T,e)插入CreateSortTree(T)创建DeleteSortTree(T)删除 图4.二叉排序树函数调用关系图Main_Ticket()订票系统

9、主函数ReadFile(L)读文件Create_Ticket(L)创建Menu_Ticket(L)菜单TuiTicket(L,j)退票Printscreen(L)打印Inite_Ticket(L)初始化ChaXun_Ticket(L)查询DingTicket(L)订票WritehangbanFile(L)写航班文件WritehangbanFile(L)写航班文件WritedingpiaoFile(s)写订票文件图5.订票系统函数调用关系图Menu()总菜单Main_List()链表的函数Main_Expression()表达式求值的函数Main_BiTree()二参叉树求值的函数MainSor

10、tTree()二叉排序树的函数Main_Ticket()订票系统的函数图6.菜单程序的函数调用关系图五、详细设计：1.线性表：typedef struct Linklist /结点结构datatype data; /数据类型struct Linklist *next; /指向下一个结点的指针LNode,*Link;void Create_List(Link &L) /创建链表void Insert_List(Link &L,int i) /第i个元素前插入void Delete_List(Link &L,int i) /删除第i个元素void Print_List(Link L) /遍历2.表

11、达式求值 typedef struct Stack /结点结构char* Data; /数据类型int Top; /指示栈顶Stack;void InitStack(Stack &s); /栈初始化void Push(Stack &s,char e); /进栈 char Pop(Stack &s); /出栈int IsEmpty(Stack s); /判断栈空int IsFull(Stack s); /判断栈满char CalExp(char exp); /计算表达式的值int IsOperator(char ch); /判断是否为字符char Calculate(char a, char o

12、per,char b);/计算两个字符数字的值void Menu_Expression(char exp); /表达式求值的菜单void Main_Expression(); /表达式求值的主函数3.二叉树typedef struct BiTree /树的结点结构elemtype data; /数据类型struct BiTree *lchild; /指向左孩子struct BiTree *rchild; /指向右孩子TNode,*Tree;void Inite_BiTree(Tree &T); /二叉树初始化 void Create_BiTree(Tree &T); /创建二叉树void Pr

13、eOrderTraverse(Tree T); /递归地前序遍历void InOrderTraverse(Tree T); /递归地中序遍历void PostOrderTraverse(Tree T); /递归地后序遍历int CalculateLeaf(Tree T); /统计叶子结点数void Menu_BiTree(Tree &T); /菜单void Main_BiTree(); /二叉树的主函数4.二叉排序树typedef struct Sorttree /排序树的结点信息 int data; /数据类型 struct Sorttree *lc,*rc; /指向左右孩子结点STNode

14、,*STLink; void IniteSortTree(STLink &T);/初始化二叉排序树void CreateSortTree(STLink &T);/创建void InsertSortTree(STLink &T,int e);/插入void SearchSortTree(STLink &T,int e); /查找并删除 void DeleteSortTree(STLink &T);/删除void PrintSortTree(STLink T); /中序遍历void MenuSortTree(STLink &T);/菜单void MainSortTree();/主函数5.订票系统

15、typedef struct Hangban /航班信息结点结构int num; /航班号int price; /票价float zhekou; /折扣 char time110; /起飞时间char time210; /降落时间char qidian10; /起点char zhongdian10; /终点int shengyu; /剩余票数 struct Hangban * next; /指向下一个结点Tnode,*Ticket;typedef struct dingpiao /订票的信息结点结构int NO; /订单号 char name10; /订票人的姓名long ID; /订票人证件

16、号int piaoshu; /订票的数目Ticket Xingxi; /所订票的信息Ding;void Inite_Ticket(Ticket &L);/初始化航班信息链表void Create_Ticket(Ticket &L);/创建链表void ReadFile(Ticket &L);/读文件赋值void ChaXun_Ticket(Ticket L);/查询航班信息void DingTicket(Ticket &L);/订票void Printscreen(Ticket L);/打印void WriteFile(Ticket L);/写航班信息文件void WritedingpiaoF

17、ile(Ding s);/写订票文件void TuiTicket(Ticket &L,int j);/退票void Menu_Ticket(Ticket &L);/菜单void Main_Ticket();/订票系统的主函数六、程序编码：1.线性表的基本操作 #include#include#includelinklist.hvoid Inite_List(Link &L)/初始化链表 L=NULL; void Create_List(Link &L) /创建链表 int i=0,n; printf(输入链表的长度：); /设定要创建链表的长度 scanf(%d,&n); L=(Link)ma

18、lloc(sizeof(LNode);/申请结点空间 if(!L) /判断链表是否为空 printf(存储分配失败); exit(0); Link p=L,q;printf(输入链表结点数据); while(idata);p-next=q;p=q; i+;p-next=NULL;void Insert_List(Link &L,int i) /第i个元素前插入Link p=L,s;int j=0; while(p&jnext ; /p指向下一个结点j+;if(!p|ji-1) /i等于0或i大于表长加1，位置不合法printf(插入位置不对n);exit(0);s=(Link)malloc(s

19、izeof(LNode);printf(插入的元素为：);scanf(%d,&s-data);s-next=p-next;p-next=s;void Delete_List(Link &L,int i) /删除第i个元素 Link p=L,q;int j=0;while(p-next&jnext; /p指向下一个结点j+;if(!p-next|ji-1) /如果找不到第i个元素，删除位置不合法printf(删除位置不对n);exit(0);q=p-next;printf(删除的元素为:%dn,q-data);p-next=q-next;free(q); /释放结点空间int Length_Li

20、st(Link L)/计算表长int n=0;if(!L)printf(链表为空n);return NULL;Link p=L;while(p-next)p=p-next;n+;return n;void Print_List(Link L) /遍历if(!L) /如果链表为空printf(链表为空n);exit(0); Link p=L;p=p-next; /将p指向第一个数据元素printf(遍历结果为：);while(p) /循环读取各元素的数据printf(%dt,p-data);p=p-next; printf(当前链表的长度为%dn,Length_List(L);void Menu

21、_List(Link &L)/菜单printf(tt*链表菜单*n ); printf(ttt 退出按0n );printf(ttt 创建链表按1n );printf(ttt 插入元素按2n );printf(ttt 删除元素按3n );printf(ttt 遍历按4n );printf(ttt 返回主菜单按5n );printf(tt*n );int i; while(1) printf(请输入选择：); scanf(%d,&i);if(i=0)exit(0);else if(i=1)Create_List(L);/创建else if(i=2) int j; printf(输入插入元素的位置

22、:);/第j个位置插入 scanf(%d,&j); Insert_List(L,j); /插入else if(i=3)int i; printf(输入删除元素的位置:);/第i个位置删除 scanf(%d,&i); Delete_List(L,i);/删除else if(i=4)Print_List(L);/遍历else if(i=5)system(cls);/清空屏幕return;elseprintf(输入选择错误，重新输入： );printf(n);void Main_List()/线性表的主函数Link L;Inite_List(L);/初始化链表 Menu_List(L);/菜单2.表

23、达式求值#include #include #include expression.hvoid InitStack(Stack &s)/栈的初始化s.Data = (char*)malloc(N*sizeof(char);s.Top = -1;void Push(Stack &s,char e)/进栈if(s.Top=N)/栈的容量超出printf(Stack overflow); elses.Top+;s.Datas.Top = e;char Pop(Stack &s)/出栈char e;if(s.Top 0 )/如果栈为空printf(Stack is empty);elsee = s.D

24、atas.Top;s.Top-;return e;int IsEmpty(Stack s)/判断栈空if(s.Top 0 )return 1;return 0;int IsFull(Stack s)/判断栈满if(s.Top=N )return 1;return 0;int IsOperator(char ch)/判断是否为运算符if(ch=+ | ch =- | ch =*|ch=/|ch=#)return 1;return 0;char Calculate(char a, char oper,char b)/计算两个字符的值int c;switch(oper)/运算符的选择语句case +

25、:c = atoi(&a) + atoi(&b);/将字符转换成整型相加break;case -:c = atoi(&b) - atoi(&a);/将字符转换成整型相减break;case *:c = atoi(&a) * atoi(&b);/将字符转换成整型相乘break;case /:c = atoi(&b) / atoi(&a);/将字符转换成整型相除break;return c+0;char CalExp(char exp)/计算表达式的值Stack s;/定义栈char a,b,c;int cur = 0;InitStack(s);/初始化栈while(expcur != 0)/当前

26、字符不为“0”，则进行下面的循环if(IsOperator(expcur)/字符为运算符a = Pop(s);/出栈b = Pop(s);/出栈c = Calculate(a, expcur,b);/将上面出栈的两元素计算出结果Push(s,c);/将上面运算的结果进栈else/当前字符不为运算符时，继续进栈Push(s,expcur);cur+;/下一个字符return Pop(s);/将运算的结果返回void Menu_Expression(char exp)/表达式求值的菜单char value;int a;printf(tt*表达式求值菜单*n);printf(tt 退出按0n);pr

27、intf(tt 求表达式的值按1n);printf(tt 返回主菜单按2n);printf(tt*n); while(1)printf(n请输入选择：);scanf(%d,&a);switch(a)case 0:exit(0);case 1:printf(请输入后缀表达式：);scanf(%s,exp);value = CalExp(exp);/求值结果printf(该表达式求值的结果为:%s is %cn,exp,value);break;case 2:system(cls);return;void Main_Expression()/表达式求值的主函数char exp100;Menu_Ex

28、pression(exp);/菜单3.二叉树#include #include #include bitree.hvoid Inite_BiTree(Tree &T)/二叉树初始化T=NULL;void Create_BiTree(Tree &T)/创建二叉树 elemtype ch;scanf(%1s,&ch);if(ch=#)T=NULL;else if(!(T=(Tree)malloc(sizeof(TNode)printf(存储分配失败);exit(0);T-data=ch;Create_BiTree(T-lchild);Create_BiTree(T-rchild); void Pr

29、eOrderTraverse(Tree T)/递归地前序遍历if(T)printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild);void InOrderTraverse(Tree T)/递归地中序遍历if(T) InOrderTraverse(T-lchild);printf(%c,T-data); InOrderTraverse(T-rchild);void PostOrderTraverse(Tree T)/递归地后序遍历if(T) PostOrderTraverse(T-lchild); PostO

30、rderTraverse(T-rchild);printf(%c,T-data);int CalculateLeaf(Tree T)/统计叶子结点数int sum=0,m,n;if(T) if(!T-lchild)&(!T-rchild) sum+; m=CalculateLeaf(T-lchild); sum+=m; n=CalculateLeaf(T-rchild); sum+=n; return sum; void Menu_BiTree(Tree &T)int n;printf(tt*二叉树菜单* n);printf(tt 退出按0 n);printf(tt 创建二叉树按1 n); p

31、rintf(tt 先序遍历二叉树按2 n);printf(tt 中序遍历二叉树按3 n);printf(tt 后序遍历二叉树按4 n);printf(tt 输出叶子结点数按5 n);printf(tt 返回主菜单按6 n);printf(tt* n); while(1) printf(n请输入选择:); scanf(%d,&n); switch(n) case 0: exit(0); case 1: printf(请输入二叉树的结点信息(带#):); Create_BiTree(T); break;/创建树 case 2: printf(先序遍历结果为：); PreOrderTraverse(

32、T); break;/先序遍历 case 3:printf(中序遍历结果为：);InOrderTraverse(T);break;/中序遍历 case 4: printf(后序遍历结果为：); PostOrderTraverse(T); break;/后序遍历 case 5: printf(叶子结点数为：%dn,CalculateLeaf(T); break; case 6: system(cls); return; default: printf(选择错误，请重新输入选择：); break; void Main_BiTree()Tree T;Inite_BiTree(T);/初始化树Menu

33、_BiTree(T); /菜单程序4.二叉排序树 #include#include#include sorttree.hvoid IniteSortTree(STLink &T)/初始化二叉排序树T=NULL;void CreateSortTree(STLink &T)/创建二叉排序树int i=0,n;printf(请输入要创建的二叉排序树的长度：);scanf(%d,&n);printf(请输入各结点的信息：);while(ilc = T-rc = NULL; T-data = e; else if( e = T- data )/若n与当前节点的值相等，则不需插入了 printf(t插入失

34、败！该元素已存在！);return ; else if( e data)/若n比当前节点的值小，则往当前节点的左子树插 InsertSortTree( T-lc,e ); else/若n比当前节点的值大，则往当前节点的右子树插 InsertSortTree( T-rc,e ); void SearchSortTree(STLink &T, int e )/查找要删除的结点并删除 if( T ) if( T-data = e )/若找到节点，则返回当前节点 DeleteSortTree(T);printf(t删除成功!); else if( e data )/若x比当前节点的值小，则在当前节点的

35、左子树中去找 SearchSortTree( T - lc, e ); else/若x比当前节点的值大，则在当前节点的右子树中去找 SearchSortTree( T- rc, e ); elseprintf(t删除失败！找不到该元素!);return ;void DeleteSortTree(STLink &p)/删除结点STLink q,s; if( !p - rc) /要删除的结点没有右孩子 q=p; p=p-lc; free(p); else if(!p-lc)/要删除的结点没有孩子q=p;p=p-rc;free(q);else/要删除的结点左右孩子都有q=p;s=p-lc;while

36、(s-rc)q=s;s=s-rc;p-data=s-data;if(q!=p)q-rc=s-lc;else q-lc=s-lc;free(s);void PrintSortTree( STLink T ) if( T ) /递归的中序遍历 PrintSortTree( T - lc ); printf( %d ,T - data ); PrintSortTree( T - rc ); void MenuSortTree(STLink &T)/二叉排序菜单printf(tt*排序树菜单*n);printf(tt 退出按0 n);printf(tt 创建二叉排序树按1 n);printf(tt 插

37、入结点按2 n);printf(tt 删除结点按3 n);printf(tt 遍历二叉排序树按4 n);printf(tt 返回主菜单按5 n); printf(tt*n); int a;while(1)printf(n请输入选择：);scanf(%d,&a);switch(a)case 0:exit(0);case 1: CreateSortTree(T);/创建break;case 2:printf(输入要插入的元素为：);int e;scanf(%d,&e);InsertSortTree(T,e);/插入break;case 3:printf(输入要删除的元素：);STLink p;sc

38、anf(%d,&e); SearchSortTree(T,e);/删除break;case 4:printf(遍历结果为：); PrintSortTree(T);/中序遍历break;case 5:system(cls);return;default:printf(输入错误，请重新输入!);break;void MainSortTree()/二叉排序树的主函数STLink T;IniteSortTree(T);/初始化树MenuSortTree(T);/菜单5. 订票系统#include #include #include ticket.hvoid Inite_Ticket(Ticket &L)/航班信息链表的初始化 L=NULL;void Create_Ticket(Ticket &L)/创建航班信息的链表 Ticket p,q;int i=0;p=L=(Ticket)malloc(sizeof(Tnode);/申请结点空间if(L=NULL)printf(存储分配失败);exit(0);for(;inext=q;p=p-next;p-next=NULL;void ReadFile(Ticket &L)/读航班信息的文件FILE *fp;i