【数据结构】线性表之《顺序表》超详细实现

前言：相信大家在学完C语言后，对于指针，结构体以及动态内存管理有了一定的见解，那么数据结构像是检验真理的唯一标椎，它考察了你掌握这三种语法的程度，如果掌握的不是很理想的友友们，建议看看鄙人主页总结的文章，好啦，数据结构之旅就正式开始啦。

一.数据结构

数据结构：计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

1.逻辑结构

逻辑结构：数据对象中数据元素之间的相互关系。
逻辑结构分为：集合结构，线性结构，树形结构和图形结构。

2.物理结构

物理结构：数据的逻辑结构在计算机中的存储形式。
物理结构分为：顺序存储结构和链式存储结构。

二.顺序表的分类

顺序表实际属于线性表这个大家族，那么什么是线性表呢？

1. 线性表：是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
2. 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
3. 线性表在物理上存储时，通常以数组和链式结构的形式存储。

1.静态顺序表

#define MAXSIZE 100     //静态顺序表的容量
typedef int SLDataType; //增强程序的可维护性typedef struct SeqList
{SLDataType arr[MAXSIZE];//定长数组int size;               //有效的数据个数
}SeqList;

也许有人会问：这个静态顺序表说的这么神秘，本质上不就是一个数组吗？

答：没错，顺序表的低层就是数组，逻辑结构与物理结构都是连续的。不过顺序表对数组进行了封装，提供了大量常用的接口（所谓接口就是调用函数），方便完成数据进行增，删，查，改等一系列的操作。

静态顺序表的缺点：程序一但运行，数组的大小就确定了，不能被修改。数组大小给小了，空间就不够用；数组大小给大了，空间就白白的浪费掉了；

为了方便对静态顺序表进行扩容，于是，动态顺序表便应运而生。

2.动态顺序表

typedef int SLDataType;//增强程序的可维护性typedef struct SeqList
{SLDataType* arr; //动态的，可以扩容int size;        //有效的数据个数int capacity;    //容量
}SL;

动态顺序表：通过堆区的动态内存管理控制顺序表空间的大小，即容量。

以下介绍的是基于动态顺序表的实现。

三.顺序表的实现

1.创建顺序表

创建一个顺序表结构，包含指向这块空间的起始地址，顺序表中存储数据的个数以及顺序表的最大容量。

typedef int SLDataType;//增强程序的可维护性，改变数据类型，只需改变int即可typedef struct SeqList
{SLDataType* arr; //指向顺序表的起始位置，方便扩容int size;        //顺序表的有效的数据个数int capacity;    //顺序表的容量大小
}SL;//类型的重命名
//等价于typedef struct SeqList SL;

2.初始化顺序表

一般初始化我们都习惯赋值为0，指针赋值为NULL。

void SeqListInit(SL* ps)
{assert(ps);//断言操作，等价于assert(ps != NULL);ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}

3.判断是否扩容

当我们想要增加数据的时候，会遇到容量不够用的问题。所以在此之前，应该检查容量与有效数据之间的关系，判断是否要扩容，接着插入数据。

void SeqListCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity)//顺序表已满，进行扩容操作{//判断顺序表容量是否为0，若为0，开辟储存4个数据大小的空间，若不为0，则容量翻倍int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//开辟空间SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL)//开辟失败{perror("realloc fail!");exit(1);//强行退出程序（表示遇到异常情况）}ps->arr = tmp;//开辟成功，修改指针ps->capacity = newcapacity;//修改容量}
}

注意：若传入realloc的指针为空指针(NULL)，则realloc函数等价于malloc函数。

4.打印顺序表

循环遍历顺序表数据即可。

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

5.插入操作

1.头插

头插的思想：将数据整体向后挪动一位。注意：为了防止覆盖原先的数据，采用从后向前挪动。再进行头部插入，最后有效数据个数+1。

void SeqListPushFront(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);//检查容量int end = ps->size;while (end > 0){ps->arr[end] = ps->arr[end - 1];//将数据整体向后挪动一位。end--;}ps->arr[0] = x;//头插ps->size++;//有效数据个数+1//等价于在下标为0处插入：SeqListInsert(ps, 0, x);
}

2.尾插

尾插的思想：直接在尾部插入，有效数据个数+1即可。

void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);//检查容量ps->arr[ps->size++] = x;//尾插：采用后置++//等价于在下标为ps->size处插入：SeqListInsert(ps, ps->size, x);
}

3.按照下标插入

按照下标插入的思想：与头插的思想相同，只不过是要挪动数据的起始位置不同而已。

void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//判断下标的合法性SeqListCheckCapacity(ps);int end = ps->size;while (end > pos){ps->arr[end] = ps->arr[end - 1];end--;}ps->arr[pos] = x;ps->size++;
}

6.删除操作

1.头删

头删的思想：不是真正意义上的删除数据，而是将头部之后的数据整体向前挪动一位，覆盖头部数据，达到与头删相同的效果，最后有效数据个数-1。注意：为了防止覆盖原先的数据，采用从前向后挪动，这里与头插不同。

void SeqListPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);//前提：顺序表存在数据int start = 0;while (start < ps->size - 1){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;//有效数据个数-1//等价于在下标为0处删除：SeqListErase(ps, 0);
}

2.尾删

尾删的思想：有效数据个数-1即可。

void SeqListPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);//前提：顺序表存在数据ps->size--;//有效数据个数-1//等价于在下标为ps->size - 1处删除：SeqListErase(ps, ps->size - 1);
}

3.按照下标删除

按照下标删除的思想：与头删的思想相同，只不过是要挪动数据的起始位置不同而已。

void SeqListErase(SL* ps, int pos)
{assert(ps);assert(ps->size > 0);//前提：顺序表存在数据assert(pos >= 0 && pos < ps->size);//判断下标的合法性int start = pos;while (start < ps->size - 1){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;
}

7.查找数据

查找的思想：遍历数据，找到了返回下标，未找到返回-1即可。

int SeqListFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;//找到该数据，返回下标}}return -1;//未找到，返回-1
}

8.修改数据

修改的思想：利用下标确定位置，直接修改就行。较为简单。

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

9.清空顺序表

清空的思想：将有效数据个数与容量赋值为0。

void SeqListClear(SL* ps)
{assert(ps);ps->size = 0;ps->capacity = 0;
}

10.销毁顺序表

销毁的思想：由于空间是利用动态内存函数 realloc 在堆区开辟的，所以要及时释放，避免内存泄漏。

void SeqListDestory(SL* ps)
{assert(ps);if (ps->arr != NULL){free(ps->arr);}ps->arr = NULL;//置为NULL，防止野指针SeqListClear(ps);//清空顺序表
}

四.模块化源代码

1.SeqList.h

//#pragma once：防止头文件被重复包含
#ifndef __SEQLIST_H__
#define __SEQLIST_H__#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>typedef int SLDataType;//增强程序的可维护性typedef struct SeqList
{SLDataType* arr; //动态的，可以扩容int size;        //有效的数据个数int capacity;    //容量
}SL;void SeqListInit(SL* ps);//顺序表初始化void SeqListCheckCapacity(SL* ps);//检查顺序表的容量void SeqListPrint(SL* ps);//打印顺序表void SeqListPushBack(SL* ps, SLDataType x);//顺序表尾部插入void SeqListPushFront(SL* ps, SLDataType x);//顺序表头部插入void SeqListPopBack(SL* ps);//顺序表尾部删除void SeqListPopFront(SL* ps);//顺序表头部删除void SeqListInsert(SL* ps, int pos, SLDataType x);//顺序表按照位置（下标）插入void SeqListErase(SL* ps, int pos);//顺序表按照位置（下标）删除int SeqListFind(SL* ps, SLDataType x);//顺序表查找元素值，返回下标void SeqListModify(SL* ps, int pos, SLDataType x);//顺序表按位置（下标）修改void SeqListClear(SL* ps);//清空顺序表void SeqListDestory(SL* ps);//销毁顺序表#endif

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"void SeqListInit(SL* ps)
{assert(ps);//等价于assert(ps != NULL);ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SeqListCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//扩容if (tmp == NULL){perror("realloc fail!");exit(1);//强行退出程序（表示遇到异常情况）}ps->arr = tmp;ps->capacity = newcapacity;}
}void SeqListPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);ps->arr[ps->size++] = x;//SeqListInsert(ps, ps->size, x);
}void SeqListPushFront(SL* ps, SLDataType x)
{assert(ps);SeqListCheckCapacity(ps);int end = ps->size;while (end > 0){ps->arr[end] = ps->arr[end - 1];end--;}ps->arr[0] = x;ps->size++;//SeqListInsert(ps, 0, x);
}void SeqListPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->size--;//SeqListErase(ps, ps->size - 1);
}void SeqListPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int start = 0;while (start < ps->size - 1){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;//SeqListErase(ps, 0);
}void SeqListInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SeqListCheckCapacity(ps);int end = ps->size;while (end > pos){ps->arr[end] = ps->arr[end - 1];end--;}ps->arr[pos] = x;ps->size++;
}void SeqListErase(SL* ps, int pos)
{assert(ps);assert(ps->size > 0);assert(pos >= 0 && pos < ps->size);int start = pos;while (start < ps->size - 1){ps->arr[start] = ps->arr[start + 1];start++;}ps->size--;
}int SeqListFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}void SeqListModify(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;
}void SeqListClear(SL* ps)
{assert(ps);ps->size = 0;ps->capacity = 0;
}void SeqListDestory(SL* ps)
{assert(ps);if (ps->arr != NULL){free(ps->arr);}ps->arr = NULL;SeqListClear(ps);
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"enum//匿名枚举
{EXIT,PUSHBACK,PUSHFRONT,POPBACK,POPFRONT,INSERT,ERASE,FIND,MODIFY,PRINT,CLEAR
};void Menu()
{printf("*************顺序表************\n");printf("****1.尾插           2.头插****\n");printf("****3.尾删           4.头删****\n");printf("****5.插入           6.删除****\n");printf("****7.查找           8.修改****\n");printf("****9.打印          10.清空****\n");printf("****0.退出               ******\n");printf("*******************************\n");
}int main()
{SL sl;SeqListInit(&sl);int select = 0;   //菜单选项SLDataType value; //插入的值int pos = 0;      //插入或删除的下标do{Menu();printf("请选择您的操作：");scanf("%d", &select);switch (select){case EXIT:printf("退出顺序表!");break;case PUSHBACK:printf("请输入您要尾插的值(输入-1代表结束)：");while ((scanf("%d", &value), value != -1)) //逗号表达式{SeqListPushBack(&sl, value);}break;case PUSHFRONT:printf("请输入您要头插的值(输入-1代表结束)：");do{scanf("%d", &value);if (value != -1){SeqListPushFront(&sl, value);}} while (value != -1);break;case POPBACK:SeqListPopBack(&sl);break;case POPFRONT:SeqListPopFront(&sl);break;case INSERT:printf("请输入要插入的《下标》与《值》：");scanf("%d %d", &pos, &value);SeqListInsert(&sl, pos, value);break;case ERASE:printf("请输入要删除的《下标》：");scanf("%d", &pos);SeqListErase(&sl, pos);break;case FIND:printf("请输入要查找的《值》：");scanf("%d", &value);int ret = SeqListFind(&sl, value);if (ret != -1){printf("找到了下标为：%d\n", ret);}else{printf("找不到!");}break;case MODIFY:printf("请输入要修改的《下标》以及修改后的《值》:");scanf("%d %d", &pos, &value);SeqListModify(&sl, pos, value);break;case PRINT:SeqListPrint(&sl);break;case CLEAR:SeqListClear(&sl);break;default:printf("您输入的值错误，请重新选择!\n");break;}} while (select);SeqListDestory(&sl);return 0;
}

五.顺序表必做OJ题

1. 原地移除元素
2. 合并两个有序数组

创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！