第一章緒論
一、 基本概念：
資料、資料元素、資料項
資料結構、邏輯結構、物理結構
線性結構、非線性結構
順序儲存結構、鏈式儲存結構、雜湊儲存結構、索引儲存結構
資料型別、抽象資料型別。
演算法、語句的頻度、演算法的時間複雜度、演算法的漸進複雜度
空間複雜度
二、 資料結構概念：
資料結構包括資料的邏輯結構、資料的儲存結構和資料的運算。
資料的運算定義在資料的邏輯結構上，是通過演算法來描述的。
資料運算的實現依賴於資料的儲存結構。
資料結構分類方法：
按資料元素間的邏輯關係分類：
集合、線性、樹狀、圖狀或網狀
按元素間的邏輯關係和施加的運算分類（抽象資料型別）：
線性表、棧、佇列、串、資料、廣義表
樹、二叉樹、圖
查詢表檔案三、 演算法的時間複雜度
演算法的時間複雜度t(n):演算法的時間消耗
演算法的時間消耗：所有語句的執行次數（頻度）之和
演算法的漸進時間複雜度（簡稱時間複雜度）：當n->∞時，t(n)的數量級。
即為t(n)中階最高的那一項，是演算法中頻度最大的語句頻度。
空間複雜度：除資料集合所需的空間外，為實現運算所需的輔助空間的數量（級）。
第二章線性表
一、線性表的邏輯特徵
資料元素**性表中的相對位置是線性的，可以用乙個連續的整數編碼來標識，即資料元素**性表中的位置只依賴於它們自己的序號，與資料元素的具體內容無關。
二、對線性表的基本操作
1、 初始化操作
2、 求線性表的長度
3、 取表中第i個元素:若1≤i≤length(l)，則函式值為給定線性表中第i個元素，否則為元素null。
4、 定位函式:返回元素x的位序。
5、 insert（l，i,b）:前插函式。在第i 個元素前插入資料元素b。
6、 delete（l，i）:刪除第i個資料元素。
7、 刪除指標p指定的結點。
三、線性表的順序儲存結構（向量結構）
用一組連續的儲存單元依次儲存線性表的元素。
特點：1、邏輯上相鄰的資料元素ai和ai+1的儲存位置也相鄰。即以資料元素在計算機內「物理位置相鄰」來表示線性表中資料元素之間的邏輯關係。
loc(ai)=loc(a1)+(i-1)*l
loc(a1)是第乙個資料元素的儲存位置，通常稱為線性表的起始位址或基位址。
2、只要確定了儲存線性表的起始位址，就直接確定了線性表中任一資料元素的儲存位置，並且通過該公式實現對線性表元素的隨機訪問（訪問）。
線性表順序儲存結構的c描述
線性表順序儲存結構的操作
1、定位操作：定位平均比較次數為(∑i)/n=(n+1)/2，演算法的時間複雜度為o(n)。
不成功，則要比較n+1。
2、 insert(v,i,b):前插操作，在第i個資料元素之前插入乙個元素b。
所需移動元素次數的期望值（平均次數）為：
eis=∑pi(n-i+1)=(n(n+1)/2)/(n+1)=n/2 (i=1,2,…,n+1)
即：演算法的時間複雜度為o(n).
3、刪除運算：在長度為n的線性表中刪除第i個元素。
刪除第i個元素移動次數為n-i
平均移動次數為ede=(∑(n-i))/n=(n-1)/2 (i=1,2,...,n)
刪除運算的時間複雜度為o(n)
缺點：插入刪除操作可能要移動大量元素。
四、線性表的鏈式儲存結構
特點：用一組任意的儲存單元存放線性表的資料元素（儲存單元可以不連續）。
資料元素間的邏輯關係表示：儲存乙個指示其直接後繼的資訊。
用獨立結點來儲存資料元素的資訊和指示資料元素間的邏輯關係。
實現的c語言描述
單鏈表的特點
1、頭指標：指示線性鍊錶中第乙個結點。
2、最後乙個結點無後繼，其指標域設為「空」（nil），表示鍊錶到此結束。
3、結點指標域：把記憶體中可能不連續的資料元素順序組成乙個線性表。
4、要訪問任一元素，必須從頭指標出發尋找，是順序訪問結構。
5、增設乙個頭結點，作為線性表的第乙個結點，可以簡化插入、刪除演算法。
線性鍊錶的運算
1、在相鄰元素a和b之間插入乙個值為x的資料元素的基本操作步驟：
生成乙個資料域值為x的結點s;
使x結點的指標域指向結點b: s->next=p->next;
修改a結點的指標域指向結點x:p->next=s;
2、在第i個元素前插入乙個元素x的步驟：
生成乙個資料域值為x的結點s;
查詢第i-1個接點p
使x結點的指標域指向結點p的後繼接點: s->next=p->next;
使p結點的指標域指向結點s:p->next=s;
3、刪除第i個結點。
實現：修改前驅結點(第i-1結點)的指標域使其指向第i+1個結點。
插入和刪除運算的關鍵：尋找前驅結點。
在兩種運算中，while迴圈平均比較次數：
(∑i)/(n+1)=(n+1)/2 （i=1,2,n+1）
迴圈體的執行次數: (∑（i-1）/(n+1)=n/2
時間複雜度為ｏ(n)。
採用線性鍊錶的優點：
①有效利用儲存資源，提高程式執行的可靠性。有多少資料元素，才申請多少相應的儲存空間。不使用的單元可歸還給系統。
儲存密度
②插入和刪除，不需移動元素。
3、迴圈鍊錶
使最後乙個結點的指標域又指向第乙個結點或頭結點。這樣的線性鍊錶就叫迴圈鍊錶。
特點：從任一結點出發，可以訪問表中所有其它結點。
為了使得空表和非空表的運算統一，設定乙個表頭結點。它的值域或為空.
用指向表尾結點的指標來表示迴圈鍊錶的優點
4、雙向迴圈鍊錶
雙向鍊錶：每個結點設定兩個指標，乙個指向直接前驅，乙個指向直接後繼。
雙向迴圈鍊錶：在雙向鍊錶中，若第乙個結點（後頭結點）的前向指標指向最後乙個結點，最後乙個結點的後向指標指向第乙個結點（或頭結點），則就是雙向迴圈鍊錶。
雙向迴圈鍊錶結點的插入：在p結點前插入乙個結點s
雙向迴圈鍊錶結點的刪除
第三章棧和佇列
一、棧（stack）
1、棧的定義：限定僅在表的一端進行插入和刪除操作的線性結構。
棧頂（top）： 允許進行插入和刪除操作的一端。
2、棧的特點：後進先出（或先進後出）：last in first out＝lifo
3、棧的基本操作
inistack(s):初始化棧。設定乙個空棧。
empty(s):判棧空函式。棧空時返回真，否則返回假。
push（s，x）：入棧操作函式。在棧頂插入元素x。
pop（s,&e）：出棧函式。若棧不空，返回棧頂元素值，並從棧中刪除該元素，否則返回空元素null。
gettop（s,&e）：取棧頂元素函式。若棧不空，返回棧頂元素值，否則返回空元素null。
4、棧的順序儲存表示及其實現
用一組位址連續的儲存單元依次存放自棧底到棧頂的資料元素。
實現的c描述
棧的初始化
進棧操作
出棧操作
棧的「下溢」極其意義。
5、棧的鏈式儲存結構
煉表頭指標用top表示。
棧空時：top=nil
入棧：每當乙個元素進棧時，申請乙個新結點，插入到表頭。
出棧：每當乙個元素出棧時，從表頭釋放乙個結點。
判斷進棧、出棧序列的正確性
二、佇列（queue）
定義：佇列是一種先進先出的線性表（結構）。
特點：插入運算在表的一端進行。刪除運算在表的另一端進行。
隊頭：允許刪除的一端，用front表示。
隊尾：允許插入的一端，用rear表示。
3、佇列的基本操作
iniqueue（q）：初始化佇列，設定乙個空佇列。
empty（q）：判佇列空函式。佇列空，返回true,否則返回false。
enqueue（q）：入隊操作，在佇列尾部插入乙個元素。
dequeue（q）：出隊操作，若隊不空，出隊頭元素，並返回該元素值，否則返回null。
4、佇列的鏈式儲存結構----鏈佇列
c語言描述
頭指標----指向刪除的一端
尾指標----指向插入的一端
隊空時： 頭、尾指標為null,或都指向頭結點。
出隊操作要判斷尾指標的正確性
5、佇列的順序儲存結構
假上溢。
假上溢的原因是：頭指標和尾指標的值總是不斷增加，已使用過的儲存單元無法再使用。
解決假上溢的方法：
迴圈佇列
解決隊空隊滿都有頭尾指標相等問題：
1、乙個標誌字段區分隊空隊滿
2、少用乙個元素空間，ｍ個元素單元最多隻存放ｍ－１個元素，且：
front=rear ----隊空
rear+1）%m=front ----隊滿
3、長度記數器
要能夠區分線性表、棧、佇列的異同
第四章串
一、串及其操作
1、串的邏輯結構定義：串（字串）：是由０個或多個字元組成的有限序列。
串的長度，空串，空格串、子串，主串、主串、字元在串中的位置、子串在串中的位置。
2、串的基本操作
判斷相等、求串長、聯接、串複製、求子串、串的模式匹配
二、 串的儲存結構
1、靜態儲存分配：
分配一組連續的儲存單元存放串的字串行。
c語言可描述
2、鏈式儲存結構----動態儲存結構----塊鏈儲存結構
儲存密度=串值所佔儲存位/實際分配的儲存位
3、堆分配與儲存映像
四、 kpm演算法
基本思想
next函式
第五章陣列和廣義表
一、 陣列的邏輯結構特點
陣列元素個數
①乙個元素都受n個關係的約束,每個關係都是線性關係。
②每個陣列元素屬於同一資料型別。
③每個陣列元素對應於一組下標，
④每個下標有由一對界偶（ci,di）限定其範圍。
陣列的兩個定義
1、乙個 n維陣列被定義為乙個線性表，其元素是乙個 n-1維陣列。
2、乙個 n維陣列的資料元素受n個關係的約束，且每個關係都是線性的。
二、對陣列的操作：
給定一組下標，訪問相應的資料元素。
給定一組下標，修改相應資料中的某乙個或幾個資料項的值。
資料結構複習
0.緒論 一 填空題 1 資料的邏輯結構是資料元素之間的邏輯關係，通常有下列4類 2 資料的儲存結構是資料在計算機儲存器裡的表示，主要有4種基本儲存方法 二 選擇題 1 乙個演算法必須在執行有窮步之後結束，這是演算法的 a 正確性 b 有窮性 c 確定性 d 可行性 2 演算法的每一步必須有確切的定...
資料結構複習
1.以niklus wirth的觀點，程式等於什麼?2.演算法的重要特性。3.好演算法的標準。4.線性結構的特點。5.線性結構與非線性結構的區別。6.列出所學過的線性結構與非線性結構。7.頭指標 頭結點 首元結點的區別。8.帶頭結點和不帶頭結點的線性鍊錶的區別。9.單鏈表 雙鏈表 迴圈鍊錶的區別及各...
資料結構複習
2 掌握圖的兩種儲存結構，鄰接矩陣及鄰接表 重點掌握圖的鄰接矩陣表示方法。掌握給定乙個圖，採用鄰接矩陣或鄰接表表示法，對圖中邊 頂點的度 任意兩點是否有邊相連的確定方法 3 最小生成樹，重點掌握採用普里姆演算法及克魯斯卡爾演算法如何求最小生成樹 4 重點掌握圖的深度優先遍歷及廣度優先遍歷 重點掌握圖...