數據結構各章要點

(n^)……k次方階O(n^k)指數階O(^n)
空間復雜度是某個算法的空間耗費它是該算法所求解問題規模n的函數
算法的時間復雜度和空間復雜度合稱算法復雜度

第二章 線性表
************************************************************************
線性表是由n≥個數據元素組成的有限序列n=是空表非空表只能有一個開始結點有且只能有一個終端結點
************************************************************************
線性表上定義的基本運算·構造空表Initlist(L)
·求表長Listlength(L)
·取結點GetNode(Li)
·查找LocateNode(Lx)
·插入InsertList(Lxi)
·刪除Delete(Li)
************************************************************************
順序表是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關

系是一致的地址計算LOCa(i)=LOCa()+(i)*d（首地址為）
在順序表中實現的基本運算 ·插入平均移動結點次數為n/平均時間復雜度均為O(n)
·刪除平均移動結點次數為（n）/平均時間復雜度均為O(n)
************************************************************************
線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同為了能正確表示結點間的邏輯關系在存儲每個結點值的同時還存儲

了其後繼結點的地址信息(即指針或鏈)這兩部分信息組成鏈表中的結點結構 一個單鏈表由頭指針的名字來命名
************************************************************************
單鏈表運算·建立單鏈表·頭插法s>next=headhead=s生成的順序與輸入順序相反平均時間復雜度均為O(n)
·尾插法head=rear=nullif(head=null) head=s;else r>next=s;r=s; 平均時間復雜度均為O(n)
·加頭結點的算法對開始結點的操作無需特殊處理統一了空表和非空表
·查找·按序號與查找位置有關平均時間復雜度均為O(n)
·按值與輸入實例有關平均時間復雜度均為O(n)
·插入運算p=GetNode(Li)s>next=p>nextp>next=s平均時間復雜度均為O(n)
·刪除運算p=GetNode(Li)r=p>nextp>next=r>nextfree(r)平均時間復雜度均為O(n)
************************************************************************
單循環鏈表是一種首尾相接的單鏈表終端結點的指針域指向開始結點或頭結點鏈表終止條件是以指針等於頭指針或尾指針
采用單循環鏈表在實用中多采用尾指針表示單循環鏈表優點是查找頭指針和尾指針的時間都是O()不用遍歷整個鏈表
************************************************************************
雙鏈表就是雙向鏈表就是在單鏈表的每個結點裡再增加一個指向其直接前趨的指針域prior形成兩條不同方向的鏈由頭指針head惟一

確定
雙鏈表也可以頭尾相鏈接構成雙(向)循環鏈表
雙鏈表上的插入和刪除時間復雜度均為O ()
************************************************************************
順序表和鏈表的比較·基於空間 ·順序表的存儲空間是靜態分配存儲密度為適於線性表事先確定其大小時采用
·鏈表的存儲空間是動態分配存儲密度＜適於線性表長度變化大時采用
  ·基於時間 ·順序表是隨機存儲結構當線性表的操作主要是查找時宜采用
·以插入和刪除操作為主的線性表宜采用鏈表做存儲結構
·若插入和刪除主要發生在表的首尾兩端則宜采用尾指針表示的單循環鏈表

第三章 棧和隊列
************************************************************************
棧(Stack)是僅限制在表的一端進行插入和刪除運算的線性表稱插入刪除這一端為棧頂另一端稱為棧底表中無元素時為空棧棧

的修改是按後進先出的原則進行的我們又稱棧為LIFO表(Last In First Out)通常棧有順序棧和鏈棧兩種存儲結構
************************************************************************
棧的基本運算有六種 ·構造空棧InitStack(S)
·判棧空: StackEmpty(S)
·判棧滿 StackFull(S)
·進棧 Push(Sx)
·退棧 Pop(S)
·取棧頂元素StackTop(S)
************************************************************************
在順序棧中有上溢和下溢的現象 ·上溢是棧頂指針指出棧的外面是出錯狀態
·下溢可以表示棧為空棧因此用來作為控制轉移的條件
順序棧中的基本操作有六種·構造空棧·判棧空·判棧滿·進棧·退棧·取棧頂元素

************************************************************************
鏈棧則沒有上溢的限制因此進棧不要判棧滿鏈棧不需要在頭部附加頭結點只要有鏈表的頭指針就可以了
鏈棧中的基本操作有五種·構造空棧·判棧空·進棧·退棧·取棧頂元素
************************************************************************
隊列(Queue)是一種運算受限的線性表插入在表的一端進行而刪除在表的另一端進行允許刪除的一端稱為隊頭(front)允許插入的

一端稱為隊尾(rear) 隊列的操作原則是先進先出的又稱作FIFO表(First In First Out) 隊列也有順序存儲和鏈式存儲兩種存儲結

構
************************************************************************
隊列的基本運算有六種 ·置空隊InitQueue(Q)
·判隊空QueueEmpty(Q)
·判隊滿QueueFull(Q)
·入隊EnQueue(Qx)
·出隊DeQueue(Q)
·取隊頭元素QueueFront(Q)
************************************************************************
順序隊列的假上溢現象由於頭尾指針不斷前移超出向量空間這時整個向量空間及隊列是空的卻產生了上溢現象
為了克服假上溢現象引入循環向量的概念是把向量空間形成一個頭尾相接的環形這時隊列稱循環隊列
判定循環隊列是空還是滿方法有三種 ·一種是另設一個布爾變量來判斷
·第二種是少用一個元素空間入隊時先測試（(rear+)%m = front）? 滿空 
·第三種就是用一個計數器記錄隊列中的元素的總數
********************
From:http://tw.wingwit.com/Article/program/sjjg/201311/24001.html