1.線性表
線性表（英語：Linear List）是由n（n≥0）個元素（）a[0]，a[1]，a[2]…，a[n-1]組成的。
其中：
- 數據元素的個數n定義為表的長度 = “list”.length() （”list”.length() = 0（表裡沒有一個元素）時稱為空表）
- 將非空的線性表（n>=1）記作：（a[0]，a[1]，a[2]，…，a[n-1]）
- 數據元素a[i]（0≤i≤n-1）只是個抽象符號，其具體含義在不同情況下可以不同
一個數據元素可以由若干個數據項組成。數據元素稱為記錄，含有大量記錄的線性表又稱為文件。這種結構具有下列特點：存在一個唯一的沒有前驅的（頭）數據元素；存在一個唯一的沒有後繼的（尾）數據元素；此外，每一個數據元素均有一個直接前驅和一個直接後繼數據元素。
2.線性表的存儲結構
- 鏈表
- 單鏈表
- 動態單鏈表
- 靜態單鏈表
- 循環鏈表
- 單循環鏈表
- 雙循環鏈表
- 靜態鏈表
- 單鏈表
3.順序表
利用數組的連續存儲空間順序存放線性表的各元素
3.1結構體定義
如果需要使用自定義的結構體來維護一個順序表，通常來講結構體的元素一般是一個固定大小的數組（可用長度足夠大），以及當前數組存放的元素個數，也即數組的長度
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
int Last;//記錄順序表的最後一個元素的下標
} ;
struct LNode L;
List PtrL;訪問結構體的成員
- 訪問下標為 i 的元素：L.Data[i] 或 PtrL->Data[i]
- 線性表的長度：L.Last+1 或 PtrL->Last+1
- 指針變量PtrL還可以這樣訪問兩個屬性
(*PtrL).Data[i]和(*PtrL).Last，不過這種訪問方式並不常用
而一般來講，為了簡單，不會去維護這樣一個結構體，(因為一旦維護了這個結構體，就需要去封裝相應的函數，比如說常見的插入、刪除、查找等操作)，而是直接類似下面這樣
ElementType data[MaxSize];
int length;定義一個足夠大的數組，然後定義一個對應關聯的變量來時刻維護數組的長度。
這兩種定義方式沒有什麼區別，一種是把常用操作封裝好，方便調用，另一種則是需要時刻自己維護對應的屬性。因為順序表的結構足夠簡單，所以不定義結構體也是可以的。
3.2順序表的常見操作
為了方便，這一節內容記錄的都是在定義的結構體基礎上，封裝的常見操作。
1.初始化
List MakeEmpty( ) {
List PtrL;
PtrL = (List )malloc( sizeof(struct LNode) );
PtrL->Last = -1;
return PtrL;
}初始化的順序表，長度為0，所以Last為-1
2.查找
int Find( ElementType X, List PtrL ) {
int i = 0;
while( i <= PtrL->Last && PtrL->Data[i]!= X )
i++;
if (i > PtrL->Last) return -1; /* 如果沒找到，返回-1 */
else return i; /* 找到后返回的是存儲位置 */
}查找操作比較簡單，從順序表的第一個元素（下標為0開始）開始遍歷。
還有一種更加巧妙一點的實現方式，就是引入哨兵思想。
int Find( ElementType X, List PtrL ) {
PtrL->Data[0] = x;//順序表第一個元素就是哨兵，賦值為x
int i = PtrL->Last;//從最後一個元素開始遍歷
while( PtrL->Data[i]!= X )
i--;
return i;
}這樣做的好處很明顯，少了邊界的判斷，可以優化時間複雜度，編碼也更加簡單。
注意：這裏把下標為0的元素設置為哨兵，則要求順序表從下標為1開始存儲。而且，函數如果沒有找到，則一定返回i=0
3.插入
看圖示應該要注意，移動的方向是從后往前移，如果從前往後移，則Data[i]=Data[i+1]=…=Data[n]，因為後面的元素都被前面移過來的元素給覆蓋了。
void Insert( ElementType X, int i, List PtrL ) {
int j;
if ( PtrL->Last == MAXSIZE-1 ) { /* 表空間已滿，不能插入*/
printf(＂表滿＂);
return;
}
if ( i < 1 || i > PtrL->Last+2) { /*檢查插入位置的合法性*/
printf(＂位置不合法＂);
return;
}
for ( j = PtrL->Last; j >= i-1; j-- )
PtrL->Data[j+1] = PtrL->Data[j]; /*將 ai～ an倒序向後移動*/
PtrL->Data[i-1] = X; /*新元素插入*/
PtrL->Last++; /*Last仍指向最後元素*/
return;
}為什麼這裏需要判斷順序表的空間是否已滿？
因為這個數組，是在初始化之後就固定了數組可容納的元素個數MaxSize，一旦超出，則程序下標就會越界。C++提供了動態數組vector，可以很方便的支持動態擴展數組長度，而且基本的插入刪除等操作都封裝好了，可以很方便的使用。
4.刪除
同樣的，需要注意元素移動的方向，如果從后往前移，則最後面的元素會一直覆蓋到Data[i]。
void Delete( int i, List PtrL ) {
int j;
if( i < 1 || i > PtrL->Last+1 ) { /*檢查空表及刪除位置的合法性*/
printf (“不存在第%d個元素”, i );
return ;
}
for ( j = i; j <= PtrL->Last; j++ )
PtrL->Data[j-1] = PtrL->Data[j]; /*將 ai+1～ an順序向前移動*/
PtrL->Last--; /*Last仍指向最後元素*/
return;
}5.排序
因為排序算法比較多，本文不展開講解，可以參考以下博文，內容包括了常見的十大排序算法的算法分析，時間複雜度和空間複雜度分析以及c實現和動圖圖解。
4.鏈表
不要求邏輯上相鄰的兩個元素物理上也相鄰；通過“鏈”建立起數據元素之間的邏輯關係。插入、刪除不需要移動數據元素，只需要修改“鏈”。
4.1單鏈表
typedef struct LNode *List;
struct LNode {
ElementType Data;
List Next;
};
struct Lnode L;
List PtrL;1.求表長
int Length ( List PtrL ) {
List p = PtrL; /* p指向表的第一個結點*/
int j = 0;
while ( p ) {
p = p->Next;
j++; /* 當前p指向的是第 j 個結點*/
}
return j;
}時間複雜度O(n)
2.查找
按序查找
List FindKth( int K, List PtrL ) {
List p = PtrL;
int i = 1;
while (p !=NULL && i < K ) {
p = p->Next;
i++;
}
if ( i == K ) return p;
/* 找到第K個，返回指針 */
else return NULL;
/* 否則返回空 */
}時間複雜度O(n)
按值查找
List Find( ElementType X, List PtrL ) {
List p = PtrL;
while ( p!=NULL && p->Data != X )
p = p->Next;
return p;
}時間複雜度O(n)
3.插入
（1）先構造一個新結點，用s指向；
（2）再找到鏈表的第 i-1個結點，用p指向；
（3）然後修改指針，插入結點 ( p之後插入新結點是 s)
List Insert( ElementType X, int i, List PtrL ) {
List p, s;
if ( i == 1 ) { /* 新結點插入在表頭 */
s = (List)malloc(sizeof(struct LNode)); /*申請、填裝結點*/
s->Data = X;
s->Next = PtrL;
return s; /*返回新表頭指針*/
}
p = FindKth( i-1, PtrL ); /* 查找第i-1個結點 */
if ( p == NULL ) { /* 第i-1個不存在，不能插入 */
printf("參數i錯");
return NULL;
} else {
s = (List)malloc(sizeof(struct LNode)); /*申請、填裝結點*/
s->Data = X;
s->Next = p->Next; /*新結點插入在第i-1個結點的後面*/
p->Next = s;
return PtrL;
}
}4.刪除
（1）先找到鏈表的第 i-1個結點，用p指向；
（2）再用指針s指向要被刪除的結點（p的下一個結點）;
（3）然後修改指針，刪除s所指結點;
（4）最後釋放s所指結點的空間。
List Delete( int i, List PtrL ) {
List p, s;
if ( i == 1 ) { /* 若要刪除的是表的第一個結點 */
s = PtrL; /*s指向第1個結點*/
if (PtrL!=NULL) PtrL = PtrL->Next; /*從鏈表中刪除*/
else return NULL;
free(s); /*釋放被刪除結點 */
return PtrL;
}
p = FindKth( i-1, PtrL ); /*查找第i-1個結點*/
if ( p == NULL ) {
printf("第%d個結點不存在", i-1);
return NULL;
} else if ( p->Next == NULL ) {
printf("第%d個結點不存在", i);
return NULL;
} else {
s = p->Next; /*s指向第i個結點*/
p->Next = s->Next; /*從鏈表中刪除*/
free(s); /*釋放被刪除結點 */
return PtrL;
}
}4.2雙鏈表
雙向鏈表，又稱為雙鏈表，是的一種，它的每個數據結點中都有兩個，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;4.3循環鏈表
4.3.1單循環鏈表
存儲結構和單鏈表相同。
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
// 設立尾指針的單循環鏈表的12個基本操作
void InitList(LinkList *L) { // 操作結果：構造一個空的線性表L
*L = (LinkList)malloc(sizeof(struct LNode)); // 產生頭結點，並使L指向此頭結點
if (!*L) // 存儲分配失敗
exit(OVERFLOW);
(*L)->next = *L; // 指針域指向頭結點
}
void DestroyList(LinkList *L) { // 操作結果：銷毀線性表L
LinkList q, p = (*L)->next; // p指向頭結點
while (p != *L) { // 沒到表尾
q = p->next;
free(p);
p = q;
}
free(*L);
*L = NULL;
}
void ClearList(LinkList *L) /* 改變L */ { // 初始條件：線性表L已存在。操作結果：將L重置為空表
LinkList p, q;
*L = (*L)->next; // L指向頭結點
p = (*L)->next; // p指向第一個結點
while (p != *L) { // 沒到表尾
q = p->next;
free(p);
p = q;
}
(*L)->next = *L; // 頭結點指針域指向自身
}
Status ListEmpty(LinkList L) { // 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE
if (L->next == L) // 空
return TRUE;
else
return FALSE;
}
int ListLength(LinkList L) { // 初始條件：L已存在。操作結果：返回L中數據元素個數
int i = 0;
LinkList p = L->next; // p指向頭結點
while (p != L) { // 沒到表尾
i++;
p = p->next;
}
return i;
}
Status GetElem(LinkList L, int i, ElemType *e) { // 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR
int j = 1; // 初始化，j為計數器
LinkList p = L->next->next; // p指向第一個結點
if (i <= 0 || i > ListLength(L)) // 第i個元素不存在
return ERROR;
while (j < i) { // 順指針向後查找，直到p指向第i個元素
p = p->next;
j++;
}
*e = p->data; // 取第i個元素
return OK;
}
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 初始條件：線性表L已存在，compare()是數據元素判定函數
// 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。
// 若這樣的數據元素不存在，則返回值為0
int i = 0;
LinkList p = L->next->next; // p指向第一個結點
while (p != L->next) {
i++;
if (compare(p->data, e)) // 滿足關係
return i;
p = p->next;
}
return 0;
}
Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e) { // 初始條件：線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，
// 否則操作失敗，pre_e無定義
LinkList q, p = L->next->next; // p指向第一個結點
q = p->next;
while (q != L->next) { // p沒到表尾
if (q->data == cur_e) {
*pre_e = p->data;
return TRUE;
}
p = q;
q = q->next;
}
return FALSE; // 操作失敗
}
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { // 初始條件：線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
// 否則操作失敗，next_e無定義
LinkList p = L->next->next; // p指向第一個結點
while (p != L) { // p沒到表尾
if (p->data == cur_e) {
*next_e = p->next->data;
return TRUE;
}
p = p->next;
}
return FALSE; // 操作失敗
}
Status ListInsert(LinkList *L, int i, ElemType e) /* 改變L */ { // 在L的第i個位置之前插入元素e
LinkList p = (*L)->next, s; // p指向頭結點
int j = 0;
if (i <= 0 || i > ListLength(*L) + 1) // 無法在第i個元素之前插入
return ERROR;
while (j < i - 1) { // 尋找第i-1個結點
p = p->next;
j++;
}
s = (LinkList)malloc(sizeof(struct LNode)); // 生成新結點
s->data = e; // 插入L中
s->next = p->next;
p->next = s;
if (p == *L) // 改變尾結點
*L = s;
return OK;
}
Status ListDelete(LinkList *L, int i, ElemType *e) /* 改變L */ { // 刪除L的第i個元素，並由e返回其值
LinkList p = (*L)->next, q; // p指向頭結點
int j = 0;
if (i <= 0 || i > ListLength(*L)) // 第i個元素不存在
return ERROR;
while (j < i - 1) { // 尋找第i-1個結點
p = p->next;
j++;
}
q = p->next; // q指向待刪除結點
p->next = q->next;
*e = q->data;
if (*L == q) // 刪除的是表尾元素
*L = p;
free(q); // 釋放待刪除結點
return OK;
}
void ListTraverse(LinkList L, void(*vi)(ElemType)) { // 初始條件：L已存在。操作結果：依次對L的每個數據元素調用函數vi()
LinkList p = L->next->next; // p指向首元結點
while (p != L->next) { // p不指向頭結點
vi(p->data);
p = p->next;
}
printf("\n");
}4.3.2雙循環鏈表
// 線性表的雙向鏈表存儲結構
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;
// 帶頭結點的雙向循環鏈表的基本操作(14個)
void InitList(DuLinkList *L) {
// 產生空的雙向循環鏈表L
*L = (DuLinkList)malloc(sizeof(DuLNode));
if (*L)
(*L)->next = (*L)->prior = *L;
else
exit(OVERFLOW);
}
void DestroyList(DuLinkList *L) {
// 操作結果：銷毀雙向循環鏈表L
DuLinkList q, p = (*L)->next; // p指向第一個結點
while (p != *L) { // p沒到表頭
q = p->next;
free(p);
p = q;
}
free(*L);
*L = NULL;
}
void ClearList(DuLinkList L) { // 不改變L
// 初始條件：L已存在。操作結果：將L重置為空表
DuLinkList q, p = L->next; // p指向第一個結點
while (p != L) { // p沒到表頭
q = p->next;
free(p);
p = q;
}
L->next = L->prior = L; // 頭結點的兩個指針域均指向自身
}
Status ListEmpty(DuLinkList L) {
// 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE
if (L->next == L && L->prior == L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L) {
// 初始條件：L已存在。操作結果：返回L中數據元素個數
int i = 0;
DuLinkList p = L->next; // p指向第一個結點
while (p != L) { // p沒到表頭
i++;
p = p->next;
}
return i;
}
Status GetElem(DuLinkList L, int i, ElemType *e) {
// 當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR
int j = 1; // j為計數器
DuLinkList p = L->next; // p指向第一個結點
while (p != L && j < i) { // 順指針向後查找，直到p指向第i個元素或p指向頭結點
p = p->next;
j++;
}
if (p == L || j > i) // 第i個元素不存在
return ERROR;
*e = p->data; // 取第i個元素
return OK;
}
int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
// 初始條件：L已存在，compare()是數據元素判定函數
// 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。
// 若這樣的數據元素不存在，則返回值為0
int i = 0;
DuLinkList p = L->next; // p指向第1個元素
while (p != L) {
i++;
if (compare(p->data, e)) // 找到這樣的數據元素
return i;
p = p->next;
}
return 0;
}
Status PriorElem(DuLinkList L, ElemType cur_e, ElemType *pre_e) {
// 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，
// 否則操作失敗，pre_e無定義
DuLinkList p = L->next->next; // p指向第2個元素
while (p != L) { // p沒到表頭
if (p->data == cur_e) {
*pre_e = p->prior->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L, ElemType cur_e, ElemType *next_e) {
// 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
// 否則操作失敗，next_e無定義
DuLinkList p = L->next->next; // p指向第2個元素
while (p != L) { // p沒到表頭
if (p->prior->data == cur_e) {
*next_e = p->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L, int i) { // 另加
// 在雙向鏈表L中返回第i個元素的地址。i為0，返回頭結點的地址。若第i個元素不存在，
// 返回NULL
int j;
DuLinkList p = L; // p指向頭結點
if (i < 0 || i > ListLength(L)) // i值不合法
return NULL;
for (j = 1; j <= i; j++)
p = p->next;
return p;
}
Status ListInsert(DuLinkList L, int i, ElemType e) {
// 在帶頭結點的雙鏈循環線性表L中第i個位置之前插入元素e，i的合法值為1≤i≤表長+1
// 改進算法2.18，否則無法在第表長+1個結點之前插入元素
DuLinkList p, s;
if (i < 1 || i > ListLength(L) + 1) // i值不合法
return ERROR;
p = GetElemP(L, i - 1); // 在L中確定第i個元素前驅的位置指針p
if (!p) // p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅)
return ERROR;
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s)
return OVERFLOW;
s->data = e;
s->prior = p; // 在第i-1個元素之後插入
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}
Status ListDelete(DuLinkList L, int i, ElemType *e) {
// 刪除帶頭結點的雙鏈循環線性表L的第i個元素，i的合法值為1≤i≤表長
DuLinkList p;
if (i < 1) // i值不合法
return ERROR;
p = GetElemP(L, i); // 在L中確定第i個元素的位置指針p
if (!p) // p = NULL,即第i個元素不存在
return ERROR;
*e = p->data;
p->prior->next = p->next; // 此處並沒有考慮鏈表頭，鏈表尾
p->next->prior = p->prior;
free(p);
return OK;
}
void ListTraverse(DuLinkList L, void(*visit)(ElemType)) {
// 由雙鏈循環線性表L的頭結點出發，正序對每個數據元素調用函數visit()
DuLinkList p = L->next; // p指向頭結點
while (p != L) {
visit(p->data);
p = p->next;
}
printf("\n");
}
void ListTraverseBack(DuLinkList L, void(*visit)(ElemType)) {
// 由雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函數visit()
DuLinkList p = L->prior; // p指向尾結點
while (p != L) {
visit(p->data);
p = p->prior;
}
printf("\n");
}4.4靜態鏈表
前面講解的都是動態鏈表，即需要指針來建立結點之間的連接關係。而對有些問題來說結點的地址是比較小的整數（例如5位數的地址），這樣就沒有必要去建立動態鏈表，而應使用方便得多的靜態鏈表。
靜態鏈表的實現原理是hash，即通過建立一個結構體數組，並令數組的下標直接表示結點的地址，來達到直接訪問數組中的元素就能訪問結點的效果。另外，由於結點的訪問非常方便，因此靜態鏈表是不需要頭結點的。靜態鏈表結點定義的方法如下：
struct Node{
typename data;//數據域
int next;//指針域
}node[size];參考資料：
- 《算法筆記》
- 《數據結構和算法》-極客時間專欄
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"
※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線
※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整
※南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!
