网络设计实验报告

1、实验名称：第 9 章实验实验类型：验证性实验姓名：车红岫实验日期： 2013.6问题描述以下四个验证性实验都做。1）顺序查找验证2）折半查找验证3）二叉排序树的建立4）哈希表的建立数据结构设计（ 1）顺序查找验证typedef struct KeyType *elem;/零号单元留空int length;/表长度SSTable;2）折半查找验证 int score100;int length; int key;3）二叉排序树的建立typedef struct nodedatatype key;struct node *lchild,*rchild;bsnode;（ 4）哈希表的建立typede

2、f structLnodeint data;structLnode *next;Lnode, *ListLink; /建立链表结点typedef structintpos;ListLinkfirstnode; /建立数组结点HashBox;typedef structHashBoxHArraryINIT_MAXSIZE; /建立哈希数组 ( 哈希表的地址表头)HashArray;算法设计界面设计1）顺序查找验证2）折半查找验证3）二叉排序树的建立4）哈希表的建立运行、测试（一）顺序查找验证1）运行程序，显示菜单2） 输入 n输出结果（二）折半查找验证1）运行程序，显示菜单2）输入 n输出结果（

3、三）二叉排序树的建立1）运行程序，显示菜单（ 2）输入 n输出结果（四）哈希表的建立1）运行程序，显示菜单2）输入 n输出结果实验收获及思考建立哈希表时没有考虑冲突处理问题，做程序时要谨慎小心。附录：源代码（ 1）顺序查找验证#include #include #define MAX_LENGTH 100typedef int KeyType;typedef struct KeyType *elem;/零号单元留空int length;/表长度SSTable;int Search_Seq(SSTable ST, KeyType key)int i;ST.elem0 = key;/“哨兵”for

4、(i = ST.length; ST.elemi != key; i-);/从后往前找return i; /找不到时，i为0void main()int i, key;SSTable T;T.elem = (KeyType *)malloc(sizeof(KeyType);printf(输入数据个数 n);scanf(%d, &T.length);for(i=1; i=T.length; i+)printf(输入数据 %d ； n, i);scanf(%d, &T.elemi);for (i=1; i=T.length; i+)printf(%5d,T.elemi);printf(n输入要查找

5、的数据n);scanf(%d, &key);i = Search_Seq(T,key);printf(位置是 %dn,i);system(pause);（ 2）折半查找验证#include#include#define OK 1#define ERROR 0void main()int score100;int length;int key;printf(输入数据个数 :n);scanf(%d,&length);for(int i=1;i=length;i+)printf(输入第 %d个元素 ,i);scanf(%d,&scorei);printf(n输入要查找的关键字n);scanf(%d,

6、&key);int low,high,mid;low=1;high=length;while(low=high)mid=(low+high)/2;if(scoremid=key)/找到待查元素printf(数据位置 %d,mid);system(pause);else if(keyscoremid)low=mid+1;/继续在后半区间进行查找printf(无此数据 );system(pause);（ 3）二叉排序树的建立#include#includetypedef int datatype;typedef struct nodedatatype key;struct node *lchild

7、,*rchild;bsnode;typedef bsnode *bstree;void insertbstree(bstree *t,datatype x)bstree f,p;p = *t;while(p)f = p;if(x key)p = p -lchild;elsep = p -rchild;=(bstree)malloc(sizeof(bsnode); p-key = x; p-lchild=p-rchild=NULL;if(*t = NULL) *t = p;elseif(x key) f-lchild = p;elsef-rchild = p;bstree creatbstree

8、(bstree t)datatype key;scanf(%d,&key);while(key != -1)insertbstree(&t,key);scanf(%d,&key);return t;void inorder(bstree t)if (t)inorder(t-lchild);printf(%d ,t-key);inorder(t-rchild);void qorder(bstree t) if(t)printf(%d ,t-key); qorder(t-lchild); qorder(t-rchild);void horder(bstree t)if(t)horder(t-lch

9、ild);horder(t-rchild);printf(%d ,t-key);int main()bstree t = NULL,p;printf(请输入一个 -1 为结束标记的结点序列:n);p = creatbstree(t);printf(中序遍历： );inorder(p);printf(n);printf(先序遍历： );qorder(p);printf(n);printf(后序遍历： );horder(p);system(pause);return 0;4）哈希表的建立#include #include #define INIT_MAXSIZE 10 typedef struct

10、Lnodeint data;structLnode *next;Lnode, *ListLink; /typedef structintpos;建立链表结点ListLinkfirstnode; / HashBox; typedef struct 建立数组结点HashBoxHArraryINIT_MAXSIZE; /建立哈希数组( 哈希表的地址表头)HashArray;void InitHashList(HashArray&l, int input, int account); /建立哈希表void VistHashList(HashArray&l); / int main(void)遍历输出哈

11、希表 int account = 0, i = 0, input256; HashArray l;printf( 请输入要插入哈希表元素的个数 :); scanf(%d, &account);printf(请输入要插入哈希表的元素:);for (i = 0; i account; i+) scanf(%d, &inputi);InitHashList(l, input, account);printf(n哈希表如下 :n);VistHashList(l);return 0;void InitHashList(HashArray&l, int input, int account) /建立哈希表 int i = 0, j = 0, pos = 0;ListLink q, p;char ch = A;for (i = 0; i INIT_MAXSIZE; i+) / l.HArraryi.pos = ch+;l.HArraryi.firstnode = NULL;for (i = 0; i data = inputi; q-next = NULL;申请结点if(l.HArrarypos.firstnode = NULL)/ l.HArrarypos.firstnode = q;判断当前地址表头是否还没有元素连入else p = l.HA