【数据结构 · 初阶】- 顺序表

目录

一、线性表

二、顺序表

1.实现动态顺序表

SeqList.h

SeqList.c

Test.c

问题

经验：free 出问题，2种可能性

解决问题

（2）尾删

（3）头插，头删

（4）在 pos 位插

（5）在 pos 位删

（6）查找

2.整体代码

SeqList.h

SeqList.c

test.c

---

一、线性表

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

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

二、顺序表

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

分类：
（1）静态顺序表：使用定长数组存储元素
（2）动态顺序表：使用动态开辟的数组存储

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

1.实现动态顺序表

SeqList.h 

为方便替换成其他类型，我们将这些类型统一重命名为 SLDataType

typedef int SLDataType;
#define INIT_CAPACITY 4 // 初始化容量typedef struct SeqList
{SLDataType* a;int size;     // 有效数据个数int capacity; // 空间容量
}SL;// 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);//打印顺序表数据
void SLPrint(SL* ps);void SLPushBack(SL* ps, SLDataType x); // 尾插
void SLPopBack(SL* ps); // 尾删
void SLPushFront(SL* ps, SLDataType x); // 头插
void SLPopFront(SL* ps); // 头删// 扩容，2倍合适
void SLCheckCapacity(SL* ps);

SeqList.c

void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0; // 结合性，从右往左赋值
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}// 扩容，2倍合适
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2);//思考这里对不对if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp; // 防止不是原地扩容ps->capacity *= 2;}}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);// 扩容  2倍合适SLCheckCapacity(ps);ps->a[ps->size++] = x;
}

Test.c

void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);SLDestroy(&s);
}int main()
{TestSeqList1();return 0;
}

运行上面的代码，顺序表里插入1234：，程序没毛病

---

问题

void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPrint(&s);SLDestroy(&s);
}

奇怪的事情发生了：

SLPushBack(&s, 6);
SLPushBack(&s, 7);

奇怪的事情又发生了：    光标在闪

这里反反复复调试都发现不了问题

---

经验：free 出问题，2种可能性

（1）野指针 或 位置不对。这种情况不多
eg：申请一块空间，从中间位置释放，报错。(应该从起始位置释放)
（2）指针指向的空间（数组）上面，可能有越界。

• 下标越界
• 开少了

---

解决问题

realloc 返回的是地址，->a，a 我们没有动过，动的都是 a 指向的内容
free 有时候出问题，通常不是free ( ) 里面有问题，而是前面有越界

仔细查，动空间的只有 SLPushBack(    )

// 扩容，2倍合适
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2);//思考这里对不对if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp; // 防止原地扩容ps->capacity *= 2;}}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);// 扩容  2倍合适SLCheckCapacity(ps);ps->a[ps->size++] = x;
}

ps->a[ps->size++] = x; 逻辑没有问题，问题大概率出现在扩容

先看下标越界了吗？size 没有越界的可能性

还有一种可能是开少了。
你以为你原来是 4 个，扩容到 8 个。你以为你有 8 个，实际上没有 8 个。你当成 8 个访问的呀，就越了。

8 个 SLDataType 是 4*8=32 字节。
ps->capacity * 2 这里是 4*2=8 字节

---

正确写法：

// 扩容  2倍合适
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}

 问题解决

（2）尾删

void SLPopBack(SL* ps) // 尾删
{assert(ps);//ps->a[ps->size - 1] = 0; 加上没用ps->size--;
}

由 size 遍例顺序表，size -- 后，前 size-1个是有效数据，第 size 个访问不到了

注意：这里不用释放，一部分一部分释放会报错。
但是不用担心，当我们不用这个顺序表时会 SLDestroy(&s) ; 空间还是会释放的

---

删空了还删，会报错。所以要检查

void SLPopBack(SL* ps) // 尾删
{assert(ps);// 温柔的检查if (ps->size == 0)return;ps->size--;
}

断言 assert 会直接告诉你哪出错了，并且终止掉程序

void SLPopBack(SL* ps) // 尾删
{assert(ps);// 暴力检查assert(ps->size > 0);ps->size--;
}

---

（3）头插，头删

要挪动数据，以实现顺序表连续性
顺序表尾插，尾删效率不错。头插，头删效率不太行。但有时候就要头插，头删

void SLPushFront(SL* ps, SLDataType x) // 头插
{assert(ps);SLCheckCapacity(ps);//挪动memmove(&(ps->a[1]), &(ps->a[0]), sizeof(SLDataType) * ps->size);//头插ps->a[0] = x;ps->size++;
}void SLPopFront(SL* ps) // 头删
{assert(ps);assert(ps->size > 0);memmove(&(ps->a[0]), &(ps->a[1]), sizeof(SLDataType) * ps->size);ps->size--;
}

我们发现：插入N个数据。尾插时间复杂度：O(N)     头插时间复杂度：O(N^2)
头插1万个数据，要执行1亿次。所以，尽量避免使用头插

疑问：为什么头插用memmove库函数了，时间复杂度还是O(N^2)
答：虽然我们用的是库函数，一步到位，没有用模拟实现。我们分析它的时间复杂度，还是要看到本质，本质就是模拟实现，通过模拟实现分析它的时间复杂度。

本质：

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}

可以看到，头插1个数据，执行N次，时间复杂度O(N)。头插N个数据，执行N^2次，时间复杂度O(N^2)  从模拟实现的角度看，它是一个等差数列

（4）在 pos 位插

// 顺序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);// 插入时 = size 相当于尾插SLCheckCapacity(ps);//挪动memmove(&(ps->a[pos + 1]), &(ps->a[pos]), sizeof(SLDataType) * (ps->size - pos));//插入ps->a[pos] = x;ps->size++;
}

---

我们可以简化头插(在第0位)，尾插(在第size位)。

void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);/*SLCheckCapacity(ps);ps->a[ps->size++] = x;*/SLInsert(ps, ps->size, x);
}void SLPushFront(SL* ps, SLDataType x) // 头插
{assert(ps);/*SLCheckCapacity(ps);//挪动memmove(&(ps->a[1]), &(ps->a[0]), sizeof(SLDataType) * ps->size);//头插ps->a[0] = x;ps->size++;*/SLInsert(ps, 0, x);
}

（5）在 pos 位删

// 顺序表删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//覆盖memmove(&(ps->a[pos]), &(ps->a[pos + 1]), sizeof(SLDataType) * (ps->size - pos - 1));ps->size--;
}

---

可以简化 头删，尾删 的代码。

void SLPopBack(SL* ps) // 尾删
{assert(ps);/*// 暴力检查assert(ps->size > 0);温柔的检查//if (ps->size == 0)//	return;ps->size--;*/SLErase(ps, ps->size - 1);
}void SLPopFront(SL* ps) // 头删
{assert(ps);/*assert(ps->size > 0);memmove(&(ps->a[0]), &(ps->a[1]), sizeof(SLDataType) * ps->size);ps->size--;*/SLErase(ps, 0);
}

疑问：用这个新的代码尾删，假设现在size = 8，根据上面代码，最大容量 capacity 也 = 8。要尾删，删下标为7的位置，传给 pos，pos+1 = 8 。SLErase 里面 &(ps->a[pos + 1]) 不会越界访问吗？
解答：这时要 memmove 移动 ps->size - pos - 1 = 0 个字节。我们看 memmove 模拟实现：num 是要移动的字节个数，这里 num = 0 ，循环没进去，也就不存在越界访问了

（6）查找

//顺序表查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->a[i]){return i;}}return -1;
}

---

问：为什么删除后，不用 realloc 回收一部分内存的使用权？
答：当扩容时，realloc 开内存，分为异地扩容，本地扩容。想要新开辟空间，如果原空间后面的大小够，就本地扩容，效率高。后面大小不够，就异地扩容，效率低。
而现代计算机内存空间的数量很多，不怕浪费，为保证运行效率，宁愿占着茅坑不拉屎。

当我们确认不再使用时，也会 SLDestroy 释放全部空间

问：为什么不写菜单？
答：数据结构部分，菜单没有什么价值。而且不好调试。菜单一般在命令行程序，控制数据库的服务器，会输入选项(指令去控制)。
写菜单的话，也不要一上来就写菜单。先在 test.c 里写一组一组测试 ，测的没问题了，再写菜单

2.整体代码

SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
#define INIT_CAPACITY 4 // 初始化容量typedef struct SeqList
{SLDataType* a;int size;     // 有效数据个数int capacity; // 空间容量
}SL;// 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);//打印顺序表数据
void SLPrint(SL* ps);void SLPushBack(SL* ps, SLDataType x); // 尾插
void SLPopBack(SL* ps); // 尾删
void SLPushFront(SL* ps, SLDataType x); // 头插
void SLPopFront(SL* ps); // 头删// 顺序表查找
int SLFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SLErase(SL* ps, int pos);// 扩容，2倍合适
void SLCheckCapacity(SL* ps);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0; // 结合性，从右往左赋值
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}// 扩容  2倍合适
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPushBack(SL* ps, SLDataType x) // 尾插
{assert(ps);/*SLCheckCapacity(ps);ps->a[ps->size++] = x;*/SLInsert(ps, ps->size, x);
}void SLPopBack(SL* ps) // 尾删
{assert(ps);/*// 暴力检查assert(ps->size > 0);温柔的检查//if (ps->size == 0)//	return;ps->size--;*/SLErase(ps, ps->size - 1);
}void SLPushFront(SL* ps, SLDataType x) // 头插
{assert(ps);/*SLCheckCapacity(ps);//挪动memmove(&(ps->a[1]), &(ps->a[0]), sizeof(SLDataType) * ps->size);//头插ps->a[0] = x;ps->size++;*/SLInsert(ps, 0, x);
}void SLPopFront(SL* ps) // 头删
{assert(ps);/*assert(ps->size > 0);memmove(&(ps->a[0]), &(ps->a[1]), sizeof(SLDataType) * ps->size);ps->size--;*/SLErase(ps, 0);
}//顺序表查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->a[i]){return i;}}return -1;
}// 顺序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);// 插入时 = size 相当于尾插SLCheckCapacity(ps);//挪动memmove(&(ps->a[pos + 1]), &(ps->a[pos]), sizeof(SLDataType) * (ps->size - pos));//插入ps->a[pos] = x;ps->size++;
}// 顺序表删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//覆盖memmove(&(ps->a[pos]), &(ps->a[pos + 1]), sizeof(SLDataType) * (ps->size - pos - 1));ps->size--;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"void TestSeqList1()//第一组测试用例
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPushBack(&s, 7);SLPushBack(&s, 8);SLPrint(&s);SLPopBack(&s);SLPopBack(&s);SLPrint(&s);SLPushFront(&s, 9);SLPushFront(&s, 10);SLPushFront(&s, 11);SLPushFront(&s, 12);SLPushFront(&s, 13);SLPushFront(&s, 14);SLPrint(&s);SLPopFront(&s);SLPopFront(&s);SLPopFront(&s);SLPrint(&s);SLInsert(&s, 3, 30);SLPrint(&s);SLErase(&s, 3);SLPrint(&s);int pos = SLFind(&s, 3);if (pos == -1){printf("没找到\n");}else{printf("找到了，下标是：%d", pos);}SLDestroy(&s);
}int main()
{TestSeqList1();return 0;
}