文章主要是對于資料結構與演算法課程學習的讀書記錄，歡迎學習交流，
[內容范圍]第二章線性表-順序表和鏈式表概念及其代碼實作，

1 線性表的定義

線性表： n個同型別資料元素的有限序列,記為：
L= (a1，a2,…，ai,…，an)
L為表名；
i為資料元素ai 在線性表中的位序；
n為線性表的表長; n=0 時稱為空表；
資料元素之間的關系是：
ai-1領先于ai，ai領先于ai+1，
稱ai-1是ai的直接前驅，ai+1是ai的直接后繼，
除第一元素a1外，均有唯一的前驅；

2 基于線性表的簡單操作

2.1 合并線性表

演算法設計：
思想：從LB中逐一取出元素，判斷元素是否存在LA中，若不在則將這個元素插入到LA中

//依次從LB中取出第i個資料元素:List_Retrieve(Lb, i, &elem) →elem
//判elem是否在LA中存在:List_Locate(La,elem,&j)
//若不存在，則將elem插入到LA中:List_Insert(La,1,elem)

Status List_Union (SqListPtr La, SqListPtr Lb){
ElemType elem; /* 存放從Lb中取出的元素*/
Status status; /*狀態代碼*/
int i, j, len = List_Size(Lb); /*len存放Lb的元素個數*/
for (i=1; i<=len; i++){
List_Retrieve(Lb, i, &elem); /*取出Lb中第i個資料元素*/
status = List_Locate(La,elem,&j); /*判它是否在La中*/
if(status!= success){ /*如果不在*/
status = List_Insert(La,1,elem); /*插入到第一個位置*/
if(status!= success) break; /*插入失敗則退出*/ }
else List_Add(La,j,1);/*La的第j個資料加1*/
}
return status;
}

2.2 合并有序表

問題：已知線性表La和Lb中的元素按照遞增順序排列，現要求將他們合并成一個新的線性表Lc,病似的Lc中元素也按照遞增的順序排列

思想：線性表Lc初始為空，依次掃描La和Lb中的元素，比較
當前元素的值，將較小值的元素插入Lc的表尾之后，如此反
復，直到一個線性表掃描完畢，然后將未完的那個線性表中
余下的元素逐個插入到Lc的表尾之后

Status List_Merge (SqListPtr La, SqListPtr Lb, SqListPtr Lc){
ElemType elem1, elem2; status = List_Init(Lc);
int i=1, j=1, k=1; /*i, j, k分別用于指示La, Lb, Lc中當前元素*/
int n = List_Size(La)，m = List_Size(Lb);
while(i<=n && j<=m){ /*兩個表都還未處理完*/
List_Retrieve(La,i,&elem1); List_Retrieve(Lb,j,&elem2);
if(elem1<elem2){ status = List_Insert(Lc,k,elem1); i=i+1; }
else{ status = List_Insert(Lc,k,elem2); j=j+1; }
k=k+1;
}

Status List_Merge (SqListPtr La, SqListPtr Lb, SqListPtr Lc){
…….
while(i<=n){ /*表La都還未處理完*/
List_Retrieve(La, i, &elem1);
status = List_Insert(Lc, k, elem1);
i=i+1; k=k+1; }
while(j<=m){ /*表Lb都還未處理完*/
List_Retrieve(Lb, j, &elem2);
status = List_Insert(Lc, k, elem2);
j=j+1; k=k+1; }
return status;
}

3 線性表的順序存盤結構（全）

3.1 線性表的順序存盤基本概念

3.2 順序存盤的C代碼實作

3.2.1 順序存盤表的定義

#define LIST_INIT_SIZE 100 //空間個數
#define LIST_INCREAMENT 10 //每次增加的空間個數
typedef int ElemType;//重新命名型別
typedef struct SqList//重新命名結構體
{
ElemType *elem;//一大片連續空間的首地址
int length; //長度 開始未知
int list_size;//個數 開始未知
}SqList, *Ptr;
typedef Ptr *SqlListPtr;

3.2.2 初始化順序存盤表

Status List_Init(SqListPtr L)
{
Status s = success;
L->list_size = LIST_INIT_SIZE;//宏定義的值
L->length = 0;//初始為0
L->elem = (ElemType *)malloc(sizeof(ElemType)*L->list_size);//開辟空間
if (L->elem == NULL)
s=fatal;
return s;
}

3.2.3 表中按照位置查找值

Status List_Retrival(SqListPtr L, int pos, ElemType *elem)
{
Status s = range_error;
if (L)//如果鏈表存在
{
if ((pos-1) >= 0 && (pos-1) < L->length)//從0開始 在范圍內
{
*elem = L->elem[pos-1];//* 表示取值 取出放入
s = success;//修改狀態
}
}
else
s = fatal;
return s;
}

3.2.4 表中按照值查找位置

Status List_Locate(SqListPtr L, ElemType elem, int *pos)
{
Status s = range_error;
if (L){
for (int i = 0; i < L->length; ++i){
if (L->elem[i] == elem){
*pos = i+1;
s = success;
break;
}
}
}
else s = fatal;
retu

3.2.5 在指定位置插入元素

Status List_Insert(SqListPtr L, int pos, ElemType elem)
{
Status s = range_error;
if ((pos-1) >= 0 && (pos-1) <= L->length)//在順序表范圍內
{
//順序表存在并且還存在未使用的空間方便后移
if (L && L->length <L-> list_size )
{
//回圈遍歷后移 記得-1
for (int i = L->length-1; i >= pos-1; --i){
L->elem[i+1] = L->elem[i];
}
//插入
L->elem[pos-1 ] = elem;
//實際長度增加1
L->length++;
s = success;
}
}
else s = fail;
return 

3.2.6 洗掉指定位置的元素

Status List_delete(SqListPtr L, int pos)
{
Status s = range_error;
if ((pos-1) >= 0 && (pos-1) < L->length){
if(L && L->length > 0){
for (int i = pos ; i < L->length; ++i){
L->elem[i-1] = L->elem[i ];
L->length--;
s=success;
}
}
}
else s = fail;
return s;
}

3.3 順序存盤結構存在的問題

1. 不能知道預先分配多少空間合適，盡管當空間不夠可以分配更大的空間但是資料的前移造成時間浪費
2. 插入和洗掉開銷很大，回圈遍歷，

4 線性表的鏈式存盤結構（全）

4.1 線性表的鏈式存盤的基本概念

帶頭結點和不帶頭結點的區別

4.2 鏈式存盤的C代碼實作

4.2.1 鏈式存盤的型別定義

typedef struct Node
{
ElemType elem;
struct Node *next;
}Node,*Ptr;
typedef Ptr *SqListPtr;

4.2.2 變數的定義和實作

Node n1, n2;
/* 定義2個結點變數*/
Ptr p = &n1;
/* 定義一個指向結點的指標變數p, 并存放n1的地址
(指標) */
n1.next=&n2; /* 結點n1的指標域存放結點n2的地址
*/
SqListPtr L=p; //定義一個單鏈表L
N2.next=NULL;

4.2.3 單鏈表按位置查找值

Status List_Retrieve(SqListPtr L, int pos, ElemType *elem)
{
//SqListPtr L是一個二重指標 
Status s = range_error;
Ptr p = (*L)->next;; /* 帶頭結點，移動p指向第一個元素結點*/
int i = 1;/*計數器*/
while (p && i < pos)){ /* p指向的結點存在,且未到達指定位置*//*條件１防止pos>表長;條件２
控制取第pos個, 防pos<1 */
{
i++;
p = p->next;
}
if (p && i == pos)) /*找到指定位置,且該結點存在 防止i=0 -1 這種情況*/
{
*elem = p->data;
s = success;
}
return s;
}

4.2.4 單鏈表按值查找位置

Status List_Locate(SqListPtr L, ElemType elem, int *pos)
{
Status s = range_error;
Ptr p = (*L)->next;
int i = 1;
while (p != NULL){
if (p->elem == elem)break;
i++;
p = p->next;
}
if (p){
*pos = i;
s = success;
}
return s;
}

4.2.5 單鏈表上的插入操作

步驟（易錯）

• 找到ai-1的位置
• 構造一個資料域為elem的新結點
• 將ai-1 ->next 先掛到新節點上（elem->next=ai-1 ->next）
• 再將ai-1->next=elem（不可換）

Status List_Insert(SqListPtr L, int pos-1, ElemType elem)
{
Status status ;
Ptr p,s;
status = List_Retrival (L, pos-1, &p);//判斷是否存在這個位置 有沒有越界
if (status == success){
s = (LinkedPtr)malloc(sizeof(Node));//創建新節點
if (s){
s->elem = 資料;//新結點掛上資料
s->next = p->next;//新節點next掛上ai
p->next = s;//ai-1掛上next
status = success;
}
else status = fatal;
}
else status = range_error;
return status;
}

4.2.6 單鏈表上的洗掉操作

步驟

• 首先求得第i-1個結點的指標p
• 修改第i-1個結點的后繼域為第i+1個結點的地址
• 再釋放第pos個結點所占的存盤空間

//不完整 要先用查找 找到對應位置（s p）的指標 
//再用如下函式進行洗掉
Status List_delete(SqListPtr L, int pos)
{
Status status=fail;
Ptr s, p;
status = List_Retrival (L, pos - 1, &p);
if (status == success)
{
s = p->next;
p->next = s->next;
free(s);
s = NULL;
status = success;
}
return status;
}

4.2.7 單鏈表的創建及插入n個資料

首先明確插入都是前插，操作都在空節點和第一個節點之間，如果要求a1 到 a n 順序插入，那么實際上我們操作順序是an 到 a1，看下圖理解

Status List_Create(SqListPtr L, ElemType data[], int len){
Status s;
Ptr p;
s = List_Init(L);
if (s == success){
for (int i = len-1; i>=0; --i)//len個資料
{
p = (Ptr)malloc(sizeof(Node));//回圈初始化len個節點
if (p)
{
p->elem = data[i];//資料放入新結點
//先填充新節點的next ，否則資料覆寫就不存在，順序不能換
p->next = (*L)->next;
(*L)->next = p;//新結點掛載空節點的next上
}
else{
s = fail;
break;
}
}
}
return s

總結

對于資料結構與演算法課程的重新學習整理，如有錯誤歡迎指出，