实验五实验五 查找与排序查找与排序实验课程名实验课程名：数据结构（数据结构（c c 语言版）语言版） 专业班级：专业班级： 学学 号：号： 姓姓 名：名： 实验时间：实验时间： 实验地点：实验地点： 指导教师：指导教师： 一、实验目的一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算二、实验的内容和步骤二、实验的内容和步骤下面是查找与排序的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。# define MAX_LENGTH 100typedef int KeyType;/*/* 顺序查找表的存储类型顺序查找表的存储类型 */*/typedef struct/define structure SSTable KeyType *elem;int length;SSTable;/*/* 在查找表中顺序查找其关键字等于在查找表中顺序查找其关键字等于 keykey 的数据元素。的数据元素。 */*/int Search_Seq(SSTable ST,KeyType key)/Search_Seq function int i;ST.elem0=key;for(i=ST.length;!(ST.elemi=key);-i);return (i);/if not find,return i=0/*/* 在有序查找表中折半查找其关键字等于在有序查找表中折半查找其关键字等于 keykey 的数据元素的数据元素*/*/int Search_Seq(SSTable ST,KeyType key)/Search_Seq function int mid,low=1,high=ST.length;while(lowdata) p=T;return (OK);else if(keydata)SearchBST(T-lchild,key,T,p);elseSearchBST(T-rchild,key,T,p);/*/*二叉排序树中插入算法二叉排序树中插入算法*/*/int SearchBST(BiTree T,KeyType key,BiTree f,BiTree return (ERROR);else if(key=T-data) p=T;return (OK);else if(keydata)SearchBST(T-lchild,key,T,p);elseSearchBST(T-rchild,key,T,p); /SearchBST() end/*/*二叉排序树中删除算法二叉排序树中删除算法*/*/int Delete(BiTree if(!p-data) q=p;p=p-lchild;free(q);else if(!p-lchild) q=p;p=p-rchild;free(q);else q=p;s=p-lchild;while(s-rchild) q=s;s=s-rchild;p-data=s-data;if(q!=p) q-rchild=s-lchild;elseq-lchild=s-rchild;/*/*链地址链地址HashHash表类型表类型*/*/typedef int ElemType;typedef struct LNodeElemType key;struct LNode *next;LNode,*LinkList;typedef LNode * CHashTable MAXSIZE ; /链地址Hash表类型/*/*求求HashHash函数函数*/*/int H(int s)/ if(s) return s%11; /求关键字else return 0;/H /*/*输入数据的关键字函数输入数据的关键字函数*/*/ElemType Inputkey()ElemType x;coutx;return x;/*/*输入一组关键字输入一组关键字, ,建立建立HashHash表，表长为表，表长为m m，用链地址法处理冲突，用链地址法处理冲突*/*/int Build_Hash (CHashTable LNode* q;int n;if(mdata=key; q-next=NULL; n=H(key); /查HASH表得到指针数组的地址 q-next=Tn; /原来的头指针后移Tn=q; /新元素插入头部 /whilereturn OK;/*/*输出用链地址法处理冲突的输出用链地址法处理冲突的HashHash表表*/*/int Print_Hash (CHashTable int n;for(int i=0; idatanext;cout0rlow=rhigh; /比支点小的记录交换到低端；while(low0; - - i ) /把r1length建成大根堆HeapAdjust(r, i, length ); /使rilength成为大根堆 / HeapSort/*/*堆排序的算法实现堆排序的算法实现 */*/void HeapSort (HeapType i 0; - - i )HeapAdjust(H,i, H.length ); /for,建立初始堆for ( i = H.length; i 1; - -i) H.r1 H.ri; /交换，要借用tempHeapAdjust( H, 1,i-1 ); /从头重建最大堆, i-1=m HeapAdjust(r, i, m )current=i; temp=ri; child=2*i; while(child=rchild.key ) breack; /根大则不必调整，函数结束else rcurrent=rchild; /否则子女中的大者上移current= child; child=2* child; /从根降到子女位置继续向下整理！/ whilercurrent=temp; /直到自下而上都满足堆定义，再安置函数入口的那个结点ri (即temp) / HeapAdjust 1.顺序表的顺序查找 程序代码：程序代码：#include #include #define MX_LENGTH 100 typedef int KeyType; typedef struct KeyType *elem; int length; SSTable; int creat(SSTable L.elem=(int*)malloc(MX_LENGTH*sizeof(int); if(!L.elem) return 0;L.length=0; coutk; L.length=k; coutL.elemi; int out(SSTable coutkey; x=Search_Seq(L,key); cout #include #define MX_LENGTH 100 typedef int KeyType; typedef struct KeyType *elem; int length; SSTable; int creat(SSTable L.elem=(int*)malloc(MX_LENGTH*sizeof(int); if(!L.elem) return 0; L.length=0; coutk; L.length=k; coutL.elemi; int out(SSTable coutkey; x=Search_Seq(L,key); cout #include #define MX_LENGTH 100 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int KeyType; typedef char TElemType;/* 二叉树节点的存储类型二叉树节点的存储类型 */ typedef struct BiTNode/define stricture BiTree TElemType data;struct BiTNode *lchild,*rchild; BiTNode, *BiTree;/*建立二叉树建立二叉树*/ int CreateBiTree(BiTree coutch;if(ch=/) T=NULL;else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) coutdata=ch;CreateBiTree(T-lchild); /create lchildCreateBiTree(T-rchild); /create rchildreturn (OK); /CreateBiTree() end /*前序遍历二叉树的递归算法前序遍历二叉树的递归算法*/ int PreOrderTraverse(BiTree T)/PreOrderTravers sub-function if(T) coutdata“; /visite T if (PreOrderTraverse(T-lchild)/traverse lchildif (PreOrderTraverse(T-rchild)/traverse rchildreturn (OK);return (ERROR); /if endelsereturn (OK); /PreOrderTraverse() end /* 中序遍历二叉树的递归算法中序遍历二叉树的递归算法*/ int InOrderTraverse(BiTree T) /InOrderTraverse sub-function if(T) if (InOrderTraverse(T-lchild)/traverse lchild coutdata“;/visite Tif(InOrderTraverse(T-rchild) /traverse rchildreturn (OK); return (ERROR); /if endelsereturn (OK); /InOrderTraverse() end /*在二叉排序树中查找某关键字等于在二叉排序树中查找某关键字等于 key 的数据元素的数据元素*/ int SearchBST(BiTree T,char key,BiTree f,BiTree return (ERROR);else if(key=T-data) p=T;return (OK); else if(keydata) SearchBST(T-lchild,key,T,p);else SearchBST(T-rchild,key,T,p); /二叉排序树的插入二叉排序树的插入 int Insert(BiTree if(!SearchBST(T,e,NULL,p) s=(BiTree)malloc(sizeof(BiTNode); s-data=e; s-lchild=s-rchild=NULL; if(!p) T=s; else if(edata) p-l