【数据机构】2. 线性表之“顺序表”

- 第 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; // 未找到
}