數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)(詳細(xì)無(wú)題目).

1、數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)內(nèi)容概要：排序基本概念線(xiàn)性表?xiàng)Ｅc隊(duì)列樹(shù)與二叉樹(shù) 圖查找算法 算法ftliA insert () xemove()棧與亂列push(), put () pop Ox 妙()jW易二丈樹(shù) pre_order) in_order() - pcstozdcT (I蠻叭)一 bfs()圖算法MSTt圖算法 岡Prim耳法一0(以)%o Kruskal 算法一O(ElogE) SPTj_(B Dijkstra 算法一0(，)0 Floyd 菲法一0(V A0V*0*# 序一0V + E) AOEIO(V + E)查找算法I蛉冬席構(gòu)柚顒摩查我一 0仿) 0折豐查找一O(logn)i 動(dòng)歳姑

2、曲0 BSTWO(n)O(logn) 0 AVL W *O(logn) 0B-MO(logMn) 快建排序一0(*) + 0(logrt)0單排序一0(m log對(duì))序L/基荻咼序 0(d)、基本概念1、數(shù)據(jù)元素是數(shù)據(jù)的基本單位。2、數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。3、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)(抽象的，與實(shí)現(xiàn)無(wú)關(guān))物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))順序映像(順序存儲(chǔ)結(jié)構(gòu))位置“相鄰”非順序映像(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))指針表示關(guān)系4、 算法特性：算法具有正確性、有窮性，確定性，(可行性)、輸入，輸出 正確性：能按設(shè)計(jì)要求解決具體問(wèn)題，并得到正確的結(jié)果。有窮性：任何一條指令都只能執(zhí)行有限次，即算法必須在執(zhí)行有限步后結(jié)束。 確

3、定性：算法中每條指令的含義必須明確，不允許由二義性可行性：算法中待執(zhí)行的操作都十分基本，算法應(yīng)該在有限時(shí)間內(nèi)執(zhí)行完畢。2)輸入：一個(gè)算法的輸入可以包含零個(gè)或多個(gè)數(shù)據(jù)。輸出：算法有一個(gè)或多個(gè)輸出5、算法設(shè)計(jì)的要求：（1）正 確性：算法應(yīng)能滿(mǎn)足設(shè)定的功能和要求 。（2）可 讀性：思路清晰、層次分明、易讀易懂 。（3）健 壯 性：輸入非法數(shù)據(jù)時(shí)應(yīng)能作適當(dāng)?shù)姆磻?yīng)和處理。（4）高 效性（時(shí)間復(fù)雜度）：解決問(wèn)題時(shí)間越短，算法的效率就越高。（5）低存儲(chǔ)量（空間復(fù)雜度）：完成同一功能，占用存儲(chǔ)空間應(yīng)盡可能少二、線(xiàn)性表1、線(xiàn)性表List:最常用且最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。含有大量記錄的線(xiàn)性表稱(chēng)為文件。2、線(xiàn)性表是n個(gè)數(shù)

4、據(jù)元素的有限序列。線(xiàn)性結(jié)構(gòu)的特點(diǎn)：“第一個(gè)” “最后一個(gè)” 前驅(qū)后繼3、順序表線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)a）邏輯上相鄰的元素在物理位置上相鄰L.elemL.elemL.elemb）隨機(jī)訪(fǎng)問(wèn)。1）typedef structDataType elemMAXSIZE;int len gth; SqList;2）表長(zhǎng)為n時(shí)，線(xiàn)性表進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度為O （n）插入一個(gè)元素時(shí)大約移動(dòng)表中的一半元素。刪除一個(gè)元素時(shí)大約移動(dòng)表中的（n-1） 24、線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1)類(lèi)型定義簡(jiǎn)而言之，“數(shù)據(jù)+指針datan exttypedef struct LNode DataType data;stru

5、ct LNode *n ext; LNode, *L in kList;不帶頭結(jié)點(diǎn)的空表判定為L(zhǎng)= =null帶頭結(jié)點(diǎn)的空表判定為L(zhǎng)- next= =null 循環(huán)單鏈表為空的判定條件為 L.n ext= =L 線(xiàn)性鏈表的最后一個(gè)結(jié)點(diǎn)的指針為 NULL 頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?，指針域指向第一個(gè)元素的指針5、順序表和單鏈表的比較順序表單鏈表以地址相鄰表示關(guān)系用指針表示關(guān)系隨機(jī)訪(fǎng)問(wèn)，取兀素 0(1)順序訪(fǎng)冋，取兀素 0(n)插入、刪除需要移動(dòng)兀素0( n)插入、刪除不用移動(dòng)兀素 0(n)(用于查找位 置)6、順序存儲(chǔ)：優(yōu)點(diǎn)：存儲(chǔ)密度大，可隨機(jī)存儲(chǔ)缺點(diǎn)：大小固定；不利于增減節(jié)點(diǎn)；存儲(chǔ)空間不能充分利用；容

6、量 難擴(kuò)充鏈?zhǔn)酱鎯?chǔ)：優(yōu)點(diǎn)：易于插入刪除；可動(dòng)態(tài)申請(qǐng)空間；表容量?jī)H受內(nèi)存空間限 制缺點(diǎn)：增加了存儲(chǔ)空間的開(kāi)銷(xiāo)；不可以隨機(jī)存儲(chǔ)元素三、棧與隊(duì)列1、棧棧：限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。 棧頂：表尾端棧底：表頭棧是先進(jìn)后出的線(xiàn)性表。插入棧頂元素稱(chēng)為入棧，刪除棧頂元素稱(chēng)為出棧。2、棧分為鏈棧和順序棧鏈棧八用不帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)。；順序棧類(lèi)似于順序表，插入和刪除操作固定于表尾。進(jìn)棧進(jìn)棧運(yùn)算是在棧頂位置插入一個(gè)新元素 算法思想：算法步驟.(a) 判棧是否為滿(mǎn)，若棧滿(mǎn)，作溢出處理，并返回 算步驟(b) 若棧未滿(mǎn)，棧頂指top加1 ；(a)(c) 將新元素送入棧頂，并返回算法實(shí)現(xiàn)：/、(c)int

7、Push (SeqSta6, datatypx) if (s-top= =MAXLEN算法實(shí)現(xiàn)：/棧滿(mǎn)不能入棧，且返回 datatypcPop (SeqSta*) datatype if (SEmptys )return 0 /若棧空不能出棧且返回 else x=s-datas；top/棧不空則棧頂元素存入出棧出棧運(yùn)算是指取出棧頂元素，賦給某一個(gè)指定變量判棧是否為空，若?？?，作下溢處理，并返回(b)若棧非空，將棧頂元素賦給變量 指針op減1，并返回。return 0 else s-top+ s-datas-top=X棧不滿(mǎn)，則壓入元素 return 1/進(jìn)棧成功，返回s-top-；return

8、 x /出棧成功，返回3、隊(duì)列先進(jìn)先出的線(xiàn)性表。隊(duì)尾入隊(duì)對(duì)頭出隊(duì) 允許插入的一端叫做隊(duì)尾 允許刪除的一端叫做對(duì)頭4、鏈隊(duì)列typedef struct queuenodedatatype data;struct queuenode *next;queuenode;/鏈隊(duì)結(jié)點(diǎn)的類(lèi)型 datatypetypedef structqueuenode *front,*rear;linkqueue; II將頭指針、尾指針?lè)庋b在一起的鏈隊(duì)frontrear圖4-6鏈隊(duì)列示意圖（2）出隊(duì)3.鏈甌的基本運(yùn)算：(1)入甌進(jìn)駅void InQueue (Linkqueue *q.queuenode *p)進(jìn)駅函藪

9、int x;卅定叉入隊(duì)元素類(lèi)型queucnode *p=malloc (sizeof ( quelienode); p-data=i;輸入元素puextNULL;修比指針lf(l-frout= =NLLL) q-front=p;dse(|-iear-nextp;q-rear=p;int OutQueue(linkqueiie *q, datatype出駅函數(shù)(queueuode *p:if(q-front= =NLLL)-爭(zhēng)叫人空retiirn 0;elsep=q-front;./若隊(duì)不空，則作出隊(duì)處理v-pdata;q -front=p-n ext; if(q-front=XULL) q-r

10、ear=NlLL;free ( P );回收結(jié)點(diǎn)returtL 1:坂回 15、循環(huán)隊(duì)列typedef struct DataType elemMAXSIZE;int front, rear;/隊(duì)頭、隊(duì)尾位置 SqQueue;循環(huán)隊(duì)列判斷隊(duì)空的條件為fron t=rear循環(huán)隊(duì)列判斷隊(duì)滿(mǎn)的條件為（rea葉1） %m=front在一個(gè)循環(huán)隊(duì)列中刪除元素時(shí)，首先需要后移隊(duì)首指針。6、 棧與隊(duì)列比較：都是線(xiàn)形結(jié)構(gòu)，棧的操作LIFO（后進(jìn)先出），隊(duì)列操作FIFO（先進(jìn)先出）四、樹(shù)和二叉樹(shù)樹(shù)與二叉樹(shù)重點(diǎn)內(nèi)容樹(shù)專(zhuān)二更#i|44與二更樹(shù)的基本観金莓tU迪厲援作二夏対皓存儲(chǔ)衣示定全二兄梢 二殳饋表蜿車(chē)二鬼梢二

11、夏樹(shù)與村.拯林的柯互轉(zhuǎn)按 枷時(shí)與儲(chǔ)我岳I*或歩表示謹(jǐn)r航子袁示法t_養(yǎng)子-兄第衣京袪二殳制的盛用撫尢圾亂列 Huffman -W期的應(yīng)用匕劃分爭(zhēng)價(jià)灸（UfSeO1. 樹(shù)的定義樹(shù)（Tree）:是n （n0）個(gè)有限數(shù)據(jù)元素的集合。在任意一棵非空樹(shù)T中（1）有且僅有一個(gè)特定的稱(chēng)為樹(shù)根（Root）的結(jié)點(diǎn)，根結(jié)點(diǎn)無(wú)前趨結(jié)點(diǎn)；（2） 當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成 m（m0個(gè)互不相交的集 合T1, T2,，Tm其中每一個(gè)集合Ti （K i n，則無(wú)左孩子；i的右孩子是2i + 1,如果2i + 1n則無(wú)右孩子。4. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)用數(shù)組、編號(hào)i的結(jié)點(diǎn)存放在i-1處。適合于存儲(chǔ)完全二叉

12、樹(shù)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表：typedef struct BTNode DataType data;struct BTNode *lchild, *rchild; BTNode, *B in Tree;三叉鏈表：typedef struct BTNode DataType data;struct BTNode *lchild, *rchild, *pare nt; BTNode, *B in Tree;lchilddata rch Ilchilddatapare ntrchild存儲(chǔ)結(jié)構(gòu)中，含有n個(gè)結(jié)點(diǎn)的二叉鏈表有n+1個(gè)空鏈域5.遍歷二叉樹(shù)（先序DLR中序LDR后序LRD方法與C語(yǔ)言描述由二

13、叉樹(shù)的遞歸定義可知，一棵二叉樹(shù)由根結(jié)點(diǎn)（D）、根結(jié)點(diǎn)的左子樹(shù)（L）和根結(jié)點(diǎn)的右子樹(shù)（R）三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹(shù)。一般有三 種方法：先序（前序）遍歷DLR（根左右）、中序遍歷LDR（左根右）、后序遍歷LRD（左右根）1 .先序遍歷(DLR )的遞歸過(guò)程void P reorder(BT *T) if (T= =NULL) return;/先序遍歷二叉樹(shù)BT/遞歸調(diào)用的結(jié)束條件II輸出結(jié)點(diǎn)的數(shù)據(jù)域II先序遞歸遍歷左子樹(shù)II先序遞歸遍歷右子樹(shù)6.2 中序遍歷（LDR)的遞歸過(guò)程void Inorder(BT*T) if (T= =NULL) return; ln

14、order(T-lchild); printf(T-data); Inorder(T-rchild);后序遍歷(LRD)的遞歸過(guò)程void Postorder(BT *T) if (T= =NULL) return; Postorder(T-lchild);Postorder(T-rchild); printf(T-data);/中序遍歷二叉樹(shù)BT/遞歸調(diào)用的結(jié)束條件 中序遞歸遍歷左子樹(shù) 輸出結(jié)點(diǎn)的數(shù)據(jù)域 中序遞歸遍歷右子樹(shù)/后序遍歷二叉樹(shù)BT遞歸調(diào)用的結(jié)束條件 后序遞歸遍歷左子樹(shù) 后序遞歸遍歷右子樹(shù)輸出結(jié)點(diǎn)的數(shù)據(jù)域線(xiàn)索二叉樹(shù)可以利用其指向前驅(qū)或后繼結(jié)點(diǎn)，叫線(xiàn)索，同lchild ltagdat

15、artagrchildn個(gè)結(jié)點(diǎn)的二叉鏈表中有 n+1個(gè)空指針, 時(shí)需附加一個(gè)標(biāo)志，區(qū)分是子樹(shù)還是線(xiàn)索。0/1 0/1Ichild有左子樹(shù)，則指向左子樹(shù)，標(biāo)志沒(méi)有左子樹(shù)，可作為前驅(qū)線(xiàn)索，標(biāo)志rchild有右子樹(shù)，則指向右子樹(shù)，標(biāo)志沒(méi)有右子樹(shù)，可作為后繼線(xiàn)索，標(biāo)志Itag = 0;Itag = 1。rtag = 0;rtag = 1。7.樹(shù)和森林 printf(T-data); Preorder(T-lchild); Preorder(T-rchild);樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法，孩子表示法，孩子兄弟表示法。特點(diǎn)：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子, 但求雙親麻煩；兩者

16、可以結(jié)合起來(lái)使用。孩子兄弟表示法，容易求得孩子和兄弟, 求雙親麻煩，也可以增加指向雙親的指針來(lái)解決。樹(shù)與二叉樹(shù)的轉(zhuǎn)換表 錯(cuò)誤！文檔中沒(méi)有指定樣式的文字。.1樹(shù)和二叉樹(shù)的對(duì)應(yīng)關(guān)系樹(shù)對(duì)應(yīng)的二叉樹(shù)根根第一個(gè)孩子左孩子下一個(gè)兄弟右孩子樹(shù)的遍歷樹(shù)的結(jié)構(gòu)：根，根的子樹(shù)。先根遍歷：。例：ABCDEFGHIJK后根遍歷：。例：CEDFBHGJKIA遍歷森林森林的結(jié)構(gòu)：第一棵樹(shù)的根，第一棵樹(shù)的根的子樹(shù)森林，其余樹(shù)（除第一棵外）組成的森林。先序遍歷：。例：ABCDEFGHU中序遍歷：。例： BDCEAGFIJH注：先序遍歷森林，相當(dāng)于依次先根遍歷每一棵樹(shù)；中根遍歷森林相當(dāng)于后根遍歷每一棵樹(shù)。樹(shù)的結(jié)構(gòu)劃森林的結(jié)構(gòu)劃

17、分遍歷樹(shù)、森林與遍歷二叉樹(shù)的關(guān)系遍歷樹(shù)、森林和二叉樹(shù)的關(guān)系樹(shù)森林二叉樹(shù)先根遍歷先序遍歷先序遍歷后根遍歷中序遍歷中序遍歷8哈夫曼樹(shù)：葉子結(jié)點(diǎn)帶有權(quán)值的最小帶權(quán)路徑長(zhǎng)度的最優(yōu)二叉樹(shù)WPL= Z Wh Lkk=l構(gòu)造赫夫曼樹(shù)每次取兩個(gè)最小的樹(shù)組成二叉樹(shù)赫夫曼編碼(前綴碼)向左分支為0,向右分支為1,從根到葉子的路徑構(gòu)成葉子的前綴編碼。五、完全圖：有12 n( n-1)條變得無(wú)向圖有向完全圖：具有n (n-1)條弧的有向圖。 權(quán)：與圖的邊或弧相關(guān)的數(shù)。頂點(diǎn)v的度：和v相關(guān)聯(lián)的邊的數(shù)目。入度：以頂點(diǎn)v為頭的弧的數(shù)目出度：以頂點(diǎn)v為尾的弧的數(shù)目回路或環(huán)：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑 簡(jiǎn)單路徑：序列中

18、頂點(diǎn)不重復(fù)出現(xiàn)的路徑。2.圖的存儲(chǔ)結(jié)構(gòu)0110000110000101000010010-鄰接矩陣:ABCDE-鄰接表:typedef struct ArcNode / 弧結(jié)點(diǎn)int adjvex;struct ArcNode *n extarc; ArcNode;/鄰接點(diǎn)/下一個(gè)鄰接點(diǎn)typedef struct VexNode / 頂點(diǎn)結(jié)點(diǎn)VertexTypeArcNode *firstarc; VexNode;data; II頂點(diǎn)信息/第一個(gè)鄰接點(diǎn)constint MAX_VERTEX =最大頂點(diǎn)個(gè)數(shù) typedef struct Graph / 圖VexNodeint vexnum,

19、arcnum; Graph;vexsMAX_VERTEX; 頂點(diǎn)向量II頂點(diǎn)和弧的個(gè)數(shù)邊(弧)多則需要存儲(chǔ)空間多。A1B亠2C3八D0八E001234-*2/*3/3/-十字鏈表:十字鏈表是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？梢钥闯墒菍⒂邢驁D的鄰接表和逆 鄰接表結(jié)合起來(lái)的一種鏈表。在十字鏈表中，對(duì)應(yīng)于有向圖中每一條弧有一個(gè)結(jié) 點(diǎn)，對(duì)應(yīng)于每個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)。鄰接多重表3. 圖的遍歷1）深度優(yōu)先（DFS搜索訪(fǎng)問(wèn)方式：從圖中某頂點(diǎn)v出發(fā)：a）訪(fǎng)問(wèn)頂點(diǎn)v；b）從v的未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)，繼續(xù)對(duì)圖進(jìn)行深度優(yōu)先遍歷，若從某點(diǎn) 出發(fā)所有鄰接點(diǎn)都已訪(fǎng)問(wèn)過(guò)，退回前一個(gè)點(diǎn)繼續(xù)上述過(guò)程，若退回開(kāi)始點(diǎn)， 結(jié)束。2）廣度（寬

20、度，BFS優(yōu)先搜索a）訪(fǎng)問(wèn)頂點(diǎn)v ；b）訪(fǎng)問(wèn)同v相鄰的所有未被訪(fǎng)問(wèn)的鄰接點(diǎn) wi,W2,wc）依次從這些鄰接點(diǎn)出發(fā)，訪(fǎng)問(wèn)它們的所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)；依此類(lèi)推， 直到圖中所有訪(fǎng)問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wèn)；4. 生成樹(shù)和最小生成樹(shù)每次遍歷一個(gè)連通圖將圖的邊分成遍歷所經(jīng)過(guò)的邊和沒(méi)有經(jīng)過(guò)的邊兩部分， 將遍歷經(jīng)過(guò)的邊同圖的頂點(diǎn)構(gòu)成一個(gè)子圖，該子圖稱(chēng)為生成樹(shù)。因此有DFS生成 樹(shù)和BFS生成樹(shù)。1）最小生成樹(shù) Kruskal算 法一句話(huà)，“不構(gòu)成環(huán)的情況下，每次選取最小邊”。-普里姆算法記V是連通網(wǎng)的頂點(diǎn)集，U是求得生成樹(shù)的頂點(diǎn)集，TE是求得生成樹(shù)的邊集。 普里姆算法：(a) 開(kāi)始時(shí)，U=vo, TES

21、;(b) 計(jì)算U到其余頂點(diǎn)V-U的最小代價(jià)，將該頂點(diǎn)納入U(xiǎn),邊納入TE;(c) 重復(fù)(b)直到U=V。普里姆算法和克魯斯卡爾算法的比較算法普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜O(n2)O(e loge)度特點(diǎn)只與頂點(diǎn)個(gè)數(shù)n有關(guān)只與邊的數(shù)目e有關(guān)與邊的數(shù)目e無(wú)關(guān)與頂點(diǎn)個(gè)數(shù)n無(wú)關(guān)適用于稠密圖適用于稀疏圖5. AOV-網(wǎng)用頂點(diǎn)表示活動(dòng)，邊表示活動(dòng)的優(yōu)先關(guān)系的有向圖稱(chēng)為AOV網(wǎng)拓?fù)渑判颍簩?duì)AOV網(wǎng)絡(luò)中頂點(diǎn)構(gòu)造拓?fù)溆行蛐蛄械倪^(guò)程。拓?fù)渑判虻姆椒?1)在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和所有以它為尾的弧6.關(guān)鍵路徑AOE網(wǎng)，關(guān)鍵路徑AOE網(wǎng)(Activity On Edge)帶權(quán)的有向無(wú)環(huán)

22、圖， 其中頂點(diǎn)表示事件， 弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間。在工程上常用來(lái)表示工程進(jìn)度計(jì)劃。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)的一條路徑，或者全部由關(guān)鍵活動(dòng)構(gòu)成的路徑。7. 最短路徑(1)迪杰斯特拉算法求一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短路徑。算法：(a)初始化：用起點(diǎn)v到該頂點(diǎn)w的直接邊(弧)初始化最短路徑，否則設(shè)為R；(b) 從未求得最短路徑的終點(diǎn)中選擇路徑長(zhǎng)度最小的終點(diǎn)u:即求得v到u的最短路徑；(c) 修改最短路徑：計(jì)算u的鄰接點(diǎn)的最短路徑，若(V,u)+(u,w)(v,，則期(V,u,w)代替。(d) 重復(fù)(b)-(c)，直到求得v到其余所有頂點(diǎn)的最短路徑。特點(diǎn)：總是按照從小到大的順序求得最短路徑。

23、(2) 弗洛伊德算法求每對(duì)頂點(diǎn)之間的最短路徑。依次計(jì)算 A(0),A，,A(n)。為鄰接矩陣，計(jì)算 A(k)時(shí)，A(k)(i,j)=minA(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)。 技巧：計(jì)算A(k)的技巧。第k行、第k列、對(duì)角線(xiàn)的元素保持不變，對(duì)其余元素，考查A(i,j)與A(i,k)+A(k,j)(“行+列”)，如果后者更小則替換 A(i,j)，同時(shí)修改路徑。六、查找1. 查找分為：靜態(tài)查找表、動(dòng)態(tài)查找表、哈希查找表2. 靜態(tài)查找表：對(duì)查找表只作查找操作的查找表。 動(dòng)態(tài)查找表：查找過(guò)程中同時(shí)插入表中不含的元素，或者刪除查找表中已有 的元素的操作的查找表。3.

24、 順序查找：順序查找又稱(chēng)線(xiàn)性查找，是最基本的查找方法之一。順序查找既 適用于順序表，也適用于鏈表。4. 二分法(折半)查找：是一種效率較高的查找方法，但前提是表中元素必須 按關(guān)鍵字有序(按關(guān)鍵字遞增或遞減)排列。5. 索引順序表查找又稱(chēng)分塊查找。分塊查找：塊內(nèi)無(wú)序、塊間有序、如何分塊 效率最高6. 動(dòng)態(tài)查找表：二叉排序樹(shù)查找：二叉排序樹(shù)的生成二叉排序樹(shù) (二叉查找樹(shù) )：或者是一顆空樹(shù)?；蛘呷缦?1 若它的左子樹(shù)不空， 則左子樹(shù)上所有的結(jié)點(diǎn)的值均小于他的根結(jié)點(diǎn)的值。 2 若右子樹(shù)不空，則右 子樹(shù)所有結(jié)點(diǎn)的值均大于她得根結(jié)點(diǎn)的值。 3 左右子樹(shù)也分別為二叉排序 樹(shù)。7. 哈希表：哈希函數(shù)構(gòu)造：

25、直接定址法、除留余數(shù)法、 平方取中法，隨機(jī)數(shù)法， 數(shù)字分析法沖突解決方法：開(kāi)放定址法、拉鏈法、公共溢出區(qū)法七、排序1. 插入類(lèi)排序：直接插入排序每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng) 位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。折半插入排序希爾排序基本思想：先將整個(gè)待排序記錄序列分成為若干個(gè)子序列分別進(jìn)行直接 插入排序，待整個(gè)序列中的記錄 基本有序 時(shí)在對(duì)全體序列進(jìn)行一次直 接插入排序，子序列的構(gòu)成不是簡(jiǎn)單的逐段分割，而是將像個(gè)某個(gè)增量 的記錄組成一個(gè)子序列。2. 交換類(lèi)排序起泡排序也稱(chēng)冒泡法，每相鄰兩個(gè)記錄關(guān)鍵字比大小，大的記錄往下沉（也可以小 的往上?。?/p>

26、。每一遍把最后一個(gè)下沉的位置記下，下一遍只需檢查比較到 此為止；到所有記錄都不發(fā)生下沉?xí)r，整個(gè)過(guò)程結(jié)束（每交換一次，記 錄減少一個(gè)反序數(shù)）?？焖倥判蛟诋?dāng)前無(wú)序區(qū)R1.H中任取一個(gè)數(shù)據(jù)元素作為比較的 基準(zhǔn)（不妨記為X），用此基 準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R1.l-1和RI+1.H，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素， 右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R1.l-1 X.KeyW RI+1.H（1 I手H）當(dāng)R1.l-1和RI+1.H均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過(guò)程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?. 選擇類(lèi)排序簡(jiǎn)單選擇排序每一趟從待排序的數(shù)據(jù)元素中