《验证性实验.doc》由会员分享，可在线阅读，更多相关《验证性实验.doc（12页珍藏版）》请在三一文库上搜索。
1、实验名称：第9章实验实验类型：验证性实验姓名：车红岫实验日期：2013.61. 问题描述以下四个验证性实验都做。（1）顺序查找验证（2）折半查找验证（3）二叉排序树的建立（4）哈希表的建立2. 数据结构设计（1）顺序查找验证typedef struct KeyType *elem; /零号单元留空int len gth; /表长度SSTable;（2）折半查找验证int score100;int len gth;int key;（3）二叉排序树的建立typedef struct nodedatatype key;struct node *lchild,*rchild;bs no de;（4）哈
2、希表的建立typedef structL nodeint data;structL node *n ext;Ln ode, *ListLi nk; /建立链表结点typedef structin tpos;ListLi nkfirst node; /建立数组结点HashBox;typedef structHashBoxHArraryINIT_MAXSIZE; /建立哈希数组(哈希表的地址表头 )HashArray;3. 算法设计4. 界面设计(1) 顺序查找验证(2) 折半查找验证(3) 二叉排序树的建立(4) 哈希表的建立5. 运行、测试(一) 顺序查找验证(1) 运行程序，显示菜单(2)
3、输入n(3) 输岀结果(二) 折半查找验证(1) 运行程序，显示菜单(2) 输入n(3) 输岀结果(三) 二叉排序树的建立(1) 运行程序，显示菜单(2) 输入n(3) 输岀结果(四) 哈希表的建立(1) 运行程序，显示菜单(2) 输入n(3) 输岀结果6. 实验收获及思考建立哈希表时没有考虑冲突处理问题，做程序时要谨慎小心 附录：源代码(1) 顺序查找验证#i nclude #i nclude #defi ne MAX_LENGTH 100typedef int KeyType;typedef struct KeyType *elem; / 零号单元留空int len gth; /表长度SS
4、Table;int Search_Seq(SSTable ST, KeyType key)int i;ST.elemO = key; /“哨兵”for(i = ST.length; ST.elemi != key; i-);/从后往前找return i; / 找不到时，i为0void mai n()int i, key;SSTable T;T.elem = (KeyType *)malloc(sizeof(KeyType);printf(输入数据个数n);scanf(%d, &T.length);for(i=1; i=T .len gth; i+)printf(输入数据 %d ； n, i);
5、sca nf(%d, & T.elemi);for (i=1; i=T .len gth; i+)prin tf(%5d,T.elemi);pri ntf(n输入要查找的数据n);sea nf(%d, & key);i = Search_Seq(T,key);printf(位置是 %dn,i);system(pause);(2) 折半查找验证#i nclude#in clude#defi ne OK 1#defi ne ERROR 0void mai n()int score100;int len gth;int key;printf(输入数据个数:n);sca nf(%d,&len gth)
6、;for(i nt i=1;i=le ngth;i+) printf( 输入第d个元素,i);sca nf(%d，& scorei);prin tf(n输入要查找的关键字n);sca nf(%d,&key);int low,high,mid;low=1;high=le ngth;while(low=high)mid=(low+high)/2;if(scoremid=key) /找到待查元素printf(” 数据位置 %d,mid); system(pause);else if(keyscoremid)low=mid+1; /继续在后半区间进行查找printf(无此数据);system(paus
7、e);(3) 二叉排序树的建立#i nclude#in cludetypedef int datatype;typedef struct nodedatatype key;struct node *lchild,*rchild;bs no de;typedef bsnode *bstree;void in sertbstree(bstree *t,datatype x)bstree f,p;p = *t；while(p)f = p;if(x key)p = p -lchild;elsep = p -rchild;p =(bstree)malloc(sizeof(bs no de); p-key
8、 = x;p-lchild=p-rchild=NULL;if(*t = NULL)*t = p;elseif(x key)f-lchild = p;elsef-rchild = p;bstree creatbstree(bstree t)datatype key;sca nf(%d,&key);while(key != -1)in sertbstree(&t,key);sca nf(%d,&key);return t;void in order(bstree t)if (t)ino rder(t-lchild);prin tf(%d ,t-key); ino rder(t-rchild);vo
9、id qorder(bstree t) if(t)prin tf(%d ,t-key); qorder(t-lchild); qorder(t-rchild);void horder(bstree t)if(t)horder(t-lchild); horder(t-rchild);prin tf(%d ,t-key);int mai n()bstree t = NULL,p;printf（ 请输入一个-1为结束标记的结点序列:n）;p = creatbstree(t);printf(“中序遍历：);ino rder(p);prin tf(n);prin tf(先序遍历：);qorder(p);
10、prin tf(n);prin tf(后序遍历：);horder(p);system(pause);return 0;(4) 哈希表的建立#i nclude #i nclude #defi ne INIT_MAXSIZE 10typedef structL nodeint data;structL node *n ext;Ln ode, *ListL ink; /建立链表结点typedef structin tpos;ListLi nkfirst no de; /建立数组结点HashBox;typedef structHashBoxHArraryINIT_MAXSIZE; /建立哈希数组(哈希
11、表的地址表头)HashArray;void In itHashList(HashArra y&I, i nt in put, i nt accou nt); /建立哈希表void VistHashList(HashArra y&l); /遍历输出哈希表int main( void) int accou nt = 0, i = 0, i nput256;HashArray l;pri ntf(请输入要插入哈希表元素的个数:);scanf(%d, &account);pri ntf(”请输入要插入哈希表的元素：)；for (i = 0; i accou nt; i+) scanf(%d, &inp
12、uti);In itHashList(l, in put, accou nt);printf(n哈希表如下：n);VistHashList(l);return 0;void In itHashList(HashArra y&l, i nt in put, i nt accou nt) / int i = 0, j = 0, pos = 0;建立哈希表ListL ink q, p;char ch = A;for (i = 0; i INIT_MAXSIZE; i+) / l.HArraryi.pos = ch+;l.HArraryi.first node = NULL;for (i = 0; i
13、 data = in puti;q- next = NULL;初始化哈希表头计算元素地址i f(l.HArrarypos.firstnode = NULL)/ 判断当前地址表头是否还没有元素连入l .HArrarypos.firstnode = q;else p = l.HArrarypos.first no de;while (p- next != NULL) p = p- next; /找到链表表尾p- next = q; /将要插入的结点接入表尾void VistHashList(HashArra y&l) /输岀哈希表 ListLink p;int i;for (i = 0; i %d, p-data);p = p_n ext;prin tf(n “);