順序存盤的定義：
定義：由零個或多個資料元素組成的有限序列，
- 首先他是一個序列，也就是說元素之間是有先來后到
- 若元素存在多個，則第一個元素無前驅，最后一個元素無后繼，其他元素有且只有一個前驅和后繼
- 另外，線性表強調是有限的，
數學語言的定義：
若將線性表記為(a1，...，ai-1，ai，ai+1，...an)，則表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素，
所以線性表元素的個數n定義線性表的長度，當n=0是，則稱為空表
例如：公司的組織架構是否屬于線性關系? 否，星座也屬于一種線性表
在較為復雜的線性表中，一個資料元素也可以由若干個資料項組成
抽象資料型別：
資料型別：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱，
例如很多編程語言的整型，浮點型，字符型這些指的就是資料型別，
例如在C語言中，按照取值的不同，資料型別可以分為兩類：
- 原子型別：不可以在分解的基本型別，例如整型、浮點型、字符型等，
- 結構型別：由若干個型別組合而成的，是可以在分解的，例如整型是由若干個整型資料組成的
抽象：是指抽取的事務具有普遍性的本質，他要求抽出問題的特征而忽略非本質的細節，是對具體事物的一個概括，抽象是一種思考問題的方式，它隱藏了繁雜的細節，
我們對已有的資料型別進行抽象，就有了抽象資料型別，
抽象資料型別是指一個數學模型及定義在該模型上的一組操作，
抽象資料型別的定義僅僅取決于它的一組邏輯特性，而與其在計算機內部如何表示和實作無關，
例如：1+1=2，在不同CPU的處理上可能不一樣，但由于其定義的數學特性相同，所以在計算機編程者來看，他們都是相同的，
"抽象"的意義在于資料型別的數學抽象特性，
而且，抽象資料型別不僅僅是指那些已經定義并實作的資料型別，還可以是計算機編程者在設計軟體程式時自己定義的資料型別，
抽象資料型別的標準格式：
ADT 抽象資料型別名
Data
資料元素之間邏輯關系的定義
Operation
操作
endADT
線性表的抽象資料型別
線性表的抽象資料型別定義：
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
對于不同的應用，線性表的基本操作是不同的，上述操作時最基本的，對于實際問題中涉及的關于線性表的更復雜操作，完全可以用這些基本操作的組合來實作
例如集合A{A,C,D}，集合B{A,C,W}，
其實仔細思考一下，我們只需要回圈遍歷集合B中的每個元素，判斷當前元素是否在A中，若不存在，則插入A中即可，
需要的基本操作組合：ListLength(L);GetElem(L,i,*e);LocateElem(L,e);ListInsert(*L,i,e);
//La表示A集合，Lb表示B集合 void unionL(List *La,list Lb) { int La_len,Lb_len,i; ElemType e;/*宣告一個La和Lb相同的資料元素e*/ La_len=ListLength(*La);/*得到線性表的長度*/ Lb_len=ListLength(Lb); for(i=1;i<Lb_len;i++)/*回圈遍歷Lb*/ { GetElem(Lb,i,&e);將線性表的第i個位置的元素回傳給e if(！LocateElem(*La,e))進行判斷，是否在La中存在e { ListInsert(La,++La_len,e);/*不存在 將e插入到La的最后一個位置*/ } } }
我們可以想象，線性表有兩種存盤結構：順序存盤結構和鏈式存盤結構
線性表的順序存盤結構，指的是用一段地址連續的存盤單元依次存盤線性表的資料元素
線性表（a1,a2,...,an）的順序存盤如下：
| a1 | a2 | a3 | a4 | ... | ai-1 | ai | ai+1 | ... | an |
線性表順序存盤結構代碼：
#define MAXSIZE 20 /*開始為存盤空間分配空間*/ typedef int ElemType; ElemType型別根據實際情況而定，這假設為Int typedef struct { ElemType data[MAXSIZE];/*陣列 存盤資料元素，最大值為MAXSIZE*/ int length;//線性表當前的長度 } SqList;
這里我們封裝了一個結構，事實上就是對陣列進行封裝，增加當前長度的變數，
總結：順序存盤結構封裝需要三個屬性：
- 存盤空間的起始位置，陣列data，它的存盤位置就是線性表存盤空間的存盤位置，
- 線性表的最大存盤容量：陣列長度MAXSIZE.
- 線性表的當前長度：length.
注意：陣列的長度與線性表的當前長度需要區分：陣列的長度是存放線性表的存盤空間的總長度，一般初始化后不變，而線性表的當前長度是線性表中元素的個數，是會發生變化的，
任意時刻，線性表的長度應該小于等于陣列的長度
地址計算方法：
存盤器中的每個存盤單元都有自己的編號，這個編號稱為地址
陣列是從0開始計算，而線性表是從1開始
假設ElemType占用的是c個存盤單元（位元組），那么線性表中第i+1個資料元素和第i個資料元素的存盤關系是（LOC表示獲得存盤位置的函式）：LOC(ai+1)=LOC(ai)+c
所以對于第i個資料元素ai的存盤位置可以由a1推算得出：LOC(ai)=LOC(a1)+(i-1)*c
| 元素 | a1 | a2 | ... | ai-1 | ai | ... | an | 空閑空間 |
| 下標 | 0 | 1 | ... | i-2 | i-1 | ... | n-1 |
根據這個公式，我們可以計算出線性表中任意位置的地址，不管它是第一個還是最后一個，都是相同的時間，那么它的存盤時間性能當然就為O(1)，我們通常稱為隨機存盤結構，
順序存盤結構的獲取與洗掉
獲取元素的操作：
例如：實作GetElem的具體操作，即將線性表L中的第i個位置元素值回傳，注意回傳型別Status是一個整型
#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; //Status是函式的型別，其值是函式結果的狀態代碼，如OK等， //初始條件：順序線性標L已經存在，1<=i<=ListLength(L) //操作結果：用e回傳L中第i個資料元素的值， Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0||i<1||i>L.length) { return ERROR; } *e=L.data[i-1]; return OK; }
插入操作：
線性表的順序存盤結構具有隨機存盤結構的特點，時間復雜度為O(1)，
如果要實作ListInsert(*L,i,e)，既在線性表L中的第i個位置插入新元素e，代碼如何實作，
實作插入操作的思路：
- 如果插入位置不合理，拋出例外；
- 如果線性表的長度大于等于陣列長度則拋出例外或動態增加陣列容量；
- 從最后一個元素開始向前遍歷到第i個位置，分別將他們都向后移動一個位置；
- 將要插入的元素填入第i個位置；
- 線性表長度+1；
/*初始條件：順序線性表L已存在，1<=i<=ListLength(L),*/ /*操作結果：在L中第i個位置之前插入新的資料元素e，L長度+1*/ Status ListInsert (SqList *L,int i,ElemType e) { int l; if(L->length==MAXSIZE)//順序線性表已滿 { return ERROR; } if(i<1||i>L->length+1)//當i不在范圍內時 { return ERROR; } if(i<=L-<length)//若插入資料位置不在表尾 { //若要插入資料，則向后移動一位 for(k=L->length-1;k>=i-1;k--) { L->data[k+1]=L->data[k]; } } L->data[i-1]=e; L->length++; return OK; }
洗掉操作
洗掉操作思路：
- 洗掉的位置不合理，拋出例外
- 取出洗掉元素
- 從洗掉元素位置開始遍歷到最后一個元素位置，分別將他們向前移動一個位置
- 表長度減一
具體實作代碼
Staus delete(*L,int i,ElemType *e){ int k; if(L->Length==0) 如果線性表長度為0 rerurn ERROR; if(i<1||i>L->Length) rerurn ERROR; *e=L->data[i-1]; if(i<L->length){/*如果洗掉的不是最后一個位置，直接將線性變的長度-1，可以自動洗掉最后一個元素*/ for(k=1;k<L->length;k++){ /*將洗掉位置后繼怨怒是前移*/ L->data[k-1]=L->data[k]; } L-length--; return OK; } }
分析插入和洗掉的時間復雜度：
插入和洗掉均是最后一個元素的時候，此時的時間復雜度為O(1)，做這些操作不需要移動其他元素；
最歡的情況是插入或洗掉第一個元素，意味著所有元素都得向后或者向前移動，此時的時間復雜度為O(n);
至于平均情況，由于插入或者洗掉第i個元素，需要移動n-i個元素，每個位置插入或者洗掉元素的可能性相同，也就是說位置越向前，移動的元素越多，位置越靠后移動的元素越少，最終移動次數和中間那個元素的移動次數相同，為(n-1)/2
根據時間復雜度的推導平均時間復雜度還是O(n)，
對于線性存盤結構的優缺點：
優點：
- 無需為表示表中元素之間的邏輯關系而額外的存盤空間
- 可以快速的存取表中任一位置的元素
缺點：
- 插入和洗掉操作需要移動大量的元素
- 當線性表變化較大時，難以確定存盤空間的容量
- 造成存盤空間的“碎片”
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/9966.html
標籤：C