柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)（C語言版）

http://yzkb.51969.com/

第一章? ? ? ? 緒論

1.2? ? ? ? 基本概念和術(shù)語

數(shù)據(jù)：所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱

數(shù)據(jù)元素：數(shù)據(jù)的基本單位，一個數(shù)據(jù)元素有若干個數(shù)據(jù)項(xiàng)組成

一本書的書目信息為數(shù)據(jù)元素，書目信息中的每一項(xiàng)（如書名，作者名等）為一個數(shù)據(jù)項(xiàng)

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

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

結(jié)構(gòu)：數(shù)據(jù)之間存在的各種關(guān)系

集合：除同屬于一個集合外，無關(guān)系線性結(jié)構(gòu)：一對一樹形結(jié)構(gòu)：一對多網(wǎng)狀結(jié)構(gòu)或圖狀結(jié)構(gòu)：多對多

邏輯結(jié)構(gòu)：結(jié)構(gòu)定義中的“關(guān)系”描述的是數(shù)據(jù)元素之間的邏輯關(guān)系

物理結(jié)構(gòu)（存儲結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）

計(jì)算機(jī)中表示信息的最小單位是二進(jìn)制中的一位，叫做位

用一個由若干位組合起來形成的一個位串表示一個數(shù)據(jù)元素，稱這個位串為元素或結(jié)點(diǎn)

當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時，位串中對應(yīng)于各個數(shù)據(jù)項(xiàng)的子位串成為數(shù)據(jù)域

順序映像特點(diǎn)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系

元素之間位置相對固定

非順序映像的特點(diǎn)是借助元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系

用指針找位置

數(shù)據(jù)類型：是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，是一個值的集合和定義在這個值集上的一組操作的集合

非結(jié)構(gòu)的原子類型：原子類型的值不可分解結(jié)構(gòu)類型：值是由若干成分按某種結(jié)構(gòu)組成的，是可以分解的，成分為非結(jié)構(gòu)或結(jié)構(gòu)

抽象數(shù)據(jù)類型（ADT）：指一個數(shù)學(xué)模型以及定義在該模型上的一組操作，其定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，只要數(shù)學(xué)特性不變，都不影響其外部的使用

基本操作的定義格式：

基本操作名（參數(shù)表）

? ? ? ? 初始條件：<初始條件描述>

? ? ? ? 操作結(jié)果：<操作結(jié)果描述>

基本操作有兩種參數(shù)：

賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供參數(shù)值外，還將返回操作結(jié)果；&-->引用參數(shù)? /??返回結(jié)果

初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息操作結(jié)果：說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之

第二章? ? ? ? 線性表

2.1????????線性表的類型定義

線性結(jié)構(gòu)的特點(diǎn)是：在數(shù)據(jù)元素的非空有限集中，

存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個元素均只有一個前驅(qū)除最后一個外，集合中的每個元素均只有一個后繼

線性表：最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)，即一個線性表是n個數(shù)據(jù)元素的有限序列

在稍復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(xiàng)組成，在這種情況下，數(shù)據(jù)元素被稱為記錄，含有大量記錄的線性表又稱為文件同一線性表中的元素必定由相同的特性，即屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。線性表索引從1開始線性表中元素的個數(shù)n(n>=0)定義為線性表的長度，n=0時稱為空表線性表中的元素有序排列，可以提高歸并算法的時間效率

抽象數(shù)據(jù)類型線性表見書P19

2.2????????線性表的順序表示和實(shí)現(xiàn)

線性表的順序：

指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素特點(diǎn)是，為表中相鄰的元素賦以相鄰的存儲位置，相鄰元素位置相鄰線性表中的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)

假設(shè)線性表的每個元素需占用L個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i + 1個數(shù)據(jù)元素的存儲位置LOC(a[i+1])和第i個數(shù)據(jù)元素的存儲位置LOC[a(i)]之間滿足下列關(guān)系：

LOC(a[i+1]) = LOC(a[i]) + L

一般來說，線性表的第i個數(shù)據(jù)元素a(i)的存儲位置為：

LOC(a[i]) = LOC(a[1]) + (i-1)L

LOC(a[1])是線性表的第一個數(shù)據(jù)元素a[1]的存儲位置，通常稱為線性表的起始位置或基地址

線性表的插入：

一般情況下，在第 i (1<= i <= n)個元素之前插入一個元素時，需將第 n?至第 i (共n-i+1)個元素向后移動一個位置

線性表的刪除：

一般情況下，刪除第? i?個元素時需要將從第 i + 1?至第 n?個元素依次向前移動一個位置

2.3? ? ? ? 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

線性鏈表

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素結(jié)點(diǎn)包括兩個域，其中存儲的信息稱為數(shù)據(jù)域；存儲直接后繼存儲位置的域稱為指針域

指針域中存儲的信息稱為指針或鏈，n個結(jié)點(diǎn)鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。又由于此鏈表的每個結(jié)點(diǎn)中只包含一個指針域，故又稱線性鏈表或單鏈表

線性表的線性鏈?zhǔn)酱鎯Y(jié)構(gòu)，整個鏈表的存取必須從頭指針開始進(jìn)行，頭指針指示鏈表中第一個結(jié)點(diǎn)（即第一個數(shù)據(jù)元素的存儲映像）的存儲位置。同時，由于最后一個數(shù)據(jù)元素沒有直接后繼，則線性鏈表中最后一個結(jié)點(diǎn)的指針為空用線性鏈表表示線性表時，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的單鏈表可由頭指針唯一確定（頭指針:指向鏈表中第一個結(jié)點(diǎn)）若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)榭諉捂湵碇?，任何兩個元素的存儲位置之間沒有固定的聯(lián)系，單鏈表是非隨機(jī)存取的存儲結(jié)構(gòu)

線性表的插入與刪除

線性表的插入:

在a,b兩結(jié)點(diǎn)中插入數(shù)據(jù)元素x，首先生成一個數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，

然后實(shí)現(xiàn),假設(shè)s為指向結(jié)點(diǎn)x的指針：

s -> next = p -> next;

p -> next = s;

線性表的刪除：

僅需修改結(jié)點(diǎn)a中的指針域：

p -> next = p -> next -> next;

在已知鏈表中元素插入或刪除的確切位置的情況下，在單鏈表中插入或刪除一個結(jié)點(diǎn)時，僅需修改指針而不需要移動元素

c語言中的標(biāo)準(zhǔn)函數(shù)malloc：

malloc函數(shù)（全稱memory allocation函數(shù)），是C語言中進(jìn)行內(nèi)存動態(tài)分配的標(biāo)準(zhǔn)庫函數(shù)，中文叫動態(tài)內(nèi)存分配，用于申請一塊連續(xù)的指定大小的內(nèi)存塊區(qū)域以void*類型返回分配的內(nèi)存區(qū)域地址。

使用malloc函數(shù)，如果分配成功則返回指向被分配內(nèi)存的指針（此存儲區(qū)中的初始值不確定），否則返回空指針NULL。

在c語言中，線性鏈表可用結(jié)構(gòu)指針描述結(jié)點(diǎn)：

數(shù)據(jù) +?下一個元素的位置（指針）。還可用數(shù)組的一個元素表示一個結(jié)點(diǎn)：數(shù)據(jù) +?下一個元素的位置（數(shù)組下標(biāo)）

靜態(tài)列表

靜態(tài)列表：用一維數(shù)組來描述線性列表

靜態(tài)列表（與順序表有兩點(diǎn)不同）：

每個元素包括數(shù)據(jù)域和指針域邏輯上相鄰的數(shù)據(jù)元素存儲位置可不相鄰

循環(huán)列表

循環(huán)列表：是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。特點(diǎn)：表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個鏈表形成一個環(huán)。由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中的其他結(jié)點(diǎn)。循環(huán)鏈表的操作和線性表基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next?是否為空，而是它們是否等于頭指針。尾結(jié)點(diǎn)p滿足：p->next ==head

雙向列表：在雙向列表的結(jié)點(diǎn)中有兩個指針域，其一指向直接后繼，另一指向直接前驅(qū)

對于雙向列表，在兩結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)，需要修改共4個指針

有序鏈表的基本操作定義與線性鏈表有兩處不同：

LocateElem的職能不同需增加按有序關(guān)系進(jìn)行插入的操作OrderInsert

第三章? ? ? ? 棧和隊(duì)列

棧

抽象數(shù)據(jù)類型棧的定義：

棧（又稱后進(jìn)先出的線性表）：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。

對棧來說，表尾端有特殊含義，稱為棧頂；表頭端稱為棧底；不含元素的空表稱為空棧；

允許插入和刪除的一端稱為棧頂；另一端稱為棧底

棧的基本操作除了在棧頂進(jìn)行插入和刪除之外，還有棧的初始化，判空及取頂元素等

棧的表現(xiàn)和形式：

順序棧，即棧的順序存儲結(jié)構(gòu)是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針 top?指示棧頂元素在順序棧中的位置鏈棧：

采用單鏈表來存儲棧中的元素只在鏈表頭部進(jìn)行插入和刪除，不必設(shè)頭結(jié)點(diǎn)鏈表的頭指針就是棧頂指針

表達(dá)式求值：

任何一個表達(dá)式都是由操作數(shù)，運(yùn)算符和界限符組成的，稱它們?yōu)閱卧~。一般地，操作數(shù)既可以是常數(shù)也可以是被說明為變量或常量的標(biāo)識符；運(yùn)算符可以分為算術(shù)運(yùn)算符，關(guān)系運(yùn)算符和邏輯運(yùn)算符3類；基本界限符有左右括號和表達(dá)式結(jié)束符等

OPTR--用以寄存運(yùn)算符；OPND--用以寄存操作數(shù)或運(yùn)算結(jié)果

算法的基本思想是：

首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧的棧底元素依次讀入表達(dá)式中每個字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達(dá)式求值完畢

棧與遞歸的實(shí)現(xiàn)

遞歸函數(shù)：一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)

迭代：通過某段代碼的重復(fù)執(zhí)行來實(shí)現(xiàn)循環(huán)

遞歸：通過重復(fù)調(diào)用函數(shù)自身來實(shí)現(xiàn)循環(huán)

通常，當(dāng)在一個函數(shù)的運(yùn)行期間調(diào)用另一個函數(shù)時，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需完成：

將所有的實(shí)在參數(shù)，返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口。

從背調(diào)函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)應(yīng)完成；

保存被調(diào)函數(shù)的計(jì)算結(jié)果；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)

當(dāng)有多個函數(shù)構(gòu)成嵌套調(diào)用時，按照“后調(diào)用先返回”的原則

隊(duì)列

抽象數(shù)據(jù)類型隊(duì)列的定義

隊(duì)列是一種先進(jìn)先出的線性表。只允許在表的一端進(jìn)行插入，而在另一端刪除元素在隊(duì)列中，允許插入的一端叫做隊(duì)尾；允許刪除的一端則稱為隊(duì)頭空隊(duì)：不包含元素的空表隊(duì)列中元素的插入和刪除操作分別稱為入隊(duì)和出隊(duì)雙端隊(duì)列：一種限定性數(shù)據(jù)結(jié)構(gòu)。是限定插入和刪除操作在表的兩端進(jìn)行的線性表超隊(duì)列：刪除一端，插入兩端超棧：插入一端，刪除兩端雙棧：那端插入的只能從該端刪除

鏈隊(duì)列——隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

鏈隊(duì)列：用鏈表表示的隊(duì)列一個鏈隊(duì)列顯然需要兩個分別指示隊(duì)頭和隊(duì)尾的指針（分別稱為頭指針和尾指針）才能唯一確定。為方便操作，給鏈隊(duì)列添加一個頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)。由此，空的鏈隊(duì)列的判決條件為頭指針和尾指針均指向頭結(jié)點(diǎn)鏈隊(duì)列的操作即為單鏈表的插入和刪除操作等特殊情況，只是尚需修改尾指針或頭指針。即，鏈隊(duì)列的插入刪除操作只需修改頭尾指針

循環(huán)隊(duì)列——隊(duì)列的順序表示和實(shí)現(xiàn)

在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個指針front?和rear?分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置初始化鍵空隊(duì)列時，令front =?rear =0,每當(dāng)插入新的隊(duì)列尾元素時，“尾指針增+1”；每當(dāng)刪除隊(duì)列頭元素時，“頭指針+1”在非空隊(duì)列中，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個位置有一循環(huán)隊(duì)列Q，只憑Q.front = Q.rear?無法判別隊(duì)列空間是“滿”還是“空”。處理方法有：

另設(shè)一個標(biāo)志位以區(qū)別隊(duì)列是“空”還是“滿”；少用一個元素空間，約定以“隊(duì)列頭指針在隊(duì)列尾指針的下一位置（指環(huán)狀的下一位置）上”作為隊(duì)列呈“滿”狀態(tài)的標(biāo)志

第四章? ? ? ? 串

串類型的定義

串（字符串）：是由零個或多個字符組成的有限序列? ? ? ? 如：S = 'a1a2a3...an'（n>0）

其中S是串的名，用單引號括起來的字符序列是串的值，值可以是字母，數(shù)字或其他字符；

串中字符的數(shù)目n稱為串的長度。零個字符的串稱為空串，長度為零

串中任意個連續(xù)字符組成的子序列稱為該串的字串。包含子串的串相應(yīng)地稱為主串。通常稱字符在序列中的序號為該字符在串中的位置。子串在主串中的位置則以子串的第一個字符在主串中的位置來表示當(dāng)且僅當(dāng)兩個串的值相等時，稱這兩個串是相等的串值必須用一對單括號括起來，但單括號本身不屬于串，它的作用只是為了避免與變量名或數(shù)的常量混淆而已由一個或多個空格組成的串稱為空格串

串的表示和實(shí)現(xiàn)

定長順序存儲表示

串的順序表示：用一組地址連續(xù)的存儲單元存儲串值的字符序列。在串的定長順序存儲結(jié)構(gòu)中，按照預(yù)定義的大小，為每個定義的串變量分派一個固定長度的存儲區(qū)超過預(yù)定長度的串值則被舍去，稱之為截?cái)鄬Υ袃煞N表示方式：

以下標(biāo)為0的數(shù)組分量存放串的實(shí)際長度在串值后面加一個不計(jì)入串長的結(jié)束標(biāo)記字符

（1）串聯(lián)名Contact（&T,S1,S2）

T的前一段和串S1的值相等，串T的值的后一段和S2的值相等?；诖甋1和S2長度的不同情況，串T值的產(chǎn)生可能有如下3種情況：

①S1[0]+S2[0]<=MAXSTRIEN,得到的串T是正確的結(jié)果；

②S1[0]MAXSTRLEN,則將串S2的一部分截?cái)?，得到的串T只包含串S2的一個子串；

③S1[0]=MAXSTRLEN，則得到的串T并非聯(lián)接結(jié)果，而和串S1相等

（2）求子串SubString（&Sub,S,pos,len）

求子串的過程即復(fù)制字符序列的過程，將串中從第pos個字符開始長度為len的字符序列復(fù)制到串Sub中。無截?cái)?，但要檢驗(yàn)用戶給出的參數(shù)是否符合操作的初始條件

在順序存儲結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為“字符序列的復(fù)制”，操作的時間復(fù)雜度基于復(fù)制的字符序列的長度

堆分配存儲表示

特點(diǎn)：仍以一組地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序過程中動態(tài)分配而得。在C語言中，存在一個稱為“堆”的自由存儲區(qū)，并由C語言的動態(tài)分配函數(shù)malloc（）和free（）來管理。利用函數(shù)malloc（）為每個新產(chǎn)生的?串分配一塊實(shí)際串長所需的存儲空間，若分配成功，則返回一個指向起始地址的指針，作為串的基址

串的快鏈存儲表示

塊鏈：用單鏈表示存儲結(jié)構(gòu)每個結(jié)點(diǎn)可以存放一個字符，也可以存放多個字符當(dāng)結(jié)點(diǎn)大小大于1時，由于串不一定是結(jié)點(diǎn)大小的整數(shù)倍，則鏈表中的最后一個結(jié)點(diǎn)不一定全被串值占滿，此時通常補(bǔ)上“#”或其他的非串值字符（通?！?”不屬于串的字符集，是一個特殊的符號）由于一般情況下，

柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu)（C語言版）

http://yzkb.51969.com/

相關(guān)鏈接