《综合训练项目》由会员分享，可在线阅读，更多相关《综合训练项目（103页珍藏版）》请在金锄头文库上搜索。
1、目录实验一 查找、排序2实验二 长整数运算23实验三 一元稀疏多项式计算器26实验四 迷宫求解39综合训练项目一 航空订票系统41综合训练项目二 文章编辑系统60综合训练项目三 家族族谱管理67综合训练项目四 图书管理系统84综合训练项目五 校园导游系统98实验一 查找、排序【问题描述】对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现；以及各种排序算法的实现。【基本要求】 1、掌握常用的查找、排序方法，及相应的算法实现。 2、能实现并应用某一种查找算法。理解各种排序方法的特点，并能加以灵活应用。 3、了解各种排序算法的时间复杂度分析。【实现提示】 1、查找相关实验内容及
2、步骤。 建立顺序存储结构，构建一个顺序表，实现顺序查找算法。 typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; /表的长度 SSTable; 对顺序表先排序后，实现行二分法查找相关操作。 定义二叉树节点，根据节点的值进行查找，并且实现节点的插入，删除等操作。 typedef struct BiTnode /定义二叉树节点 int data; /节点的值 struct BiTnode *lchild,*rchild; BiTnode,*BiTree; 定义哈希表以及要查找的节点元素，创建哈希表，实现其相
3、关查找操作。 typedef struct int num; Elemtype; /定义查找的结点元素 typedef struct Elemtype *elem; /数据元素存储基址 int count; /数据元素个数 int sizeindex; HashTable;/定义哈希表。 2. 排序相关实验内容及步骤。 定义记录类型。 typedef struct int key; /关键字项 RecType; 实现直接插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。 实现冒泡排序：设想被排序的记录数组R1n垂直排序。根据轻气泡
4、不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。 实现快速排序：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。 实现直接选择排序：第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin（1in-1），该趟排序则是从当前无序区中选择出关键字最小的记录R
5、k，将它与无序区的的第一个记录Ri交换，有序区增加一个记录，使R1i,和Ri+1n分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。 实现堆排序：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R1作为二叉树的根，以下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是Ri/2。 实现二
6、路归并排序：假设初始序列n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直到一个长度为n的有序序列为止。记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。【附录-查找源程序】#includeiostream#includestdlib.h#includestdio.h#include malloc.h#define MAX 11 using namespace std;typedef int ElemType ;/顺序存储结构typedef struct ElemT
7、ype *elem; /数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; /表的长度 SSTable; void Create(SSTable *table, int length);void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem);void Create(SSTable *table, int length) / 构建顺序表 SSTable *t =
8、 (SSTable*) malloc(sizeof(SSTable);/分配空间t-elem=(ElemType*)malloc(sizeof(ElemType)*(length+1);t-length=length;*table=t;void FillTable(SSTable *table) / 无序表的输入ElemType *t=table-elem; for(int i=0; ilength; i+) /for循环，输入各个元素t+;scanf(%d, t); /输入元素getchar();void Destroy(SSTable *table) / 销毁表 free(table-el
9、em);/释放元素空间free(table);/释放表的空间void PrintTable(SSTable *table) / 打印查找表 int i; /定义变量ElemType *t=table-elem;for(i=0; ilength; i+) /进入循环，依次打印表中元素 t+;printf(%d , *t); /打印输出printf(n);int Search_Seq(SSTable *table, ElemType key) /哨兵查找算法table-elem0=key; /设置哨兵int result=0; / 找不到时，返回int i;for (i=table-length;
10、 i=1;i-) if (table-elemi=key) result=i;break;return result; /返回结果void printSeq()SSTable *table; /先设置几个变量int r;intn;ElemType key;printf(请输入元素个数:); scanf(%d,&n); /输入元素个数Create(&table, n); /建立表printf(请输入);cout0)printf( 关键字%d 在表中的位置是：%dn,key, r);/打印关键字在表中的位置printf(n);else /查找失败printf (查找失败，表中无此数据。nn);vo
11、id Sort(SSTable *table ) / 排序算法 int i, j;ElemType temp; for (i=table-length; i=1 ;i-) / 从前往后找 for (j=1; jelemjtable-elemj+1)temp=table-elemj;table-elemj=table-elemj+1;table-elemj+1=temp; int Search_Bin(SSTable *table, ElemType key) / 二分法查找（非递归） int low=1; int high=table-length; int result=0; / 找不到时，返回 while(low elemmid=key) /如果找到result=mid;break;else i
