- 第 96 篇 -
Date: 2025 - 05 - 09
Author: 鄭龍浩/仟墨
【數據結構 2】

數據結構 - 2 -

線性表之“順序表”

1 基本概念

一種邏輯結構，表示元素之間具有一對一的線性關系（即除首尾元素外，每個元素有且只有一個前驅和一個后繼）

• 邏輯上是“一條線”的結構（如 a? → a? → a? → ... → a?）
• 不關心物理存儲方式（可以是連續內存或離散內存）

線性表(linear list) 是 n 個具有相同特征的數據元素的有限序列。線性表是一種在實際中廣泛使用的的數據結構，常見的有: 順序表、鏈表、棧、列隊、字符串

線性表在邏輯上是線性結構，也就是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理存儲時，通常以數組和鏈表結構的形式存儲

• 順序表是在物理和邏輯上都是連續的
• 鏈表在邏輯上是連續的，在物理是非連續的

什么叫做邏輯結構呢？什么叫做物理結構呢？

• 物理結構 –> 內存中的存儲結構

• 鏈表結構 –> 是我們想象出來的存儲結構，為了方便我們自己理解和使用

擴展概念

內存一般分為四個區域

• 棧
• 堆
• 靜態去(數據段)
• 常量區(代碼段)

2 順序表(一般為數組)

① 基本介紹

線性表的一種物理實現方式，基于連續內存（通常是數組）存儲元素

• 從物理和邏輯上都是連續的
• 支持隨機訪問（通過下標直接訪問，時間復雜度 O(1)）
• 插入 / 刪除需移動元素（時間復雜度 O(n)）

② 分類 (靜態與動態)

順序表分為兩種

• 靜態順序表 –> 使用定長數組存儲 (數組長度是固定的)

  0	1	2	3	4	5	6	7	8	9

• 動態順序表 –> 使用動態開辟的數組存儲 (長度可以改)

  比如使用malloc

  p1，p2，p3 的地址并不是連續的，通過鏈表的形式可以在上一個元素中存下一個元素的地址，后面同理，直到最后一個元素

③ 動態順序表的實現

補充:

#pragma once 什么作用？是解決頭文件被重復包含的問題。比如第一次遇到#include "math.h"，后續再遇到相同的 #include "math.h" 的時候，直接跳過，避免重復內容

我用VS寫的動態順序表以及一些用于順序表的函數，內容如下

test.c文件:

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"// 測試頭尾插入刪除
void Test_SeqList1() {SeqList s;SeqListInit(&s);printf("\n尾插6次，依次插入 1 ~ 6:\n");SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3);SeqListPushBack(&s, 4);SeqListPushBack(&s, 5);SeqListPushBack(&s, 6);SeqListPrint(&s);printf("尾刪1次:\n\n");SeqListPopBack(&s);SeqListPrint(&s);printf("\n頭插6次，依次插入111，222，333，444，555，666:\n");SeqListPushFront(&s, 111);SeqListPushFront(&s, 222);SeqListPushFront(&s, 333);SeqListPushFront(&s, 444);SeqListPushFront(&s, 555);SeqListPushFront(&s, 666);SeqListPrint(&s);printf("\n頭刪2次:\n");SeqListPopFront(&s);SeqListPopFront(&s);SeqListPrint(&s);printf("\n查找順序表中的數據(找到返回1，沒有返回0):\n");printf("查找222:%d\n", SeqListFind(&s, 222));printf("查找123:%d\n", SeqListFind(&s, 123));printf("\n對數據進行排序\n");QuickSort(&s, 0, s.size);SeqListPrint(&s);
}
int main(void) {Test_SeqList1();return 0;
}

SeqList.h文件:

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 順序表 --> 靜態存儲
// 只是將數組簡單的封裝了一下，并不能按需索取
#define N 100
typedef int SLDataType; // 將int名字變為SLDataType, 有什么好處呢，如果以后想將下面的所有的int變為double 的話，不需要改下面的類型，直接在這將int變為double即可
// 順序表，在有效數組中必須是連續的
typedef struct SeqList1 {SLDataType arr[100]; // 定長數組size_t size; // 有效數據的個數 --> 有效數據長度
}SeqList1;// 順序表 --> 動態存儲    用的比較多的還是動態數據表
typedef int SLDataType; // 將int名字變為SLDataType, 有什么好處呢，如果以后想將下面的所有的int變為double 的話，不需要改下面的類型，直接在這將int變為double即可
// 順序表，在有效數組中必須是連續的
typedef struct SeqList {SLDataType* array; // 指向動態開辟的數組size_t size; // 有效數據個數 --> 有效數據長度size_t capacity; // 容量的大小 capacity 英文意思 “容量”
}SeqList;// 接口 ---> 增刪查改
// 基本增刪查改接口
// 順序表初始化
void SeqListInit(SeqList* psl);
// 順序表銷毀
void SeqListDestory(SeqList* psl);
// 順序表打印
void SeqListPrint(SeqList* psl);
// 檢查空間，如果滿了，進行增容 --> 單獨封裝接口，避免頭插，尾插，隨機插入的重復代碼
void CheckCapacity(SeqList* psl);
// 順序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 順序表尾刪
void SeqListPopBack(SeqList* psl);
// 順序表頭插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 順序表頭刪
void SeqListPopFront(SeqList* psl);
// 順序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 順序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 順序表刪除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 交換兩個元素
void Swap(SLDataType* a, SLDataType* b);
// 順序表排序
void QuickSort(SeqList* psl, size_t L, size_t R);
// 順序表二分查找
int SeqListBinarySearch(SeqList* psl, SLDataType x);

SeqList.c文件:

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 順序表 --> 靜態存儲
// 只是將數組簡單的封裝了一下，并不能按需索取
#define N 100
typedef int SLDataType; // 將int名字變為SLDataType, 有什么好處呢，如果以后想將下面的所有的int變為double 的話，不需要改下面的類型，直接在這將int變為double即可
// 順序表，在有效數組中必須是連續的
typedef struct SeqList1 {SLDataType arr[100]; // 定長數組size_t size; // 有效數據的個數 --> 有效數據長度
}SeqList1;// 順序表 --> 動態存儲    用的比較多的還是動態數據表
typedef int SLDataType; // 將int名字變為SLDataType, 有什么好處呢，如果以后想將下面的所有的int變為double 的話，不需要改下面的類型，直接在這將int變為double即可
// 順序表，在有效數組中必須是連續的
typedef struct SeqList {SLDataType* array; // 指向動態開辟的數組size_t size; // 有效數據個數 --> 有效數據長度size_t capacity; // 容量的大小 capacity 英文意思 “容量”
}SeqList;// 接口 ---> 增刪查改
// 基本增刪查改接口
// 順序表初始化
void SeqListInit(SeqList* psl) {psl->array = NULL; // 初始化數組為空psl->size = 0; // 元素個數為 0psl->capacity = 0; // 容量為 0
}// 順序表銷毀
void SeqListDestory(SeqList* psl) {free(psl->array);psl->array = NULL; // 將指針指向 “空” --> 也就是重置為空指針psl->size = 0; // 有效數據個數重置為 0psl->capacity = 0; // 容量大小重置為 0
}// 順序表打印
void SeqListPrint(SeqList* psl) {// assert(psl);for (int i = 0; i < psl->size; ++i) {printf("%d ", psl->array[i]);}printf("\n");
}// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* psl) {// 如果滿了，需要“增容” --> 增容多少呢，一般來說，都增二倍   多了太多，少了太少if (psl->size >= psl->capacity) {// 一定要判斷是否為0,若為0,則增容為4，否則 0*2*2*2...不管*多少個，都是0size_t new_capacity = psl->capacity == 0 ? 4 : psl->capacity * 2;  // 初始容量設為4，后續二倍// new_arr 定義該變量是為了保護原本數組，假設擴容失敗，就不會對原數據進行任何修改SLDataType* new_arr = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * new_capacity);// 判斷增容是否失敗 --> 若指向的是空指針，則增容失敗if (new_arr == NULL) {printf("擴容失敗\n");return ;}// 若成功擴容，則不會執行上面 if 的語句,而是下面psl->array = new_arr;psl->capacity = new_capacity;}
}// 順序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x) {// assert(psl); // 若psl為空，則終止執行，否則，執行 --> 僅用于Debug模式，在 Release 模式下會被禁用CheckCapacity(psl); // 檢查是否要進行擴容psl->array[psl->size] = x; // 插入 xpsl->size++; // 增加有效數據個數 ++
}// 順序表尾刪
void SeqListPopBack(SeqList* psl) {// assert(psl); // 若psl為空，則終止執行，否則，執行 --> 僅用于Debug模式，在 Release 模式下會被禁用//psl->array[psl->size - 1] = 0; // 最后一個數據重置為 0 --> 是否重置為0都可以，做這一步操作只是為了刪除“臟數據”，一般來說不重置，因為重置的話效率降低，而不重置也不影響使用psl->size--; // 有效數據個數--
}
// 順序表頭插 --> 將數據往后挪動
void SeqListPushFront(SeqList* psl, SLDataType x) {// assert(psl);CheckCapacity(psl); // 檢查是否要進行擴容int end = (int)psl->size - 1; // 1指向最后一個數據 （用int,如果用size_t的話是不會出現end < 0的情況的）// 從最后一個數據開始，往后挪一位,直到將第一個數據挪到第二個數據的為止while (end >= 0) {psl->array[end + 1] = psl->array[end]; // 將指向數據挪動到下一位--end; // 向前遍歷，依次指向前一數據}psl->array[0] = x; // 表頭部插入xpsl->size++; // 表有效數據++
}
// 順序表頭刪
void SeqListPopFront(SeqList* psl) {//assert(psl);int start = 0;while (start < psl->size - 1) {psl->array[start] = psl->array[start + 1]; // 將當前數據存儲到下一位start++; // 向后遍歷，依次指向后一個數據}psl->size--;
}
// 順序表查找  參數1是數組地址   參數2是查找的數據
int SeqListFind(SeqList* psl, SLDataType x) {// assert(psl);for (int i = 0; i < psl->size; i++) {if (psl->array[i] == x) return i;}return -1;
}
// 順序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) {assert(psl && pos <= psl->size);  // 必須添加邊界檢查CheckCapacity(psl); // 檢查是否要進行擴容int end = (int)psl->size - 1; // 存儲當前需要移動的位置while (end >= 0 && end >= pos) {psl->array[end + 1] = psl->array[end];end--; // 指向前一個}psl->array[pos] = x;  // 插入 xpsl->size++; // 有效數據個數++
}
// 順序表刪除pos位置的值  
void SeqListErase(SeqList* psl, size_t pos) {assert(psl && pos <= psl->size);  // 必須添加邊界檢查int start = (int)pos;while (start < psl->size - 1) {psl->array[start] = psl->array[start + 1];start++;}psl->size--; // 有效數據個數--
}// 交換兩個元素
void Swap(SLDataType* a, SLDataType* b) {SLDataType tmp = *a;*a = *b;*b = tmp;
}
// 順序表排序
void QuickSort(SeqList* psl, size_t L, size_t R) {if (L >= R)return ;int left = (int)L, right = (int)R;int key = left;//定義基準點keywhile (left < right)//當left<right說明還沒相遇，繼續數組內元素的交換{while (left < right && psl->array[right] >= psl->array[key])//right找小{right--;}while (left < right && psl->array[left] <= psl->array[key])//left找大{left++;}Swap(psl->array + right, psl->array + left); // 交換 left 和 right 位置的元素}Swap(psl->array + key, psl->array + left); // 此時left與right已經指向了同一個位置，只需要將基準點k的元素與left(right)指向的元素進行互換即可// 此時left位置的元素就是原來key位置的元素，而left位置左邊全部是小于psl->array[left]的元素，left右邊全部是大于psl->array[left]的元素if (left > 0) QuickSort(psl, L, left - 1); // 對左半部分進行排序if (left < R) QuickSort(psl, left + 1, R);// 對右半部分進行排序
}
// 順序表二分查找 未找到->返回-1
int SeqListBinarySearch(SeqList* psl, SLDataType x) {// assert(psl);if (psl->size == 0) return -1;int left = 0, right = (int)psl->size - 1, mid/*中間*/; // 確定最初查找范圍while (left <= right) {mid = left + ((right - left) >> 1);if (x < psl->array[mid]) // 在mid的左邊right = mid - 1;else if (x > psl->array[mid]) // 在mid的右邊left = mid + 1;elsereturn mid; // 找到了}return -1; // 未找到
}