数据结构（C语言）：顺序表

目录

一、线性表是什么

线性表的存储结构

二、顺序表

总结

一、线性表是什么

在C语言中，线性表（Linear List）是一种最基本的数据结构之一，它是具有相同数据类型的n（n≥0）个数据元素的有限序列。线性表中的数据元素按照线性顺序排列，每个数据元素都有唯一的前驱和后继（头尾元素除外），使得数据元素之间存在一对一的线性关系。

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

线性表的存储结构

在C语言中，线性表主要有两种存储方式：

1. 顺序存储结构（数组）：
   • 优点：随机访问速度快，存储空间连续，容易实现。
   • 缺点：插入和删除操作需要移动大量元素，可能会造成内存浪费或溢出。
   • 实现：使用数组（如 int arr[100];）来存储线性表的元素。
2. 链式存储结构（链表）：
   • 优点：插入和删除操作方便，只需修改指针，不会浪费存储空间。
   • 缺点：随机访问速度慢，需要额外的存储空间来存储指针。
   • 实现：使用结构体和指针来构建链表节点，每个节点包含数据域和指针域。

二、顺序表

1. 概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下，采用数组存储。

注意：

        顺序表和数组的区别：顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口。

 而数组分为两种，一种是静态的，一种是动态的，导致顺序表也分为两种，底层用动态数组的就是动态顺序表，底层用静态数组的就是静态顺序表。

1.动态顺序表

#define N 100
typedef int DataType;
typedef struct SqList {
	DataType* arr;
	int size;      //当前数据的长度
	int capaity;    //顺序表的容量
}SL;

2.静态顺序表 

#define N 100
typedef int DataType;
typedef struct SqList {
	DataType arr[N];
	int size;      //当前数据的长度
	int capaity;    //顺序表的容量
}SL;

 在这里，因为静态数组存在一些内存上的缺陷，空间给少了就不够用，给多了就造成空间的浪费，我们就选用动态数组当作我们顺序表的底层存储结构。

三、顺序表的实现

这里，我们列举了顺序表的初始化、尾插、尾删、头删、查找、插入、销毁 这8个函数来实现顺序表中涉及到的一些常用的实现方法，来满足我们平常对顺序表的一些操作。

假如，我们实例化一个顺序表s1，下面的操作均争对s1展开。

SL s1;

 seqList.h头文件所有的函数

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define N 100
typedef int DataType;
typedef struct SqList {
	DataType* arr;
	int size;      //当前数据的长度
	int capaity;    //顺序表的容量
}SL;
//1.初始化
void SLInit(SL* ps);
//2.尾插法
void SLPushBack(SL* ps, DataType e);
//3.头插法
void SLPushFront(SL* ps, DataType e);
//4.尾删
void SLPopBack(SL* ps);
//5.头删
void SLPopFront(SL* ps);
//5.查找x,查找到了就返回下标
int SLFind(SL* ps, DataType x);
//6.在指定位置插入数据
void SLInsert(SL* ps, int pos, DataType e);
//7.删除指定位置的数据
void SLErase(SL* ps, int pos);
//8.销毁
void SLDesTroy(SL* ps);

 1. 初始化顺序表 s1

//1.初始化顺序表
void SLInit(SL* ps) {
	ps->arr = NULL;
	ps->size = ps->capaity = 0;
}
void SLcheckCapacity(SL* ps) {
	//空间不够，先增加空间(增加的是DataType),在赋值
	if (ps->size == ps->capaity) {
		//容量=0时，容量变为4,否则 容量 = capaity * 2
		int newCapacity = ps->capaity == 0 ? 4 : ps->capaity * 2;
		//申请空间
		DataType* temp = (DataType*)realloc(ps->arr, newCapacity * sizeof(DataType));
		if (temp == NULL) {
			perror("realloc fail!");    //申请空间失败
			exit(1);
		}
		ps->arr = temp;        //将临时地址的给 ps->arr
		ps->capaity = newCapacity;   //将新的空间大小赋值给capaity
	}
}

在这里，我们需要对顺序表s1进行操作，所以一级指针去接收s1的地址，将s1的地址给指针ps。

注意：这里不能用值传递，否则会创建一个临时顺序表ps，ps是s1的临时拷贝，对ps的操作不能改变原顺序表s1 

 1.尾插法：直接在当前有效值的后面加上要插入的数据。

2.头插法：遍历当前的数据后移一位，把下标为0的位置插入数据。

尾删和头删与上图类似，这里就不画图示意了。 

//2.尾插法
void SLPushBack(SL* ps, DataType e) {
	SLcheckCapacity(ps);    //此时，传的是指针（地址）
	ps->arr[(ps->size)++] = e;
}
void SLPushFront(SL* ps, DataType e) {
	SLcheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = e;
	(ps->size)++;
}

3.  在指定位置插入：把这个位置之后的所有元素后移一位，然后在该位置插入数据。

//6.在指定位置插入数据
void SLInsert(SL* ps, int pos, DataType e) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckCapacity(ps);
	for (int i = ps->size; i > pos; i--) {
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = e;
	(ps->size)++;
}

  seqList.h头文件所有的函数的实现

  seqList.c文件

#include"SeqList.h"
//1.初始化顺序表
void SLInit(SL* ps) {
	ps->arr = NULL;
	ps->size = ps->capaity = 0;
}
void SLcheckCapacity(SL* ps) {
	//方法1.
	/*if (ps == NULL) {
		return;
	}*/
	//空间不够，先增加空间(增加的是DataType),在赋值
	if (ps->size == ps->capaity) {
		//容量=0时，容量变为4,否则 容量 = capaity * 2
		int newCapacity = ps->capaity == 0 ? 4 : ps->capaity * 2;
		//申请空间
		DataType* temp = (DataType*)realloc(ps->arr, newCapacity * sizeof(DataType));
		if (temp == NULL) {
			perror("realloc fail!");    //申请空间失败
			exit(1);
		}
		ps->arr = temp;        //将临时地址的给 ps->arr
		ps->capaity = newCapacity;   //将新的空间大小赋值给capaity
	}
}
//2.尾插法
void SLPushBack(SL* ps, DataType e) {
	SLcheckCapacity(ps);    //此时，传的是指针（地址）
	ps->arr[(ps->size)++] = e;
}
void SLPushFront(SL* ps, DataType e) {
	SLcheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = e;
	(ps->size)++;
}
//3.尾删
void SLPopBack(SL* ps) {
	assert(ps && ps->size > 0);  //ps不为NULL，ps->size不为0
	(ps->size)--;
}
//4.头删
void SLPopFront(SL* ps) {
	assert(ps && ps->size > 0);
	for (int i = 0; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	(ps->size)--;
}
//5.查找x,查找到了就返回下标
int SLFind(SL* ps, DataType x) {
	for (int i = 0; i < ps->size; i++) {
		if (ps->arr[i] == x)
			return i;
	}
	//没找到
	return -1;
}
//6.在指定位置插入数据
void SLInsert(SL* ps, int pos, DataType e) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckCapacity(ps);
	for (int i = ps->size; i > pos; i--) {
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = e;
	(ps->size)++;
}
//7.删除指定位置的数据
void SLErase(SL* ps, int pos) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	(ps->size)--;
}
//8.销毁
void SLDesTroy(SL* ps) {
	if (ps->arr)      //判断地址是否合法
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capaity = 0;
}

 test.c测试文件

#include"SeqList.h"
void SLTest() {
	SL s1;
	
}
int main() {
	SLTest();
	return 0;
}

总结

这里的顺序表，相关操作和数组的操作几乎一样，我们在操作原顺序表的时候，要注意存储容量是否满了，要是满了就扩容，只要是操作原顺序表就要传地址，不要传值。最后，希望各位大佬对本篇文章多多提出意见。