線性表： 定義：由零個或多個數據元素組成的有限序列。 首先他是一個序列，也就是說元素之間是有先來後到 若元素存在多個，則第一個元素無前驅，最後一個元素無後繼，其他元素有且只有一個前驅和後繼 另外，線性表強調是有限的。 數學語言的定義： 若將線性表記為(a1，...，ai-1，ai，ai+1，...a ...
線性表：
定義：由零個或多個數據元素組成的有限序列。
- 首先他是一個序列，也就是說元素之間是有先來後到
- 若元素存在多個，則第一個元素無前驅，最後一個元素無後繼，其他元素有且只有一個前驅和後繼
- 另外，線性表強調是有限的。
數學語言的定義：
若將線性表記為(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_len=ListLength(*La); Lb_len=ListLength(Lb); for(i=1;i<Lb_len;i++) { GetElem(Lb,i,&e); if(！LocateElem(*La,e)) { ListInsert(La,++La_len,e); } } }
我們可以想象，線性表有兩種物理存儲結構：順序存儲結構和鏈式存儲結構
線性表的順序存儲結構，指的是用一段地址連續的存儲單元依次存儲線性表的數據元素
線性表（a1,a2,...,an）的順序存儲如下：
| a1 | a2 | a3 | a4 | ... | ai-1 | ai | ai+1 | ... | an |
線性表順序存儲結構代碼：
#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[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; }
上海華頌商旅汽車租賃服務有限公司
