一、線性表的定義 ###1.1 定義 ###? n個(n ≥ 0)具有相同特性的資料元素的有限序列，L =（a1, a2, … ai-1，ai，ai＋1，… an），n是線性表的長度
###1.2 特點 ###? 表中元素個數有限 ###? 表中元素具有順序性 ###? 表中元素資料型別相同 ###? 表中元素具有抽象性
二、線性表的順序表示與基本操作 ###2.1 線性表的順序表示
###? 定義：指的是用一組地址連續的存盤單元依次存盤線性表中的資料元素 ###【注意】
| 線性表的順序存盤又稱為順序表 |
| 邏輯上相鄰的資料元素，物理上也相鄰 |
| 順序表是隨機存取的存盤結構 |
| 若已知表中首元素在存盤器中的位置，則可求出線性表中其他元素的存放位置 |
| 線性表的起始地址為a1,稱作線性表的基地址 |
###2.2 順序表的型別描述
//no.1 **靜態分配**
#define MaxSize 50//宏
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
SqList L;
L.data[0] = 0;
L.length = 1;
//no.2 **動態分配**
#define InitSize 50
typedef int ElemType;
typedef struct{
ElemType *data;
int length,MaxSize;
}SqList;
SqList L;
L.data = https://www.cnblogs.com/lastk/p/(ElemType *)malloc(sizeof(ElemType)*InitSize);
L.data[0] = 0;
L.length = 1;
L.MaxSize = InitSize;//當空間不足時，呼叫realloc()函式
###2.3 順序表基本操作-初始化操作 ###目標：構造一個空表，設定表的起始位置、表長及可用空間
#define OK 1
#define OVERFLOW 0
//構造一個空的線性表L
int InitSqList(SqList &L){
L.data = https://www.cnblogs.com/lastk/p/(ElemType *)malloc(sizeof(ElemType)*InitSize);
if(!L.data)
exit(OVERFLOW); // 存盤分配失敗
L.length = 0; // 空表長度為0
L.MaxSize = InitSize; // 初始存盤容量
return OK;
}
###2.4 順序表基本操作-插入操作
###目標：在順序表L的第i(1≤i≤L.length+1)個位置插入新元素e
###【注意】當插入的位置為第i個結點時，需要移動 n-i+1 個元素
int ListInsert(SqList &L,int i,ElemType e)
{
if(i<1||i>L.length+1)//判斷插入位置i 是否合法
return ERROR;
if(L.length>=MaxSize)//判斷順序表的存盤空間是否已滿
return ERROR;
for(int j =L.length;j>=i;j--)
L.data[j] = L.data[j-1];//將第n至第i 位的元素依次向后移動一個位置，空出第i個位置
L.data[i-1] = e;//將要插入的新元素e放入第i個位置
L.length++;
return OK;//表長加1，插入成功回傳OK
}
該演算法的時間復雜度分析：
最好情況：在表尾插入（即i = n+1）此時為O(1)
最壞情況：在表頭插入（即i = 1）此時為O(n)
平均情況：平均時間復雜度為O(n)
###2.5 順序表基本操作-洗掉操作
###目標：洗掉順序表L的第i(1≤i≤L.length)個位置的元素，并將洗掉的元素用參考變數回傳
###【注意】當洗掉的位置為第i個結點時，需要移動 n-i 個元素
int ListDelete(SqList &L,int i,ElemType &e)
{
if(i<1||i>L.length)//判斷洗掉位置i 是否合法（合法值為1≤i≤n）
return ERROR;
e = L.data[i-1];//將欲洗掉的元素保留在e中
for(int j = i;j<L.length;j++)
L.data[j-1] = L.data[j];//將第i+1至第n 位的元素依次向前移動一個位置
L.length--;
return OK;//表長減1，洗掉成功回傳
}
該演算法的時間復雜度分析：
最好情況：在表尾洗掉（即i = n）此時為O(1)
最壞情況：在表頭洗掉（即i = 1）此時為O(n)
平均情況：平均時間復雜度為O(n)
###2.6 順序表基本操作-獲取指定位置的資料元素 ###目標：獲取順序表L的第i(1≤i≤L.length)個位置的元素，并將其用參考變數e回傳
int GetElem(SqList L,int i,ElemType &e)
{
if(i<1||i>L.length)
return ERROR;
e = L.data[i-1];
return OK;
}
//對比洗掉操作代碼
int ListDelete(SqList &L,int i,ElemType &e)
{
if(i<1||i>L.length)
return ERROR;
e = L.data[i-1];
for(int j = i;j<L.length;j++)
L.data[j-1] = L.data[j];
L.length--;
return OK;
}
###2.7 順序表基本操作-按值查找操作 ###目標：在順序表L中查找第一個元素值等于e的元素，并回傳其位序
int LocateElem(SqList L,ElemType e)
{
int i;
for(i = 0;i<L.length;i++)//從順序表的第1個元素開始，依次判斷其值是否為e
if(L.data[i]==e)//若不是e，則繼續判斷下一個元素
return i+1;//若是e，則回傳當前元素所在的位序
return 0;
}
該演算法的時間復雜度分析：
最好情況：查找元素在表頭此時僅比較1次，故為O(1)
最壞情況：查找元素在表尾（或不存在）此時需比較n次，故為O(n)
平均情況：平均時間復雜度為O(n)
查看更多
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73579.html
標籤：其他