数据结构(C语言)课程设计.doc

数据结构与算法课程设计报告（2012 2013学年 第 1 学期） 计算机与信息工程学院2013年7月8日目 录一. 课程设计的目的与要求（含设计指标）2二. 方案实现与调试22.1 题目：航班查询系统22.2题目：字符串操作42.3：二叉树的运算262.4二叉树运算18三课程设计分析与总结10四. 源程序清单102.1航班查询系统102.2字符串操作182.3二叉树运算2192.4二叉树运算22设计日志25一. 课程设计的目的与要求（含设计指标） 设计目的1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。3、培养学生初步的软件设计及软件测试的能力。基本要求：学生必须仔细阅读数据结构课程设计指导书，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课程设计过程中不断检测自己的计划完成情况，有困难及时向教师汇报。课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）上机调试程序时间不少于4小时，总共至少要上机调试程序15小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。每位同学必须有可运行的程序，学生能清楚解释各自编写的程序，并回答教师的提问，学生回答的问题和程序运行的结果作为评分的主要衡量标准；（周三开始逐一检查）。二. 方案实现与调试2.1 题目：航班查询系统 2.1.1 题目内容 飞机航班信息包括：航班号、起点站、终点站、起飞时间、到达时间、机型以及票价，实例如下：设计航班查询系统要求能对飞机航班信息进行增加、删除、排序和查找。可按航班的航班号、起点站、终点站、起飞时间以及到达时间进行查询2.1.2算法描述及实验步骤 算法描述该航班查询系统采用线性链表存储。开始，创建链表。然后输出提示操作选项，由用户输入所选项序号。执行选项。当第一次操作结束后，提示是否继续进行操作，再有用户决定。 流程图 开始初始化变量输入操作选项判断选项执行操作输出执行结果判断是否继续操作结束是否2.1.3调试过程及实验结果 （1） 完成第一模块：链表创建以及添加，编译时出现警告：“warning c4091: typedef : ignored on left of struct fly when no variable is declared”，“typedef”时在结构体后面定义一个变量名，所以只需在结构体后面加一个变量名，或者是把结构体的“typedef”去掉。运行，结果提示错误。重新检查，发现调用的创建函数和添加函数位置放反了，修改错误，运行成功。 （2）完成其他模块。在编写排序模块时，链表的排序不懂，通过网上查找，用冒泡法，通过调换链表节点的数据进行排序。2.2题目：字符串操作 2.2.1题目内容字符串采用数组存储，建立两个字符串string1和string2.输出两个字符串。将字符串string2的头n个字符添加到string1的尾部，输出结果 查找string3在串string1中的位置，若string3在string1中不存在，则插入string3在string1中的m位置上。输出结果。2.2.2算法描述及实验步骤算法描述开始，输入两个字符串，然后将string2复制到string1后面。然后输string3，判断string3是否在string1内，若存在，输出找到；若不存在，输入插入位置，然后将string3插入string1中，输出string1，结束。流程图开始初始化变量输入两个字符串合并两个字符串输入字符串3判断3是否存在1中输出结果将3添加到1中结束是否2.2.3调试过程及实验结果（1）拷贝string3到string1时，因为移动string1后面的字符，忘了加结束标志，结果输出乱码。2.3：二叉树的运算2 2.3.1题目内容 任务 ：请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。2.3.2算法描述及实验步骤 算法描述 该题采用线性链表存储结构。开始，创建二叉树，链表。遍历整棵二叉树，查找叶子节 点，当找到是，将叶子节点放入链表当中。输出结果，结束。 流程图开始初始化变量创建二叉树创建链表输入数据遍历二叉树判断是否为叶子节点加入链表中输出链表结束判断是否结束是是否否2.3.3调试过程及实验结果2.4二叉树运算1 2.4.1题目内容 任务：求二叉树中指定两个结点共同的最近祖先。2.4.2算法描述及实验步骤算法描述 开始，创建二叉树。输入要查找的两个节点。判断两个节点位于根节点的哪一侧，若位于两侧，这根节点为它们的最近共同祖先，否则用递归遍历继续判断，查找。最后输出结果，结束。流程图开始初始化变量创建链表输入查找的节点是否位于根节点的两侧往节点所在一侧遍历输出结果结束是否2.4.3调试过程及实验结果 调试过程 这道题的核心的内容是找到要查找的两个节点，然后再找共同祖先，所以我采用的一下方法： 创建的树是事先排好序的，大于根节点的放在右边，小于根节点的放左边，相等输不进去。所以，通过判断查找的节点位于根节点的那一边，然后往那边查找。当两节点位于上一节点两侧时，则上一节点为最近共同祖先。 运行结果：三课程设计分析与总结1、这次课程设计为我们提供了一次实践机会，让我们用所学知识有所运用。2、在这次课程设计上，巩固了以前所学，并且查缺补漏；通过这次课程设计，有学习了许多新知识。四. 源程序清单2.1航班查询系统#include#include#include#define error 1#define ok 0typedef int status; /给int一个别名statustypedef struct fly /定义结构体char flynum6;char star10;char reach10;char startime6;char reachtime10;char type10;int price;typedef struct node /定义航班信息链表的机构体struct fly data; /数据域struct node *next; /指针域node,*link; void createlist(link &l) l = ( link ) malloc ( sizeof ( node ) ); l-next = null; / 先建立一个带头结点的空链表 status listinsert(link &l ) /增加航班信息link p,s,r;s=l-next;r=l;p = ( link ) malloc ( sizeof ( node ) ); /生成新节点if(!p)printf(n空间分配失败);return error;printf(n请输入航班信息);scanf(%s%s%s%s%s%s%d,&p-data.flynum,&p-data.star,&p-data.reach,&p-data.startime,&p-data.reachtime,&p-data.type,&p-data.price); while(s!=null) /判断该航班是否已经安排了if(strcmp(p-data.flynum,s-data.flynum)=0)printf(n该航班已经重复);return error;s=s-next;while ( r-next!=null) /添加航班 r=r-next; p-next=r-next;r-next=p;return ok;status delete(link &l) /删除航班信息link p,q;char num10;printf(n请输入要删除的航班号:);scanf(%s,&num);q=l;p=l-next;while(p-next!=null)if(strcmp(num,p-data.flynum)=0)break;q=q-next;p=p-next;q-next=p-next;free(p);return ok;void such_num(link l) /按航班号查询link p;char num10;printf(n请输入要查找的航班号);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.flynum)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_star(link l) /按起飞地点查询link p;char num10;printf(n请输入起飞地点:);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.star)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_reach(link l) /按到达地点查询link p;char num10;printf(n请输入到达地点:);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.reach)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_stime(link l) /按起飞时间查询link p;char num10;printf(n请输入起飞时间:);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.startime)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_rtime(link l) /按到达时间查询link p;char num10;printf(n请输入到达时间:);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.reachtime)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void show(link l) /显示航班信息link p;printf(n以下为所有航班信息:);p=l;while(p-next!=null)p=p-next;printf(n %s ,p-data.flynum); printf( %s ,p-data.star); printf( %s ,p-data.reach); printf( %s ,p-data.startime); printf( %s ,p-data.reachtime); printf( %s ,p-data.type); printf( %d ,p-data.price);printf(n);status sort(link l) /排序，通过交换数据进行排序；冒泡排序法link p,q,s;s = ( link ) malloc ( sizeof ( node ) ); if(!s)printf(n空间分配失败);return error;for(p=l-next;p!=null;p=p-next)for(q=p-next;q!=null;q=q-next)if(strcmp(p-data.startime,q-data.startime)0)s-data=p-data;p-data=q-data;q-data=s-data;show(l);return ok;void main() / 主函数link l;int i,a;printf( |-欢迎使用航班查询系统-|n);printf(n);printf(n *);printf(n * *);printf(n * 1 显示所有航班信息 *);printf(n * 2 航班号查询 *);printf(n * 3 起飞时间查询 *);printf(n * 4 到达时间查询 *);printf(n * 5 起飞地点查询 *);printf(n * 6 到达地点查询 *);printf(n * 7 增加航班信息 *);printf(n * 8 删除航班信息 *);printf(n * 9 航班排序 *);printf(n * *);printf(n *);createlist(l); /创建链表printf(n |-航班号-|-起飞地点-|-到达地点-|-起飞时间-|-到达时间-|-飞机类型-|-票价-|);for(i=0;i100;i+) /用于多长操作printf(nn请输入服务编号:);scanf(%d,&a);switch(a)case 1:show(l);break;case 2:such_num(l);break;case 3:such_stime(l);break;case 4: such_rtime(l); break;case 5:such_star(l);break;case 6:such_reach(l);break;case 7:listinsert(l);break;case 8:delete(l);case 9:sort(l);break;default:printf(输入无效);break;printf(n请按任意键继续操作! 退出请按0n);scanf(%d,&a);if(a=0)break;2.2字符串操作#include#includevoid main()int i,m,len1,len3,j;char string1100,string2100,string3100;char *p;printf(n请输入string1:);scanf(%s,&string1);printf(n请输入string2:);scanf(%s,&string2);printf(n请输入拷贝数n:);scanf(%d,&i);p=strncat(string1,string2,i); /调用strncat函数，完成字符串的合并。printf(%s,p);printf(n请输入string3:);scanf(%s,&string3);p=strstr(string1,string3); /查找string1中是否存在string3的片段if(p)printf(存在n);else /string3的插入printf(请输入插入位置m:);scanf(%d,&m);len3=strlen(string3);len1=strlen(string1);for(i=len1-1;i=m-1;i-)string1i+len3=string1i;string1len1+len3=0;for(i=0,j=m-1;ilen3;i+,j+)string1j=string3i;printf(%sn,string1);2.3二叉树运算2#include #include typedef int telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;binode, *bitree;bitree root;/定义根结点 void insert_data(int x) /*生成二叉排序树*/ bitree p,q,s;s=(bitree)malloc(sizeof(binode); /创建结点s-data=x; /结点赋值s-lchild=null;s-rchild=null;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序树的适当位置*/q=p;if(p-data=x) /相同结点不能重复插入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;void createlist(bitree &l) l = ( bitree ) malloc ( sizeof ( binode ) ); l-rchild = null; / 先建立一个带头结点的空链表 int preordertraverse(bitree root,bitree &l)bitree n,p,r;r=l;n=root;if(!n) return 0;if(n-lchild=null & n-rchild=null) /判断叶子结点并利用指针rchild生成单链表p=( bitree )malloc( sizeof ( binode ) );p-data=n-data;while ( r-rchild!=null) r=r-rchild; p-rchild=r-rchild;r-rchild=p;return 0;if(n-lchild)preordertraverse(n-lchild,l);if(n-rchild)preordertraverse(n-rchild,l);return 0;/*递归输出二叉树*/dlr( bitree root ) if (root !=null) /非空二叉树 printf( %d ,root-data); /访问d dlr(root-lchild); /递归遍历左子树 dlr(root-rchild); /递归遍历右子树 return(0); void main() bitree l;int i=1,x; /i记录结点个数，x存放结点值root=null; /*千万别忘了赋初值给root!*/printf(请输入数据,-9999表示输入结束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*从键盘采集数据，以-9999表示输入结束*/if(x=-9999) printf(nnow output data value:n); else insert_data(x); /*调用插入数据元素的函数*/while(x!=-9999);createlist(l); dlr(root); /遍历二叉树preordertraverse(root,l); /查找叶子节点printf(n now output data:n);l=l-rchild;while(l) /输出从左到右叶子节点printf( %d ,l-data);l=l-rchild;2.4二叉树运算#include #include typedef int telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild,*tag;binode, *bitree;bitree root;/定义根结点 void insert_data(int x) /*生成二叉排序树*/ bitree p,q,s;s=(bitree)malloc(sizeof(binode); /创建结点s-data=x; /结点赋值s-lchild=null;s-rchild=null;if(!root)root=s; elsep=root; while(p) /*