資料結構學習筆記（線性表）

　　1.基礎概念：

　　*資料（（資料對象（資料元素（資料項）））------包含關系。　

　　*資料結構是互相之間存在一種或多種特定關系的資料元素的集合。

　　*邏輯結構：集合機構，線性結構，樹形結構，圖形結構。

　　*實體結構：順序儲存結果、連結儲存結構。

　　2.算法效率問題：

　　*判斷一個算法的效率時，函數中的常熟和其他次要項常常可以忽略，而更應該關注主項（最高次項）的階數。

最高次項的指數大的，函數随着n的增長，結果也會變得增長特别快。

　　*常數項：不管這個常數是多少，我們都計作O(1)。

　　*單純的分支結構（不包含在循環結構中），其時間複雜度也是O(1)。

　　*推導大O階（時間複雜度）方法：

　　a.用常數1取代運作時間中的所有加法常數。

　   b.在修改後運作次數函數中，隻保留最高階項。

　　c.如果最高階項存在且不是1，則去除與這個項相乘的常熟，得到的結果就是大O階。

　　*對算法的分析，一般在沒有特殊說明的情況下，都是指最壞時間複雜度。

　　*當不用限定詞地使用“複雜度”時，通常都是指時間複雜度。

　　*算法的定義：算法是解決特定問題求解步驟的描述，在計算機中為指令的有限程式列，而且每條指令表示一個或者多個操作。

　　*算法的特性：有窮性、确定性、可行性、輸入、輸出。

　　*算法的設計的要求：正确性、可讀性、健壯性、高效率和低儲存量的要求。

　　*算法的度量方法：事後統計方法（不科學、不準确）、事後分析估算方法。

　　3.線性表

　　線性表：零個或多個資料元素的有限序列。

　　首先它是一個序列，元素之間是有順序的，其次，線性表是有限的。

　　在任意時刻，線性表的長度應該小于等于數組的長度。

　　一些操作：

　　ADT 線性表（List)

　　Data

　　線性表的資料對象集合為{a1,a2,......,an}，每個元素的類型均為DataType。其中，除第一個元素a1外，每一個元素有且隻有一個直接前驅元素，除了最後一　個元素an外，每一個元素有且隻有一個直接後置元素。資料元素之間的關系是一對一的關系。

　　Operation

　　InitList(*L): 初始化操作，建立一個空的線性表L。

　　ListEmpty(L): 若線性表為空，傳回true，否則傳回false。

　　ClearList(*L): 将線性表清空。

　　GetElem(L,i,*e) 将線性表L中的第i個位置元素值傳回給e。

　　LocateElem(L,e): 線上性表L中查找與給定值e相等的元素，如果查找成功，傳回鈣元素在表中序号表示成功；否則，傳回0表示失敗。

　　ListInsert(*L,i,e): 線上性表L中的第i給位置插入新元素e.

　　ListDelete(*L, i, *e): 删除線性表L中第i個位置元素，并用e傳回其值。

　　ListLength(L): 傳回線性表L的元素個數。

　　endADT

　　4.順序存儲結構：

　　順序存儲結構需要三個屬性：

　　a.存儲空間的起始位置：數組data，它的存儲位置就是存儲空間的存儲位置。

　　b.線性表的最大存儲容量：數組長度MAXSIZE。

　　c.線性表的目前長度：length。

　

　　線性表順序存儲結構

　　優點：*無須為表示表中元素之間的邏輯關系而增加額外的存儲空間

　　*可以快速地存取表中任一位置的元素

　　缺點：*插入和删除操作需要移動大量元素

　　*當線性表長度變化較大時，難以确定存儲空間的容量

　　*造成存儲空間的“碎片”

　　

　　線性表的順序存儲結構，在存、讀資料時，不管是哪個位置，時間複雜度都是O[1]；而插入或者删除時，時間複雜度都是O[n]。這說明，它比較适合元素個數不太變化，而更多存取資料的應用。

　　插入算法ListInsert(*L, i, e)的思路：

　　*如果插入位置不合理，抛出異常；

　　*如果線性表長度大于等于數組長度，則抛出異常或動态增加容量；

　　*從最後一個元素開始向前周遊到第i個位置，分别将它們都向後移動一個位置；

　　将要插入元素填入位置i處；

　　*表長加1。

　　删除算法ListDelete(*L, i, *e)的思路；

　　*如果删除位置不合理，抛出異常；

　　*取出删除元素；

　　*從删除元素位置開始周遊到最後一個元素，分别将它們都向前移動一個位置；

　　*表長減1。

　　5.頭指針與頭結點：

　　頭指針：

　　*頭指正是指連結清單指向第一個結點的指針，若連結清單有頭結點，則是指向頭結點的指針

　　*頭指針是具有辨別作用，是以常用頭指針冠以連結清單的名字

　　*無論連結清單是否為空，頭指針均不為空。頭指針是連結清單的必要元素。

　　頭結點：

　　*頭結點是為了操作的統一和友善而設立的，放在第一進制素的結點之前，其資料域一般無意義（也可存放連結清單的長度）

　　*有了頭結點，對在第一進制素結點前和删除第一結點，其操作與其它結點的操作就統一了

　　*頭結點不一定是連結清單必須要素。

　　6.單連結清單：

　　malloc函數：向系統申請配置設定指定size個位元組的記憶體空間。傳回類型是 void* 類型。

　　對于插入或删除資料越頻繁的操作，單連結清單的效率優勢就越是明顯。

　　獲得單連結清單第i個資料的算法GetElem(L,i,*e)思路：

　　*聲明一個結點P指向連結清單第一個結點，初始化j從1開始；

　　*當j<i時，就周遊連結清單，讓P的指針向後移動，不斷指向下一結點，j累加1；

　　*若到連結清單末尾P為空，則說明第i個元素不存在；

　　*否則查找成果，傳回結點P的資料。

　　單連結清單第i個資料插入結點的算法思路：

　　*.聲明一結點P指向連結清單第一個結點，初始化j從1開始；

　　*.當j<i時，就周遊連結清單，讓P的指針向後移動，不斷指向下一結點，j累加1；

　　*.若到連結清單末尾P為空，則說明第i個元素不存在；

　　*.否則查找成功，在系統中生成一個空結點s;

　　*.将資料元素e指派給s->data;

　　*.單連結清單的插入标準語句s->next=p->next; p->next=s;

　　*.傳回成功。

　　單連結清單第i個資料删除結點的算法思路：

　　*聲明一結點p指向連結清單第一個結點，初始化j從1開始；

　　*當j<i時，就周遊連結清單，讓p的指針向後移動，不斷指向下一個結點，j累加1；

　　*若到連結清單末尾p為空，則說明第i個元素不存在；

　　*否則查找成功。将欲删除的結點p->nest賦給去q；

　　*單連結清單的删除标準語句p->next=q->next；

　　*将q結點中的資料指派給e，作為傳回；

　　*釋放q結點；

　　*傳回成功。

　　單連結清單整表建立的算法思路：

　　*聲明一結點p和計數器變量i；

　　*初始化一空連結清單L；

　　*讓L的頭結點的指針指向NULL，即建立一個帶頭結點的單連結清單；

　　*循環：

　　*生成一新節點指派給p；

　　*随機生成一數字指派給p的資料域p->data;

　　*将p插入到頭結點與前一新節點之間。

　　單連結清單整表删除的算法思路：

　　*聲明一結點p和q；

　　*将第一個結點指派給p；

　　*将下一個結點指派給q；

　　*釋放p；

　　*将q指派給p。

　　7.順序存儲結構與單連結清單的差別：

　　單連結清單結構與順序存儲結構優缺點

　　存儲配置設定方式：

　　*順序存儲結構用一段連續的存儲單元一次存儲線性表的資料元素

　　*單連結清單采用鍊式存儲單元存放線性表的元素

　　時間性能

　　*順序存儲結構O(1)、單連結清單O(n);

　　*插入和删除：順序存儲結構需要平均異動表長一半的元素，時間為O(n); 單連結清單線上處某位置的指針後，插入和删除時間僅為O(1)。

　　空間性能：

　　*順序存儲結構需要預配置設定存儲空間，分大了，浪費，分小了易發生上溢

　　*單連結清單不需要配置設定存儲空間，隻要有就可以配置設定，元素個數也不受限制。

　　總結：

　　*若線性表需要頻繁查找，很少進行插入和删除操作時，宜采用順序存儲結構。若需要頻繁插入和删除時，宜采用單連結清單結構。

　　*當線性表中的元素個數變化較大或者根本不知道有多大時，最後用單連結清單結構，這樣可以不需要考慮存儲空間的大小問題。而如果事先知道線性表的大緻長度，用順序存儲結構效率會高很多。

　　8.靜态連結清單優缺點：

　　*優點：在插入和删除操作時，隻需要修改遊标，不需要移動元素，進而改進了在順序存儲結構中的插入和删除操作需要移動大量元素的缺點。

　　*缺點：沒有解決連續存儲配置設定帶來的表長難以确定的問題；失去了順序存儲結構随機存取的特性。

　　總結：靜态連結清單其實是為了給沒有指針的進階語言設計的一種實作單連結清單能力的方法。

　　9.循環連結清單：将單連結清單中終端結點的指針端由空指針改為指向頭結點，就使整個單連結清單形成一個環，這種頭尾相接的單連結清單稱為單循環連結清單，簡稱循環連結清單。

并不是說，循環連結清單一定要頭結點。

　　10.雙向清單：雙向清單是在單連結清單的每個結點中，再設定一個指向其前驅結點的指針域。

　　/*線性表的雙向連結清單存儲結構*/

　　typedef struct DulNode

　　{

　　ElemType data;

　　struct DulNode *prior; /*直接前驅指針*/

　　struct DulNode *next; /*直接後繼指針*/

　　}DulNode, *DuLinkList;

　　雙向清單在插入和删除時，需要更改兩個指針變量。

　　插入：

　　s->prior = p; /*把p賦給s的前驅*/

　　s->next = p->next; /*把p->next賦給s的後繼*/

　　p->next->prior = s; /*把s指派給p->next的前驅*/

　　p->next = s; /*把s賦給p的後繼*/

　　順序是先搞定s的前驅和後繼，再搞定後結點的前驅，最後解決前結點的後繼。

　　删除：

　　p->prior->next = p->next; /*把p->next指派給p->prior的後繼*/

　　p->next->prior = p->prior; /*把p->prior指派給p->next的前驅*/

　　11.總結：

　　線性表分為順序存儲結構和鍊式存儲結構，其中鍊式存儲結構包括：單連結清單、靜态連結清單、循環連結清單和雙向連結清單這四種。