網(wǎng)絡(luò)設(shè)計方案某報告

實驗名稱：第9章實驗實驗類型：驗證性實驗姓名：車紅岫實驗日期：2013.6問題描述以下四個驗證性實驗都做。（1）順序查找驗證（2）折半查找驗證（3）二叉排序樹的建立（4）哈希表的建立數(shù)據(jù)結(jié)構(gòu)設(shè)計順序查找驗證typedefstruct{KeyType*elem;//零號單元留空intlength;//表長度}SSTable;折半查找驗證 intscore[100]; intlength; intkey;二叉排序樹的建立typedefstructnode{ datatypekey; structnode*lchild,*rchild;}bsnode;（4）哈希表的建立typedefstructLnode{intdata;structLnode*next;}Lnode,*ListLink;//建立鏈表結(jié)點typedefstruct{intpos;ListLinkfirstnode;//建立數(shù)組結(jié)點}HashBox;typedefstruct{HashBoxHArrary[INIT_MAXSIZE];//建立哈希數(shù)組(哈希表的地址表頭)}HashArray;3.算法設(shè)計4.界面設(shè)計（1）順序查找驗證折半查找驗證二叉排序樹的建立（4）哈希表的建立5.運行、測試（一）順序查找驗證（1）運行程序，顯示菜單輸入n(3)輸出結(jié)果折半查找驗證（1）運行程序，顯示菜單輸入n(3)輸出結(jié)果二叉排序樹的建立運行程序，顯示菜單（2）輸入n(3)輸出結(jié)果哈希表的建立運行程序，顯示菜單（2）輸入n(3)輸出結(jié)果實驗收獲及思考建立哈希表時沒有考慮沖突處理問題，做程序時要謹慎小心。附錄：源代碼（1）順序查找驗證#include<stdio.h>#include<stdlib.h>#defineMAX_LENGTH100typedefintKeyType;typedefstruct{KeyType*elem;//零號單元留空intlength;//表長度}SSTable;intSearch_Seq(SSTableST,KeyTypekey){inti;ST.elem[0]=key;//“哨兵”for(i=ST.length;ST.elem[i]!=key;i--);//從后往前找returni;//找不到時，i為0}voidmain(){inti,key;SSTableT;T.elem=(KeyType*)malloc(sizeof(KeyType));printf("輸入數(shù)據(jù)個數(shù)\n");scanf("%d",&T.length);for(i=1;i<=T.length;i++){printf("輸入數(shù)據(jù)%d；\n",i);scanf("%d",&T.elem[i]);}for(i=1;i<=T.length;i++)printf("%5d",T.elem[i]);printf("\n輸入要查找的數(shù)據(jù)\n");scanf("%d",&key);i=Search_Seq(T,key);printf("位置是%d\n",i);system("pause");}（2）折半查找驗證#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0voidmain(){ intscore[100]; intlength; intkey; printf("輸入數(shù)據(jù)個數(shù):\n"); scanf("%d",&length); for(inti=1;i<=length;i++) {printf("輸入第%d個元素",i); scanf("%d",&score[i]); } printf("\n輸入要查找的關(guān)鍵字\n"); scanf("%d",&key); intlow,high,mid; low=1; high=length; while(low<=high) { mid=(low+high)/2; if(score[mid]==key)//找到待查元素 {printf("數(shù)據(jù)位置%d",mid); system("pause"); } elseif(key<score[mid]) high=mid-1;//繼續(xù)在前半?yún)^(qū)間進行查找 elseif(key>score[mid]) low=mid+1;//繼續(xù)在后半?yún)^(qū)間進行查找 } printf("無此數(shù)據(jù)"); system("pause");}（3）二叉排序樹的建立#include<stdio.h>#include<stdlib.h>typedefintdatatype;typedefstructnode{ datatypekey; structnode*lchild,*rchild;}bsnode;typedefbsnode*bstree;voidinsertbstree(bstree*t,datatypex){ bstreef,p; p=*t; while(p) { f=p; if(x<p->key) p=p->lchild; else p=p->rchild; } p=(bstree)malloc(sizeof(bsnode)); p->key=x; p->lchild=p->rchild=NULL; if(*t==NULL) *t=p; else { if(x<(f->key)) f->lchild=p; else f->rchild=p; } }bstreecreatbstree(bstreet){ datatypekey; scanf("%d",&key); while(key!=-1) { insertbstree(&t,key); scanf("%d",&key); } returnt;}voidinorder(bstreet){ if(t) { inorder(t->lchild); printf("%d",t->key); inorder(t->rchild);}} voidqorder(bstreet){if(t) { printf("%d",t->key); qorder(t->lchild); qorder(t->rchild);}}voidhorder(bstreet){ if(t) { horder(t->lchild); horder(t->rchild); printf("%d",t->key); } }intmain(){bstreet=NULL,p; printf("請輸入一個-1為結(jié)束標記的結(jié)點序列:\n"); p=creatbstree(t); printf("中序遍歷："); inorder(p); printf("\n"); printf("先序遍歷："); qorder(p); printf("\n"); printf("后序遍歷："); horder(p); system("pause"); return0;}（4）哈希表的建立#include<stdio.h>#include<malloc.h>#defineINIT_MAXSIZE10typedefstructLnode{intdata;structLnode*next;}Lnode,*ListLink;//建立鏈表結(jié)點typedefstruct{intpos;ListLinkfirstnode;//建立數(shù)組結(jié)點}HashBox;typedefstruct{HashBoxHArrary[INIT_MAXSIZE];//建立哈希數(shù)組(哈希表的地址表頭)}HashArray;voidInitHashList(HashArray&l,intinput[],intaccount);//建立哈希表voidVistHashList(HashArray&l);//遍歷輸出哈希表intmain(void){intaccount=0,i=0,input[256];HashArrayl;printf("請輸入要插入哈希表元素的個數(shù):");scanf("%d",&account);printf("請輸入要插入哈希表的元素:");for(i=0;i<account;i++) {scanf("%d",&input[i]); }InitHashList(l,input,account);printf("\n哈希表如下:\n");VistHashList(l);return0;}voidInitHashList(HashArray&l,intinput[],intaccount)//建立哈希表{inti=0,j=0,pos=0;ListLinkq,p;charch='A';for(i=0;i<INIT_MAXSIZE;i++)//初始化哈希表頭 {l.HArrary[i].pos=ch++; l.HArrary[i].firstnode=NULL; }for(i=0;i<account;i++) {pos=input[i]%INIT_MAXSIZE;//計算元素地址 q=newLnode;//申請結(jié)點 q->data=input[i]; q->next=NULL; if(l.HArrary[pos].firstnode==NULL)//判斷當前地址表頭是否還沒有元素連入 l.HArrary[pos].firstnode=q; else {p=l.HArrary[pos].firstnode; while(p->next!=NULL) {p=p->next;//找到鏈表表尾 } p->next=q;//將要插入的結(jié)點接入表尾 } }}v