《數(shù)據(jù)結(jié)構(gòu)》知識(shí)點(diǎn)總結(jié)

1、數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概括數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概括第一章第一章概論數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)結(jié)構(gòu)的定義：邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。線性結(jié)構(gòu)：一對(duì)一關(guān)系。線性結(jié)構(gòu)：多對(duì)多關(guān)系。存儲(chǔ)結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：如鏈表。索引存儲(chǔ)結(jié)構(gòu)：稠密索引：每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。稀疏索引：每

2、組結(jié)點(diǎn)都有索引項(xiàng)。散列存儲(chǔ)結(jié)構(gòu)：如散列表。數(shù)據(jù)運(yùn)算。對(duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的有：檢索、插入、刪除、更新、排序。數(shù)據(jù)類(lèi)型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱(chēng)。結(jié)構(gòu)類(lèi)型：由用戶(hù)借助于描述機(jī)制定義，是導(dǎo)出類(lèi)型。抽象數(shù)據(jù)類(lèi)型ADT：是抽象數(shù)據(jù)的組織和與之的操作。相當(dāng)于在概念層上描述問(wèn)題。優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好

3、的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。算法是一個(gè)良定義的計(jì)算過(guò)程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法的好壞的因素：算法是正確的；執(zhí)行算法的時(shí)間；執(zhí)行算法的存儲(chǔ)空間（主要是輔助存儲(chǔ)空間）；算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。漸近時(shí)間復(fù)雜度：是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。算法中語(yǔ)句的頻度不僅與問(wèn)

4、題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O（1）、對(duì)數(shù)階O（log2n）、線性階O（n）、線性對(duì)數(shù)階O（nlog2n）、平方階O（n^2）、立方階O（n^3）、……k次方階O（n^k）、指數(shù)階O（2^n）?？臻g復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱(chēng)算法復(fù)雜度。第二章第二章線性表線性表線性表是由n≥0個(gè)數(shù)據(jù)元素組成的有限序列。n=0是空表

5、；非空表，只能有一個(gè)開(kāi)始結(jié)點(diǎn)，有且只能有一個(gè)終端結(jié)點(diǎn)。線性表上定義的基本運(yùn)算：構(gòu)造空表：Initlist（L）求表長(zhǎng)：Listlength（L）取結(jié)點(diǎn)：GetNode（L，i）查找：LocateNode（L，x）插入：List（L，x，i）刪除：（L，i）順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算：LOCa（i）=LOCa（1）（i1）d；

6、（首地址為1）在順序表中實(shí)現(xiàn)的基本運(yùn)算：FirstOut）.隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有六種：置空隊(duì)：InitQueue（Q）判隊(duì)空：QueueEmpty（Q）判隊(duì)滿(mǎn)：QueueFull（Q）入隊(duì)：EnQueue（Q，x）出隊(duì)：DeQueue（Q）取隊(duì)頭元素：QueueFront（Q）順序隊(duì)列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上

7、溢”現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成一個(gè)頭尾相接的環(huán)形，這時(shí)隊(duì)列稱(chēng)循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿(mǎn)，方法有三種：一種是另設(shè)一個(gè)布爾變量來(lái)判斷；第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（（rear1）%m=front）？滿(mǎn)：空；第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈隊(duì)列，一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入（入隊(duì)）的操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針

8、唯一地確定。鏈隊(duì)列不存在隊(duì)滿(mǎn)和上溢的問(wèn)題。在鏈隊(duì)列的出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。第四章第四章串串是零個(gè)或多個(gè)字符組成的有限序列?？沾菏侵搁L(zhǎng)度為零的串，也就是串中不包含任何字符（結(jié)點(diǎn)）?？瞻状褐复邪粋€(gè)或多個(gè)空格字符的串。在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱(chēng)為該串的子串，包含子串的串就稱(chēng)為主串。子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置?？沾侨我獯淖哟?，任意串是自身

9、的子串。串分為兩種：串常量在程序中只能引用不能改變；串變量的值可以改變。串的基本運(yùn)算有：求串長(zhǎng)strlen（s）串復(fù)制strcpy（to，from）串聯(lián)接strcat（to，from）串比較cmp（s1，s2）字符定位strchr（s，c）串是特殊的線性表（結(jié)點(diǎn)是字符），所以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類(lèi)似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為順序串。順序串又可按存儲(chǔ)分配的不同分為：靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)組來(lái)定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度

10、快，但不適合插入、鏈接操作。動(dòng)態(tài)存儲(chǔ)分配：是在定義串時(shí)不分配存儲(chǔ)空間，需要使用時(shí)按所需串的長(zhǎng)度分配存儲(chǔ)單元。串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決“存儲(chǔ)密度”低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。順序串上子串定位的運(yùn)算：又稱(chēng)串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱(chēng)為目標(biāo)（串），子串稱(chēng)為模式（串