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

時間：2021-03-10作者：山東博信教育科技有限公司瀏覽：66

**章    概論




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

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

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

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

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

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

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




*二章    線性表




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

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

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

線性表的鏈接存儲：各個結(jié)點(diǎn)在內(nèi)存中的存儲位置并不一定連續(xù)，可存放在內(nèi)存的不同位置。   5.單鏈表的插入：p->next=q->next 和 q->next=p 兩條語句的執(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.棧的簡單應(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）成立

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

特殊矩陣：n 階的對稱矩陣和三角矩陣占用存儲空間大小為：

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

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




*四章    樹和二叉樹




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

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

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

二叉樹的性質(zhì)：

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

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

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

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

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

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

二叉樹的鏈?zhǔn)酱鎯Γ憾鏄溆胁煌逆準(zhǔn)酱鎯Y(jié)構(gòu)，其中較常用的是二叉鏈表與三叉鏈表。

每個二叉鏈表還必須有一個指向根結(jié)點(diǎn)的指針，該指針稱為根指針。對二叉鏈表的訪問只能從根   指針開始。

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

先序遍歷：根-左-右

中序遍歷：左-根-右

后序遍歷：左-右-根

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

樹的存儲結(jié)構(gòu)：

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

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

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

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

森林的遍歷：

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

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

分類與判定樹：用于描述分類過程的二叉樹稱為判定樹。

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

哈夫曼編碼：左 0 右 1




*五章    圖




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

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

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

鄰接矩陣：無向圖的鄰接矩陣是一個對稱矩陣。

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

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

連通圖的深度**搜索：深度**搜索遍歷類似于樹的先序遍歷。（注意：可回退）

連通圖的廣度**搜索：廣度**搜索遍歷類似于樹的按層次遍歷的過程。

圖的應(yīng)用：

較小生成樹

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

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

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

單源較短路徑（Dijkstra 算法）

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

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

圖中選擇一個入度為 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ù)渑判蛲瓿?，或者圖中再也沒有入度

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








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

• 詞條

  詞條說明

• 秘書學(xué)專業(yè)簡介

  ?秘書學(xué)專業(yè)簡介：?1、秘書學(xué)專業(yè)培養(yǎng)培養(yǎng)企事業(yè)單位和其他社會組織中全面協(xié)助**工作的高層次秘書人才。 2、秘書學(xué)專業(yè)主要課程 ?秘書學(xué)，文書學(xué)，公共關(guān)系學(xué)，社會心理學(xué)，教育學(xué)，行政管理學(xué)，傳播學(xué)，管理學(xué)概論，檔案與信息管理，寫作，現(xiàn)代漢語，中國文化概論，中國古代文學(xué)作品選讀，中國現(xiàn)當(dāng)代文學(xué)作品選讀，中國通史，辦公自動化，會計(jì)學(xué)原理，市場營銷，計(jì)算機(jī)基礎(chǔ)與應(yīng)用，計(jì)算機(jī)

• 【山東**報(bào)名】**報(bào)名的過程

  **報(bào)名的過程1、**考試有*、年齡、時間限制嗎？沒有。這也是**有別于其他教育形式的特點(diǎn)之一。**是一種國家考試、社會助學(xué)、個人*三者相結(jié)合的考試制度。參加**的人不受年齡、性別、已有*、職業(yè)（特殊專業(yè)除外）、民族、居住區(qū)域、身體條件等限制。而且目前國內(nèi)大部分地區(qū)都沒有限制**的時間（只有少數(shù)地區(qū)有**8年內(nèi)必須考完的限制，具體政策請咨詢當(dāng)?shù)?*辦）。2、國家承認(rèn)**的

• **：*者如何安排學(xué)習(xí)時間

  對于利用業(yè)余時間學(xué)習(xí)的**考生，如何來合理規(guī)劃學(xué)習(xí)時間呢？對于**中的上班族來說，學(xué)習(xí)時間的安排也成了一件頭疼的事情：白天工作了一天，晚上回去已經(jīng)很累了，沒有了看書的精力，慢慢的接近考試了，要考的幾門課一點(diǎn)都沒復(fù)習(xí)，今天我們來聊聊上班族如何安排**學(xué)習(xí)時間。一、根據(jù)自己時間多少選擇報(bào)考科目計(jì)劃要從你開始報(bào)考那一天就開始做，比如：要報(bào)考4月份考試了，先看看自己現(xiàn)在到4月份的工作計(jì)劃，空余時間是否多，

• 00533《中國古代文學(xué)作品選》（二）**重點(diǎn)

  《中國古代文學(xué)作品選》（二）精簡白皮書宋代部分知識點(diǎn) 001：柳永一、柳永：北宋**個專力寫詞的作家。以鋪敘見長，以口語、俗語入詞，慢詞?！稑氛录?。二、《雨霖鈴》（寒蟬凄切）寫離情別緒。以秋天為背景。藝術(shù)特點(diǎn)：（1）全詞圍繞“傷離別”來構(gòu)思，層次清晰。可分三層：上片五句到“留戀處、蘭舟催發(fā)”寫別前留戀，“執(zhí)手相看”四句寫別時傷感，下片都寫別后想象。既有眼前的實(shí)景，又有想象的虛景，虛實(shí)相間，層層推