理學(xué)數(shù)據(jù)結(jié)構(gòu)PPTPPT學(xué)習(xí)教案

1、會計學(xué)1理學(xué)數(shù)據(jù)結(jié)構(gòu)理學(xué)數(shù)據(jù)結(jié)構(gòu)PPT2第1頁/共86頁3第2頁/共86頁4集合名集合名 指針指針0 S11 S22 S30427681935第3頁/共86頁5n一個集合中一個集合中,可用可用 Union(S, i, j)將它們合并到一個集合中。將它們合并到一個集合中。第4頁/共86頁6parent集合集合 和和 的雙親表的雙親表示示- -4 4 - -3 2 - -3 2 0 0 0 40 1 2 3 4 5 6 7 8 90768419235第5頁/共86頁7 parent集合集合 和和 的雙親表的雙親表示示- -7 4 - -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7

2、8 907684194190876第6頁/共86頁8并查集的結(jié)構(gòu)定義并查集的結(jié)構(gòu)定義const int SetSize = 50; /并查集元素個數(shù)typedef struct /并查集結(jié)構(gòu)定義 int parentSetSize; /集合元素數(shù)組 UFSets;void InitUFSets (UFSets *S) /集合初始化 for ( int i = 0; i parenti = -1; /每一個自成一個單元素集合第7頁/共86頁950123Find (S,4)Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1Find (S,0) = 0 = - -

3、5 parent x parent x ); -5 0 1 2 35 0 1 2 3Parent4 =3 Parent3 =2Parent2 =1Parent1 =0Parent0 =-50 1 2 3 4第9頁/共86頁11n n 成的森林，成的森林，S-parenti = - -1。做處理做處理Union(n- -2, n- -1), ,Union(1, 2), Union(0, 1)后，將后，將產(chǎn)生退化的樹。產(chǎn)生退化的樹。第10頁/共86頁1211111350313322Union(0,1)23412Union(1,2)Union(2,3)Union(3,4)第11頁/共86頁13nin

4、i12OO)()(第12頁/共86頁14111111107252223323302Union(2, 0)第13頁/共86頁15void WeightedUnion (UFSets *S, int Rt1, int Rt2 ) 按Union的加權(quán)規(guī)則改進(jìn)的算法 int temp = S-parentRt1 + S-parentRt2; if ( S-parentRt2 parentRt1 ) S-parentRt1 = Rt2; /Root2中結(jié)點多 S-parentRt2 = temp; /Root1指向Root2 else S-parentRt2 = Rt1; /Root1中結(jié)點多 S-pa

5、rentRt1 = temp; /Root2指向Root1 第14頁/共86頁16000000002221223323302Union(2, 0)第15頁/共86頁170067867819193535從 i = 5 壓縮路徑第16頁/共86頁18int CollapsingFind (UFSets *S, int i ) /使用折疊規(guī)則的搜索算法 int j = i; while ( S-parentj = 0 ) j = S-parentj; /讓 j 循雙親指針走到根 while ( i != j ) /換 parenti 到 j int temp = S-parenti; S-paren

6、ti = j; i = temp; return j;第17頁/共86頁19第18頁/共86頁20第19頁/共86頁21第20頁/共86頁22#define MaxSize 100 /搜索表最大尺寸typedef int DataType; /搜索數(shù)據(jù)的類型 typedef struct /搜索表結(jié)點定義 DataType key; /關(guān)鍵碼域 other; /其他數(shù)據(jù)域 ListNode;typedef struct dataList /搜索表結(jié)點定義 ListNode dataMaxSize; /數(shù)據(jù)存儲數(shù)組 int n; /數(shù)組當(dāng)前長度第21頁/共86頁23n另外衡量一個搜索算法還要考另

7、外衡量一個搜索算法還要考慮算法所需要的存儲量和算法慮算法所需要的存儲量和算法的復(fù)雜性等問題。的復(fù)雜性等問題。第22頁/共86頁24n關(guān)鍵碼與關(guān)鍵碼與x相等的對象相等的對象, 則搜索則搜索失敗。給出失敗信息。失敗。給出失敗信息。第23頁/共86頁25int LinearSearch ( dataList A, DataType x ) /在數(shù)據(jù)表A.data1.n中順序搜索關(guān)鍵碼為 x/的數(shù)據(jù)對象, A.data0.key 作為控制搜索自動/結(jié)束的“監(jiān)視哨”使用 A.data0.key = x; int i = A.n; /將x送0號位置設(shè)置監(jiān)視哨 while ( A.datai.key !=

8、x ) i- ; /從后向前順序搜索 return i;第24頁/共86頁26 1010niiniiisuccpcpASL) 1 ( .)(11inpASLniisucc第25頁/共86頁27.)()(nisuccnnnninnASL12121111第26頁/共86頁28int SequentSearch ( dataList A, dataType x, int& loc ) /在數(shù)據(jù)表 A.data0.n- -1 中搜索其關(guān)鍵碼與/給定值匹配的對象, 函數(shù)返回其表中位置。/參數(shù) loc 是在表中開始搜索位置 if ( loc = A.n ) return -1; /搜索失敗 else if

9、 ( A.dataloc.key = x ) return loc; /搜索成功 else return SequentSearch ( A, x, loc+1 ); /遞歸搜索第27頁/共86頁29int SequentSearch ( dataList A, DataType x ) /在數(shù)據(jù)表 A.data0.n- -1 中順序搜索關(guān)鍵碼為 x 的數(shù)據(jù)對象 for ( int i = 0; i x ) break; return -1; /順序搜索失敗, 返回失敗信息第28頁/共86頁301050602030402716150isucciASL727617150iunsucciASL第2

10、9頁/共86頁31象，仍未找到想要搜索的對象，象，仍未找到想要搜索的對象，則搜索失敗。則搜索失敗。第30頁/共86頁32搜索成功的例子搜索成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6第31頁/共86頁33搜索失敗的例子搜索失敗的例子- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high5第32頁/共86頁34

11、int BinarySearch ( dataList A, DataType x, int low, int high ) int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( A.datamid.key x )mid = BinarySearch ( A, x, low, mid -1 ); return mid;第33頁/共86頁35int BinarySearch ( dataList A, DataType x ) int high = A.n-1, low = 0, mid; while ( low = hig

12、h ) mid = ( low + high ) / 2; if ( A.datamid.key x ) high = mid - 1; /左縮搜索區(qū)間 else return mid; /搜索成功 return -1; /搜索失敗第34頁/共86頁36105030204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 第35頁/共86頁37即即pi= 1/n，則搜索成功的平均，則搜索成功的平均搜索長度為搜索長度為第36頁/共86頁38)221)(23 2211111221101hhniin0iiisucchh

13、(nCnCpASL121)(221)( 2322111221hhhhhh11)(log11)(log1 )1)(1)log(11)21)(1 222nnnnnnnnhnASLhsucc第37頁/共86頁39定義定義 第38頁/共86頁40351545504025102030第39頁/共86頁4151*2*34*5*6*41C13133*2122133132123123123 132 213 231 312 321第40頁/共86頁42typedef char DataType; /樹結(jié)點數(shù)據(jù)類型typedef struct node /搜索樹結(jié)點定義 DataType data; struct

14、 node *leftChild, *rightChild; BstNode;typedef BstNode *BST; /二叉搜索樹定義第41頁/共86頁43351545504025102030第42頁/共86頁44第43頁/共86頁4535154550251020302245第44頁/共86頁46BstNode * Find ( BstNode *ptr, DataType x ) /二叉搜索樹的迭代的搜索算法 if ( ptr != NULL ) BstNode * p = ptr; /從根搜索 while ( p != NULL ) if ( p-data = x ) return p

15、; if ( p-data rightChild; /右子樹 else p = p-leftChild; /左子樹 return NULL; /搜索失敗 第45頁/共86頁4735154550402510203028插入新結(jié)點插入新結(jié)點28第46頁/共86頁48void Insert ( DataType x, BstNode * & ptr) /將新元素x插到以*ptr為根的二叉搜索樹中第47頁/共86頁49 if ( ptr = NULL ) /空二叉樹 ptr = new BstNode; /創(chuàng)建結(jié)點 if ( ptr = NULL ) cout “存儲不足 data = x; ptr-

16、leftChild = ptr-rightChild = NULL; else if ( x data ) /在左子樹插入 Insert ( x, ptr-leftChild ); else if ( x ptr-data ) /在右子樹插入 Insert ( x, ptr-rightChild );第48頁/共86頁50 535378537865537865175378658717537865091787537865811787095378651517870981第49頁/共86頁51void CreateBST ( BstNode *& T, DataType Refvalue ) 輸入數(shù)

17、據(jù), 建立二叉搜索樹。RefValue 是輸入/結(jié)束標(biāo)志。這個值應(yīng)取不可能在輸入序列中/出現(xiàn)的值, 例如輸入序列的值都是正整數(shù)時, /取RefValue為0或負(fù)數(shù)。 dataType x; T = NULL; cin x; while ( x != RefValue ) if ( Find (T, x) = NULL ) Insert ( x, T ); cin x; 第50頁/共86頁52123111132223323第51頁/共86頁53n結(jié)點頂替它的位置，再釋放它。結(jié)點頂替它的位置，再釋放它。第52頁/共86頁545378651787092345刪除45缺右子樹, 用左子女頂替53786

18、517870923第53頁/共86頁558853788817940923刪除78缺左子樹, 用右子女頂替53948817092353788117940945刪除78在右子樹上找中序下第一個結(jié)點填補2365538188179409452365第54頁/共86頁56 n增加了外部結(jié)點的二叉搜索樹增加了外部結(jié)點的二叉搜索樹稱為擴(kuò)充二叉搜索樹。稱為擴(kuò)充二叉搜索樹。Cnnn211第55頁/共86頁57第56頁/共86頁58doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)第57頁/共86頁59doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p

19、2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)第58頁/共86頁60).(*1p1i liASLnisuccnjunsuccjljASL0q. *第59頁/共86頁61第60頁/共86頁62第61頁/共86頁63.nisucciASL121log.1nniunsucciASL212log第62頁/共86頁64doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15q1=0.1q2=0.05q3= 0.05p1=0.5p2=0.1p3=0.05(a)(b)第63頁/共86頁65doifto q0=0.

20、15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(d)(c)圖圖(b) :ASL = 1.9; 圖圖(d) :ASL = 2.15;第64頁/共86頁66doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e)第65頁/共86頁67 ABCABCDEDE第66頁/共86頁68, n 可保持在可保持在O(log2n),平均搜索長平均搜索長度也可保持在度也可保持在O(log2n)。第67頁/共86頁69typedef int DataType; /結(jié)點數(shù)據(jù)類型typedef struct node /AVL樹結(jié)點定義 DataType data; /結(jié)點數(shù)據(jù)域 int balance; /結(jié)點平衡因子域 struct node *leftChild, *rightChild; /結(jié)點左、右子女指針域結(jié)點左、右子女指針域 AVLNode;typedef AVLNode * AVLTree; /AVL樹第68頁/共86頁70根的路徑回溯根的路徑