目录

概念及结构

接口函数实现

顺序表的初始化

容量判断

 顺序表尾插

 顺序表尾删

顺序表头插

顺序表头删

顺序表查找

顺序表指定位置插入

顺序表指定位置删除

打印顺序表

销毁顺序表

顺序表完整代码

概念及结构

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

顺序表一般分为：

1、静态顺序表——使用定长数组进行存储元素。

#define N 100
//顺序表的静态存储
typedef int SLDatatype;
typedef struct SeqList
{SLDataType Data[N]; //定长数组int size;           //有效数据个数
}SeqList;

这种存储方式在存储数据时比较有局限性，当数据存储量非常小的时候，数组长度太长，会造成空间的浪费；当数据存储量非常大的时候，数组空间可能会不够，但是这种存储方式不能进行扩容。所以在实现顺序表时，我们通常使用的是动态顺序表。这样能够提高我们的空间利用率。

2、动态顺序表——使用动态开辟的数组进行存储元素。

//顺序表的动态存储
typedef int SLDatatype;
typedef struct SeqList
{SLDataType* Data; //定长数组int size;         //有效数据个数int capacity;     //空间容量的大小
}SeqList;

接口函数实现

顺序表的初始化

//初始化链表
void SLInit(SeqList* ps)
{assert(ps);   //判空，如果传入的空指针，后面对它进行解引用就会报错ps->data = NULL; //将data初始化为空指针ps->capacity = ps->size = 0;
}

现在顺序表的初始化完成了，接下来就是顺序表的增删查改了。

在实现顺序表增加元素的函数功能前，首先我们先实现一个检查顺序表是否已经存满。如果已经存满了，那么我们就需要对它进行扩容。

容量判断

//容量判断
void Check_Capacity(SeqList* ps)
{assert(ps);if (ps->capacity == ps->size) //判断顺序表中有效数据个数是否已经达到容量大小{int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;//如果容量为0的话，此时就是第一次向顺序表中添加元素，capacity就设为4//如果容量不为0，此时就是有效数据个数达到容量，就进行扩容，新容量设置为原容量的2倍SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType));if (tmp == NULL)  //如果扩容失败，就终止程序。{perror("ralloc fail");exit(-1);}ps->data = tmp;ps->capacity = new_capacity;}
}

这里扩容使用的是realloc函数，当我们进行第一次插入的时候，ps->data指针还是空指针，这时我们也可以使用realloc，realloc函数在使用的时候，如果传入的指针是空指针，它的作用就与malloc相同。 

 顺序表尾插

//顺序表尾插
void SL_PushBack(SL* ps, SLDataType x)
{assert(ps);Check_Capacity(ps);ps->data[ps->size] = x;ps->size++;
}

 顺序表尾删

//顺序表尾删
void SL_PopBack(SL* ps)
{assert(ps);assert(ps->size > 0); //如果顺序表中已经没有元素，那么就不用进行删除，所以//这里需要检查顺序表中是否还有元素。ps->size--;
}

 无论是尾删还是头删，都要对顺序表进行检查表中是否还有元素。

顺序表头插

//顺序表头插
void SL_PushFront(SL* ps, SLDataType x)
{assert(ps);Check_Capacity(ps); //检查容量//将所有数据向后移动一位for (int i = ps->size - 1; i >= 0; i--){ps->data[i + 1] = ps->data[i];}ps->data[0] = x;ps->size++;
}

头插时不仅要对容量进行检查，同时，我们也要将数据向后移动一位再进行插入操作，不然会造成数据丢失。

顺序表头删

//顺序表头删
void SL_PopFront(SL* ps)
{assert(ps);//如果顺序表中只有一个数据，那么直接将数据个数-1//如果对数据进行挪动，会造成越界if (ps->size == 1){ps->size--;return;}如果数据个数不为1，就将数据中第2个到最后一个都往前移动一位for (int i = 1; i < ps->size; i++){ps->data[i - 1] = ps->data[i];}ps->size--;
}

顺序表查找

//顺序表查找
int SL_Find(SeqList* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->data[i] == x){//找到就返回下标return i;}}//找不到就返回-1return -1;
}

顺序表指定位置插入

//顺序表指定位置插入
void SL_Insert(SeqList* ps, int pos, SLDataType x)
{assert(ps);//判定pos是否合法assert(pos <= ps->size);assert(pos >= 0);Check_Capacity(ps); //检查容量是否够用//将pos位置后的元素全部都向后移动一位for (int i = ps->size-1; i >= pos; i--){ps->data[i + 1] = ps->data[i];}ps->data[pos] = x;ps->size++;
}

顺序表指定位置删除

//顺序表指定位置删除
void SL_Erase(SeqList* ps, int pos)
{assert(ps);//检查pos位置是否合法assert(pos >= 0);assert(pos < ps->size);//将pos位置后面的元素全都向前移动一位for (int i = pos; i < ps->size; i++){ps->data[i] = ps->data[i + 1];}ps->size--;
}

有了顺序表指定位置的插入和删除后，我们就可以对尾插尾删、头插头删进行改写：

//尾插
void SL_PushBack(SeqList* ps, SLDataType x)
{SL_Insert(ps, ps->size, x);
}//尾删
void SL_PopBack(SeqList* ps)
{SL_Erase(ps, ps->size - 1);
}
//头插
void SL_PushFront(SeqList* ps, SLDataType x)
{SL_Insert(ps, 0, x);
}
//头删
void SL_PopFront(SeqList* ps)
{SL_Erase(ps,0);
}

打印顺序表

//打印顺序表
void SLPrint(SeqList* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");
}

销毁顺序表

//销毁顺序表
void SL_Destroy(SeqList* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->capacity = ps->size = 0;
}

顺序表完整代码

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include typedef int SLDataType;
typedef struct SeqList
{SLDataType* data;int size;int capacity;
}SeqList;//初始化顺序表
void SLInit(SeqList* ps);//删除顺序表
void SL_Destroy(SeqList* ps);//打印顺序表
void SLPrint(SeqList* ps);//检查容量
void Check_Capacity(SeqList* ps);//尾插尾删
void SL_PushBack(SeqList* ps,SLDataType x);
void SL_PopBack(SeqList* ps);//头插头删
void SL_PushFront(SeqList* ps, SLDataType x);
void SL_PopFront(SeqList* ps);//顺序表查找
int SL_Find(SeqList* ps, SLDataType x);//顺序表指定位置插入
void SL_Insert(SeqList* ps, int pos, SLDataType x);//顺序表指定位置删除
void SL_Erase(SeqList* ps, int pos);

SeqList.c

#include "SeqList.h"void SLInit(SeqList* ps)
{assert(ps);  ps->data = NULL; ps->capacity = ps->size = 0;
}void SL_Destroy(SeqList* ps)
{assert(ps);free(ps->data);ps->data = NULL;ps->capacity = ps->size = 0;
}void SLPrint(SeqList* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->data[i]);}printf("\n");
}void Check_Capacity(SeqList* ps)
{assert(ps);if (ps->capacity == ps->size) {int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType));if (tmp == NULL){perror("ralloc fail");exit(-1);}ps->data = tmp;ps->capacity = new_capacity;}
}void SL_PushBack(SeqList* ps, SLDataType x)
{//assert(ps);//Check_Capacity(ps);//ps->a[ps->size] = x;//ps->size++;SL_Insert(ps, ps->size, x);
}void SL_PopBack(SeqList* ps)
{//assert(ps);//assert(ps->size > 0);//ps->size--;SL_Erase(ps, ps->size - 1);
}void SL_PushFront(SeqList* ps, SLDataType x)
{//assert(ps);//Check_Capacity(ps);//for (int i = ps->size - 1; i >= 0; i--)//{//	ps->a[i + 1] = ps->a[i];//}//ps->a[0] = x;//ps->size++;SL_Insert(ps, 0, x);
}void SL_PopFront(SeqList* ps)
{//assert(ps);//if (ps->size == 1)//{//	ps->size--;//	return;//}//for (int i = 1; i < ps->size; i++)//{//	ps->data[i - 1] = ps->data[i];//}//ps->size--;SL_Erase(ps,0);
}int SL_Find(SeqList* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->data[i] == x){return i;}}return -1;
}void SL_Insert(SeqList* ps, int pos, SLDataType x)
{assert(ps);assert(pos <= ps->size);assert(pos >= 0);Check_Capacity(ps);for (int i = ps->size-1; i >= pos; i--){ps->data[i + 1] = ps->data[i];}ps->data[pos] = x;ps->size++;
}void SL_Erase(SeqList* ps, int pos)
{assert(ps);assert(pos >= 0);assert(pos < ps->size);for (int i = pos; i < ps->size; i++){ps->data[i] = ps->data[i + 1];}ps->size--;
}

以上就是顺序表相关实现的全部内容了，希望能够帮到大家。