《數(shù)據(jù)結(jié)構(gòu)課程總結(jié)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、l數(shù)據(jù)：能夠被計算機(jī)識別、存儲和加工處理的信息的載體。l數(shù)據(jù)元素：數(shù)據(jù)的基本單位，可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。l數(shù)據(jù)結(jié)構(gòu)的定義：l邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨立于計算機(jī)。線性結(jié)構(gòu)：一對一關(guān)系。線性結(jié)構(gòu)：多對多關(guān)系。l存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)。順序存儲結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯Y(jié)構(gòu)：如鏈表。索引結(jié)構(gòu)：索引表。散列存儲結(jié)構(gòu)：如散列表。l對數(shù)據(jù)的操作：定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算集合。常用的有：檢索、插入、刪除、更新、排序。l數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。原子類型：簡單類型，由語言提

2、供。結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。l程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。l算法是一個自定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。l評價算法的好壞的因素：算法是正確的;執(zhí)行算法的時間;執(zhí)行算法的存儲空間;算法易于理解、編碼、調(diào)試。l時間復(fù)雜度：是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復(fù)雜度：是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。評價一個算法的時間性能時，主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度。l算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實例中各元素的取

3、值相關(guān)。l時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階、對數(shù)階、線性階、線性對數(shù)階、平方階、立方階、……k次方階、指數(shù)階。l空間復(fù)雜度：是某個算法的空間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。l算法的時間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。l線性表是由n≥0個數(shù)據(jù)元素組成的有限序列。n=0是空表;非空表，只能有一個開始結(jié)點，有且只能有一個終端結(jié)點。l線性表上定義的基本運算：構(gòu)造空表：Initlist；求表長：Listlength；取結(jié)點：GetNode；查找：LocateNode；插入：InsertList；刪除：Delete。l順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組

4、地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點相鄰關(guān)系是一致的。地址計算：？l在順序表中實現(xiàn)的基本運算：插入：平均移動結(jié)點次數(shù)為？;平均時間復(fù)雜度均為？。刪除：平均移動結(jié)點次數(shù)為？;平均時間復(fù)雜度均為？。l線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還存儲了其后繼結(jié)點的地址信息。這兩部分信息組成鏈表中的結(jié)點結(jié)構(gòu)。一個單鏈表由頭指針的名字來命名。l單鏈表運算：建立單鏈表（頭插法：生成的順序與輸入順序相反。平均時間復(fù)雜度均為？。尾插法：平均時間復(fù)雜度均為？。加頭結(jié)點的算法：對開始

5、結(jié)點的操作無需特殊處理，統(tǒng)一了空表和非空表。查找（按序號：與查找位置有關(guān)，平均時間復(fù)雜度均為？。按值：與輸入實例有關(guān)，平均時間復(fù)雜度均為。插入運算：p=GetNode;s-next=p-next;p-next=s;平均時間復(fù)雜度均為？，刪除運算：平均時間復(fù)雜度均為？）l單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點的指針域指向開始結(jié)點或頭結(jié)點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是O？，不用遍歷整個鏈表。l雙鏈表就是雙向鏈表，就是在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域pri

6、or，形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相構(gòu)成雙循環(huán)鏈表。雙鏈表上的插入和刪除時間復(fù)雜度均為O？。l順序表和鏈表的比較：l基于空間：順序表的存儲空間是靜態(tài)分配，存儲密度為1;適于線性表事先確定其大小時采用。鏈表的存儲空間是動態(tài)分配，存儲密度1;適于線性表長度變化大時采用。l基于時間：順序表是隨機(jī)存儲結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。l棧是僅限制在表的一端進(jìn)行插入和刪除運算的線性表，稱插入、刪除這一端為棧頂，另一端稱

7、為棧底。表中無元素時為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱棧為LIFO表。通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu)。l棧的基本運算有六種：構(gòu)造空棧：InitStack，判?？眨篠tackEmpty，判棧滿：StackFull，進(jìn)棧：Push，退棧：Pop，取棧頂元素：StackTopl在順序棧中有“上溢”和“下溢”的現(xiàn)象?！吧弦纭笔菞ｍ斨羔樦赋鰲５耐饷媸浅鲥e狀態(tài)。“下溢”可以表示棧為空棧，因此用來作為控制轉(zhuǎn)移的條件。l順序棧中的基本操作有六種：構(gòu)造空棧，判?？?，判棧滿，進(jìn)棧，退棧，取棧頂元素l鏈棧則沒有上溢的限制，因此進(jìn)棧不要判棧滿。鏈棧不需要在