数据结构01线性表之顺序表整理人计算机小窦同学窦鑫奇学习目标线性表概念顺序表实现顺序表相关OJ题练习1. 线性表线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储如下图所示。线性表空间连续性数组的空间是连续的内存层面链式结构链表的空间是不连续的内存层面2. 顺序表实现2.1 概念及结构顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为静态顺序表使用定长数组存储。栈内存动态顺序表使用动态开辟的数组存储。堆内存顺序表的特点1、连续的物理空间存储——数组2、数据必须是从头开始依次存储不能说有序// 顺序表的静态存储 #define N 100 typedef int SLDataType; typedef struct SeqList { SLDataType array[N]; // 定长数组 size_t size; // 有效数据的个数 }SeqList;// 顺序表的动态存储 typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 size_t size; // 有效数据个数 size_t capacity; // 容量空间的大小 }SeqList;2.2 接口实现静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们实现动态顺序表。接口的定义SeqList.h#pragma once // 防止头文件被重复包含 ​ #include stdio.h #include string.h #include stdlib.h #include assert.h // 断言的头文件 #define VALUE 4 // 顺序表的容量初始值在这里我设置为4 typedef int SLDataType; // 顺序表的初始数据类型在这里我以int为例 ​ // 顺序表的动态存储 typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 size_t size; // 有效数据个数 size_t 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);接口的实现SeqList.c#include SeqList.h ​ // 基本增删查改接口 ​ // 顺序表初始化 void SeqListInit(SeqList* psl) { psl-array NULL; psl-size 0; psl-capacity 0; } ​ // 顺序表销毁 void SeqListDestory(SeqList* psl) { free(psl-array); // 堆内存的释放 psl-array NULL; psl-capacity psl-size 0; } ​ // 顺序表打印 void SeqListPrint(SeqList* 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) { int newcapacity psl-capacity 0 ? 4 : psl-capacity * 2; SLDataType* tmp (SLDataType*)realloc(psl-array, newcapacity * 2 * sizeof(SLDataType)); if (tmp NULL) { printf(realloc fail\n); exit(-1); // 直接结束程序 } else { psl-array tmp; psl-capacity newcapacity; } } } ​ // 顺序表尾插 void SeqListPushBack(SeqList* psl, SLDataType x) { CheckCapacity(psl); ​ psl-array[psl-size] x; psl-size; } ​ // 顺序表尾删 void SeqListPopBack(SeqList* psl) { assert(psl-size 0); psl-size--; } ​ // 顺序表头插 void SeqListPushFront(SeqList* psl, SLDataType x) { CheckCapacity(psl); ​ int end psl-size - 1; while (end 0) { psl-array[end 1] psl -array[end]; --end; } psl-array[0] x; psl-size; } ​ // 顺序表头删 void SeqListPopFront(SeqList* psl) { assert(psl-size 0); ​ int start 1; while (start psl-size) { psl-array[start - 1] psl-array[start]; start; } psl-size--; } ​ // 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x) { 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(pos psl-size); CheckCapacity(psl); ​ size_t end psl-size; while (end pos) { psl-array[end] psl-array[end - 1]; --end; } ​ psl-array[pos] x; psl-size; } ​ // 顺序表删除pos位置的值 void SeqListErase(SeqList* psl, size_t pos) { assert(pos psl-size); ​ int start pos 1; while (start psl-size) { psl-array[start - 1] psl-array[start]; start; } psl-array[psl-size - 1] 0; psl-size--; }3. 顺序表相关OJ题练习3.1 原地移除元素OJ链接https://leetcode-cn.com/problems/remove-element/3.2 合并两个有序数组OJ链接https://leetcode-cn.com/problems/merge-sorted-array/