综合训练项目.doc

目录实验一 查找、排序2实验二 长整数运算23实验三 一元稀疏多项式计算器26实验四 迷宫求解39综合训练项目一 航空订票系统41综合训练项目二 文章编辑系统60综合训练项目三 家族族谱管理67综合训练项目四 图书管理系统84综合训练项目五 校园导游系统98实验一 查找、排序【问题描述】对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现；以及各种排序算法的实现。【基本要求】 1、掌握常用的查找、排序方法，及相应的算法实现。 2、能实现并应用某一种查找算法。理解各种排序方法的特点，并能加以灵活应用。 3、了解各种排序算法的时间复杂度分析。【实现提示】 1、查找相关实验内容及步骤。 建立顺序存储结构，构建一个顺序表，实现顺序查找算法。 typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; /表的长度 SSTable; 对顺序表先排序后，实现行二分法查找相关操作。 定义二叉树节点，根据节点的值进行查找，并且实现节点的插入，删除等操作。 typedef struct BiTnode /定义二叉树节点 int data; /节点的值 struct BiTnode *lchild,*rchild; BiTnode,*BiTree; 定义哈希表以及要查找的节点元素，创建哈希表，实现其相关查找操作。 typedef struct int num; Elemtype; /定义查找的结点元素 typedef struct Elemtype *elem; /数据元素存储基址 int count; /数据元素个数 int sizeindex; HashTable;/定义哈希表。 2. 排序相关实验内容及步骤。 定义记录类型。 typedef struct int key; /关键字项 RecType; 实现直接插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。 实现冒泡排序：设想被排序的记录数组R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。 实现快速排序：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。 实现直接选择排序：第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin（1in-1），该趟排序则是从当前无序区中选择出关键字最小的记录Rk，将它与无序区的的第一个记录Ri交换，有序区增加一个记录，使R1i,和Ri+1n分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。 实现堆排序：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R1作为二叉树的根，以下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是Ri/2。 实现二路归并排序：假设初始序列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 ElemType *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 = (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-elem);/释放元素空间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; 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);void 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 if(keyelemmid) /如果关键字小于mid对应的值high=mid-1;else low=mid+1; return result; /返回结果void printBin()SSTable *table; /声明变量int r;intn;ElemType key;printf(请输入元素个数:);scanf(%d,&n);Create(&table, n); /建立表printf(请输入);cout0)printf(关键字%d 在表中的位置是：%dn,key, r);else printf (查找失败，表中无此数据。nn);/二叉排序树typedef struct BiTnode /定义二叉树节点int data; /节点的值struct BiTnode *lchild,*rchild; /节点的左孩子，节点的右孩子BiTnode,*BiTree;/查找（根据节点的值查找）返回节点指针BiTree search_tree(BiTree T,int keyword,BiTree *father)BiTree p; / 临时指针变量*father = NULL; /先设其父亲节点指向空p = T; /p赋值为根节点（从根节点开始查找）while (p & p-data!=keyword) /如果不是p不指向空且未找到相同值的节点*father = p;/先将父亲指向自己（注意：这里传过来的father是二级指针）if (keyword data) /如果要找的值小于自己的值p = p-lchild; / 就向自己的左孩子开始找elsep = p-rchild; /否则向自己的右孩子开始查找return p; /如果找到了则返回节点指针BiTree creat_tree(int count)BiTree T,p; /设置两个临时变量T,pint i = 1;while (i data);/输入p指向节点的值p-lchild = p-rchild = NULL;/p的左孩子和右孩子都指向空i+;elseint temp;/ 如果不是空树scanf(%d,&temp);/输入节点的值search_tree(T,temp,&p);/查找节点要插入的位置。（T是根节点，插入的节点的值，父亲节点的地址）if (temp data)/如果插入的值小于父亲节点的值p-lchild = (BiTnode *)malloc(sizeof(BiTnode);/那么就为父亲节点的左孩子分配一个节点空间，并指向这个空间if (!p-lchild)return NULL;p = p-lchild;/分配成功，p指向自己的左孩子else/ 如果插入的值大于父亲节点的值p-rchild = (BiTnode *)malloc(sizeof(BiTnode);if (!p-rchild)return NULL;/分配不成功，退出p = p-rchild;/p指向自己的右孩子p - data = temp;/新分配的节点的值赋值为插入的值p - lchild = p-rchild = NULL;/使其左右节点均为NULLi+;return T;/返回根节点void InOrder(BiTree T)if(T)InOrder(T-lchild);printf(%d ,T-data);InOrder(T-rchild);int insert_tree(BiTree *T,int elem)/插入（根节点，插入的值）返回-1和,-1代表插入失败，代表成功BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode);/s指向新开辟一个节点if (!s)/为开辟成功return -1;/ 返回值-1s-data = elem;/新节点的值赋值为插入的值s-lchild = s-rchild = NULL;/其左右孩子为空p = search_tree(*T,elem,&father);/p赋值为要插入的节点if (!p)return -1;/未开辟成功，返回-1if (father = NULL)/如果父亲节点指向空，说明是空树*T = s;/让根节点指向selse if (elem data)/否则如果插入的值小于父亲的值father-lchild = s;/父亲的左孩子赋值为selsefather-rchild = s;/否则父亲的右孩子赋值为sreturn 0;/返回int delete_tree(BiTree *T,int elem) /删除树结点的操作BiTree s,p,q,father;/声明变量p = search_tree(*T,elem,&father);/查找if(!p)return -1;if(!p-lchild)/如果p的左孩子为空if (father = NULL)*T = p-rchild;/T指向左孩子free(p);/释放preturn 0;if (p = father-lchild)/如果p和father的左孩子相等father-lchild = p-rchild; /将p的左孩子的值赋给father的左孩子elsefather-rchild = p-rchild;/将p的左孩子的值赋给father的右孩子free(p);/释放preturn 0;elseif(!p-rchild)if (father = NULL)/如果father为空*T = p-lchild;/将p的左孩子赋给Tfree(p);/释放preturn 0;if (p = father-lchild)/如果p等于father的左孩子的值father-lchild = p-lchild; /将p的左孩子的值赋给father的左孩子elsefather-rchild = p-lchild; /将p的左孩子的值赋给father的右孩子free(p);return 0;elseq = p;s = p-lchild;/将p的左孩子赋给swhile (s-rchild)q = s;s = s-rchild;p-data = s-data;/将s的值赋给pif (q != p)/如果q不等于pq-rchild = s-lchild; /将s的左孩子值赋给p的右孩子elseq-lchild = s-lchild; /将s的左孩子值赋给p的右孩子free(s);/释放sreturn 0;void print1() /定义print1（）以便调用printf(t*n);printf(t1,输出中序遍历n);printf(t2,插入一个结点n);printf(t3,删除一个结点n);printf(t4,查找一个结点n);printf(t5,返回主菜单n);printf(t*n);void printTree()BiTree T,p; /声明变量T=NULL;inti,n;ElemType key;printf(请输入结点个数：n);scanf(%d,&n);/输入值printf(请输入);coutn;printf(个值：);T=creat_tree(n);/建立树print1();scanf(%d,&i);/输入各个值while(i!=5)/i不等于5时switch(i)case 1:printf(中序遍历二叉树结果如下：n);InOrder(T);/中序遍历break;case 2:printf(请输入要插入的结点值：);scanf(%d,&key);/输入要查找的关键字if(insert_tree(&T,key)/如果插入成功printf(插入成功！);elseprintf(已存在此元素！);break;case 3:printf(请输入要删除的结点值：);scanf(%d,&key); /输入要删除的关键字if(!(delete_tree(&T,key)/如果删除成功printf(删除成功！);elseprintf(不存在此元素！);break;case 4:printf(请输入要查找的结点值：);scanf(%d,&key); /输入要查找的关键字if(search_tree(T,key,&p)/如果查找成功printf(查找成功！);elseprintf(不存在此元素！);break;default:printf(按键错误！);printf(n);print1();scanf(%d,&i);/哈希表typedef struct int num; Elemtype;/定义查找的结点元素typedef struct Elemtype *elem; /数据元素存储基址int count; /数据元素个数int sizeindex; HashTable;/定义哈希表int Hash(int num) int p; p=num%11; return p; /定义哈希函数/冲突处理函数，采用二次探测再散列法解决冲突int collision(int p,int &c) int i,q; i=c/2+1; while(i=0) return q; else i=c/2+1; else q=(p-i*i)%MAX; c+; if(q=0) return q; else i=c/2+1; return 0;void InitHash(HashTable *H)/创建哈希表 int i; H-elem=(Elemtype *)malloc(MAX*sizeof(Elemtype); H-count=0; H-sizeindex=MAX; for(i=0;ielemi.num=0;/初始化，使SearHash函数能判断到底有没有元素在里面 int SearHash(HashTable H,int key,int *p)/查找函数 *p=Hash(key); while(H.elem*p.num!=key&H.elem*p.num!=0) *p=*p+1; if(H.elem*p.num=key) return 1; else return 0; void InsertHash(HashTable *H,Elemtype e) /如果查找不到就插入元素int p; SearHash(*H,e.num,&p); /查找H-elemp=e; +H-count; void printHash()/调用哈希表 HashTable H; int p,key,i,n; Elemtype e; InitHash(&H);printf(输入数据个数(11 ):);scanf(%d,&n);printf(请输入各个值：);for(i=0;in;i+) /输入n个元素scanf(%d,&e.num);/输入数字if(!SearHash(H,e.num ,&p) InsertHash(&H,e );/插入元素 else printf(已经存在n);/否则就表示元素的数字已经存在 printf(输入查找的数字:); scanf(%d,&key);/输入要查找的数字if(SearHash(H,key,&p)/能查找成功 printf(查找成功！);/输出位置 else printf( 不存在此元素！); void print()printf(t*n);printf(t1,顺序查找n);printf(t2,二分查找n);printf(t3,二叉排序树n);printf(t4,哈希查找n);printf(t5,退出程序n);printf(t*n);/ 主函数int main(int argc, char* argv)int i;/定义变量print();scanf(%d,&i);/输入要数字选择要使用的查找方法while(i!=5)/i不等于5时switch(i) case 1:/i=1时printf(顺序查找法：n);printSeq();/顺序查找法break;/跳出循环case 2:printf(二分查找法：n);printBin();/二分查找法break; /跳出循环case 3:printf(二叉排序树：n);printTree();/二叉排序树break; /跳出循环case 4:printf(哈希查找法：n);printHash();/哈希查找法break; /跳出循环default:printf(按键错误！);printf(n);print();/调用函数print()scanf(%d,&i);return 0;/返回0【附录-排序源程序】#includestdio.h#includestdlib.h#include string.h#define Max 100 typedef struct /定义记录类型int key; /关键字项RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第0个元素作为哨兵int n; /顺序表实际的长度/1、 直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。/=直接插入排序法=void InsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序 int i,j;for(i=2;i=n;i+) /依次插入R2，Rnif(Ri.keyRi-1.key) /若Ri.key大于等于有序区中所有的keys，则Ri留在原位 R0=Ri;j=i-1; /R0是Ri的副本 do /从右向左在有序区R1i-1中查找Ri 的位置 Rj+1=Rj; /将关键字大于Ri.key的记录后移 j-; while(R0.keyRj.key); /当Ri.keyRj.key 是终止Rj+1=R0; /Ri插入到正确的位置上/2、 冒泡排序的基本思想：设想被排序的记录数组R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上漂浮（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。/=冒泡排序=typedef enumFALSE,TRUE Boolean; /FALSE为0，TRUE为1void BubbleSort(SeqList R) /自下向上扫描对R做冒泡排序int i,j; Boolean exchange; /交换标志 for(i=1;i=i;j-) /对当前无序区Rin 自下向上扫描if(Rj+1.keyRj.key) /两两比较，满足条件交换记录R0=Rj+1; /R0不是哨兵，仅做暂存单元Rj+1=Rj;Rj=R0;exchange=TRUE; /发生了交换，故将交换标志置为真if(! exchange) /本趟排序未发生交换，提前终止算法return; /3、 快速排序的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。/1.=一次划分函数=int Partition(SeqList R,int i,int j) /对Rij做一次划分，并返回基准记录的位置 RecType pivot=Ri; /用第一个记录作为基准while(ij) /从区间两端交替向中间扫描，直到i=jwhile(i=pivot.key) /基准记录pivot相当与在位置i上j-; /从右向左扫描，查找第一个关键字小于pivot.key的记录Rjif(ij) /若找到的Rj.key pivot.key，则Ri+=Rj; /交换Ri和Rj，交换后i指针加1while(ij &Ri.key=pivot.key) /基准记录pivot相当与在位置j上i+; /从左向右扫描，查找第一个关键字小于pivot.key的记录Riif(i pivot.key，则Rj-=Ri; /交换Ri和Rj，交换后j指针减1Ri=pivot; /此时，i=j，基准记录已被最后定位return i; /返回基准记录的位置/2.=快速排序=void QuickSort(SeqList R,int low,int high) /Rlow.high快速排序 int pivotpos; /划分后基准记录的位置if(lowhigh) /仅当区间长度大于1时才排序pivotpos=Partition(R,low,high); /对Rlow.high做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1); /对左区间递归排序QuickSort(R,pivotpos+1,high); /对右区间递归排序/4、 直接选择排序的基本思想：第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin（1in-1），该趟排序则是从当前无序区中选择出关键字最小的记录Rk，将它与无序区的的第一个记录Ri交换，有序区增加一个记录，使R1i,和Ri+1n分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。/=直接选择排序=void SelectSort(SeqList R)int i,j,k;for(i=1;in;i+) /做第i趟排序（1in-1）k=i;for(j=i+1;j=n;j+) /在当前无序区Rin中选key最小的记录Rkif(Rj.keyRk.key)k=j; /k记下目前找到的最小关键字所在的位置if(k!=i) /交换Ri和RkR0=Ri;Ri=Rk;Rk=R0; /5、 堆排序的基本思想：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R1作为二叉树的根，以下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是Ri/2。对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列条件：/Ri.keyR2i.key并且Ri.keyR2i+1.key 称小堆根/或 Ri.keyR2i.key并且Ri.keyR2i+1.key 称大堆根/=大根堆调整函数=void Heapify(SeqList R,int low,int high) / 将Rlow.high调整为大根堆，除Rlow外，其余结点均满足堆性质 int large; /large指向调整结点的左、右孩子结点中关键字较大者RecType temp=Rlow; /暂存调整结点for(large=2*low; largehigh,则表示Rlow是叶子，调整结束；否则先令large指向Rlow的左孩子if(largehigh & Rlarge.key=Rlarge.key) /temp始终对应Rlowbreak; /当前调整结点不小于其孩子结点的关键字，结束调整Rlow=Rlarge; /相当于交换了Rlow和Rlargelow=large; /令low指向新的调整结点，相当于temp已筛下到large的位置Rlow=temp; /将被调整结点放入最终位置上/=构造大根堆=void BuildHeap(SeqList R) /将初始文件R1.n构造为堆 int i;for(i=n/2;i0;i-)Heapify(R,i,n); /将Ri.n调整为大根堆/=堆排序