1、什么是線性表

? 線性表是具有相同數據類型的n(n>=0)個數據元素的有限序列，其中n為表長，當n=0時線性表是一個空表，若用L命名線性表，則其一般表示為

? L = （a₁，a₂，…，a_i，a_i+1，…，a_n）

如圖所示：

每個數據類型都相同，也意味著每個數據元素所占空間一樣大

重要概念：

1. a_i是線性表中的“第i個”元素線性表中的位序
2. a₁是表頭元素；a_n是表尾元素
3. 除第一個元素外，每個元素有且僅有一個直接前驅；除最后一個元素外，每個元素有且僅有一個直接后繼

2、線性表的基本操作

常用操作：

• InitList(&L):初始化表。構造一個空的線性表L，分配內存空間
• DestroyList(&L):銷毀操作。銷毀線性表，并釋放線性表L所占用的內存空間。
• ListInsert(&Li,e):插入操作。在表L中的第i個位置上插入指定元素e。
• ListDelete(&L,i,&e):刪除操作。刪除表L中第i個位置的元素，并用e返回刪除元素的值。
• LocateElem(L,e):按值查找操作。在表L中查找具有給定關鍵字值的元素
• GetElem(L,i):按位查找操作。獲取表L中第i個位置的元素的值。

其他常用操作：

• Length(L):求表長。返回線性表L的長度，即L中數據元素的個數
• PrintList(L):輸出操作。按前后順序輸出線性表L的所有元素值。
• Empty(L):判空操作。若L為空表，則返回true，否則返回false。

Tips:

1. 數據元素的位序是從1開始，而程序數組下標是0開始
2. 在實際開發中，可根據實際需求定義其他的基本操作

3、順序表

3.1、順序表的定義

? 順序表指的是用順序存儲的方式來實現線性表的順序存儲。把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來體現。

3.2、順序表的實現方式：靜態分配

#define MaxSize 10		//定義最長長度
typedef struct{ElemType data[MaxSize];	//用靜態的數組存放數據int length;				//順序表當前長度
}SqList;		//順序表的類型定義(靜態分配方式)

**問題：**如果數組數組存滿了呢？

• 直接放棄治療，順序表的表長剛開始就確定后，無法更改（存儲空間是靜態的）

**思考：**如果剛開始就聲明一個很大的內存空間呢？存在什么問題？

• 過于浪費

3.3、順序表的實現方式：動態分配

#define InitSize 10		//順序表的初始長度
typedef struct{ElemType *data;	//指示動態分配數組的指針int MaxSize;	//順序表的最大容量int length;		//順序表的當前長度
}SeqList;		//順序表的類型定義(動態分配方式)

3.4、順序表的特點

1. 隨機訪問，即可以在o(1)時間內找到第i個元素
2. 存儲密度高，每個節點只存儲數據元素
3. 拓展容量不方便(即便采用動態分配的方式實現，拓展長度的時間復雜度也比較高)

3.5、順序表的初始化與插入操作

初始化順序表

#define MaxSize 50
typedef int ElemType; //讓順序表存儲其他類型元素時，可以快速改變代碼
//靜態分配
typedef struct {ElemType data[MaxSize];int length; //順序表長度
}SqList;

順序表插入

//順序表插入，因為L會改變，所以要引用
bool ListInsert(SqList &L,int pos,ElemType elemType){//判斷pos是否合法if(pos <= 1 || pos >= L.length + 1){return false;}//如果順序表滿了，也不能進行插入if(L.length == MaxSize){return false;}//將元素依次往后面移動for (int i = L.length; i >= pos; i--) {L.data[i] = L.data[i-1];}L.data[pos-1] = elemType; //存入數據L.length++;       //順序表長度+1return true;}

打印順序表

//打印順序表
void PrintList(SqList L){for (int i = 0; i < L.length; ++i) {printf("%3d",L.data[i]);}
}

在主函數中調用

//順序表的初始化與插入
int main() {SqList L;  //定義一個順序表bool result;L.data[0] = 1;  //放置元素L.data[1] = 2;L.data[2] = 3;L.length = 3; //設置順序表元素為3result = ListInsert(L,2,2);if(true == result){printf("success");} else{printf("error");}PrintList(L);return 0;
}

3.6、順序表的刪除與查詢

刪除元素

//刪除順序表中的元素
bool ListDelete(SqList &L,int pos,ElemType &del){//判斷刪除元素位置是否合法if(pos < 1 || pos > L.length ){return false;}del = L.data[pos-1];  //保存刪除元素的值//從當前下標開始，往前移動for (int i = pos;  i < L.length; i++) {L.data[i - 1] = L.data[i];}L.length--;return true;
}

查詢元素

//查詢元素位置
int LocateElem(SqList L,ElemType elemType){//遍歷順序表for (int i = 0; i < L.length; ++i) {if(L.data[i] == elemType){  //如果元素相同return i+1; //返回下標+1}}return 0;
}