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

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

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

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

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

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

6、（首地址為1）在順序表中實(shí)現(xiàn)的基本運(yùn)算：FirstOut）.隊(duì)列也有順序存儲和鏈?zhǔn)酱鎯煞N存儲結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有六種：置空隊(duì)：InitQueue（Q）判隊(duì)空：QueueEmpty（Q）判隊(duì)滿：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ì)列稱循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿，方法有三種：一種是另設(shè)一個(gè)布爾變量來判斷；第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測試（（rear1）%m=front）？滿：空；第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入（入隊(duì)）的操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針

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

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

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