数据结构实验五

专业班级： 学 号： 姓 名：

实验时间： 实验地点： 指导教师：

一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算 二、实验的内容和步骤 下面是查找与排序的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。 # define MAX_LENGTH 100 typedef int KeyType; /* 顺序查找表的存储类型 */ typedef struct { KeyType *elem; int length; }SSTable; /* 在查找表中顺序查找其关键字等于 key 的数据元素。 */ int Search_Seq(SSTable ST,KeyType key) { int i; ST.elem[0]=key; for(i=ST.length;!(ST.elem[i]==key);--i) ; return (i); } /* 在有序查找表中折半查找其关键字等于 key 的数据元素*/ int Search_Seq(SSTable ST,KeyType key) { int mid,low=1,high=ST.length; while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid]) return (mid); else if(keydata) { p=T; return (OK); } else if(keydata) SearchBST(T->lchild,key,T,p); else SearchBST(T->rchild,key,T,p); } /*二叉排序树中插入算法*/ int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) //SearchBST() { if(!T) { p=f; 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); } //SearchBST() end /*二叉排序树中删除算法*/ int Delete(BiTree &p) { BiTree q,s; if(!p->data) { q=p; p=p->lchild; //Delete() sub-function 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; else } } /*链地址Hash表类型*/ typedef int ElemType; typedef struct LNode { typedef LNode * CHashTable [MAXSIZE] ; //链地址Hash表类型 /*求Hash函数*/ int H(int s)// { if(s) return s%11; //求关键字 else return 0; }//H /*输入数据的关键字函数*/ ElemType Inputkey() { ElemType x; cout<<\"请输入数据\"<lchild=s->rchild; }LNode,*LinkList; cin>>x; return x; } /*输入一组关键字,建立Hash表，表长为m，用链地址法处理冲突*/ int Build_Hash (CHashTable & T, int m) { ElemType key; LNode* q; int n; if(m<1) return ERROR; for(int i=0; idata=key; q->next=NULL; n=H(key); //查HASH表得到指针数组的地址 q->next=T[n]; //原来的头指针后移 T[n]=q; //新元素插入头部 } //while return OK; } /*输出用链地址法处理冲突的Hash表*/ int Print_Hash (CHashTable & T) { LNode* q; int n; for(int i=0; i<11; i++) { q=T[i]; //哈希表初始化 { } cout<data<<\" \"; q=q->next; while(q ) //输入元素有效 } return OK; } /*定义每个记录（数据元素）的结构*/ Typedef struct { //定义每个记录（数据元素）的结构 KeyType key ; //关键字 InfoType otherinfo; //其它数据项 }RecordType，node ; //例如node.key表示其中一个分量 /*定义顺序表L的结构*/ Typedef struct { //定义顺序表L的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 }SqList ,L; //例如L.r或L.length表示其中一个分量 //若r数组是表L中的一个分量且为node类型，则r中某元素的key分量表示为：r[i].key /*直接插入排序算法的实现： */ void InsertSort ( SqList &L ) { //对顺序表L作直接插入排序 for ( i = 2; i <=L.length; ++ i ) //直接在原始无序表L中排序 if (L.r[i].key < L.r[i-1].key) //若L.r[i]较小则插入有序子表内 { L.r[0]= L.r[i]; //先将待插入的元素放入“哨兵”位置 L.r[i]= L.r[i-1]; //子表元素开始后移 for ( j=i-2; L.r[0].key < L.r[j].key; --j ) L.r[j+1]= L.r[j]; //只要子表元素比哨兵大就不断后移 L.r[j+1]= L.r[0]; //直到子表元素小于哨兵，将哨兵值送入 //当前要插入的位置（包括插入到表首） } //if }// InsertSort /* 希尔排序算法（主程序）*/ void ShellSort(SqList &L，int dlta[ ]，int t) { //按增量序列dlta[0…t-1]对顺序表L作Shell排序 for(k=0；k0&&(r[0].key=pivotkey ) - -high; r[low]=r[high]; //比支点小的记录交换到低端； while(low0; - - i ) //把r[1…length]建成大根堆 HeapAdjust(r, i, length ); //使r[i…length]成为大根堆 …… } // HeapSort /*堆排序的算法实现 */ void HeapSort (HeapType &H ) { //对顺序表H进行堆排序 for ( i = H.length / 2; i >0; - - i ) HeapAdjust(H,i, H.length ); //for,建立初始堆 for ( i = H.length; i > 1; - -i) { H.r[1] ←→ H.r[i]; //交换，要借用temp HeapAdjust( H, 1,i-1 ); //从头重建最大堆, i-1=m } } HeapAdjust(r, i, m ){ current=i; temp=r[i]; child=2*i; while(child<=m){ //检查是否到达当前堆尾，未到尾则整理 if ( child=r[child].key ) breack; //根大则不必调整，函数结束 else { r[current]=r[child]; //否则子女中的大者上移 current= child; child=2* child; } //从根降到子女位置继续向下整理！ }// while r[current]=temp; //直到自下而上都满足堆定义，再安置函数入口的那个结点r[i] (即temp) } // HeapAdjust 1.顺序表的顺序查找 程序代码： #include #include #define MX_LENGTH 100 typedef int KeyType; typedef struct { KeyType *elem; int length; }SSTable; int creat(SSTable &L) { int k,i; L.elem=(int*)malloc(MX_LENGTH*sizeof(int)); if(!L.elem) return 0; L.length=0; cout<<\"请输入顺序表的长度：\"; cin>>k; L.length=k; cout<<\"请输入顺序表内元素：\"; for(i=1;i<=L.length;i++) { cin>>L.elem[i]; } } int out(SSTable &L) { int i; cout<<\"顺序表内元素为：\"; for(i=1;i<=L.length;i++) { cout<>key; x=Search_Seq(L,key); cout<<\"元素在顺序表的位置为(若在顺序表中没有，为0):\"; cout< #include #define MX_LENGTH 100 typedef int KeyType; typedef struct { KeyType *elem; int length; }SSTable; int creat(SSTable &L) { int k,i; L.elem=(int*)malloc(MX_LENGTH*sizeof(int)); if(!L.elem) return 0; L.length=0; cout<<\"请输入顺序表的长度：\"; cin>>k; L.length=k; cout<<\"请输入顺序表内元素：\"; for(i=1;i<=L.length;i++) { cin>>L.elem[i]; } } int out(SSTable &L) { int i; cout<<\"顺序表内元素为：\"; for(i=1;i<=L.length;i++) { cout<>key; x=Search_Seq(L,key); cout<<\"元素在顺序表的位置为(若在顺序表中没有，为0):\"; 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 &T) //createBiTree() sub-function { TElemType ch; cout<<\"请输入二叉树结点 (/ 为空结点) : \"; cin>>ch; if(ch=='/') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\"Overflow!\"; //no alloction return (ERROR); } T->data=ch; CreateBiTree(T->lchild); //create lchild CreateBiTree(T->rchild); //create rchild } return (OK); } //CreateBiTree() end /*前序遍历二叉树的递归算法*/ int PreOrderTraverse(BiTree T) //PreOrderTravers sub-function { if(T) { cout<data<<\"->\"; //visite T if (PreOrderTraverse(T->lchild)) //traverse lchild if (PreOrderTraverse(T->rchild)) //traverse rchild return (OK); return (ERROR); } //if end else return (OK); } //PreOrderTraverse() end /* 中序遍历二叉树的递归算法*/ int InOrderTraverse(BiTree T) //InOrderTraverse sub-function { if(T) { if (InOrderTraverse(T->lchild)) //traverse lchild { cout<data<<\"->\"; //visite T if(InOrderTraverse(T->rchild)) //traverse rchild return (OK); } return (ERROR); } //if end else return (OK); } //InOrderTraverse() end /*在二叉排序树中查找某关键字等于 key 的数据元素*/ int SearchBST(BiTree T,char key,BiTree f,BiTree &p) //SearchBST() Sub-function { if(!T) { p=f; 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 &T,TElemType e) { BiTree p,s; 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->lchild=s; } else p->rchild=s; return TRUE; } else return FALSE; } /*二叉排序树中删除算法*/ int Delete(BiTree &p) //Delete() sub-function { BiTree q,s; if(!p->rchild) { 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; else q->lchild=s->rchild; delete s; } return TRUE; } int DeleteBST(BiTree &T,TElemType key) { if(!T) return FALSE; else { if(key==T->data) return Delete(T); else if(keydata) return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key); } } int main() { char key; int t; BiTree T,f,p; CreateBiTree(T); cout<<\"1.二叉排序树的查找\"<>t; switch(t) { case 0: { break; } case 1: { cout<<\"请输入要查找的值：\"; cin>>key; SearchBST(T,key,f,p); cout<data; cout<>key; Insert(T,key); cout<<\"插入后排序树的先序遍历为：\"<>key; DeleteBST(T,key); cout<<\"删除后排序树的先序遍历为：\"< #include #define OK 1 #define ERROR 0 #define MAXSIZE 100 typedef int ElemType; typedef struct LNode { ElemType key; ElemType data; struct LNode *next; }LNode,*LinkList; typedef LNode * CHashTable [MAXSIZE];//链地址Hash表类型 /*求Hash函数*/ int H(int s)// { if(s) return s%11; //求关键字 else return 0; }//H /*输入数据的关键字函数*/ ElemType Inputkey() { ElemType x; cout<<\"请输入数据\"<>x; return x; } /*输入一组关键字,建立Hash表，表长为m，用链地址法处理冲突*/ int Build_Hash (CHashTable &T, int m) { ElemType key; LNode* q; int n; if(m<1) return ERROR; for(int i=0; idata=key; q->next=NULL; n=H(key); //查HASH表得到指针数组的地址 q->next=T[n]; //原来的头指针后移 T[n]=q; //新元素插入头部 } //while return OK; } /*输出用链地址法处理冲突的Hash表*/ int Print_Hash (CHashTable &T) { LNode* q; int n; for(int i=0; i<11; i++) { cout<<\"address\"<data<<\" \"; q=q->next; } cout<>m; cout<<\"建立哈希表：\"; cout< #include #include #include typedef struct ElemType { char number[20]; char name[10]; int Chinese; int math; int English; int total; }ElemType; typedef struct SqList { ElemType *elem; int length; }SqList; int CreatSqList(SqList &L,int n) { int i; L.length=n; L.elem=(ElemType *)malloc(n*sizeof(ElemType)); for(i=0;i>L.elem[i].number; cout<<\"请输入他的姓名:\"; cin>>L.elem[i].name; cout<<\"请输入他的语文成绩:\"; cin>>L.elem[i].Chinese; cout<<\"请输入他的数学成绩:\"; cin>>L.elem[i].math; cout<<\"请输入他的英语成绩:\"; cin>>L.elem[i].English; L.elem[i].total=L.elem[i].Chinese+L.elem[i].English+L.elem[i].math; } return 0; } int Searcch(SqList L) { char ch[20]; int i; getchar(); cout<<\"请输入你要查找的学号:\"; cin>>ch; for(i=0;i>ch; cout<<\"请输入最低总分:\"; cin>>t; for(i=0;i=t) { cout<<\"学号:\"<>n; CreatSqList(L,n); cout<<\"1.查找(输入学号)\"< #include #include #include //顺序表 typedef struct { int key; int otherinfo; }RedType; typedef struct { RedType r[2001]; int length; }SqList; //冒泡排序 void MP(SqList L) { int i,j,t; for(i=1;i<=L.length-1;i++) for(j=1;j<=L.length-i;j++) if(L.r[j].key>L.r[j+1].key) { t=L.r[j].key; L.r[j].key=L.r[j+1].key; L.r[j+1].key=t; } } //快速排序 int QS(SqList &L,int low,int high) { int pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low=pivotkey) high--; L.r[low]=L.r[high]; while(low0 && L.r[j].key>L.r[0].key;j=j-d) L.r[j+d]=L.r[j]; L.r[j+d]=L.r[0]; } } void Shell(SqList L) { int d[3]={5,3,1}; int i; for(i=0;i<3;i++) ShellSort(L,d[i]); } //堆排序 void HeapAdjust(SqList &L,int s,int m) { int j; for(j=2*s;j<=m;j=j*2) { L.r[0]=L.r[s]; if(j=1;i--) HeapAdjust(L,i,L.length); for(i=L.length;i>1;i--) { t=L.r[1]; L.r[1]=L.r[i]; L.r[i]=t; HeapAdjust(L,1,i-1); } } void main() { int rand(); int i; SqList L; LARGE_INTEGER large; __int64 c1,c2; double dff; L.length=2000; for(i=1;i<=L.length;i++) L.r[i].key=rand(); QueryPerformanceFrequency(&large); dff=large.QuadPart; QueryPerformanceCounter(&large); c1=large.QuadPart; MP(L); QueryPerformanceCounter(&large); c2=large.QuadPart; cout<<\"冒泡法所用的时间为\"<<(c2-c1)/dff*1000<<\"ms\"<