理工類專業(yè)課復(fù)習(xí)資料-《數(shù)據(jù)結(jié)構(gòu)》基本概念

1數(shù)據(jù)數(shù)據(jù)是信息的載體，在計算機科學(xué)中是指所有能輸入到計算機中并能被計算機程序識別和處理的符號數(shù)據(jù)元素慮和處理。數(shù)據(jù)項的不可分割的最小單位。數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)結(jié)構(gòu)是一個二元組DataStructure=(D,數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示。通常有兩種存儲結(jié)構(gòu)：順順序存儲結(jié)構(gòu)的基本思想是：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是鏈接存儲結(jié)構(gòu)的基本思想是：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是用指抽象數(shù)據(jù)類型構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實算法的定義通俗地講，算法是解決問題的方法，嚴格地說，算法是對特定問題求解步驟的一種描述，是指令的有算法的特性法可以沒有輸入)，這些輸入通常取自于某個特定的對象法必須要有輸出)，通常輸出與輸入之間有著某種特定的2線性表的定義線性表簡稱表，是零個或多個具有相同類型的數(shù)據(jù)元素的有限序列。數(shù)據(jù)元素的個數(shù)稱為線性表的長線性表的邏輯關(guān)系nan順序表的存儲結(jié)構(gòu)定義#defineMaxSize100typedefstruct{ElemTypedataMaxSize//ElemType表示不確定的數(shù)據(jù)類型intlength;//length表示線性表的長度順序表是隨機存取結(jié)構(gòu)LOC(ai)=LOC(a1)＋(i－1)×c順序表的優(yōu)缺點順序表利用了數(shù)組元素在物理位置上的鄰接關(guān)系來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，這使得順；⑵可以快速地存取表中任一位置的元素(即隨機存取)。單鏈表的存儲結(jié)構(gòu)定義StructNodeemTypedataElemTypeNodenext}*first;//first為單鏈表的頭指針雙鏈表的存儲結(jié)構(gòu)定義3ode{ElemTypedata//ElemType表示不確定的數(shù)據(jù)類型xt}*first;//first表示雙鏈表的頭指針棧的定義棧的操作特性隊列的定義隊列是只允許在一端進行插入操作，而另一端進行刪除操作的線性表。允許插入的一端稱為隊尾，允隊列的操作特性循環(huán)隊列中解決隊空隊滿的判斷條件方法二：修改隊滿條件，浪費一個元素空間，隊滿時數(shù)組中只有一個空閑單元；即隊空的條件是arfrontQueueSizeQueueSize串的定義空格串和空串的定義串的比較當下列條件之一成立時，稱X＜Y：改進的模式匹配算法中next[j]的求法nextjtj對應(yīng)的k值(1≤j≤m)，其定義如下：數(shù)組的基本操作數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。因此，在4二維數(shù)組的尋址按行優(yōu)先，設(shè)二維數(shù)組的行下標與列下標的范圍分別為[l1，h1]與[l2，h2]，則任一元素aij的存儲特殊矩陣的定義矩陣壓縮存儲的基本思想ikjjiki×(i-k稀疏矩陣的壓縮存儲方式字鏈表三元組的定義nt{introwcollemTypeitem廣義表的定義廣義表是n(n≥0)個數(shù)據(jù)元素的有限序列。表頭表尾長度深度樹的定義結(jié)點的度、樹的度5葉子結(jié)點、分支結(jié)點。孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點結(jié)點稱為該結(jié)點的孩子結(jié)點；反之，該結(jié)點稱為其孩子結(jié)點的雙親路徑、路徑長度祖先、子孫如果從結(jié)點x到結(jié)點y有一條路徑，那么x就稱為y的祖先，而y稱為x的子孫。結(jié)點的層數(shù)、樹的深度(高度)二叉樹的定義nn合或者為空集(稱為空二叉樹)，或者由一個根結(jié)點和兩叉樹組成。二叉樹的特點叉樹中不存在度大于2的結(jié)點；⑵子樹的次二叉樹的基本形態(tài)二叉樹具有五種基本形態(tài)：⑴空二叉樹；⑵只有一個根結(jié)點；⑶根結(jié)點只有左子樹；⑷根結(jié)點只斜樹所有結(jié)點都只有左子樹的二叉樹稱為左斜樹；所有結(jié)點都只有右子樹的二叉樹稱為右斜樹；左斜樹和滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二點。完全二叉樹二叉樹的基本性質(zhì)性質(zhì)1二叉樹的第i層上最多有2i-1個結(jié)點(i≥1)。6≤i≤n)的結(jié)點(簡稱為結(jié)點i)，有：二叉樹的存儲ode{TypedataBiNodelchildrchild}*root;//root表示二叉鏈表的頭指針Node{TypedataTriNode*lchild,*rchild,*parent;//parent指向該結(jié)點的雙親}*root;//三叉鏈表的頭指針遍歷的含義所謂遍歷就是無重復(fù)無遺漏地訪問。二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的二叉樹的遍歷次序定義前序遍歷(或稱前根遍歷、先序遍歷)操作返回；否則中序遍歷(或稱中根遍歷)操作返回；否則后序遍歷(或稱后根遍歷)操作返回；否則7二叉樹的層序遍歷是從二叉樹的第一層(根結(jié)點)開始，從上至下逐層遍歷，在同一層中，則按從左線索二叉樹的定義nn點在某種遍歷序列中的前驅(qū)和二叉鏈表稱為線索鏈表。線索二叉樹的存儲結(jié)構(gòu)定義umflagChildThreadrNode{ElemTypedata//ElemType表示不確定的數(shù)據(jù)類型rNodelchildrchildtagrtag}*root;//root表示線索鏈表的頭指針樹的存儲結(jié)構(gòu)defineMaxSize100;de{mTypedatarent/樹中最大結(jié)點個數(shù)數(shù)組元素的類型該結(jié)點的雙親在數(shù)組中的下標PNodeTreeMaxSizeode{孩子結(jié)點hildnextstructCBNode/表頭結(jié)點{TypedataCTNodefirstchild/指向孩子鏈表的頭指針de{TypedatafirstchildderightsibElemType表示不確定的數(shù)據(jù)類型firstchild指向該結(jié)點的第一個孩子/rightsib指向該結(jié)點的右兄弟樹轉(zhuǎn)換為二叉樹8森林轉(zhuǎn)換為二叉樹二叉樹轉(zhuǎn)換為樹或森林xyx孩子、……，都與結(jié)點y用線連起來；叉樹的遍歷序列之間的對應(yīng)關(guān)系根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及樹和二叉樹遍歷的操作定義可知，樹的遍歷序列與由樹轉(zhuǎn)化成的二叉樹的遍歷序列之間具有如下對應(yīng)關(guān)系：樹的前序遍歷序列等于二叉樹的前序遍歷序列，樹的后序遍歷序列哈夫曼樹中葉子結(jié)點的權(quán)值量。二叉樹的帶權(quán)路徑長度n各個葉子結(jié)點的路徑長度與相應(yīng)葉子結(jié)點權(quán)值的乘：nWPL=wklkk=1哈夫曼樹定義給定一組具有確定權(quán)值的葉子結(jié)點，可以構(gòu)造出不同的二叉樹，將其中帶權(quán)路徑長度最小的二叉樹稱哈夫曼算法的基本思想；圖的定義無向圖與有向圖9intarcMaxSizeMaxSize//存放圖中邊的信息intarcMaxSizeMaxSize//存放圖中邊的信息簡單圖鄰接、依附無向完全圖、有向完全圖，則稱該圖為無向完全圖。含有n個頂點的無向完全圖互為相反的兩條弧，則稱該圖為有向完全圖。含有n個稠密圖、稀疏圖頂點的度、入度、出度nTD(vi)=2eennID(vi)=OD(vi)=ei=1i=1連通圖、連通分量j強連通圖、強連通分量鄰接矩陣的存儲結(jié)構(gòu)定義defineMaxSize10typedefstruct{defineMaxSize10typedefstruct{ertexertexNumarcNumertexe/圖的頂點數(shù)和邊數(shù)鄰接表的存儲結(jié)構(gòu)定義接存儲相結(jié)合的存儲方法，具體方法為：將頂點vi的所有鄰接點鏈成一個單鏈表，稱為頂點vi的邊表(對于有向圖則稱為出邊表)，邊表的頭指針和頂點的數(shù)據(jù)信息采用順序存儲 (稱為頂點表)。所以，在鄰接表中存在兩種結(jié)點：頂點表結(jié)點和邊表結(jié)點。ext邊表結(jié)點結(jié)點結(jié)構(gòu)exodejvex//定義邊表結(jié)點/鄰接點域ArcNodenext;texNode{Typevertex//定義頂點表結(jié)點//ElemType表示不確定的數(shù)據(jù)類型ArcNodefirstedge#defineMaxSize10typedefstruct{VertexNodeadjlistMaxSizetvertexNumarcNum圖的遍歷次序定義//頂點表圖的頂點數(shù)和邊數(shù)最小生成樹的定義普里姆(Prim)算法的基本思想克魯斯卡爾(Kruskal)算法的基本思想迪杰斯特拉(Dijkstra)算法的基本思想與原來的假設(shè)相比較，取路徑長度較小者為當前最短路徑。重復(fù)上述過程，直到集合V中全部頂點加入到Floyd算法的基本思想AOV網(wǎng)的定義在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂拓撲序列的定義j拓撲排序的基本思想查找算法的時間性能查找算法用關(guān)鍵碼的比較次數(shù)來度量查找算法的時間性能。對于查找成功的情況，將關(guān)鍵碼比較次數(shù)nASL=picii=1順序查找算法的時間復(fù)雜度ni順序查找的適用情況順序查找對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可應(yīng)用；對表中記錄的有序性也沒折半查找的適用情況折半查找(也稱對半查找、對分查找、二分查找)要求線性表中的記錄必須按關(guān)鍵碼有序，并且必須折半查找的基本思想比較對象，則(1)若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；(2)若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；(3)若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。折半查找的時間復(fù)雜度O(log2n)。二叉排序樹的定義：二叉排序樹的查找性能排序樹是平衡的，則其查找效率為O(log2n)。如果二叉排序樹為一棵斜樹，則其查找效率為平衡二叉樹的定義構(gòu)造平衡二叉樹的基本思想。平衡調(diào)整的四種類型散列查找的基本思想散列查找的基本概念采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表，將關(guān)鍵碼映射。散列查找的關(guān)鍵問題處理沖突的方法沖突得到的散列表叫做閉散列表。所謂開放定址法，就是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個空的散列地址，只測法H(key)=d，閉散列表的長度為m，則發(fā)生沖突時，尋找下一個散列地址的公式為：m爭奪的現(xiàn)象，稱為堆積或聚集。次探測法機探測法當發(fā)生沖突時，隨機探測法探測下一個散列地址的位移量是一個隨機數(shù)列，即尋找下一個散列地址的Hi=(H(key)+di)%m(di是一個隨機數(shù)列，i=1，2，……，m-1)拉鏈法(鏈地址法)沖突構(gòu)造的散列表叫做開散列表。拉鏈法的基本思想是：將所有散列地址相同的記錄，即所有關(guān)鍵碼為同義詞的記錄存儲在一個單鏈表直接插入排序的基本思想直接插入排序的基本思想是：依次將待排序序列中的每一個記錄插入到一個已排好序的序列中，直到直接插入排序算法的性能。希爾排序的基本思想希爾排序的基本思想是：先將整個待排序記錄序列分割成若干個子序列，在子序列內(nèi)分別進行直接插希爾排序算法的性能gnn起泡排序的基本思想的記錄為止。起泡排序算法的性能快速排序的基本思想成獨立的兩部分，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值，然后分別快速排序的性能nn簡單選擇排序的基本思想簡單選擇