一、線性表的基本概念
線性表是由n（n≥0）個資料元素（結點）a1，a2，a3，……an組成的有限序列；資料元素的個數n定義為表的長度，當n=0時，稱為空表，
將非空的線性表（n＞0）記作：L=（a1，a2，a3，……，an）
- a1：起始結點(沒有直接前驅)
- an：終端結點(沒有直接后繼)，
- a1稱為a2的直接前驅
- a3稱為a2的直接后繼
線性表的特點：
- 線性表中只有1個起始結點，1個終端結點，
- 起始結點沒有直接前驅，有1個直接后繼，
- 終端結點有1個直接前驅，沒有直接后繼，
- 除這2個結點外，每個結點都有且只有1個直接前驅和1個直接后繼，
線性表的基本運算
- 1，初始化 Initiate(L) ：建立一個空表L=()，L不含資料元素，
- 2，求表長度 Length(L)：回傳線性表L的長度，
- 3，取表元 Get(L,i)：回傳線性表第i個資料元素，當i不滿足1≤i≤Length(L)時，回傳一特殊值，
- 4，定位 Locate(L,x)：查找線性表中資料元素值等于x的結點序號，若有多個資料元素值與x相等，運算結果為這些結點中序號的最小值，若找不到該結點，則運算結果為0，
- 5，插入 Insert(L,x,i):在線性表L的第i個資料元素之前插入一個值為x的新資料元素，引數i的合法取值范圍是1≤i≤n+1，操作結束后線性表L由（a1,a2,…，ai-1,ai,ai+1,.…，an )變為(a1,a2,…,ai-1,x,ai,ai+1 .…,an )表長度加1，
- 6，洗掉 Delete(L,i):洗掉線性表L的第i個資料元素ai ，i的有效取值范圍是1≤i≤n，洗掉后線性表L由(a1,a2,…,ai-1,ai,ai+1,.…,an )變為(a1,a2,…,ai-1,ai+1,.…,an )，表長度減1
二、線性表的順序存盤
線性表順序存盤的方法：將表中的結點依次存放在計算機記憶體中一組連續的存盤單元中，
- ◆ 資料元素在線性表中的鄰接關系決定其在存盤空間中的存盤位置，
- ◆ 即邏輯結構中相鄰的結點，其物理存盤位置也相鄰，
- ◆ 用順序存盤實作的線性表稱為順序表，一般使用陣列存盤
順序存盤結構的特點：
- 線性表的邏輯結構與存盤結構一致
- 可以對資料元素實作隨機讀取
- 設線性表中所有結點的型別相同，則每個結點所占用存盤空間大小亦相同，
- 假設表中每個結點占用L個存盤單元，其中第一個單元的存盤地址則是該結點的存盤地址
- 并設表中開始結點a1 的存盤地址是d，那么結點ai 的存盤地址LOC(ai)=d+(i-1)*L
順序表是用一維陣列實作的線性表，陣列下標可以看成是元素的相對地址；邏輯上相鄰的元素，存盤在物理位置也相鄰的單元中
1、線性表的基本運算在順序表上的實作
=======================插入========================
插入 Insert(L,x,i):在線性表L的第i個資料元素之前插入一個值為x的新資料元素，引數i的合法取值范圍是1≤i≤n+1，操作結束后線性表L由（a1,a2,…，ai-1,ai,ai+1,.…，an )變為(a1,a2,…,ai-1,x,ai,ai+1 .…,an )表長度加1，
注意：
- 當表空間已滿，不可再做插入操作，
- 當插入位置是非法位置，不可做正常的插入操作，
順序表插入操作程序
- ① 將表中位置為n ，n-1，…，i上的結點，依次后移到位置n+1，n，…，i+1上，空出位置i，
- ② 在位置i上插入新結點x，（當插入位置i=n+1時，無須移動結點，直接將x插入表的末尾）
- ③ 該順序表長度加1，
結論：
- 假設線性表中含有n個資料元素，在進行插入操作時，有n+1個位置可插入,在每個位置插入資料的概率是：1/(n+1),在i位置插入時，要移動n-i+1個資料
- 假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數為：n/2,平均時間復雜度O(n)
===================洗掉========================
洗掉 Delete(L,i):洗掉線性表L的第i個資料元素ai ，i的有效取值范圍是1≤i≤n，洗掉后線性表L由(a1,a2,…,ai-1,ai,ai+1,.…,an )變為(a1,a2,…,ai-1,ai+1,.…,an )，表長度減1
注意：當要洗掉元素的位置i不在表長范圍內（即i＜1或i＞L-＞length）時，為非法位置，不能做正常的洗掉操作
順序表洗掉操作程序：
- 1，若i=n，則只要洗掉終端結點，無須移動結點；
- 2，若1≤i≤n-1，則必須將表中位置i+1，i+2，…，n的結點，依次前移到位置i，i+1，…，n-1上，以填補洗掉操作造成的空缺，
- 3，該表長度減1
洗掉演算法的分析
- 假設線性表中含有n個資料元素，在進行洗掉操作時，有n個位置可洗掉;每個位置洗掉資料的概率是：1/n，在i位置洗掉時，要移動n-i個資料；
- 假定在n個位置上洗掉元素的可能性均等，則平均移動元素的個數為：(n-1)/2;平均時間復雜度O(n)
插入和洗掉的結論：順序存盤結構表示的線性表，在做插入或洗掉操作時，平均需要移動大約一半的資料元素，當線性表的資料元素量較大，并且經常要對其做插入或洗掉操作時，這一點需要值得考慮，
===================定位=================
定位(查找):定位運算LocateSeqlist(L,X)的功能是求L中值等于X的結點序號的最小值，當不存在這種結點時結果為0，
演算法的程序：從第一個元素 a1 起依次和x比較，直到找到一個與x相等的資料元素，則回傳它在順序表中的存盤下標或序號；或者查遍整個表都沒有找到與 x 相等的元素，回傳0，
演算法分析：
- 最好情況下，第1個元素就是x值，此時查找比較次數為1，
- 最壞情況下，最后1個元素是x值，此時查找比較次數為n，
- 故平均查找長度為(n+1)/2，平均時間復雜度O(n)
三、線性表的鏈接存盤
鏈式存盤的結構：資料項 + 指標項
鏈表（Link List）：使用鏈式存盤的線性表
鏈表的具體存盤表示為:用一組任意的存盤單元來存放; 鏈表中結點的邏輯次序和物理次序不一定相同，還必須存盤指示其后繼結點的地址資訊，
所有結點通過指標鏈接而組成單鏈表
NULL稱為空指標
Head稱為 頭指標變數，存放鏈表中第一個結點地址；在單鏈表中，增加頭結點的目的是方便運算的實作
鏈表的表示：由于我們常常只注重結點間的邏輯順序，不關心每個結 點的實際位置，可以用箭頭來表示鏈域中的指標，單鏈表就 可以表示為下圖形式，
單鏈表特點：
? 起始節點又稱為首結點，無前驅，故設頭指標head 指向開始結點，
? 鏈表由頭指標唯一確定，單鏈表可以用頭指標的名字 來命名，頭指標名是head的鏈表可稱為表head，
? 終端結點又稱尾結點，無后繼，故終端結點的指標域 為空，即NULL
? 除頭結點之外的結點為表結點
? 為運算操作方便，頭結點中不存資料
單鏈表的基本運算
=====================初始化=====================
空表由一個頭指標和一個頭結點組成；在演算法中，變數head是鏈表的頭指標，它指向新創建的結點，即頭結 點，一個空單鏈表僅有一個頭結點，它的指標域為NULL，
====================求表長====================
在單鏈表存盤結構中，線性表的長度等于單鏈表所 含結點的個數（不含頭結點）
步驟：
1，令計數器j為0
2，令p指向頭結點
3，當下一個結點不空時，j加1，p指向下一個結點
4，j的值即為鏈表中結點個數，即表長度
=================讀表元素:查找第i個結點============
步驟：
1、令計數器j為0
2、令p指向頭結點
3、當下一個結點不空時，并且j<i 時，j加1，p指向下一個結點
4、如果j等于i，則p所指結點為要找的第i結點否則，鏈表中無第i結點
===============定位=================
定位運算是對給定表元素的值，找出這個元素的位置，對 于單鏈表，給定一個結點的值，找出這個結點是單鏈表的 第幾個結點，定位運算又稱為按值查找，
具體步驟：
1、令p指向頭結點
2、令i=0
3、當下一個結點不空時，p指向下一個結點,同時i的值加1
4、直到p指向的結點的值為x，回傳i+1的值，
5、如果找不到結點值為x的話，回傳值為0
===================插入====================
===========洗掉===========
洗掉運算是將表的第i個結點刪去，
（1）找到ai-1的存盤位置p
（2）令p-＞next指向ai的直接后繼結點
（3）釋放結點ai的空間，將其歸還給"存盤池" ，
free(p)是必不可少的，因為當一個結點從鏈表移出后，如果不釋放它的空間，它將變成一個無用的結點，它會一直占用著系統記憶體空間，其他程式將無法使用這塊空間，
四、單項回圈鏈表
普通鏈表的終端結點的next值為NULL；回圈鏈表的終端結點的next指向頭結點，在回圈鏈表中，從任一結點出發能夠掃描整個鏈表，
如何找到回圈鏈表的尾結點：在回圈鏈表中附設一個 rear 指標指向尾結點，適用于經常使用頭尾結點的鏈表操作中
若p為指向回圈鏈表中某鏈結點的指標變數，判斷回圈鏈表是否只有一個結點的標志是：p->next=p
五、雙向回圈鏈表
在鏈表中設定兩個指標域，一個指向后繼結點，一個指向前驅結點這樣的鏈表叫做雙向鏈表
雙向回圈鏈表適合應用在需要經常查找結點的前驅和后繼的場合，找前驅和后繼的復雜度均為：O(1)
雙向鏈表中結點的洗掉：設p指向待刪結點，洗掉*p可通過下述陳述句完成：
- (1)p->prior->next=p->next; //p前驅結點的后鏈指向p的后繼結點
- (2)p->next->prior=p->prior; //p后繼結點的前鏈指向p的前驅結點
- (3)free(p); //釋放*p的空間；（1）、（2）這兩個陳述句的執行順序可以顛倒，
雙向鏈表中結點的插入：在p所指結點的后面插入一個新結點*t，需要修改四個指標
- (1)t->prior=p;
- (2)t->next=p->next;
- (3)p->next->prior=t;
- (4)p->next=t;
六、順序實作與鏈式實作的比較
線性表與鏈表的優缺點：
(1)單鏈表的每個結點包括資料域與指標域，指標域需要占用額外空間，
(2)從整體考慮，順序表要預分配存盤空間，如果預先分配得過大，將造成浪費，若分配得過小，又將發生上溢；單鏈表不需要預先分配空間，只要記憶體空間沒有耗盡，單鏈表中的結點個數就沒有限制，
(3)、插入、洗掉操作，順序表需要移動元素，而鏈表不需要移動元素
時間性能的比較
順序表
- 讀表元 O（1）
- 定位（找x） O（n）
- 插入O（n）
- 洗掉O（n）
鏈表
- 讀表元O（n）
- 定位（找x）O（n）
- 插入O（n）
- 洗掉O（n）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/75842.html
標籤：其他
上一篇：perl-Compress-Zlib-2.020-129.el6.x86_64.rpm怎么安裝
下一篇：演算法與時空復雜度