考研計機(jī)數(shù)據(jù)結(jié)構(gòu)思維導(dǎo)圖一圖了解知識脈絡(luò)和考點(diǎn)

數(shù)據(jù)數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)、字符及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理的符號的集合

數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常作為一個整體進(jìn)行考慮和處理

數(shù)據(jù)對象數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集

數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱

數(shù)據(jù)類型原子類型：其值不可再分的數(shù)據(jù)類型

基本概念和術(shù)語

分類結(jié)構(gòu)類型：其值可以再分解為若干成分（分量）的數(shù)據(jù)類型

抽象數(shù)據(jù)類型：抽象數(shù)據(jù)組織及與之相關(guān)的操作

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)包括三方面存儲結(jié)構(gòu)

數(shù)據(jù)的運(yùn)算

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

與數(shù)據(jù)的存今旨無關(guān)，是獨(dú)立于計算機(jī)的

線性表

數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)笆

1.1線性結(jié)構(gòu)

隊列

分類數(shù)組

集合

非線性結(jié)構(gòu)樹

圖

存儲結(jié)構(gòu)是推號數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（又稱映像），也稱物理結(jié)構(gòu)

概述數(shù)據(jù)元素的表示和關(guān)系的表示

存儲結(jié)構(gòu)是用計算機(jī)語言實現(xiàn)的邏輯結(jié)構(gòu)，它依賴于計算機(jī)語言

把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)

順序存儲優(yōu)點(diǎn)：可以實現(xiàn)隨機(jī)存取，每個元素占用最少的存儲空間

數(shù)據(jù)的存儲結(jié)構(gòu)缺點(diǎn)：只能使用相鄰的一整塊存儲單元，因此可能產(chǎn)生較多的外部碎片

數(shù)據(jù)結(jié)構(gòu)三要素要求邏輯上相鄰的元素在物理位置上也相鄰，借助指示元素存儲地址的指針來表示元素之間的邏輯關(guān)系

鏈?zhǔn)酱鎯?yōu)點(diǎn)：不會出現(xiàn)碎片現(xiàn)象，能充分利用所有存儲單元

缺點(diǎn)：每個元素因存儲指針而占用額外的存儲空間，且只能實現(xiàn)順序存取

分類在存儲元素信息的同時，還建立附加的索引表

優(yōu)點(diǎn)：檢索速度快

索引存儲

"一附加的索引表額外占用存儲空間

缺點(diǎn)j

!增加和刪除數(shù)據(jù)時也要修改索引表，會花費(fèi)較多的時間

根據(jù)元素的關(guān)鍵字直接計算出該元素的存儲地址，又稱哈希（Hash）存儲

散列存儲優(yōu)點(diǎn)：檢索、增加和刪除結(jié)點(diǎn)的操作都很快

缺點(diǎn)：若散列函數(shù)不好，則可能出現(xiàn)元素存儲單元的沖突，而解決沖突會增加時間和空間開銷

施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實現(xiàn)。

數(shù)據(jù)的運(yùn)算運(yùn)算的定義是針對邏輯結(jié)構(gòu)的，指出運(yùn)算的功能

運(yùn)算的實現(xiàn)是針對存儲結(jié)構(gòu)的，指出運(yùn)算的具體操作步驟

算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的第條指令表示一個或多個操作

有窮性：一個算法必須執(zhí)行有窮步之后結(jié)束，且街一步都可在有窮時間內(nèi)完成

確定性：算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出

重要特性可行性:算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運(yùn)算執(zhí)行有限次來實現(xiàn)

算法的基本概念-輸入：一個苜法有零個或多個輸入，這些輸入取自于某個特定的對象的集合

輸出：一個算法有一個或多個輸出，這些輸出是與輸入有著某種特定關(guān)系的埴

正確性：算法應(yīng)能夠正確地解決求解問題.

可讀性：算法應(yīng)具有良好的可讀性，以幫助人們理解

優(yōu)秀算法的標(biāo)準(zhǔn)

1.2算法和算法評價健壯性：輸入非法數(shù)據(jù)時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果

效率與低存儲量需求：效率是指算法執(zhí)行的時間，存儲量需求是指算法執(zhí)行過程中所需要的最大存儲空間，這兩者都與問題的規(guī)模有關(guān)

算法效率的度量是通過時間復(fù)雜度和空間復(fù)雜度來描述的

一個語句的頻度是指該語句在算法中被重匏執(zhí)行的次數(shù)}一般情況下,嵌套的循環(huán)次數(shù)是時間復(fù)雜度指數(shù)(存在特殊情況)

時間復(fù)雜度-....-----------------------------------------------

一—?常見的漸近時間復(fù)雜度為

算法效率的度量算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲空間,它是問題規(guī)模n的函數(shù).

空間復(fù)雜度一個程序在執(zhí)行時除需要存儲空間來存放本身所用的指令、常數(shù)、變員和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔助空間

算法原地工作是指算法所需的輔助空間為常由，即0(1)

加法規(guī)則：0(f(n))+0(g(n))=0(max(f(n),g(n))

計算規(guī)則

乘法規(guī)則：O(f(n))xO(g(n))=0(f(n)xg(n))

線性表是具有相同數(shù)據(jù)類型的n個數(shù)據(jù)元素的有限序列，其中n為表長，當(dāng)n=0時線性表是一個空表

表中元素的個數(shù)有限

表中元素具有邏輯上的順序性，表中元素有其先后次序

線性表的特點(diǎn)

表中元素都是數(shù)據(jù)元素，每個元素都是單個元素

■線性表的定義-

每個元索占有相同大小的存儲空間

注意線性表是一種邏輯結(jié)構(gòu)，表示元素之間一對一的相鄰關(guān)系

2.1線性表的定義和基本操作1順序表和鏈表是指存儲結(jié)構(gòu)

InitList(&L):初始化表，構(gòu)造一個空的線性表

Length(L):求表長,返回線性表L的長度，即L中數(shù)據(jù)元素的個

數(shù)

LocateElem(L,e):按值查找操作，在表L中查找具有給定關(guān)鍵字值的元素

Get日em(L,i):按位查找操作，獲取表L中第i個位置的元素的值

考試盡量使用這些函數(shù)名稱,方便老師閱卷

口線性表的基本操作-Listinsert(&L,i.e):插入操作.在表L中的第i個位置上插入指定元素

刪除操作,刪除表中第個位置的元素,并用返回刪除元素的值

ListDelete(&Lfi,&e):Lie

PrintList(L):輸出操作，按前后順序輸出線性表L的所有元素值

Empty(L):判空操作，若L為空表，則返回true,否則返回false

DestroyList(&L):銷毀操作，銷毀線性表，并釋放線性表L所占用的內(nèi)存空間

線性表的順序存儲又稱順序表gH：人_至尸一加一美

汩附*國-彷*五牌降枇本山《丑-安

用m一組地址r連s續(xù)m的存e儲單兀依次存儲線性表中1的數(shù)據(jù)兀素Ir邏輯上相鄰的兩個兀素在物理位置上也相鄰

靜態(tài)分配數(shù)組的大小和空間已經(jīng)固定，一旦空間占滿，再加入新的數(shù)據(jù)將會產(chǎn)生溢出，程序就會崩潰

—維數(shù)組空間分配存儲數(shù)組的空間是在程序執(zhí)行過程中通過動態(tài)存儲分配語句分配一

的

動態(tài)分配r-------------------------------------—————

「順序表的定義~4一~|一旦數(shù)據(jù)空間占滿，就另外開辟一塊更大的存儲空間，用以替換原來的存儲空間

注意動態(tài)分配仍然是順序存儲結(jié)構(gòu)，物理結(jié)構(gòu)沒有變化，依然是隨機(jī)存取方式，只是分配的空間大小可以在運(yùn)行時決定

隨機(jī)訪問，即通過首地址和元素序號可在時間0(1)內(nèi)找到指定的元素

特點(diǎn)存儲密度高，每個結(jié)點(diǎn)只存儲數(shù)據(jù)元素與鏈表形成對比

邏輯上相鄰的元素物理上也相鄰，當(dāng)執(zhí)行播入和刪除操作時，需要移動大量元素

2.2線性表的順序表示由于順序表的中元素的物理位置是相鄰的，所以當(dāng)插入新元素的時候就需要對表中的元素進(jìn)行整體移動

,插入操作最好情況：在表尾插入(i=n+1),元素后移語句將不執(zhí)行,時間復(fù)雜度為。(1)

最壞情況：在表頭插入(i=D,元素后移語句將執(zhí)行n次，時間復(fù)雜度為0(n)

實現(xiàn)情況(長度為n)

假設(shè)pi(pi=l/(n+l))是在第i個位置上插入一個結(jié)點(diǎn)的概率

則在長度為n的線性表中插入一個結(jié)點(diǎn)時，移動節(jié)點(diǎn)的平均次數(shù)為沙屋為"T"W'+D*第或

平均情況

時間復(fù)雜度為0(2

即為移動元素，對想要刪除的元素進(jìn)行覆蓋

最好情況：刪除表尾元素(i=n),無須移動元素，時間復(fù)雜度為0(1)

順序表上基本操作的實現(xiàn)刪除操作最壞情況：刪除表頭元素(i=l),需移動除第一個元素外的所有元素，時間復(fù)雜度為0(n)

假設(shè)pi(pi=1/n)是在第i個位置上刪除一個結(jié)點(diǎn)的概率

In-(-〃----1-)---n--l--

平均情況

理生長度為n的線性表中刪強(qiáng)一個色點(diǎn)時，刪除節(jié)點(diǎn)的巴羽逍啰2上I〃〃，“n22

時間宜雜度為0(n)

最好情況:查找的元索就在表頭，僅需比較一次,時間復(fù)雜度為0(1)

最壞情況:查找的元素在表尾(或不存在)時，在要比較n次,時間復(fù)雜度為0(n)

按值查找鯉弊整L假設(shè)pi(pi=l/n)是查找的元素在第i(l<=i<=L.length)個位置上的概率

h+1

平均情況

則在長度為n的線性表中查找值為e的元素所需比較的平均次數(shù)為Mn2

時間復(fù)雜度為0(n)

優(yōu)點(diǎn)：可以隨時存取表中的任意一個元素

缺點(diǎn)：插入和刪除操作需要移動大量元素

背景3a士優(yōu)點(diǎn)：不需要使用地址連續(xù)的存儲單元，插入和刪除操作不需要移動元素，而只需修改指針

一_—J鏈?zhǔn)酱鎯€性表(

----------------------1缺點(diǎn)：失去順序表可隨機(jī)存取的優(yōu)點(diǎn)

帶頭結(jié)點(diǎn)空表判斷：L==NULL。代碼書寫不便

-實現(xiàn)方式T不帶頭結(jié)點(diǎn)空表判斷：L?>next==NULL.寫代碼更方便

線性表的鏈?zhǔn)酱鎯τ址Q單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素

對每個鏈表結(jié)點(diǎn)，除存放元素自身的信息外，還需要存放一個指向其后繼的指針

data:數(shù)據(jù)域，存放數(shù)據(jù)元素

指針域，存放其后繼結(jié)點(diǎn)的地址

單鏈表的定義---------rnext:

優(yōu)點(diǎn)解決順序表需要大量連續(xù)存儲單元的缺點(diǎn)

單鏈表附加指針域，浪費(fèi)存儲空間

2.3線性表的鏈?zhǔn)奖硎?上)-------：查找某個特定的結(jié)點(diǎn)時，需要從表頭開始遍歷，依次直找

從一個空表開始，生成新結(jié)點(diǎn)，并將讀取到的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭,即頭結(jié)點(diǎn)之后

??與次a3所指《|刈?左

,/<D

采用頭插法建立單鏈表示意圖Ld-ti-HL±I-

一、i0每個結(jié)點(diǎn)播入的時間復(fù)雜度為0(1)

時間復(fù)雜度1-------------------------------------------

「設(shè)單鏈表長為0則總時間復(fù)雜度為0(n)

優(yōu)點(diǎn)：算法實現(xiàn)簡單

缺點(diǎn)：生成的鏈表中結(jié)點(diǎn)的次序和輸入數(shù)據(jù)的順序不一致可以利用這個特點(diǎn)進(jìn)行鏈表轉(zhuǎn)置

該方法將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，為此必須增加一個尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)

區(qū)里是財明里厚—"次*3**點(diǎn)?楨呼皂匚)

示意圖'?一?3HzlZJ-IXLJ

單鏈表上基本操作的實現(xiàn)

按序號直找結(jié)點(diǎn)值時間復(fù)雜度0(n)-IAC±M.一gqHr大心大山

Ci占一M「包.臣?、卜鏈表的本身特點(diǎn)原因,查找只能依次遍歷查找

按值杳找表結(jié)點(diǎn)時間復(fù)雜度0(n)

p=GetElem(L,i-l);

實現(xiàn)代碼段s->next=p->next;

插入結(jié)點(diǎn)操作

p->next=s;

若在給定的節(jié)點(diǎn)下進(jìn)行插入，則時間復(fù)雜度為9(D

本算法主要的時間開銷在于查找第i-1個元素，時間復(fù)雜度為0(n)

即尋找到要插入結(jié)點(diǎn)的前一個結(jié)點(diǎn)，然后按照正常插入方法執(zhí)行即可

對某一結(jié)點(diǎn)進(jìn)行前插操作

時間復(fù)雜度為O(n)

刪除結(jié)點(diǎn)操作是將單鏈表的第1個結(jié)點(diǎn)刪除。先檢查刪除位置的合法性,后直找表中第1-1個結(jié)點(diǎn)，即被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，再將其刪除

刪除結(jié)點(diǎn)操作-------1；?t_.;??-c?t—

示意圖

該算法￡.一...........L

單鏈表上基本操作的實現(xiàn)

:_