【数据结构】顺序表

一、顺序表的基本概念

1.1 概念

顺序表是一种线性表的存储结构，其特点是：使用一段连续的存储空间存储线性表中的数据元素，通过数组实现，具有随机访问的能力。

可以把顺序表直接理解为数组，只不过这个数组里可以存各种类型的数据。

连续存储：顺序表在内存中占用一段连续的地址空间。假设有数组a，a[2] 的地址加1一定为a[3]。
随机访问：顺序表支持通过下标访问元素。不用从头到尾遍历数组，通过下标访问的时间复杂度为O(1)。

2.2 分类

顺序表有静态顺序表和动态顺序表之分。静态就是固定长度的数组，动态数组可以根据数据多少进行动态开辟。

静态顺序表👇

//顺序表的大小
#define N 100 
//可更改存储的数据的类型
typedef int SLDataType;typedef struct SeqList
{SLDataType array[N];size_t size;
}SeqList;

每次运行为数组开N个大小的空间，此时如果只有几个数据就会造成空间的浪费，但是如果有超过N的数据个数，无法存储，虽然里面也可以进行空间的动态开辟，但还是比较麻烦，不如直接用动态顺序表。（平时小作业或者OJ可以用静态的比较简单直接）。

二、动态顺序表的基本操作

以下部分就基于动态顺序表的增删查改进行一步步实现和完善。

主要包括：

1.顺序表结构定义

2.顺序表的初始化和销毁

3.顺序表的扩容

5.顺序表的打印

6.顺序表元素的查找

7.顺序表元素的插入（尾插，头插，在pos位置插入）

8.顺序表元素的删除（头删，尾删，删除pos位置元素）

9.顺序表元素的修改

2.1 顺序表的结构定义

在C语言中，顺序表可以用结构体结合数组实现，结构体通常包含：数组 data 用于存储顺序表中的数据元素； size 记录此时顺序表中的元素个数； capacity 表示该顺序表的容量。

-- 容量并不等于元素个数，capacit >= size 。

-- 顺序表可以存各种类型的元素，所以可以typedef一个SLDataType记录方便修改需存储的数据类型。

-- struct SeqList 太长，可以typedef为 SL

//存储的数据类型
typedef int SLDataType;typedef struct SeqList
{SLDataType* data;//数据元素个数int size;//顺序表容量int capacity;
}SL;

2.2 初始化

对于动态顺序表需要在初始化时分配一段内存空间(也可以=NULL，但还是开了空间比较好，开了空间就要检查)，供存储数据使用，确保使用前的状态合法。对于元素个数和容量也需要赋初值，已确保之后的正确访问与使用。(初始化就是申请一块空间并清理，销毁是归还这块空间，释放后就不能正常访问这块空间了。)

而且这个结构体只是一个数据类型，之后创建的每个结构体变量都是独立的。调用的函数也只对那一个结构体变量生效。函数要改变变量，就需要传入指针。

void SLInit(SL* ps)
{assert(ps);ps->data = (SLDataType*)malloc(sizeof(SLDataType) * 4);//没有初始化成功，程序异常，退出if (ps->data == NULL){perror("malloc failed");exit(-1);}ps->size = 0;ps->capacity = 4;
}

2.3 销毁

释放动态分配的资源，防止内存泄漏，避免非法操作。

void SLDestroy(SL* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->size = 0;ps->capacity = 0;
}

2.4 尾插

顺序表的尾插还是比较方便的，直接在最后一个元素的后面插入新元素，再将size++。不过要考虑顺序表的容量是否足够，不足要扩容。

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->data[ps->size] = x;ps->size++;
}

2.5 扩容

因为有好几个插入的函数，需要检查是否需要扩容，可以直接把检查和扩容一起做了。

在使用relloc扩容时，最好使用临时变量tmp。如果扩容失败，返回NULL被直接赋值给data，导致原数据丢失。

tmp不需要被释放，因为他只是一个指针变量，并没有存有效数据，而且他只是一个局部变量，出了作用域就销毁了。

也不需要free(a),realloc的扩容成功会出现两种情况，原地扩和异地扩，也不用考虑如果出现的是异地扩是否需要释放原来的data数据。因为realloc在扩容成功时会自动释放旧内存。

2.6 打印

为了方便观察顺序表的内容可以创建一个打印的函数。

void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");
}

2.7 尾删

尾删就是从尾部删除一个数据，只要size--就行了（因为我们去访问使用的时候都是依据size的，不需要抹除数据，不需要修改，更不能释放），capacity也不会改变。但是要注意只有size>0的时候，才可以实现尾删。也可以使用 if(ps->size == 0) return;

void SLPopBack(SL* ps)
{assert(ps->size);ps->size--;
}

2.8 头插

顺序表的缺点之一就是插入删除的时间复杂度大，特别是头插，头删，需要挪动数据覆盖。

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//往后挪动覆盖数据int end = ps->size - 1;while (end >= 0){ps->data[end + 1] = ps->data[end];--end;}ps->data[0] = x;ps->size++;
}

2.9 头删

-- 删掉最前面一个元素。其实只要把所有元素都往前覆盖一个就好了。注意检查size是否>0。如果不检查看起开可能没什么问题，但是size有可能会变成负数，这是不行的。

-- 头删不能直接data++，看似没有问题，释放的时候会出错，释放时要从申请的头指针开始释放。

void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);int start = 0;//往前覆盖数据while (start < ps->size - 1){ps->data[start] = ps->data[start + 1];start++;}ps->size--;
}

2.10 pos位置插入

pos一般表示的是下标，一般配着查找使用。pos有范围，>=0 && <=size 。和头插的代码有些相似。

其实头插、头删、尾插、尾删可以直接复用在pos位置插入和在pos位置删除的代码。

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->data[end + 1] = ps->data[end];--end;}ps->data[pos] = x;ps->size++;
}

2.11 删除pos位置

和头删也是相似的。

void SLErase(SL* ps, int pos)
{assert(ps);assert(ps->size && pos >= 0 && pos <= ps->size);int start = pos;while (start < ps->size - 1){ps->data[start] = ps->data[start + 1];start++;}ps->size--;
}

2.12 查找

找到返回下标，否则返回-1；

int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->data[i] == x)return i;}return -1;
}

2.13 修改

        修改能不能直接 `s3.a[3] = 6;` 直接访问。
（这样确实是可以的，但是数据结构原则，不要轻易去直接访问数据，非常的不安全）
   - 假如有一天写了一个这样的代码↓,但是输入的时候输入的是0 100，就会发生错误，因为此时scanf输入两个数据需要用逗号隔开，而我们没注意：
   ```
   int pos = 0;
       int x = 0;
       scanf("%d,%d", &pos, &x);
       s3.a[pos] = x;
   ```
   - 其次，如果通过函数去操作就会有各种检查，越界会明确告诉你，但是直接访问报错就需要一步一步调试可能才知道错误。
   - 函数也更容易看出接口

void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->data[pos] = x;
}

2.14 菜单

为了让这个顺序表可读性更高，更具有操作性，可以设置一个菜单。

void menu()
{printf("*************************************************\n");printf("**************请选择相应操作的数字***************\n");printf("1、尾插				2、头插\n");printf("3、在指定位置插入		4、在指定位置删除\n");printf("5、头删				6、尾删\n");printf("7、查找				8、修改\n");printf("9、打印	\n");printf("-1退出\n");printf("***********************************************\n");
}int main()
{SL s1;SLInit(&s1);//选项默认为0int option = 0;do{menu();scanf("%d", &option);if (option == 1){printf("请依次输入你要插入的数据个数和数据:\n");int n = 0;int x = 0;scanf("%d", &n);assert(n > 0);for (int i = 0; i < n; ++i){scanf("%d", &x);SLPushBack(&s1, x);}}else if (option == 2){printf("请依次输入你要插入的数据个数和数据:\n");int n = 0;int x = 0;scanf("%d", &n);assert(n > 0);for (int i = 0; i < n; ++i){scanf("%d", &x);SLPushFront(&s1, x);}}else if (option == 3){printf("请依次输入你要插入的数据位置下标和数据:\n");int pos = 0;int x = 0;scanf("%d", &pos);scanf("%d", &x);SLInsert(&s1, pos, x);}//省略一部分...else if (option == 9){SLPrint(&s1);}} while (option != -1);SLDestroy(&s1);return 0;
}