2022年数据结构课程设计 2.pdf

《2022年数据结构课程设计 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课程设计 2.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法课程设计报告（2012 2013 学年第 1 学期）计算机与信息工程学院2013 年7 月8 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 25 页 - - - - - - - - - 目录一. 课程设计的目的与要求（含设计指标） . 2二. 方案实现与调试 . 22.1 题目：航班查询系统 . 22.2 题目：字符串操作 . 42.3：二叉树的运算2 . 62.4 二叉树运算 1 . 8三课程设计分析与总结 . 10四. 源程序清单 . 102.1 航

2、班查询系统 . 102.2 字符串操作 . 182.3 二叉树运算 2 . 192.4 二叉树运算 . 22设计日志 . 错误！未定义书签。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 25 页 - - - - - - - - - 一. 课程设计的目的与要求（含设计指标）设计目的1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。3、培养学生初步的软件设计及

3、软件测试的能力。基本要求：学生必须仔细阅读数据结构课程设计指导书，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间， 安排好课设的时间计划，并在课程设计过程中不断检测自己的计划完成情况，有困难及时向教师汇报。课程设计按照教学要求需要一周时间完成，一周中每天 （按每周5天）上机调试程序时间不少于4 小时，总共至少要上机调试程序15 小时。根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。每位同学必须有可运行的程序，学生能清楚解释各自编写的程序，并回答教师的提问，学生回答的问

4、题和程序运行的结果作为评分的主要衡量标准；（周三开始逐一检查）。二. 方案实现与调试2.1 题目：航班查询系统2.1.1 题目内容飞机航班信息包括：航班号、起点站、终点站、起飞时间、到达时间、机型以及票价，实例如下：设计航班查询系统要求能对飞机航班信息进行增加、删除、排序和查找。 可按航班的航班号、起点站、终点站、起飞时间以及到达时间进行查询名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 25 页 - - - - - - - - - 2.1.2 算法描述及实验步骤算法描述

5、该航班查询系统采用线性链表存储。开始，创建链表。然后输出提示操作选项，由用户输入所选项序号。 执行选项。 当第一次操作结束后，提示是否继续进行操作，再有用户决定。流程图2.1.3 调试过程及实验结果（1） 完成第一模块： 链表创建以及添加， 编译时出现警告：“warning C4091: typedef : ignored on left of struct fly when no variable is declared” ， “typedef”时在结构体后面定义一个变量名，所以只需在结构体后面加一个变量名，或者是把结构体的“typedef”去掉。运行，结果提示错误。重新检查，发现调用的创建

6、函数和添加函数位置放反了，修改错开始初始化变量输入操作选项判断选项执行操作输出执行结果判 断 是 否继续操作结束是否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 25 页 - - - - - - - - - 误，运行成功。（2）完成其他模块。在编写排序模块时，链表的排序不懂，通过网上查找，用冒泡法，通过调换链表节点的数据进行排序。2.2 题目：字符串操作2.2.1 题目内容字符串采用数组存储，建立两个字符串String1和 String2.输出两个字符串。将字符串 St

7、ring2的头 n 个字符添加到String1的尾部，输出结果查找 String3在串String1中的位置，若String3在 String1中不存在，则插入String3在 String1中的 m位置上。输出结果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 25 页 - - - - - - - - - 2.2.2 算法描述及实验步骤算法描述开始，输入两个字符串，然后将string2复制到 string1后面。然后输string3，判断string3是否在 stri

8、ng1内，若存在， 输出找到； 若不存在， 输入插入位置， 然后将 string3插入 string1中，输出string1，结束。流程图开始初始化变量输入两个字符串合并两个字符串输入字符串3 判断 3 是否存在1输出结果将 3 添加到 1 中结束是否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 25 页 - - - - - - - - - 2.2.3 调试过程及实验结果（1）拷贝 string3到 string1时，因为移动string1后面的字符，忘了加结束标志，结

9、果输出乱码。2.3：二叉树的运算2 2.3.1题目内容任务 ：请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。2.3.2 算法描述及实验步骤算法描述该题采用线性链表存储结构。开始，创建二叉树，链表。遍历整棵二叉树，查找叶子节点，当找到是，将叶子节点放入链表当中。输出结果，结束。流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 25 页 - - - - - - - - - 开始初始化变量创

10、建二叉树创建链表输入数据遍历二叉树判 断 是 否为 叶 子 节加入链表中输出链表结束判 断 是 否结束是是否否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 25 页 - - - - - - - - - 2.3.3 调试过程及实验结果2.4 二叉树运算 1 2.4.1题目内容任务：求二叉树中指定两个结点共同的最近祖先。2.4.2 算法描述及实验步骤算法描述开始，创建二叉树。输入要查找的两个节点。判断两个节点位于根节点的哪一侧，若位于两侧， 这根节点为它们的最近共同祖先，否

11、则用递归遍历继续判断，查找。最后输出结果，结束。流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 25 页 - - - - - - - - - 2.4.3 调试过程及实验结果调试过程这道题的核心的内容是找到要查找的两个节点，然后再找共同祖先，所以我采用的一下方法：创建的树是事先排好序的，大于根节点的放在右边，小于根节点的放左边，相等输不进去。所以， 通过判断查找的节点位于根节点的那一边，然后往那边查找。当两节点位于上一开始初始化变量创建链表输入查找的节点是否位于根节点

12、的两侧往节点所在一侧遍历输出结果结束是否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 25 页 - - - - - - - - - 节点两侧时，则上一节点为最近共同祖先。运行结果：三课程设计分析与总结1、这次课程设计为我们提供了一次实践机会，让我们用所学知识有所运用。2、在这次课程设计上，巩固了以前所学，并且查缺补漏；通过这次课程设计，有学习了许多新知识。四. 源程序清单2.1 航班查询系统#include #include #include #define ERRO

13、R 1 #define OK 0 typedef int Status; /给 int 一个别名Status 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 25 页 - - - - - - - - - typedef struct fly /定义结构体 char Flynum6; char star10; char reach10; char startime6; char reachtime10; char Type10; int price; ; typedef

14、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) prin

15、tf(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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

16、- 名师精心整理 - - - - - - - 第 12 页，共 25 页 - - - - - - - - - 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) i

17、f(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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 25 页 - - - - - - - - -

18、 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;

19、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 ,

20、p-data.price); void Such_Reach(Link L) /按到达地点查询 Link p; char num10; printf(n 请输入到达地点:); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 25 页 - - - - - - - - - scanf(%s,&num); p=L-next; while(p!=NULL) if(strcmp(num,p-data.reach)=0) break; p=p-next; printf( %s ,p

21、-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(s

22、trcmp(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; 名师资料总结 - - -精品资料欢

23、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 25 页 - - - - - - - - - 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); p

24、rintf( %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-

25、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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 2

26、5 页 - - - - - - - - - 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); prin

27、tf(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 增 加 航 班 信 息名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

28、 - - - 第 17 页，共 25 页 - - - - - - - - - *); 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); brea

29、k; 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

30、 第 18 页，共 25 页 - - - - - - - - - default: printf( 输入无效 ); break; printf(n 请按任意键继续操作! 退出请按0n); scanf(%d,&a); if(a=0) break; 2.2 字符串操作#include #include void main() int i,m,len1,len3,j; char string1100,string2100,string3100; char *p; printf(n 请输入 string1:); scanf(%s,&string1); printf(n 请输入 string2:); s

31、canf(%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=st

32、rlen(string3); len1=strlen(string1); for(i=len1-1;i=m-1;i-) string1i+len3=string1i; string1len1+len3=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 25 页 - - - - - - - - - for(i=0,j=m-1;ilen3;i+,j+) string1j=string3i; printf(%sn,string1); 2.3 二叉树运算 2 #includ

33、e #include typedef int TElemType; typedef struct BiTNode TElemType 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; else p=r

34、oot; while(p) /*如何接入二叉排序树的适当位置*/ q=p; if(p-data=x) /相同结点不能重复插入 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 25 页 - - - - - - - - - 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

35、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-dat

36、a; while ( r-rchild!=NULL) r=r-rchild; p-rchild=r-rchild; r-rchild=p; return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 25 页 - - - - - - - - - if(n-lchild) PreOrderTraverse(n-lchild,L); if(n-rchild) PreOrderTraverse(n-rchild,L); return 0; /*递归输出二叉树*/ DL

37、R( 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); do printf(please input data %d:,i); i+; scanf(%d,&x); /

38、*从键盘采集数据，以-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) /输出从左到右叶子节点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

39、- - - - 名师精心整理 - - - - - - - 第 22 页，共 25 页 - - - - - - - - - printf( %d ,L-data); L=L-rchild; 2.4 二叉树运算#include #include typedef int TElemType; typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild,*tag; BiNode, *Bitree; Bitree root;/ 定义根结点void insert_data(int x) /*生成二叉排序树*/ Bitree p

40、,q,s; s=(Bitree)malloc(sizeof(BiNode); /创建结点s-data=x; /结点赋值s-lchild=NULL; s-rchild=NULL; if(!root) root=s; else p=root; while(p) /*如何接入二叉排序树的适当位置*/ q=p; if(p-data=x) /相同结点不能重复插入 printf(data already exist! n); return; else if(xdata) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

41、- - - - - 第 23 页，共 25 页 - - - - - - - - - p-tag=p; p=p-lchild; else p-tag=p; p=p-rchild; if(xdata) q-lchild=s; else q-rchild=s; DLR( Bitree root ) if (root !=NULL) /非空二叉树printf( %d ,root-data); /访问 D DLR(root-lchild); /递归遍历左子树DLR(root-rchild); /递归遍历右子树 return(0); int PreOrderTraverse(Bitree root, in

42、t a,int b) /* 从根节点开始，判断所查找的节点在根节点的哪一边，即从那边开始遍历，若在两侧，则根节点为两者最近的共同祖先*/ Bitree p; p=root; if(p-dataa&p-datab) PreOrderTraverse(p-lchild,a,b); else if(p-datadatarchild,a,b); else if(p-dataa&p-datadatadatab) printf( 两者最小的共同祖先为:%dn,p-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

43、 - - - - - - 第 24 页，共 25 页 - - - - - - - - - else if(p-data=a|p-data=b) printf( 两者最小的共同祖先为:%dn,a); return 0; void main() /*先生成二叉排序树*/ int i=1,x,a,b; /i 记录结点个数，x 存放结点值root=NULL; /*千万别忘了赋初值给root!*/ printf( 请输入数据 ,-9999 表示输入结束n); do printf(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); DLR(root); printf(n 请输入查找的两个节点:); scanf(%d%d,&a,&b); PreOrderTraverse(root,a,b); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 25 页 - - - - - - - - -