厦门理工 数据结构 课程设计报告.doc

数据结构课程设计报告姓 名： 李宇翔 学 号： 1007052240 班 级： 10软件工程2班 设计时间： 2011.12.19-12.24 审阅教师： 谢彦麒 一、设计目的1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。3、培养学生初步的软件设计及软件测试的能力。二、设计任务及要求基本要求学生必须仔细阅读数据结构课程设计指导书，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准；（周二下午开始逐一检查） NO.1航班管理系统一、题目内容的描述 1航班查询系统飞机航班信息包括：航班号、起点站、终点站、起飞时间、到达时间、机型以及票价，实例如下：设计航班查询系统要求能对飞机航班信息进行增加、删除、排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间进行查询。二、应用程序功能的详细说明 通过建立一个链表来实现航班信息储存功能，每个结点的信息包括航班号、出发地、目的地、出发时间、到达时间、是否经停、价格，并编写功能函数使系统具有插入、查询、删除、更新、排序的功能。三、主要模块的算法描述 菜单选项菜单选项图航班信息的建立 插入信息 查询航班：四、结束语 通过此程序的编写我熟悉了链表的运用，链表是本学期学习的重点，灵活性比栈好，可以通过指针实现插入删除等功能，但要注意移动指针的逻辑关系，如果不注意很容易指向了不是你要的地方。五、程序的源代码清单 #include stdio.h#include stdlib.h#include ctype.h#include process.h#include string.h #includeusing namespace std;struct flight /定义航班信息结构体 char flight_num10;char flight_start20;char flight_destination20;char flight_takeoff_time10;char flight_arrive_time10;char flight_isStop5;int flight_price;struct flight *next;void welcome()/显示程序菜单 printf(*欢迎使用航班管理系统*n); printf(*n); printf(*n); printf(*按下对应数字实现相应功能*n); printf(*1.创建航班信息*n); printf(*2.增加航班信息*n); printf(*3.查询航班信息*n); printf(*4.删除航班信息*n); printf(*0.退出管理系统*n); printf(*n); printf(*n); printf(*CopyRight By KobeLee*n); printf(*n);struct flight * InitSystem(int n)/建立航班信息链表 int i;struct flight * head,* p,*s; for(i=1;iflight_num); printf(出发地：); scanf(%s,&p-flight_start); printf(目的地：); scanf(%s,&p-flight_destination); printf(起飞时间：); scanf(%s,&p-flight_takeoff_time); printf(到达时间：); scanf(%s,&p-flight_arrive_time); printf(经停：); scanf(%s,&p-flight_isStop); printf(价格：); scanf(%d,&p-flight_price); head-next=p; else s=(struct flight * )malloc(sizeof(struct flight); printf(航班号：); scanf(%s,&s-flight_num); printf(出发地：); scanf(%s,&s-flight_start); printf(目的地：); scanf(%s,&s-flight_destination); printf(起飞时间：); scanf(%s,&s-flight_takeoff_time); printf(到达时间：); scanf(%s,&s-flight_arrive_time); printf(经停：); scanf(%s,&s-flight_isStop); printf(价格：); scanf(%d,&s-flight_price); s-next=head-next; head-next=s; printf(n); return head;int Insert(struct flight *head)/添加航班信息，头插法；struct flight * p,*pi;pi=(struct flight *)malloc(sizeof(struct flight);/为新添加的航班开辟空间 p=head;printf(请输入新添加的航班信息：nn); printf(航班号：); scanf(%s,&pi-flight_num);printf(出发地：); scanf(%s,&pi-flight_start); printf(目的地：); scanf(%s,&pi-flight_destination); printf(起飞时间：); scanf(%s,&pi-flight_takeoff_time); printf(到达时间：); scanf(%s,&pi-flight_arrive_time); printf(经停：); scanf(%s,&pi-flight_isStop); printf(价格：); scanf(%d,&pi-flight_price); if(head=NULL) head-next=pi; pi-next=NULL; else pi-next=p-next; p-next=pi; return 0; void SearchByFlightNum(flight * head)char num10; printf(请输入航班号：);scanf(%s,&num);if(head-next=NULL) printf(没有航班信息，不能查询，请先创建信息。); return; else int count=0; while(head-next!=NULL) head=head-next; if(strcmp(num,head-flight_num)=0) printf(航班号 出发地 目的地 起飞时间 到达时间 是否经停 价格 n); printf(%-8s%-10s%-10s%-10s%-10s%-12s%d n,head-flight_num,head-flight_start,head-flight_destination,head-flight_takeoff_time,head-flight_arrive_time,head-flight_isStop,head-flight_price); count+; if(count=0)printf(没有找到所需航班，请重新查询。); return; void SearchByFlightStart(flight * head)char start10; printf(请输入出发地：);scanf(%s,&start);if(head-next=NULL) printf(没有航班信息，不能查询，请先创建信息。nn); return; else int count=0; while(head-next!=NULL) head=head-next; if(strcmp(start,head-flight_start)=0) printf(航班号 出发地 目的地 起飞时间 到达时间 是否经停 价格 n); printf(%-8s%-10s%-10s%-10s%-10s%-12s%d n,head-flight_num,head-flight_start,head-flight_destination,head-flight_takeoff_time,head-flight_arrive_time,head-flight_isStop,head-flight_price); count +; if(count=0) printf(没有找到所需航班，请重新查询。); return; void SearchByFlightDestination(flight * head)char destination10; printf(请输入目的地：);scanf(%s,&destination);if(head-next=NULL) printf(没有航班信息，不能查询，请先创建信息。n); return; else int count=0; while(head-next!=NULL) head=head-next; if(strcmp(destination,head-flight_destination)=0) printf(航班号 出发地 目的地 起飞时间 到达时间 是否经停 价格 n); printf(%-8s%-10s%-10s%-10s%-10s%-12s%d n,head-flight_num,head-flight_start,head-flight_destination,head-flight_takeoff_time,head-flight_arrive_time,head-flight_isStop,head-flight_price); count +; if(count=0)printf(没有找到所需航班，请重新查询。nnn); return; void SearchByFlightPrice(flight * head)int price;printf(请输入价格：);scanf(%d,&price);if(head-next=NULL) printf(没有航班信息，不能查询，请先创建信息。nn); return; else int count=0; while(head-next!=NULL) if(head-flight_price=price) printf(航班号 出发地 目的地 起飞时间 到达时间 是否经停 价格 n); printf(%-8s%-10s%-10s%-10s%-10s%-12s%d n,head-flight_num,head-flight_start,head-flight_destination,head-flight_takeoff_time,head-flight_arrive_time,head-flight_isStop,head-flight_price); count+; head=head-next; if(count=0) printf(没有找到符合条件的航班，请重新查询。nnn); return; void Search(flight * head) if(head-next=NULL) printf(没有可供查询的航班信息，请先添加信息。); return; int Search_way;system(cls);printf(*选择查询方式*n);printf(*n);printf(*1.按航班号查询*n);printf(*2.按出发地查询*n);printf(*3.按目的地查询*n);printf(*4. 按价格查询 *n);printf(*0. 退出查询*n);printf(*nnn);scanf(%d,&Search_way);switch(Search_way)case 1: SearchByFlightNum(head);break; case 2:SearchByFlightStart(head);break;case 3:SearchByFlightDestination(head);break;case 4:SearchByFlightPrice(head);break;case 0: break;default:break; return;struct flight * Delete(flight * head,char num10)struct flight *p,*q;p=head;if(p-next=NULL)printf(航班信息为空，不能删除，请先创建航班信息。n);return head; while(strcmp(p-flight_num,num)!=0)&p-next!=NULL)q=p;p=p-next;if(strcmp(p-flight_num,num)=0)if(p=head) head=p-next; else q-next=p-next; free(p); printf(成功删除。); else printf(没有您要删除的航班，请确认输入正确。n); return head; void List(struct flight * head)struct flight *p;p=head-next;printf(所有航班信息：n);printf(航班号 出发地 目的地 起飞时间 到达时间 是否经停 价格 n);while(p!=NULL) printf(%-8s%-10s%-10s%-10s%-10s%-12s%d n,p-flight_num,p-flight_start,p-flight_destination,p-flight_takeoff_time,p-flight_arrive_time,p-flight_isStop,p-flight_price); p=p-next;int main() char choice; int create_num=0;struct flight * head;int price;dosystem(cls); welcome(); scanf(%c,&choice);switch(choice)case 1:printf(请输入需要创建的信息条数:);scanf(%d,&create_num); head=InitSystem(create_num);List(head);break;case 2:Insert(head);List(head);break;case 3:Search(head);break;case 4:if(head-next!=NULL)char Delete_num10;List(head);printf(请输入要删除的航班号：n);scanf(%s,&Delete_num);head=Delete(head,Delete_num);List(head);else printf(没有航班信息，不能删除，请先添加信息。);break; default:break;system(pause);while(choice!=0);return 0; NO.2寻找二叉排序树的公共祖先一、题目内容的描述 任务：求二叉树中指定两个结点共同的最近祖先。二、应用程序功能的详细说明 建立一棵二叉排序数，任意输入其中两个结点，找到最近的公共祖先。三、输入数据类型、格式和内容限制； #include #include #define max 50typedef struct treeint data;struct tree *lchild,*rchild;test;四、主要模块的算法描述 五、结束语 在此过程中，我对二叉排序数的生成和结构有了更深的理解。在实现功能的时候，失败了很多次，但是和同学交流以及借助网络，最终成功实现了。六、程序的源代码清单 #include #include #define max 50typedef struct treeint data;struct tree *lchild,*rchild,*parent;test;tree *root,*p,*qmax;int sum=0;int m=sizeof(test); void insert_data(int x) /*生成二叉排序树*/ tree *p,*q,*s;s=(test*)malloc(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s; p=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x)if(p=s) return;printf(data already exist! n);return;else if(xdata)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;tree * findRoot(tree *T,int a,int b)tree *p,*parent;p=parent=T;while(p!=NULL)if(adata&bdata)parent=p;p=p-lchild;else if(ap-data&bp-data)parent=p;p=p-rchild;else if(adata&bp-data)|(ap-data&bdata)return p;else if(a=p-data|b=p-data)return parent; int main() /*先生成二叉排序树*/int i,x;i=1; root=NULL; /*千万别忘了赋初值给root!*/doprintf(please input data%d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999); int a,b;tree * T1,* T2;printf(请输入要寻找父亲的结点：);scanf(%d%d,&a,&b); p=findRoot(root,a,b); printf(n结点%d与结点%d的最近公共祖先是%dn,a,b,p-data); return 0; NO.3字符串的操作一、题目内容的描述 任务：字符串采用数组存储，建立两个字符串String1和String2.输出两个字符串。 将字符串String2的头n个字符添加到String1的尾部，输出结果。 查找String3在串String1中的位置，若