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

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

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

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

4、題規(guī)模有關(guān)，還與輸入實例中各元素的取值相關(guān)。時間復(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）。空間復(fù)雜度：是某個算法的空間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。算法的時間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。第二章第二章線性表線性表線性表是由n≥0個數(shù)據(jù)元素組成的有限序列。n=0是空表

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

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

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

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

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

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