數據結構(c語言版)知識點概括(已修改)

　

【正文】 數據結構知識點概括第一章 概 論數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。數據元素是數據的基本單位，可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。數據結構的定義：邏輯結構：從邏輯結構上描述數據，獨立于計算機。線性結構：一對一關系。線性結構：多對多關系。　　存儲結構：是邏輯結構用計算機語言的實現。順序存儲結構：如數組。　　鏈式存儲結構：如鏈表。　　索引存儲結構：稠密索引：每個結點都有索引項。　　稀疏索引：每組結點都有索引項。　　散列存儲結構：如散列表。數據運算。對數據的操作。定義在邏輯結構上，每種邏輯結構都有一個運算集合。　　常用的有：檢索、插入、刪除、更新、排序。數據類型：是一個值的集合以及在這些值上定義的一組操作的總稱。　　結構類型：由用戶借助于描述機制定義，是導出類型。　 抽象數據類型ADT：是抽象數據的組織和與之的操作。相當于在概念層上描述問題。 　　優點是將數據和操作封裝在一起實現了信息隱藏。程序設計的實質是對實際問題選擇一種好的數據結構，設計一個好的算法。算法取決于數據結構。算法是一個良定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。　　評價算法的好壞的因素：算法是正確的；　　執行算法的時間；執行算法的存儲空間（主要是輔助存儲空間）；算法易于理解、編碼、調試。　時間復雜度：是某個算法的時間耗費，它是該算法所求解問題規模n的函數。　漸近時間復雜度：是指當問題規模趨向無窮大時，該算法時間復雜度的數量級。　　評價一個算法的時間性能時，主要標準就是算法的漸近時間復雜度。　　算法中語句的頻度不僅與問題規模有關，還與輸入實例中各元素的取值相關。　　時間復雜度按數量級遞增排列依次為：常數階O（1）、對數階O（log2n）、線性階O（n）、線性對數階O（nlog2n）、平方階O（n^2）、立方階O（n^3）、……k次方階O（n^k）、指數階O（2^n）。　　空間復雜度：是某個算法的空間耗費，它是該算法所求解問題規模n的函數。　　算法的時間復雜度和空間復雜度合稱算法復雜度。第二章 線性表線性表是由n≥0個數據元素組成的有限序列。n=0是空表；非空表，只能有一個開始結點，有且只能有一個終端結點。　　線性表上定義的基本運算：　　構造空表：Initlist（L）　　求表長：Listlength（L）　　取結點：GetNode（L，i）　　查找：LocateNode（L，x）　　插入：InsertList（L，x，i）　　刪除：Delete（L，i）　　順序表是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。地址計算：LOCa（i）=LOCa（1）+（i1）*d；（首地址為1）　在順序表中實現的基本運算：　　插入：平均移動結點次數為n/2；平均時間復雜度均為O（n）。 刪除：平均移動結點次數為（n1）/2；平均時間復雜度均為O（n）。　　線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同，為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其后繼結點的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結點結構。 一個單鏈表由頭指針的名字來命名。單鏈表運算：建立單鏈表頭插法：snext=head；head=s；生成的順序與輸入順序相反。平均時間復雜度均為O（n）。尾插法：head=rear=null；if（head=null） head=s；else rnext=s；r=s； 平均時間復雜度均為O（n）　　加頭結點的算法：對開始結點的操作無需特殊處理，統一了空表和非空表。　　查找按序號：與查找位置有關，平均時間復雜度均為O（n）。　　按值：與輸入實例有關，平均時間復雜度均為O（n）。　　插入運算：p=GetNode（L，i1）；snext=pnext；pnext=s；平均時間復雜度均為O（n）刪除運算：p=GetNode（L，i1）；r=pnext；pnext=rnext；free（r）；平均時間復雜度均為O（n）單循環鏈表是一種首尾相接的單鏈表，終端結點的指針域指向開始結點或頭結點。鏈表終止條件是以指針等于頭指針或尾指針。　　采用單循環鏈表在實用中多采用尾指針表示單循環鏈表。優點是查找頭指針和尾指針的時間都是O（1），不用遍歷整個鏈表。　　雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。　　雙鏈表也可以頭尾相鏈接構成雙（向）循環鏈表。　　雙鏈表上的插入和刪除時間復雜度均為O （1）。　　順序表和鏈表的比較：　　基于空間：　　 順序表的存儲空間是靜態分配，存儲密度為1；適于線性表事先確定其大小時采用。鏈表的存儲空間是動態分配，存儲密度＜1；適于線性表長度變化大時采用。　　基于時間：　　順序表是隨機存儲結構，當線性表的操作主要是查找時，宜采用。　　以插入和刪除操作為主的線性表宜采用鏈表做存儲結構。若插入和刪除主要發生在表的首尾兩端，則宜采用尾指針表示的單循環鏈表。第三章 棧和隊列　　棧（Stack）是僅限制在表的一端進行插入和刪除運算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱棧為LIFO表（Last In First Out）。通常棧有順序棧和鏈棧兩種存儲結構。　　棧的基本運算有六種： 構造空棧：InitStack（S）　　判棧空： StackEmpty（S）　　判棧滿： StackFull（S）　　進棧： Push（S，x）　　退棧： Pop（S）　　取棧頂元素：StackTop（S）　　在順序棧中有“上溢”和“下溢”的現象。 “上溢”是棧頂指針指出棧的外面是出錯狀態。　　“下溢”可以表示棧為空棧，因此用來作為控制轉移的條件。　　順序棧中的基本操作有六種：構造空棧 判棧空 判棧滿 進棧 退棧 取棧頂元素　　鏈棧則沒有上溢的限制，因此進棧不要判棧滿。鏈棧不需要在頭部附加頭結點，只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種：構造空棧 判棧空 進棧 退棧 取棧頂元素隊列（Queue）是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱 為隊頭（front），允許插入的一端稱為隊尾（rear） ，隊列的操作原則是先進先出的，又稱作FIFO表（First In First Out） .隊列也有順序存儲和鏈式存儲兩種存儲結構。隊列的基本運算有六種：　　置空隊：InitQueue（Q）　判隊空：QueueEmpty（Q）　判隊滿：QueueFull（Q）　入隊：EnQueue（Q，x）　出隊：DeQueue（Q）　取隊頭元素：QueueFront（Q）　　順序隊列的“假上溢”現象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產生了“上溢”現象。　為了克服“假上溢”現象引入循環向量的概念，是把向量空間形成一個頭尾相接的環形，這時隊列稱循環隊列。判定循環隊列是空還是滿，方法有三種： 一種是另設一個布爾變量來判斷；第二種是少用一個元素空間，入隊時先測試（（rear+1）%m = front）？ 滿：空；　　第三種就是用一個計數器記錄隊列中的元素的總數。隊列的鏈式存儲結構稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入（入隊）的 操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。第四章 串　　串是零個或多個字符組成的有限序列。　　空串：是指長度為零的串，也就是串中不包含任何字符（結點）。　　空白串：指串中包含一個或多個空格字符的串。　　在一個串中任意個連續字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。　　子串在主串中的序號就是指子串在主串中首次出現的位置。　　空串是任意串的子串，任意串是自身的子串。　　串分為兩種： 串常量在程序中只能引用不能改變；　　串變量的值可以改變。　　串的基本運算有： 求串長strlen（char*s）串復制strcpy（char*to，char*from）　串聯接strcat（char*to，char*from）　串比較charcmp（char*s1，char*s2）字符定位strchr（char*s，charc）　串是特殊的線性表（結點是字符），所以串的存儲結構與線性表的存儲結構類似。串的順序存儲結構簡稱為順序串。　順序串又可按存儲分配的不同分為： 靜態存儲分配：直接用定長的字符數組來定義。優點是涉及串長的操作速度 快，但不適合插入、鏈接操作。　動態存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。　串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的 結點數據域為單個字符。為了解決“存儲密度”低的狀況，可以讓一個結點存儲多個字符，即結點的大小。　　順序串上子串定位的運算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現的位置。在串匹配中，將主串稱為目標（串），子串稱為模式（串）。這是比較容易理解的，串匹配問題就是找出給