一、順序表基礎認知?

1.順序表的定義與特點?

順序表是數據結構中一種線性存儲結構，它將數據元素按照邏輯順序依次存儲在一片連續的物理內存空間中。簡單來說，就是用一段地址連續的存儲單元依次存放線性表的元素，且元素之間的邏輯關系通過物理位置的相鄰關系直接體現。?

其核心特點包括：?

• 物理存儲連續：所有元素在內存中占據連續的存儲空間，例如第 i 個元素的存儲地址可通過首地址和元素大小計算（Loc (ai) = Loc (a0) + i×sizeof (元素類型)）。?

• 元素訪問高效：支持隨機訪問，即通過下標可以直接定位到目標元素，時間復雜度為 O (1)。?

• 容量固定或動態調整：靜態順序表的容量在初始化時確定，動態順序表則可根據元素數量動態擴容或縮容。?

• 插入刪除效率低：若在中間位置插入或刪除元素，需要移動大量后續元素以維持連續性，時間復雜度為 O (n)。

2.順序表與數組的關聯和區別?

順序表與數組密切相關，但二者并非完全等同，具體關聯和區別如下：?

關聯：?

• 順序表的底層實現依賴數組：無論是靜態還是動態順序表，都會借助數組作為物理存儲載體，利用數組的連續內存特性實現元素的線性排列。?

• 元素訪問方式一致：兩者都支持通過下標直接訪問元素，遵循 “隨機訪問” 的特性。

區別：

例如，在 C 語言中，數組是int arr[10]這樣的固定大小容器，而順序表則會通過結構體封裝數組指針、當前長度和容量，如：?

typedef struct {int* data;   // 指向數組的指針int size;    // 當前元素個數int capacity; // 容量
} SeqList;

二、順序表的初始化操作?

//1.初始化
void InitSeqList(SeqList* plist)
{//斷言assert(plist != NULL);//1.給指針malloc分配內存ELEM_TYPE* p = (ELEM_TYPE*)malloc(sizeof(ELEM_TYPE) * SXQ_INIT_SIZE);if (NULL == p){printf("初始化malooc分配內存失敗\n");return;}plist->arr = p;//2.個數plist->cursize = 0;//3.容量plist->capacity = SXQ_INIT_SIZE;
}

三、順序表的核心操作?

1.插入元素（頭部、中間、尾部）

//7.插入元素
bool InsertElem(SeqList* plist, int pos, ELEM_TYPE val)
{assert(plist != NULL);if (IsFull(plist)){if (IncMem(plist) == false){printf("無法插入\n");return false;}}if (pos<0 || pos>plist->cursize){printf("插入位置不合法\n");return false;}for (int i = plist->cursize - 1; i >= pos; i--){plist->arr[i + 1] = plist->arr[i];}plist->arr[pos] = val;plist->cursize += 1;return true;
}//8.尾插
bool Push_Back(SeqList* plist, ELEM_TYPE val)
{assert(plist != NULL);plist->arr[plist->cursize] = val;plist->cursize++;return true;
}//9.頭插
bool Push_Front(SeqList* plist, ELEM_TYPE val)
{assert(plist != NULL);InsertElem(plist, 0, val);return true;
}

2.?刪除元素（指定位置、指定值）?

//12.按位置刪除
bool ErasePos(SeqList* plist, int index)
{assert(plist != NULL);if (IsEmpty(plist)){printf("刪除失敗\n");return false;}if (index<0 || index>plist->cursize){printf("刪除失敗\n");return false;}for (int i = index; i < plist->cursize; i++){plist->arr[i] = plist->arr[i + 1];}plist->cursize -= 1;return true;
}//13.按值刪除（刪一次）
bool RemoveElem(SeqList* plist, ELEM_TYPE val)
{assert(plist != NULL);for (int i = 0; i < plist->cursize; i++){if (val == plist->arr[i]){ErasePos(plist, i);}}return true;
}//14.按值刪除（刪多次）
bool RemoveElemAll(SeqList* plist, ELEM_TYPE val)
{assert(plist != NULL);int i = 0;while (i < plist->cursize){if (plist->arr[i] == val){ErasePos(plist, i);}else{i++;}}return true;
}//15.刪除尾
bool Pop_Back(SeqList* plist)
{assert(plist != NULL);if (IsEmpty(plist)){return false;}ErasePos(plist, plist->cursize - 1);return true;
}//16.刪除頭
bool Pop_Front(SeqList* plist)
{assert(plist != NULL);if (IsEmpty(plist)){return false;}ErasePos(plist, 0);return true;
}

3.查找元素（按值查找、按位查找）

//11.查詢
int FindValue(const SeqList* plist, ELEM_TYPE val)//沒找到返回-1，找到了返回下標，有多個返回第一個
{assert(plist != NULL);if (IsEmpty(plist)){return -1;}for (int i = 0; i < plist->cursize; i++){if (plist->arr[i] == val){printf("找到了，下標為%d\n", i);return i;}}return -1;
}

四、順序表的銷毀操作?

//22.清除順序表
bool ClearElem(SeqList* plist)
{assert(plist != NULL);plist->cursize = 0;return true;
}//23.銷毀
void DestroySeqList(SeqList* plist)
{assert(plist != NULL);free(plist->arr);plist->arr = NULL;plist->cursize = 0;plist->capacity = 0;
}

五、反轉、合并兩個有序的順序表

//24.反轉順序表
void Reverse_List(SeqList* plist)
{assert(plist != NULL);if (IsEmpty(plist)){return;}int left = 0;int right = plist->cursize - 1;while (left < right){int temp = plist->arr[left];plist->arr[left] = plist->arr[right];plist->arr[right] = temp;left++;right--;}
}//25.合并兩個有序的順序表
void Merge_List(SeqList* plist1, SeqList* plist2, SeqList* plist3)
{assert(plist1 != NULL && plist2 != NULL && plist3 != NULL);int i = 0, j = 0;while (i < plist1->cursize || j < plist2->cursize){if (plist1->arr[i] > plist2->arr[j]){Push_Back(plist3, plist2->arr[j]);j++;}else{Push_Back(plist3, plist1->arr[i]);i++;}if (i == plist1->cursize){while (j < plist2->cursize){Push_Back(plist3, plist2->arr[j]);j++;}}if (j == plist2->cursize){while (i < plist1->cursize){Push_Back(plist3, plist1->arr[i]);i++;}}}}