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

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