02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論**重點(diǎn)

時(shí)間：2021-03-10作者：山東博信教育科技有限公司瀏覽：78

**章    概論




算法+數(shù)據(jù)結(jié)構(gòu)=程序

從宏觀上看，數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)實(shí)際上反映了數(shù)據(jù)組織的三個(gè)層次，數(shù)據(jù)可由若干個(gè)數(shù)據(jù)   元素組成，而數(shù)據(jù)元素又可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。

集合中任意兩個(gè)結(jié)點(diǎn)之間都沒(méi)有鄰接關(guān)系，組織形式松散；

線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鏈”，結(jié)點(diǎn)之間一個(gè)一個(gè)依次相鄰接；

樹(shù)形結(jié)構(gòu)具有分支、層次特性，其形態(tài)像自然界中的樹(shù)，上層的結(jié)點(diǎn)可以和下層多個(gè)結(jié)點(diǎn)相   鄰接，但下層結(jié)點(diǎn)只能和上層的一個(gè)結(jié)點(diǎn)相鄰接；

圖結(jié)構(gòu)較復(fù)雜，其中任何兩個(gè)結(jié)點(diǎn)都可以相鄰接。




*二章    線性表




線性表（Linear List）是一種線性結(jié)構(gòu)，它是由 n（n>0）個(gè)數(shù)據(jù)元素組成的有窮序列。

線性表的順序存儲(chǔ)：將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組連續(xù)的存儲(chǔ)單元中，一般使用數(shù)   組來(lái)表示順序表。

順序表的插入與刪除：元素的移動(dòng)次數(shù)不僅與順序表的長(zhǎng)度 n 有關(guān)，還與插入的位置 i 有關(guān)。

線性表的鏈接存儲(chǔ)：各個(gè)結(jié)點(diǎn)在內(nèi)存中的存儲(chǔ)位置并不一定連續(xù)，可存放在內(nèi)存的不同位置。   5.單鏈表的插入：p->next=q->next 和 q->next=p 兩條語(yǔ)句的執(zhí)行順序不能顛倒。

6 單鏈表上的刪除：p=q->next;Q->next=p->next;free (p); 7.雙向循環(huán)鏈表的刪除：

（1）p->prior->next=p->next;    //p 前驅(qū)結(jié)點(diǎn)的后鏈指向 p 的后繼結(jié)點(diǎn)

（2）p->next->prior=p->prior;   //p 后繼結(jié)點(diǎn)的前鏈指向 p 的前驅(qū)結(jié)點(diǎn)

（3）free (p) ;    '    //釋放的空間8.雙向循環(huán)鏈表的插入：

（1）t 一〉prior=p;

（2）t->next=p->next；

（3）p->next->prior=t；

（4）p->next=t；




*三章    棧、隊(duì)列和數(shù)組




棧的概念：棧是運(yùn)算受限的線性表，這種線性表上的插入和刪除運(yùn)算限定在表的某一端進(jìn)行。允   許進(jìn)行插入和刪除的一端稱為棧**，另一端稱為棧底。不含任何數(shù)據(jù)元素的棧稱為空棧。處于棧**位   置的數(shù)據(jù)元素稱為棧**元素。

棧的運(yùn)算特點(diǎn)：后進(jìn)先出。

棧的插入和刪除操作分別稱為進(jìn)棧和出棧。

雙棧滿的條件：top1+1=top2（假設(shè) top1<top2） 5.棧的簡(jiǎn)單應(yīng)用與遞歸：函數(shù)調(diào)用應(yīng)用棧

順序隊(duì)列的入隊(duì)操作：SQ.rear=SQ.rear+1;SQ.data[SQ.rear]=x;

出隊(duì)操作：SQ.front=SQ.front+1;

循環(huán)隊(duì)列的入隊(duì)操作：SQ.rear=(SQ.rear+1)%maxsize;SQ.data[SQ.rear]=x;

出隊(duì)操作：SQ.front=(SQ.front+1)%maxsize;

循環(huán)隊(duì)列滿條件：（（CQ.rear+1）%maxsize==CQ.front）成立隊(duì)列空條件：（CQ.rear==CQ.front）成立

矩陣的壓縮存儲(chǔ)：針對(duì)一些有許多值相同的元素或零元素的高階矩陣，為了節(jié)省空間，對(duì)這類(lèi)矩陣采用多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，零元素不存儲(chǔ)的策略，這一方法稱為矩陣的壓縮存儲(chǔ)。

特殊矩陣：n 階的對(duì)稱矩陣和三角矩陣占用存儲(chǔ)空間大小為：

（1）對(duì)稱矩陣。若一個(gè) n 階方陣 A 中的元素滿足下述條件：n(n+1)/2 11.稀疏矩陣的三元組表示法：

（i,j,a_ij）,i 表示行序號(hào)，j 表示列序號(hào)，a_ij 是非零元素的值。




*四章    樹(shù)和二叉樹(shù)




樹(shù)的概念：可為空，若不空，左右子樹(shù)互不相交。

葉子：度為 0 的結(jié)點(diǎn)

二叉樹(shù)的概念：二叉樹(shù)(Binary Tree)是 n(n≥0)個(gè)元素的有限集合，該集合或者為空，或者由一個(gè)根及兩棵互不相交的左子樹(shù)和右子樹(shù)組成，其中左子樹(shù)和右子樹(shù)也均為二叉樹(shù)。

二叉樹(shù)的性質(zhì)：

二叉樹(shù)* i（i≥1）層上至多有 2i?1 個(gè)結(jié)點(diǎn)。

深度為 k（k≥1）的二叉樹(shù)至多有 2k ?1 個(gè)結(jié)點(diǎn)。

對(duì)任何一棵二叉樹(shù)，若度數(shù)為 0 的結(jié)點(diǎn)（葉結(jié)點(diǎn)）個(gè)數(shù)為 n₀，度數(shù)為 2 的結(jié)點(diǎn)個(gè)數(shù)為 n₂，則n₀=n₂+1。

含有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 ??log2n?? +1。

完全二叉樹(shù)結(jié)點(diǎn)編號(hào)關(guān)系：編號(hào) i 的雙親為?i / 2? ，左孩子為 2*i，右孩子為 2*i+1

二叉樹(shù)的順序存儲(chǔ)：用一維數(shù)組來(lái)實(shí)現(xiàn)。對(duì)非完全二叉樹(shù)不成立。如果需要順序存儲(chǔ)非完全二叉   樹(shù)，首先必須將其轉(zhuǎn)化為完全二叉樹(shù)，可增設(shè)若干個(gè)虛擬結(jié)點(diǎn)。但這種方法造成了空間的浪費(fèi)。

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)：二叉樹(shù)有不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其中較常用的是二叉鏈表與三叉鏈表。

每個(gè)二叉鏈表還必須有一個(gè)指向根結(jié)點(diǎn)的指針，該指針?lè)Q為根指針。對(duì)二叉鏈表的訪問(wèn)只能從根   指針開(kāi)始。

二叉樹(shù)遍歷的遞歸實(shí)現(xiàn)：

先序遍歷：根-左-右

中序遍歷：左-根-右

后序遍歷：左-右-根

二叉樹(shù)的層次遍歷：二叉樹(shù)的層次遍歷是指從二叉樹(shù)根結(jié)點(diǎn)的這一層開(kāi)始，逐層向下遍歷，在每   一層上按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。層次遍歷可用隊(duì)列來(lái)實(shí)現(xiàn)。

樹(shù)的存儲(chǔ)結(jié)構(gòu)：

（1）孩子鏈表表示法；（2）帶雙親的孩子鏈表表示法。；（3）孩子兄弟鏈表；（4）雙親表示法。   孩子兄弟鏈表的結(jié)構(gòu)形式與二叉鏈表完全相同，但結(jié)點(diǎn)中指針的含義不同。

樹(shù)、二叉樹(shù)、森林的關(guān)系：

樹(shù)（森林）轉(zhuǎn)化成二叉樹(shù)：①左孩子=左孩子；②兄弟=右孩子。

二叉樹(shù)轉(zhuǎn)換成樹(shù)（森林）：①左孩子=左孩子；②右孩子=兄弟。

森林的遍歷：

森林有兩種遍歷方法：先序遍歷和中序遍歷

對(duì)森林轉(zhuǎn)換成的二叉樹(shù)分別進(jìn)行先序遍歷和中序遍歷，可以分別得到與該森林的先序序列和中序   序列相同的序列。

分類(lèi)與判定樹(shù)：用于描述分類(lèi)過(guò)程的二叉樹(shù)稱為判定樹(shù)。

哈夫曼樹(shù)的構(gòu)造：兩個(gè)較小的結(jié)點(diǎn)構(gòu)造新結(jié)點(diǎn)。   n 個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)共有 2n-1 個(gè)結(jié)點(diǎn)。

哈夫曼編碼：左 0 右 1




*五章    圖




任何兩點(diǎn)之間都有邊的無(wú)向圖稱為無(wú)向完全圖。一個(gè)具有 n 個(gè)**點(diǎn)的無(wú)向完全圖的邊數(shù)為C2 =n?n-1?/2 。任何兩點(diǎn)之間都有弧的有向圖稱為有向完全圖。一個(gè)具有 n 個(gè)**點(diǎn)的有向完全圖的弧數(shù)為P2 =n?n-1? 。

含有 n 個(gè)結(jié)點(diǎn)的圖的生成樹(shù)的邊的數(shù)目一定為 n-1，若大于，說(shuō)明有環(huán)。

圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣：無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱矩陣。

鄰接表：有向圖鄰接表的表長(zhǎng)等于點(diǎn)的出度，逆鄰接表的表長(zhǎng)等于點(diǎn)的入度。

圖的遍歷：遍歷圖的基本方法有兩種：深度**搜索和廣度**搜索。

連通圖的深度**搜索：深度**搜索遍歷類(lèi)似于樹(shù)的先序遍歷。（注意：可回退）

連通圖的廣度**搜索：廣度**搜索遍歷類(lèi)似于樹(shù)的按層次遍歷的過(guò)程。

圖的應(yīng)用：

較小生成樹(shù)

①較小生成樹(shù)的概念：一個(gè)圖的較小生成樹(shù)是圖所有生成樹(shù)中權(quán)總和較小的生成樹(shù)。

②構(gòu)造較小生成樹(shù)的 Prim 算法：從一個(gè)**點(diǎn)出發(fā)添加權(quán)值小的邊。

③構(gòu)造較小生成樹(shù)的克魯斯卡爾（Kruskal）方法：從多有邊當(dāng)中選擇權(quán)值較小的邊。

單源較短路徑（Dijkstra 算法）

拓?fù)渑判颍?/span>

前提條件：完成拓?fù)渑判虻那疤釛l件是 AOV 網(wǎng)中不允許出現(xiàn)回路。步驟：

圖中選擇一個(gè)入度為 0 的**點(diǎn)，輸出該**點(diǎn)；

從圖中刪除該**點(diǎn)及其相關(guān)聯(lián)的弧，調(diào)整被刪弧的弧頭結(jié)點(diǎn)的入度(入度減 1);

重復(fù)執(zhí)行(1)、(2)直到所有入度為 0 的**點(diǎn)均被輸出，拓?fù)渑判蛲瓿?，或者圖中再也沒(méi)有入度

為 0 的**點(diǎn)。








山東博信教育科技有限公司專注于山東**專業(yè),山東**院校,山東**網(wǎng)課,山東**報(bào)名,山東成人*報(bào)名,山東*培訓(xùn)等

• 詞條

  詞條說(shuō)明

• **報(bào)名可以選擇山東**網(wǎng)課嗎？

  **報(bào)名可以選擇山東**網(wǎng)課嗎？許多人為了提升*都會(huì)積極的在互聯(lián)網(wǎng)上搜索各類(lèi)相關(guān)的咨詢，其中近年來(lái)提升*的方式有很多種，主要涵蓋了*、成人*和***，其中全日制*限制條件比較多，已經(jīng)離開(kāi)學(xué)校的人已經(jīng)喪失了報(bào)名的資格，其次，在這其中**較高的當(dāng)屬***了。不過(guò)許多朋友對(duì)于**的了解卻不多，很多學(xué)生也會(huì)有著這樣或那樣的疑問(wèn)，卓匯教育根據(jù)**生所提出的問(wèn)題進(jìn)行了詳細(xì)的整理和分析，發(fā)現(xiàn)

• 山東**院?？寄膫€(gè)院校哪個(gè)專業(yè)好？

  山東**院?？寄膫€(gè)院校哪個(gè)專業(yè)好？一、山東財(cái)經(jīng)大學(xué)山東財(cái)經(jīng)大學(xué)是財(cái)政部、教育部、山東省共建高校，坐落于享有泉城美譽(yù)的國(guó)家歷史文化名城——濟(jì)南，是一所辦*史悠久、辦學(xué)規(guī)模較大、辦學(xué)特色鮮明，以經(jīng)濟(jì)學(xué)和管理學(xué)學(xué)科為主，兼有文、法、理、工、教育、藝術(shù)八大學(xué)科門(mén)類(lèi)，在國(guó)內(nèi)外具有較高聲譽(yù)和**度的財(cái)經(jīng)類(lèi)大學(xué)。二、會(huì)展經(jīng)濟(jì)與管理專業(yè)的優(yōu)勢(shì)1、課程量少，學(xué)制短：本科段僅12門(mén)課程，專本套讀三年即可獲得國(guó)家承認(rèn)

• 什么是全日制本科助學(xué)班？和**的區(qū)別是？

  全日制本科助學(xué)班【1】什么是全日制本科助學(xué)班？很多**考生可能都會(huì)聽(tīng)說(shuō)全日制本科科助學(xué)班，特別是“全日制**本科”這幾個(gè)詞語(yǔ)，就已經(jīng)讓很多**生都非常想了解一下，那么這個(gè)名字聽(tīng)起來(lái)非常高大上的助學(xué)班到底是什么呢？全日制本科助學(xué)班也叫“助學(xué)班”，簡(jiǎn)單來(lái)說(shuō)就是國(guó)家教育部門(mén)批準(zhǔn)，有開(kāi)班資格的普通高等學(xué)校，利用自身的富余資源——師資力量、教學(xué)環(huán)境、成熟的辦學(xué)招生體制、規(guī)范合理的管理，建立區(qū)別于全日制本科生

• 【山東成人*報(bào)名】成人*違紀(jì)處理

  作弊行為根據(jù)國(guó)家教育部《國(guó)家教育考試違規(guī)處理辦法》中有關(guān)規(guī)定，考生不遵守考場(chǎng)紀(jì)律，不服從考試工作人員的安排與要求，有下列行為之一的，應(yīng)當(dāng)認(rèn)定為考試違紀(jì)，根據(jù)規(guī)定將取消該科目的考試成績(jī)：（1）攜帶規(guī)定以外的物品進(jìn)入考場(chǎng)或者未放在*位置的；（2）未在規(guī)定的座位參加考試的；（3）考試開(kāi)始信號(hào)發(fā)出前答題或者考試結(jié)束信號(hào)發(fā)出后繼續(xù)答題的；（4）在考試過(guò)程中旁窺、交頭接耳、互打暗號(hào)或者手勢(shì)的；（5）在考場(chǎng)或