数据结构（C语言）——顺序表详解_顺序表的数据结构

一、数据结构简介

数据结构是计算机存储和组织数据的方式。常用的数据结构有：数组（Array）、栈（Stack）、队列（Queue）、链表（Linked List）、树（Tree）、图（Graph）、堆（Heap）等；而数据结构又可以通过逻辑结构与物理结构进行分类，逻辑结构是指数据元素之间的逻辑关系，也就是数据元素之间的逻辑排列方式。常见的逻辑结构有线性结构、树形结构、图形结构等。物理结构是指数据元素在计算机内存中的存储方式，常见的物理结构包括顺序存储结构和链式存储结构。

二、顺序表简介

线性表是一种数据结构，线性表是具有相同特性的数据结构的集合。而它的物理结构上不一定连续，但是在逻辑结构上抽象为线性结构，一定是连续的。常见线性表有顺序表、链表、栈、队列、字符串等。今天我们将介绍顺序表

顺序表是线性表的一种，他在逻辑结构和物理结构上都连续，且为线性。顺序表的本质是数组。

三、顺序表的分类

顺序表可以分为静态顺序表和动态顺序表。静态顺序表是创建结构体时就开辟了固定的一块空间，而动态顺序表则是在使用时再主动申请空间。很明显，静态顺序表的缺陷是我们在一开始就将它所需要的空间固定下来了，如果它的空间过小，我们在存储数据时就会遗漏泄露数据，如果它的空间过大，则会浪费空间。而动态顺序表可以按需索取空间，动态顺序表可以动态地进行增容或者删减。

下面我们来看一下代码表示。

1、静态顺序表

typedef int Datatype//我们将int 重新命名，这样可以方便我们更换数据类型
 
typedef struct SeqList
{
    int arr[10];//假设在内存静态区开辟固定的10个整形字节大小的空间
    int size;//顺序表中数据个数
    int capacity;//顺序表的容量，取决于arr[]的大小
}SL;

2、动态顺序表

typedef int Datatype//我们将int 重新命名，这样可以方便我们更换数据类型
 
typedef struct SeqList
{
    int* arr;//定义一个指针，用于之后申请和更改空间
    int size;//顺序表中数据个数
    int capacity;//顺序表的容量
}SL;

四、顺序表的基本操作

我们主要介绍动态顺序表的基本操作，静态顺序表的操作可以参考静态数组的做法。

1.动态顺序表的初始化

由于动态顺序表内涵指针，所以我们需要对其中的指针初始化，当我们不知道具体需要申请多大空间时可以赋NULL，也可以用malloc申请空间。

//对动态顺序表进行初始化
void SLInit(SL* ps)//传参为结构体的地址
{
    ps->arr=NULL;//可以赋NULL进行初始化，也可以申请空间 ps->arr=(int *)malloc(10*sizeof(int))
    int ps->size=ps->capacity=0;
}

2.动态顺序表的销毁

因为动态顺序表是在堆区申请了空间，我们需要手动释放掉这块空间。

void SLDestory(SL *ps)
{
    if(ps->arr)//判断ps是否为空指针
    {
        free(ps->arr);//用free函数对申请的空间进行释放
    }
    ps->arr=NULL;//赋空指针，防止错误错误访问其它空间
    ps->size=ps->capacity=0;
}

3.尾插与头插操作以及扩容操作

有的时候我们需要在顺序表的末端或者头部或者其他位置插入一些数据，这个时候我们就需要头插与尾插操作等，今天我们先介绍这两种操作。

1.尾插

尾插，顾名思义，就是在顺序表的末端插入新的数据，这个操作看似比较简单，但是我们需要考虑到很多问题，比如，是否有足够空间让我们插入数据？如果空间不够我们应该如何扩容？扩与尾插后的数据个数以及空间大小？这些都是我们需要考虑到的问题。

void SLPushBack(SL* ps,Datatype x)//地址传递，并且传递需要尾插的数据
{
    assert(ps);//我们需要对传过来的结构体地址判断是否为空，为空则会造成空间无法访问
              //我们可以用到assert断言，也可以用if进行判断
 
    //下面我们需要对顺序表的空间进行判断
    if(ps->size==ps->capacity)//如果实际数据个数等于我们所申请的空间，那么我们就需要进行扩容处理
    {
        int newCapacity = ps->arr == 0?4:2 * ps->capacity;
                //判断arr空间大小，如果为0就假设给4个单位的空间，
               //不为0则给两倍大小的空间（也可以给3倍，按照经验给定，不浪费也不缺乏）
 
        Datatype *tmp = (Datatype *)realloc(ps->arr ,newCapacity*sizeof(Datatype));
              //我们先用临时指针进行扩容，因为realloc有时申请空间会失败。
        if(tmp==NULL)
        {
            perror("realloc fail");
            exit(1);//如果扩容失败，则退出程序
        }
        ps->arr =tmp;//如果成功了就赋给arr
    }
    ps->arr[ps->size++]=x;//此处完成了数据个数增加和尾插数据两个操作
}

2.扩容

其实扩容是我们在顺序表中经常用到的步骤，我们可以将它写成一个函数，方便我们使用以及简化代码。

void SLCheckCapacity(SL * ps)
{
    assert(ps);
 if(ps->size==ps->capacity)//如果实际数据个数等于我们所申请的空间，那么我们就需要进行扩容处理
    {
        int newCapacity = ps->arr == 0?4:2 * ps->capacity;
                //判断arr空间大小，如果为0就假设给4个单位的空间，
               //不为0则给两倍大小的空间（也可以给3倍，按照经验给定，不浪费也不缺乏）
 
        Datatype *tmp = (Datatype *)realloc(ps->arr ,newCapacity*sizeof(Datatype));
              //我们先用临时指针进行扩容，因为realloc有时申请空间会失败。
        if(tmp==NULL)
        {
            perror("realloc fail");
            exit(1);//如果扩容失败，则退出程序
        }
        ps->arr =tmp;//如果成功了就赋给arr
    }
}

3.头插

头插操作就是在顺序表（数组）的首位插入一个数据，那么我们需要思考如何进行操作。首先，为了确保数据的完整性，我们需要将arr[0]空出来，那么我们就需要将原顺序表的数据整体往后挪动一个单位。这里也要涉及空间大小判断以及数据的增加。

void SLPushFront(SL *ps)
{
    assert(ps);
    SLCheckCapacity(ps);//将扩容操作写成一个函数会简化很多代码
    //下面进行整体后挪操作
    for(int i=ps->size;i>0;i--)
    {
        ps->arr[i]=ps->arr[i-1];
    }
    //头插操作
    ps->arr[0] = x;
    ps->size++;//注意插入了数据,size要增加
}

4.尾删和头删操作

1.尾删

尾删操作也很好理解，就是删除末尾的数据，同样要注意一些细节，如顺序表大小是否为0，数据个数要进行删减等

void SLPopBack(SL* ps)//尾删
{
	assert(ps);//顺序表为空不能执行删除,如果空则会访问arr[-1]造成越界访问
	assert(ps->size);//size不能为空
	--ps->size;//此处直接将size的大小减一，同时也删除了数据
}

2.头删

和头插反着理解，我们要先删除第一个数据，再将顺序表整体前移一个单位

void SLPopFront(SL* ps)//头删
{
	assert(ps);//顺序表为空不能执行删除,如果空则会访问arr[-1]造成越界访问
	assert(ps->size);
	
	//数据整体往前挪动一位
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}

5.打印顺序表

我们有的时候需要一边对顺序表进行操作，一边要测试我们的代码是否正确，除了进行调试外，我们还可以将顺序表打印出来直观地观察。

void SLPrint(SL ps)//打印，此处我们进行值传递即可
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
}

以上就是动态顺序表的基本操作，感谢各位的浏览。希望这篇文章对你理解和使用顺序表有帮助，如有不足或者错误请指出。