查找和排序?qū)嶒?yàn)報(bào)告

1、附件（四）深圳大學(xué)實(shí)驗(yàn)報(bào)告課程名稱(chēng):數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)與課程設(shè)計(jì)實(shí)驗(yàn)項(xiàng)目名稱(chēng): 查找排序?qū)嶒?yàn).學(xué)院:計(jì)算機(jī)與軟件學(xué)院專(zhuān)業(yè)：指導(dǎo)教師;報(bào)告人:學(xué)號(hào):班級(jí):實(shí)驗(yàn)時(shí)間:實(shí)驗(yàn)報(bào)告提交時(shí)間:教務(wù)處制一、實(shí)驗(yàn)?zāi)康呐c完成說(shuō)明：1. 簡(jiǎn)單介紹本實(shí)驗(yàn)的主要目的2. 說(shuō)明你自己在本次實(shí)驗(yàn)中完成了第幾項(xiàng)要求（必填）Contest1657 - DS實(shí)驗(yàn)-靜態(tài)查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之順序查找主要目的:給出一個(gè)隊(duì)列和要查找的數(shù)值，找出數(shù)值在隊(duì)列中的位置，隊(duì)列位置從1開(kāi)始要求使用帶哨兵的順序查找算法Input第一行輸入n,表示隊(duì)列有n個(gè)數(shù)據(jù)（完成）第二行輸入n個(gè)數(shù)據(jù)，都是正整數(shù)，用空格隔開(kāi)（完成）第三行輸

2、入t，表示有t個(gè)要查找的數(shù)值（完成） 第四行起，輸入t個(gè)數(shù)值，輸入t行（完成）Out put每行輸出一個(gè)要查找的數(shù)值在隊(duì)列的位置，如果查找不成功，輸出字符串error（完成）Problem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之折半查找主要目的:給出一個(gè)隊(duì)列和要查找的數(shù)值，找出數(shù)值在隊(duì)列中的位置，隊(duì)列位置從1開(kāi)始要求使用折半查找算法Input第一行輸入n，表示隊(duì)列有n個(gè)數(shù)據(jù)（完成）第二行輸入n個(gè)數(shù)據(jù)，都是正整數(shù)，用空格隔開(kāi)（完成）第三行輸入t，表示有t個(gè)要查找的數(shù)值（完成）第四行起，輸入t個(gè)數(shù)值，輸入t行（完成）Out put每行輸出一個(gè)要查找的數(shù)值在隊(duì)列的位置，如果查找不成功，輸出字符串error（完

3、成）Problem C:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之順序索引查找主要目的:給出一個(gè)隊(duì)列和要查找的數(shù)值，找出數(shù)值在隊(duì)列中的位置，隊(duì)列位置從1開(kāi)始（完成）要求使用順序索引查找算法，其中索引表查找和塊內(nèi)查找都采用不帶哨兵、從頭開(kāi)始的 順序查找方法。（完成）Input第一行輸入 第二行輸入 第三行輸入 第四行輸入 第五行輸入n,表示主表有n個(gè)數(shù)據(jù)（完成）n個(gè)數(shù)據(jù)，都是正整數(shù)，用空格隔開(kāi) （完成）k，表示主表劃分為 k個(gè)塊，k也是索引表的長(zhǎng)度（完成） k個(gè)數(shù)據(jù)，表示索引表中每個(gè)塊的最大值（完成）t，表示有t個(gè)要查找的數(shù)值（完成）第六行起，輸入t個(gè)數(shù)值，輸入t行（完成）Out put每行輸出一個(gè)要查找的數(shù)值在

4、隊(duì)列的位置和查找次數(shù)，數(shù)據(jù)之間用短劃線隔開(kāi)，如果查 找不成功，輸出字符串error（完成）Contest1040 - DS實(shí)驗(yàn)-動(dòng)態(tài)查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二叉排序樹(shù)之創(chuàng)建和插主要目的: 給出一個(gè)數(shù)據(jù)序列，建立二叉排序樹(shù)，并實(shí)現(xiàn)插入功能 對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，可以得到有序的數(shù)據(jù)序列Input第一行輸入t，表示有t個(gè)數(shù)據(jù)序列（完成）第二行輸入n,表示首個(gè)序列包含 n個(gè)數(shù)據(jù)（完成）第三行輸入n個(gè)數(shù)據(jù)，都是自然數(shù)且互不相同，數(shù)據(jù)之間用空格隔開(kāi)（完成）第四行輸入m，表示要插入 m個(gè)數(shù)據(jù)（完成）從第五行起,輸入m行，每行一個(gè)要插入的數(shù)據(jù)， 都是自然數(shù)且和前面的數(shù)據(jù)不等 （完成）以此類(lèi)推輸

5、入下一個(gè)示例（完成）Out put第一行輸出有序的數(shù)據(jù)序列，對(duì)二叉排序樹(shù)進(jìn)行中序遍歷可以得到（完成）從第二行起，輸出插入第m個(gè)數(shù)據(jù)后的有序序列，輸出m行（完成）以此類(lèi)推輸出下一個(gè)示例的結(jié)果（完成）Problem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)之查找主要目的:給出一個(gè)數(shù)據(jù)序列，建立二叉排序樹(shù)，并實(shí)現(xiàn)查找功能（完成）對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，可以得到有序的數(shù)據(jù)序列（完成）Input第一行輸入t，表示有t個(gè)數(shù)據(jù)序列（完成）第二行輸入n,表示首個(gè)序列包含 n個(gè)數(shù)據(jù)（完成）第三行輸入n個(gè)數(shù)據(jù)，都是自然數(shù)且互不相同，數(shù)據(jù)之間用空格隔開(kāi)（完成）第四行輸入m，表示要查找 m個(gè)數(shù)據(jù)（完成）從第五行起,輸入 m行，

6、每行一個(gè)要查找的數(shù)據(jù)，都是自然數(shù)（完成）以此類(lèi)推輸入下一個(gè)示例（完成）Out put第一行輸出有序的數(shù)據(jù)序列，對(duì)二叉排序樹(shù)進(jìn)行中序遍歷可以得到（完成）從第二行起，輸出查找結(jié)果，如果查找成功輸出查找次數(shù)，如果查找失敗輸出-1（完成）以此類(lèi)推輸出下一個(gè)示例的結(jié)果（完成）Problem C:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)之刪除主要目的:給出一個(gè)數(shù)據(jù)序列，建立二叉排序樹(shù)，并實(shí)現(xiàn)刪除功能對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，可以得到有序的數(shù)據(jù)序列Input第一行輸入t，表示有t個(gè)數(shù)據(jù)序列（完成）第二行輸入n,表示首個(gè)序列包含 n個(gè)數(shù)據(jù)（完成）第三行輸入n個(gè)數(shù)據(jù)，都是自然數(shù)且互不相同，數(shù)據(jù)之間用空格隔開(kāi)（完成）第四行輸入m

7、，表示要?jiǎng)h除 m個(gè)數(shù)據(jù)（完成）從第五行起，輸入 m行，每行一個(gè)要?jiǎng)h除的數(shù)據(jù)，都是自然數(shù)（完成）以此類(lèi)推輸入下一個(gè)示例（完成）Out put第一行輸出有序的數(shù)據(jù)序列，對(duì)二叉排序樹(shù)進(jìn)行中序遍歷可以得到（完成）從第二行起，輸出刪除第 m個(gè)數(shù)據(jù)后的有序序列，輸出m行（完成）以此類(lèi)推輸出下一個(gè)示例的結(jié)果（完成）Contest1050 - DS實(shí)驗(yàn)-哈希查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)哈希查找主要目的:給出一個(gè)數(shù)據(jù)序列，建立哈希表，采用求余法作為哈希函數(shù)，模數(shù)為 地址法和表頭插入11,哈希沖突用鏈如果首次查找失敗，就把數(shù)據(jù)插入到相應(yīng)的位置中實(shí)現(xiàn)哈希查找功能Input第一行輸入n，表示有n個(gè)數(shù)據(jù)（完成）

8、第二行輸入n個(gè)數(shù)據(jù)，都是自然數(shù)且互不相同，數(shù)據(jù)之間用空格隔開(kāi) 第三行輸入t，表示要查找t個(gè)數(shù)據(jù)（完成） 從第四行起，每行輸入一個(gè)要查找的數(shù)據(jù)，都是正整數(shù)（完成）（完成）Out put每行輸出對(duì)應(yīng)數(shù)據(jù)的查找結(jié)果（完成）Contest1060 - DS實(shí)驗(yàn)-排序算法主要目的:給出一個(gè)數(shù)據(jù)序列，使用希爾排序算法進(jìn)行從小到大的排序 間隔gap使用序列長(zhǎng)度循環(huán)除 2直到1第一行輸入 第二行輸入 第三行輸入 以此類(lèi)推Inputt，表示有t個(gè)測(cè)試示例（完成）n,表示第一個(gè)示例有 n個(gè)數(shù)據(jù)（完成）n個(gè)數(shù)據(jù)，都是正整數(shù)，數(shù)據(jù)之間用空格隔開(kāi)（完成）Out put每行輸出每個(gè)示例排序后，從小到大的結(jié)果（完成）Pro

9、blem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-快速排序主要目的: 給出一個(gè)數(shù)據(jù)序列，使用快速排序算法進(jìn)行從小到大的排序第一行輸入 第二行輸入 第三行輸入 以此類(lèi)推Inputt，表示有t個(gè)測(cè)試示例（完成）n，表示第一個(gè)示例有 n個(gè)數(shù)據(jù)（完成）n個(gè)數(shù)據(jù)，都是正整數(shù)，數(shù)據(jù)之間用空格隔開(kāi)（完成）Out put每行輸出每個(gè)示例排序后，從小到大的結(jié)果（完成）二、主要思路與方法：1.對(duì)于本次實(shí)驗(yàn)，說(shuō)明你認(rèn)為最重要的函數(shù)、算法或知識(shí)點(diǎn)，并談?wù)勀銓?duì)它們的理解Contest1657 - DS實(shí)驗(yàn)-靜態(tài)查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之順序查找比起普通的順序查找，帶哨兵的順序查找是從表尾查到表頭的, 然后將表的第一位數(shù)

10、賦值為要查找的值。這樣做能夠減少一個(gè)步驟，即在循環(huán)后減少幾行判斷語(yǔ)句來(lái)決 定返回值。查到了就返回下標(biāo)，下標(biāo)為 0即沒(méi)有找到。需要排好序后才能進(jìn)行折半查找。Problem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之折半查找找22。LowMidHigh1122334455667788fffLowMidHigh11223344551667788找88Low、Mid、High1122334455667788fffLowMidHigh1122334455667788fffLowMidHigh1122334455667788ffLow、MidHigh1122334455667788把一長(zhǎng)條數(shù)據(jù)切割成幾段，然后在這幾段中

11、分別取最代表性的數(shù)據(jù)作為索引數(shù)據(jù)，然 后查找數(shù)據(jù)時(shí)先與這幾個(gè)數(shù)據(jù)比較，找到符合條件的數(shù)據(jù)后再根這段里的數(shù)據(jù)比較。找53設(shè)定間隔為索引數(shù)目為322488622121389201=3; num=2;SS=12;5333424438244860587486V1=3+6=9;i=17;return i+1;(18)找90224886設(shè)定間隔為索引數(shù)目為3num=3; return 0;Contest1040 - DS實(shí)驗(yàn)-動(dòng)態(tài)查找P roblem A: 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)叉排序樹(shù)之創(chuàng)建和插入按照大小順序插入，如果孩子為空，比父節(jié)點(diǎn)大插右邊，比父節(jié)點(diǎn)小插左邊；如果 孩子不為空，父節(jié)點(diǎn)往右孩子或左孩子推移。根據(jù)

12、左孩子比父節(jié)點(diǎn)小，右孩子比父節(jié)點(diǎn)大的特性，通過(guò)判斷與父節(jié)點(diǎn)的 大小左移或右移，找到后就返回該結(jié)點(diǎn)，輸出移動(dòng)的次數(shù)。Problem C:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)之刪除 如果左孩子或右孩子其中一個(gè)為空，直接把它們往父節(jié)點(diǎn)提。 如果都為空，直接刪除該結(jié)點(diǎn)。 如果都不為空，從左子樹(shù)中取最大的一個(gè)值與父節(jié)點(diǎn)交換，然后刪除該 結(jié)點(diǎn)。Contest1050 - DS實(shí)驗(yàn)-哈希查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)哈希查找Contest1060 - DS實(shí)驗(yàn)-排序算法Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-希爾排序Gap表示取值的間隔和移動(dòng)的次數(shù)。gap=len gth/2;11122644433355111己444

13、22333 gap=6/2=3;6557733666 gap/2=11112264443335522111622111622111444622111333i444162255111333444排序完畢。 gap=8/2=4;775553344477666 2222555772222 gap 12=2；7777333317755566622225552222444 gap/2=1;33177774445556662222133 133771337777J133777744413377774445551337777444555666113377774445556662222排序完畢Problem

14、B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-快速排序第一種算法（有交換函數(shù)）：在low-high 區(qū)間內(nèi)找到比alow要小的值，high 等于這個(gè)值的下標(biāo)。然后 alow和ahigh互換。在low-high 區(qū)間內(nèi)找到比ahigh要小的值，low 等于這個(gè)值的下標(biāo)。然后 alow和ahigh互換。重復(fù)步驟直到low等于high。low=0;high=n-1;(5)pi votloc=P artiti on( a,0,5);a. QSort(a,low, pi votloc-1);QSort(a,0,2);b. QSort(a, p ivotloc+1,high);QSort(a,4,5);（a）low=0;high=2

15、;5522111333444552255111333444p rivotloc=2;low=0;a. QSort(a,low, pi votloc-1);QSort(a,0,1);b. QSort(a, p ivotloc+1,high);QSort(a,3,2);(a)low=0;high=1;62255111333444ttp rivotloc=0;low=0;a. QSort(a,low, pi votloc-1);QSort(a,0,-1);b. QSort(a, pivotloc+1,high);QSort(a,1,1);（b）low=4;high=5;2255111333444p

16、rivotloc=4;a. QSort(a,low, pi votloc-1);QSort(a,4,3);b. QSort(a, pivotloc+1,high);QSort(a,5,5);排序完畢。流程圖:Partitfon|ai；0,5);11144PjvatlQC=J. QSort(那0.4;P呂rtiticm(別H 打；QSort(a,431；I p rH/otlDCi4： QSort(a,43)；PivqtlQrIiqsort(a,0,l)； IcwiOthijhtl;Partition! aAlhasorta3.2)：gjQ5ort(a,S,S|;PiwpHoM； Q Sort(a

17、,Orl)； QSortaJ4)：6第二種改進(jìn)算法（沒(méi)有交換函數(shù)）：把low下標(biāo)的值賦給一個(gè)臨時(shí)變量在賦給low - high區(qū)間里找一個(gè)比臨時(shí)變量小的值 low下標(biāo)的數(shù)組。這個(gè)值的下標(biāo)賦給 high 。在low-high區(qū)間里找一個(gè)比臨時(shí)變量大的值賦給 high下標(biāo)的數(shù)組。這個(gè)值的下標(biāo)賦給low。重復(fù)步驟直到low等于high;把臨時(shí)變量的值賦給low下標(biāo)的數(shù)組。 low=0;high=7;Partitio n(a,0,7);temp=77;7755533144477666222255533144477666 22221555335554447766622221333355544477666

18、222213377555444776662222pi votloc =2;a. QSort(a,low, pi votloc-1);QSort(a,0,1);b. QSort(a, p ivotloc+1,high);QSort(a,3,7);(b) low=3;high=7;Partitio n(a,3,7);temp=555;1335554447766622227744477666222277444555666222277pi votloc =5;a. QSort(a,low, pi votloc-1);QSort(a,3,4);b. QSort(a, p ivotloc+1,high);

19、QSort(a,6,7); ( b)low=6;high=7;Partitio n(a,6,7);temp=666;13377774445556662222pi votloc =6a. QSort(a,low, pi votloc-1);QSort(a,3,5);b. QSort(a, p ivotloc+1,high);QSort(a,7,7);排序完畢。三. 實(shí)驗(yàn)程序或內(nèi)容：1. 針對(duì)每一項(xiàng)實(shí)驗(yàn)要求，給出編寫(xiě)的代碼，2. 可以粘貼全部代碼，或者可以只粘貼重要的代碼（為了節(jié)省紙張），但代碼必須完整,至少是完整的函數(shù)。3. 代碼符合以下要求，評(píng)分更高：a. 排版整齊，可讀性高b. 代碼有注釋?zhuān)?/p>

20、越詳細(xì)越清晰越好Contest1657 - DS實(shí)驗(yàn)-靜態(tài)查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之順序查找#in cludeusing n ames pace std;int Search(i nt *ArraySize,i nt S,i nt n) int i;ArraySize0=S; for(i=n; !(ArraySizei-=S););return i+1;int mai n()int n ,i,t,S ,num;cinn;int *ArraySize=new in t n+1; for(i=0;+i ArraySizei;/forcin t;while(t-)cin S;n

21、um=Search(ArraySize,S, n); if(nu m)cout num e ndl;/if else couterrore ndl;/else/whilereturn 0;/mai nProblem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之折半查找#in clude using n ames pace std;int Search(i nt *ArraySize,i nt S,i nt n)in t low=1;int high=n;int mid;while(lowS)high=mid-1; else low=mid+1;return 0; int mai n()int n ,i,t,S

22、 ,num;cinn;int *ArraySize=new in t n+1; for(i=0;+i ArraySizei;/forcin t;while(t-)cin S;num=Search(ArraySize,S ,n); if(n um)cout num e ndl;/if else couterrore ndl;/else/whilereturn 0;/mai nProblem C:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-靜態(tài)查找之順序索引查找#in clude using n ames pace std;int Search(i nt *ArraySize,i nt *max,i nt S,i nt n,i

23、 nt k,i nt &l) int num;int SS;for(num=-1; numk&!(S=max+nu m);l+); if(num=k)return 0;SS=(n/k)*( nu m);for(i nt i=SS-1;+in;int *ArraySize=new in t n;for(i=-1;+i ArraySizei;/forcin k;int *max=new in tk;for(i=-1;+i maxi;/forcin t;while(t-)cin S;l=1; num=Search(ArraySize,max,S, n,k,l); if(nu m)cout n um-

24、le ndl;/if else couterrore ndl;/else/while return 0;/mai nContest1040 - DS實(shí)驗(yàn)-動(dòng)態(tài)查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)之創(chuàng)建和插入#in clude using n ames pace std;#defi ne OK 1 #defi ne ERROR 0 class TreeNode public:int data;TreeNode *LeftChild;TreeNode *RightChild;TreeNode()LeftChild=NULL;RightChild=NULL;data=0;class Tr

25、ee public:TreeNode* Root;void CreateB in ary(i nt *a,i nt size) if(size=O)return; Root=NULL; TreeNode *t; int len gth=0;t=new TreeNode(); t-data=ale ngth;Root=t; for(;+le ngthdata=ale ngth;In sertElem(Root,t);/for/CreateBi naryvoid In sertElem(TreeNode *F,TreeNode *t) if(F-data data) if(F-RightChild

26、)In sertElem(F-RightChild,t); /ifelse F-RightChild=t;/ifelseif(F-LeftChild)In sertElem(F-LeftChild,t); else F-LeftChild=t;/else/ln sertElemvoid In Order()InO rder(Root);void In Order(TreeNode *t) if(t)In Order(t-LeftChild); coutdataRightChild); /if/ln Search;int mai n()int t,n ,i, num,N;Tree T; cin

27、t; while(t-) cinn; int *a=new in t n;for(i=-1;+i ai;/forT.CreateBi nary(a, n);T.l nOrderO; coutnum; while( num-) cin N;TreeNode *tr =new TreeNode(); tr-data=N;T.I nsertElem(T.Root,tr);T.I nOrderO; coute ndl;/while/while return 0;Problem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)之查找#in clude using n ames pace std;#defi ne OK 1#

28、defi ne ERROR 0class TreeNodepublic:int data;TreeNode *LeftChild;TreeNode *RightChild;TreeNode()LeftChild=NULL;RightChild=NULL;data=0; ;class Tree public:TreeNode* Root;bool Find;int times;void CreateB in ary(i nt *a,i nt size) if(size=O)retur n; Root=NULL; TreeNode *t; int len gth=O;t=new TreeNode(

29、); t-data=ale ngth;Root=t; for(;+le ngthdata=ale ngth;In sertElem(Root,t);/for/CreateBi naryvoid In sertElem(TreeNode *F,TreeNode *t) if(F-data data) if(F-RightChild)In sertElem(F-RightChild,t); /ifelse F-RightChild=t;/ifelseif(F-LeftChild)In sertElem(F-LeftChild,t); else F-LeftChild=t;/else/ln sert

30、Elemvoid Searchfordata(TreeNode *t, int data) if(Fi nd & t)times+;if(t-data=data)Fin d=false;else if(t-data data)Searchfordata(t-LeftChild,data); elseSearchfordata(t-RightChild,data); int Searchfordata(i nt data)Fin d=true; times=0;Searchfordata(Root,data); if(Fi nd)return -1; else return times;void

31、 In Order()InO rder(Root);void In Order(TreeNode *t)if(t)In Order(t-LeftChild); coutdataRightChild); /if/ln Search;int mai n()int t,n ,i, num,N;Tree T;cin t; while(t-) cinn;int *a=new intn; for(i=-1;+i ai;/forT.CreateBi nary(a, n);T.I nOrderO; coutnum; while( num-) ci nN; coutT.Searchfordata(N)e ndl

32、;/while/while return 0;Problem C:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-二叉排序樹(shù)之刪除#in clude using n ames pace std;#defi ne OK 1#defi ne ERROR 0 class TreeNodepublic:int data;TreeNode *LeftChild;TreeNode *RightChild;TreeNode()LeftChild=NULL;RightChild=NULL;data=0; ;class Tree public:TreeNode* Root;bool Find;int times;void CreateB in

33、ary(i nt *a,i nt size) if(size=0)return; Root=NULL; TreeNode *t; int len gth=0;t=new TreeNode(); t-data=ale ngth;Root=t;for(;+le ngthdata=ale ngth; In sertElem(Root,t);/for/CreateBi naryvoid In sertElem(TreeNode *F,TreeNode *t) if(F-data data) if(F-RightChild)In sertElem(F-RightChild,t); /ifelse F-R

34、ightChild=t;/ifelseif(F-LeftChild)In sertElem(F-LeftChild,t); else F-LeftChild=t;/else/ln sertElemvoid Searchfordata(TreeNode *t, int data) if(Fi nd & t) times+;if(t-data=data) Fin d=false;else if(t-data data) Searchfordata(t-LeftChild,data); elseSearchfordata(t-RightChild,data); void Delete(TreeNod

35、e* &p) TreeNode *q;if(! p-RightChild) q=p;p=p-LeftChild;delete q;else if(! p-LeftChild) q=p;p=p-RightChild;delete q;elseq=P；TreeNode *s;s=p-LeftChild;while(s-RightChild)q=s;s=s-RightChild; p-data=s-data;if(q!=p)q-RightChild=s-LeftChild;else q-LeftChild=s-LeftChild; delete s;void delete_data(TreeNode

36、* &t,i nt data)if(Fi nd & t)if(t-data=data)Fin d=false; Delete(t);else if(t-data data) delete_data(t-LeftChild,data);else delete_data(t-RightChild,data);/delete_datavoid delete_data(i nt data) Fin d=true; delete_data(Root,data);int Searchfordata(i nt data)Fin d=true; times=0;Searchfordata(Root,data)

37、; if(Fi nd)return -1; else return times;void In Order()InO rder(Root);void In Order(TreeNode *t) if(t)In Order(t-LeftChild); coutdataRightChild); /if/ln Search;int mai n()int t,n ,i, num,N;Tree T; cin t; while(t-) cinn; int *a=new in t n; for(i=-1;+i ai;/forT.CreateBi nary(a, n);T.I nOrderO; coutnum

38、; while( num-) cin N; T.delete_data(N); T.I nOrderO; coute ndl;/while/while return 0;Contest1050 - DS實(shí)驗(yàn)-哈希查找Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)哈希查找#in clude using n ames pace std;#defi ne SUCCESS 1#defi ne UNSUCCESS 0 #defi ne DUP LICATE -1#defi ne OK 1 #defi ne Status int class Link public:Link*n ext;int data;Lin k()

39、 next=NULL; ;class HashTablepublic:Link *elem;/數(shù)據(jù)元素存儲(chǔ)基址，動(dòng)態(tài)分配數(shù)組 int count;/當(dāng)前數(shù)據(jù)元素個(gè)數(shù)int size in dex;/hashsizesize in dex為當(dāng)前容量 Status NewElem(i nt size) elem=new Lin ksize;coun t=0;size in dex=size;for(i nt i=-1;+isize in dex;) elemi.data=NULL; return SUCCESS;/NewElemint Hash( int data) return data%11;

40、/HashStatus In sertHash(i nt data)int c=0;int p;if(SearchHash(data, p,c)return DUP LICATE; else if(p data=data;coun t+;elem p . next=te mp; return OK; elseLink *te mp=new Lin k(); temp-data=data;Link *q=elem p . next; temp-n ext=q;elem p . next=te mp; return OK;/ln sertHashStatus SearchHash( int dat

41、a,i nt &p ,i nt &c) p=Hash(data);Link *q=elem p . next; while(q!=NULL & data!=q-data) if(q- next!=NULL) q=q-n ext;c+;else break;if(q!=NULL & data=q-data) return SUCCESS;elsereturn UNSUCCESS;/SearchHash;int mai n()HashTable HT;int n,Data,t, p,c;cinn;HT.NewElem(ll);for(i nt i=-1;+i Data;HT.I nsertHash

42、(Data);/for cin t; while(t-) cin Data; c=1; if(HT.SearchHash(Data ,p ,c) cout p ce ndl;elsecouterrore ndl;HT.I nsertHash(Data); return 0;Contest1060 - DS實(shí)驗(yàn)-排序算法Problem A:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-希爾排序#in clude using n ames pace std;class ShellSort public:void dis play(i nt *a,i nt len gth) int i;for(i=-1;+ile ngth-1;)

43、 coutai;coutai1)coutvvga pen dl;for(start=-1;+startga p;) for(i=ga p+start;i=0;j-=ga p) if(aj=ate mp )break; swap(&aj,&ate mp ); temp=j;/for/fordis play(a,le ngth);/for gap/=2;/whilecout最后進(jìn)行一次直接插入排序endl;/最后進(jìn)行一次直接插入排序for(i=0;+i=0;-j)if(ajt;while(t-)cinn;int *data=new in t n; for(i=-1;+i datai;/forSS.Shell_Sort(data ,n); for(i=-1;+iv n;)coutvvdataivv;/for coute ndl;/whilereturn 0;/intProblem B:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)-快速排序第一種算法：#in clude using n ames pace std;class QuickSort public:void swa p(i nt *a,i nt *b)(*a)A=(*b)A=(*a)A=(*b);int P artiti on (i nt *a,i nt low,i nt high)int pi votkey=alow;while(lowhi