數(shù)據(jù)結(jié)構(gòu)二叉排序樹-哈希表.doc

《數(shù)據(jù)結(jié)構(gòu)二叉排序樹-哈希表.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)內(nèi)容：排序二叉樹，及哈希表系別班級(jí)：網(wǎng)絡(luò)工程1001學(xué)號(hào)：201022074姓名：楊帆一、實(shí)驗(yàn)?zāi)康模菏煜づ判蚨鏄浜凸１淼慕Y(jié)構(gòu)及部分算法二、實(shí)驗(yàn)內(nèi)容及要求：1、構(gòu)造排序二叉樹，并實(shí)現(xiàn)增刪改查。2、構(gòu)造哈希表，key值油隨機(jī)數(shù)獲得，自己選擇解決沖突的算法。并且計(jì)算查找次數(shù)及平均查找次數(shù)。三、算法描述：排序二叉樹：節(jié)點(diǎn)的結(jié)構(gòu)：typedefstructtree{intdata;structtree*left;structtree*right;}Sorttree,*BiTree;1、插入：以輸入的第一個(gè)數(shù)為樹的根節(jié)點(diǎn)，之后輸入的

2、數(shù)若小于根節(jié)點(diǎn)則插入為左孩子，若大于根節(jié)點(diǎn)則插入為右孩子，若左右孩子均已存在，則將小于根節(jié)點(diǎn)的與根節(jié)點(diǎn)的左孩子比較，將大于根節(jié)點(diǎn)的與根節(jié)點(diǎn)的又孩子比較，然后重復(fù)上述操作。2、查找：遞歸，中序遍歷二叉樹。3、刪除：首先找到與要?jiǎng)h除的數(shù)相等的節(jié)點(diǎn)，若該節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除。當(dāng)非葉子節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)在根節(jié)點(diǎn)的左邊，則用該節(jié)點(diǎn)的右子樹中最大的節(jié)點(diǎn)將它替換掉，同理，如果該節(jié)點(diǎn)在根節(jié)點(diǎn)的右邊，則用該節(jié)的左子樹中最小的節(jié)點(diǎn)將它替換掉。4、修改：查找到該節(jié)點(diǎn)，將其刪除，然后在插入修改后的節(jié)點(diǎn)。函數(shù)說(shuō)明：1、intCreatST(BiTree&T)//建

3、立排序二叉樹2、voidInorder(BiTreeT)//中序遍歷二叉樹3、intSearch(BiTreeT,inte)//查找4、voidAdd(BiTree&T,inte)//插入5、voidDelete(BiTree&T,inte)//刪除6、voidmodify(BiTree&T,inte)//修改哈希表：哈希表即通過(guò)key值將數(shù)據(jù)存儲(chǔ)到不同位置而建立起的表，通過(guò)key可值直接找到數(shù)據(jù)的存儲(chǔ)位置，減少查找所消耗的時(shí)間。所以我們需要表節(jié)點(diǎn)中添加一個(gè)key來(lái)存儲(chǔ)key值。當(dāng)添加元素的key值與表中元素key值相同時(shí)，查看下一個(gè)存儲(chǔ)位置是

4、否有元素，若沒(méi)有將該元素存儲(chǔ)在新找到的位置否則繼續(xù)找下一位置，直到找到可存儲(chǔ)的位置。Key值隨機(jī)產(chǎn)生。哈希表結(jié)構(gòu)：typedefstructele{intdata;intkey;}Elemtype;typedefstructhashtable{Elemtypeelem[Max_num];intcount;intsizeindex;}HashTable;1、宏定義表中最大存儲(chǔ)個(gè)數(shù)#defineMax_num152、表中元素初始化Key值和數(shù)據(jù)值均為-1表示沒(méi)有存儲(chǔ)數(shù)據(jù)#defineNo_key-1#defineNo_data-1四、程序代碼：1、

5、二叉排序樹代碼：#include#includetypedefstructtree{intdata;structtree*left;structtree*right;}Sorttree,*BiTree;intCreatST(BiTree&T){BiTreep,q;intj,n=1;while(n>0){printf("輸入數(shù)據(jù)：");scanf("%d",&n);if(n==-1)break;if(T==NULL){T=(Sorttree*)malloc(sizeof(Sorttree));T->dat

6、a=n;T->left=NULL;T->right=NULL;continue;}p=T;while(p){if(n==p->data){printf("該數(shù)已經(jīng)存在，請(qǐng)重新輸入!");break;}q=p;if(ndata){j=1;p=p->left;}else{j=2;p=p->right;}}if(p)continue;if(j==1){q->left=(Sorttree*)malloc(sizeof(Sorttree));p=q->left;p->data=n;p->left=NULL;p->right=NULL;}els

7、eif(j==2){q->right=(Sorttree*)malloc(sizeof(Sorttree));p=q->right;p->data=n;p->left=NULL;p->right=NULL;}}return1;}voidInorder(BiTreeT){if(T){Inorder(T->left);printf("%d",T->data);Inorder(T->right);}}intSearch(BiTreeT,inte){BiTreep;p=T;while(p){if(e==p->data)return1;elseif(e>

8、p->data)p=p->right;elsep=p->left;}return0;}voidAdd(BiTree&T,inte){BiTreep,q