一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
1、概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表可以分为：
- 静态顺序表：使用定长数组存储元素。
//顺序表静态存储 #define N 5 //这样写方便后期将int改为其他数据类型 typedef int SLDataType; typedef struct SeqList { SLDataType arr[N];//定长数组 int size; //有效数据的个数 }SeqList;
- 动态顺序表：使用动态开辟的数组存储。
//顺序表动态存储 typedef int SLDataType; typedef struct SeqList { SLDataType* a;//指向动态开辟的数组 int size; //有效数据个数 int capicity;//空间的容量 }SeqList;
2、接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> //这样写方便后期将int改为其他数据类型 typedef int SLDateType; //用一个结构体存放顺序表 typedef struct SeqList { SLDateType* a;//指向动态开辟的数组 int size; //有效数据个数 int capicity;//空间的容量 }SeqList; // 对数据的管理:增删查改 //初始化顺序表 void SeqListInit(SeqList* ps); //操作结束后释放空间 void SeqListDestroy(SeqList* ps); //打印顺序表 void SeqListPrint(SeqList* ps); //尾插 void SeqListPushBack(SeqList* ps, SLDateType x); //头插 void SeqListPushFront(SeqList* ps, SLDateType x); //头删 void SeqListPopFront(SeqList* ps); //尾删 void SeqListPopBack(SeqList* ps); // 顺序表查找 int SeqListFind(SeqList* ps, SLDateType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, int pos, SLDateType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int pos);
1>初始化顺序表
void SeqListInit(SeqList* ps) { //动态开辟内存 ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 5); if (ps->a == NULL) { perror("malloc failed"); exit(-1); } ps->size = 0; ps->capacity = 5; }
2>操作结束后释放空间
void SeqListDestroy(SeqList* ps) { free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0; }
3>打印顺序表
void SeqListPrint(SeqList* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
4>尾插
向顺序表中插入数据时，需要先判断顺序表是否已满，如果已经满了需要进行扩容，我们将检查扩容的操作封装在一个函数中
//检查是否已满 void SeqListCheck(SeqList* ps) { //当数据个数与容量相等时代表顺序表满了 if (ps->size == ps->capacity) { //因为可能会异地扩容，先用另一个指针接收 //这里扩容到原来的2倍 SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDateType))); if (tmp == NULL) { perror("realloc failed"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } }
尾插只需要在顺序表的最后加上一个数据，再将size加1即可
//尾插 void SeqListPushBack(SeqList* ps, SLDateType x) { SeqListCheck(ps); ps->a[ps->size] = x; ps->size++; }
5>头插
头插需要先检查顺序表是否已满，然后将所有元素右移一位，然后将要插入的元素放到首位，这里需要从最后一个元素开始右移，不然数据会被覆盖改变
void SeqListPushFront(SeqList* ps, SLDateType x) { SeqListCheck(ps); for (int i = ps->size - 1; i >= 0; i--) { ps->a[i + 1] = ps->a[i]; } ps->a[0] = x; ps->size++; }
6>头删
头删直接将所有元素左移一位将首元素覆盖即可，size-1，左移需要先移动最左边元素，防止元素被覆盖
void SeqListPopFront(SeqList* ps) { //判断顺序表是否为空 assert(ps->size>0); for (int i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; }
7>尾删
尾删只需将size-1使得访问不到即可
void SeqListPopBack(SeqList* ps) { //判断顺序表是否为空 assert(ps->size>0); ps->size--; }
8>顺序表查找
在顺序表中查找x，返回其下标，找不到则返回-1
int SeqListFind(SeqList* ps, SLDateType x) { for (int i = 0; i < ps->size - 1; i++) { if (ps->a[i] == x) { return i; } } return -1; }
9>顺序表在pos位置插入x
将pos下标及以后的元素右移（需要从最后一个元素开始右移，防止覆盖），然后将x插入下标pos位置
void SeqListInsert(SeqList* ps, int pos, SLDateType x) { //检查下标pos是否合法 assert(pos >= 0 && pos <= ps->size); SeqListCheck(ps); for (int i = ps->size - 1; i >= pos; i--) { ps->a[i + 1] = ps->a[i]; } ps->a[pos] = x; ps->size++; }
10>顺序表删除pos位置的值
将pos下标后面的元素都左移一位（从最左边的元素开始左移，防止被覆盖），将pos下标上的元素覆盖即删除
void SeqListErase(SeqList* ps, int pos) { //检查pos的合法性 assert(pos >= 0 && pos < ps->size); for (int i = pos; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; }
