四川省安全社区建设网站黄山旅游攻略自由行

1. 线性表

线性表(lina list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串......

线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表实现

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1.静态顺序表：使用定长数组存储。

2.动态顺序表：使用动态开辟的数组存储。

#define N 100
// 静态顺序表
struct SeqList
{int arr[N];int size;	// 有效数据个数
};

typedef int SLDataType;// 动态顺序表
typedef struct SeqList
{SLDataType* arr;int size;	// 有效数据个数int capacity;	// 空间大小
}SL;

注意：静态顺序表只适用于确定知道需要多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态地分配空间大小，所以下面我们实现动态顺序表。

2.2 顺序表初始化

// 顺序表初始化
void SLInit(SL* ps);

首先，我们需要初始化数组，数组首元素地址 ps->arr 置为NULL；有效数字个数 size 和空间容量capacity 大小都置为0。

// 顺序表初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

2.3 顺序表销毁

// 顺序表销毁
void SLDestroy(SL* ps);

我们使用完顺序表之后，都需要把顺序表进行销毁，以免造成内存被占用和内存泄漏问题。

首先，需要把开辟的空间 free 掉，再将数组首元素地址 ps->arr 置为NULL；有效数字个数 size 和空间容量 capacity 大小都置为0。

// 顺序表销毁
void SLDestroy(SL* ps)
{if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}

2.4 顺序表打印

// 顺序表打印
void SLPrint(SL s);

为了更好地对程序进行调试，我们这里需要写一个打印程序，以便我们测试每一个接口函数。

// 顺序表打印
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}

附：我们完成这些前导工作，接下来我们就可以正式编写顺序表的功能函数。

2.5 顺序表尾插

// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x);

我们得分两种情况：

不过在尾插元素之前，我们必须得确保数组空间大小是足够的，也就是说得有空间插入元素。如果说空间容量不够的话，我们就得扩容，所以说在尾插之前，我们得判断空间大小是否足够，不够咱就扩容。我们这里得写一个内存容量检查函数。

这里我们还得注意一个点：就是我们内存空间不够的情况下，一般我们是以2倍或者3倍  capacity(容量) * 2 * sizeof(数据类型) 去开辟空间。

// 检查内存函数
void SLCheckCapacity(SL* ps)
{// 插入数据之前看空间够不够if (ps->capacity == ps->size){// 申请空间// 申请之前，要判断一下capacity是否为0int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;错误写法：这里不要直接这样写，要不然申请空间失败的话，前面的数据会丢失//ps->arr = (SLDataType*)realloc(ps->arr, newCapacity * 2 * sizeof(SLDataType));// 正确写法SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * 2 * sizeof(SLDataType));// 如果申请失败if (tmp == NULL){perror("realloc fail!");exit(1);	// 直接退出程序，不再继续执行}// 空间申请成功ps->arr = tmp;ps->capacity = newCapacity;}
}

检查开辟完空间后，我们就可以进行下一步，顺序表尾插接口函数编写。

步骤：

① 程序开始前，我们要断言一下，确保指针是有效的，不是NULL；

② 检查内存是否足够；

③ 将我们需要的 x 尾插入下标 ps->size 的位置，插完之后，数组元素总个数 ps->size 得加1。

// 顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{温柔的解决方式//if (ps == NULL)//	return;assert(ps); // 等价于assert(ps != NULL)// 检查内存SLCheckCapacity(ps);/*ps->arr[ps->size] = x;++ps->size;*/ps->arr[ps->size++] = x;
}

每次写完一个函数，接下来我们都得测试一下尾插函数接口（谨记）：

测试程序：

void SLTest01()
{SL sl;// 顺序表初始化SLInit(&sl);// 增删查改操作// 测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);// 顺序表销毁SLDestroy(&sl);
}int main()
{SLTest01();return 0;
}

运行结果：依次尾插1，2，3，4

2.6 顺序表头插

// 顺序表头插
void SLPushFront(SL* ps, SLDataType x);

我们也得分两种情况：

不过我们在头插元素之前，我们也得确保数组空间大小是足够的，所以我们头插之前也得调用一下内存检查函数 SLCheckCapacity，保证我们内存容量是足够的。

步骤：

① 程序开始前，我们要断言一下，确保指针是有效的，不是NULL；

② 检查内存是否足够；

③ 将我们需要的 x 头插入下标 0 的位置，插完之后，数组元素总个数 ps->size 得加1。

// 顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);// 检查内存SLCheckCapacity(ps);// 先让顺序表中已有的数据整体往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1]; // arr[1] = arr[0]}ps->arr[0] = x;ps->size++;
}

测试程序：

void SLTest01()
{SL sl;// 顺序表初始化SLInit(&sl);// 增删查改操作// 测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);// 测试头插SLPushFront(&sl, 5);SLPushFront(&sl, 6);SLPrint(sl);// 顺序表销毁SLDestroy(&sl);
}int main()
{SLTest01();return 0;
}

运行结果：先尾插1，2，3，4，然后头插5，6，最终结果是6，5，1，2，3，4

2.7 顺序表尾删

// 顺序表尾删
void SLPopBack(SL* ps);

我们删除数据不是说要把这个数据从数组中去除，而是说我们这个所谓的“删除的数据”不能被访问，所以我们只需把数组中有效的元素个数 size - 1 即可，并不需要把这个数据变成什么其他的数，这是非常多余的(如果非要更改删除数据也不是不可)。

步骤：

① 程序开始前，我们要断言一下，确保指针是有效的，不是NULL；

② 断言一下，数据有效个数不能为0；

③ 将数据有效个数 size - 1。

// 顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);	// 顺序表有效数字不能为0// 顺序表不能为空//ps->arr[ps->size - 1] = -1;	// 这行代码有点多余ps->size--;
}

测试程序：

void SLTest01()
{SL sl;// 顺序表初始化SLInit(&sl);// 增删查改操作// 测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);// 测试头插SLPushFront(&sl, 5);SLPushFront(&sl, 6);SLPrint(sl);// 测试尾删SLPopBack(&sl);SLPrint(sl);// 顺序表销毁SLDestroy(&sl);
}int main()
{SLTest01();return 0;
}

运行结果：先尾插1，2，3，4，然后头插5，6，最后进行尾删，最终得到的结果是6，5，1，2，3

附：尾删还是非常简单的！

2.8 顺序表头删

// 顺序表头删
void SLPopFront(SL* ps);

头删数据之后，我们还需要每个数据往前一位，最后 size - 1。

步骤：

① 程序开始前，我们要断言一下，确保指针是有效的，不是NULL；

② 断言一下，数据有效个数不能为0；

③  然后将每个数据往前移动一位；

③ 将数据有效个数 size - 1。

// 顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);	// 顺序表有效数字不能为0// 数据整体往前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1]; // 最后一次，arr[size - 2] = arr[size - 1]}ps->size--;
}

测试程序：

void SLTest01()
{SL sl;// 顺序表初始化SLInit(&sl);// 增删查改操作// 测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);// 测试头插SLPushFront(&sl, 5);SLPushFront(&sl, 6);SLPrint(sl);// 测试尾删SLPopBack(&sl);SLPrint(sl);// 测试头删SLPopFront(&sl);SLPrint(sl);// 顺序表销毁SLDestroy(&sl);
}int main()
{SLTest01();return 0;
}

运行结果：先尾插1，2，3，4，然后头插5，6，然后进行尾删，再进行头删，最终得到的结果是5，1，2，3

顺序表续：顺序表--续（C语言详细版）-CSDN博客