【数据结构】顺序表

目录

前言：

线性表

先说一下线性表

线性表是一种数据结构，它由一组元素组成，这些元素按照一定的顺序排列。线性表中的元素可以是任意类型的，比如数字、字符、字符串、结构体等，在线性表中，每个元素都有一个编号，这个编号称作元素的下标或索引，从0开始递增。线性表中的元素之间存在一种线性关系，即元素只能按照一定的顺序依次排列，每个元素最多只有两个相邻的元素。常见的线性表包括数组、链表、栈、队列等。线性表通常用于实现各种算法和数据结构，如查找、排序、图论等。

 首先这里涉及 的一些 知识点 ：结构体  和  malloc 等动态内存函数

如果感到理解有些难度可以先去学习上述 知识点。

 顺序表

一、顺序表的存储

存储定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

1.顺序表的静态存储

 即 使用固定长度的数组来存储元素

#define N 25

//顺序表的静态存储
typedef int SLDDataType;
typedef struct SeqList 
{
	SLDDataType arr[N]; //定长数组
	size_t size;	//有效数据的个数
}SeqList;

该种定义的方法适用于已知数据元素的个数的情况下，提供的大小是固定的，定义N大了，就会浪费空间，定义N小了，就不够用。所以根据情况比较推荐适用动态顺序表。

2.顺序表的动态存储

typedef struct SeqList 
{
	SLDataType* a;	//定义的动态数组
	int size;		//当前数据元素的个数
	int capacity;	//数组的容量
}SeqList;

先定义一个指针，使用malloc函数进行开辟

 下面采用动态扩容的方式

二、顺序表的初始化

//初始化顺序表
void SeqListInit(SeqList* ps) 
{
	assert(ps);		//断言一下避免出现空指针
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

接下我们会顺序表的元素进行增、删、改、查，这样就需要对顺序表先进行检查

三、顺序表的检查(动态增容)

//顺序表的检查
void SLCheckCapacity(SeqList* ps) 
{
	//顺序表满了，使用realloc增容
	if (ps->size == ps->capacity)//有效数据个数 等于 当前容量
	{
		//先判断一下顺序表是否第一次使用空间
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a,sizeof(SLDataType)*newcapacity);
		if (tmp != NULL) 
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
		else 
		{
			perror("SLCheckCapacity -> realloc");
			return;
		}
	}
}

四、顺序表的销毁释放 

 顺序表的销毁

//顺序表的销毁
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->a != NULL) 
	{
		free(ps->a);//释放动态数组
		ps->a = NULL;
		ps->size = 0;
		ps->size = 0;
	}
}

五、顺序表的头尾操作

1.表尾插入元素

从顺序表的表尾插入元素

// 顺序表的尾插元素
void SeqListPushBack(SeqList* ps,SLDataType x) 
{
	assert(ps);		//避免指针为空
	//先进行顺序表的检查，动态增容
	SLCheckCapacity(ps);

	ps->a[ps->size] = x;//将元素x放到表尾
	ps->size++;		//表示有效个数据个数增加了1个
}

 注意 表尾插入元素的时间复杂度是O(1)

2.表尾删除元素

//表尾删除元素
void SeqListPopBack(SeqList* ps) 
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

 测试效果图：

3.表头插入元素 

思想：先从表尾开始，从前往后移动元素，再把要插入的元素放到表头。当表为空的时候直接插入

//表头插入元素
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	//检查容量，动态扩容
	SLCheckCapacity(ps);

	int end = ps->size - 1;	//指向表尾
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end]; //依次后移
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

 注意：这里的时间复杂度尾O(N^2)

4.表头删除元素

 主要思想：从表的头部开始前移元素

//表头删除元素
void SeqListPopFront(SeqList* ps) 
{
	assert(ps);
	assert(ps->size > 0); //首先的保证有元素
	int begin = 1;
	while (begin <ps->size)
	{
		ps->a[begin-1] = ps->a[begin];	//从头部开始前移
		begin++;
	}
	ps->size--;
}

测试效果图： 

5.顺序表查找某个元素

//顺序表的查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size;i++)
	{
		if (x == ps->a[i]) 
		{
			return i;	//查找成功返回下标
		}
	}
	//查找失败
	return -1;
}

测试效果图：

六、顺序表打印

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

 七、顺序表插入指定位置元素

void SeqListInsert(SeqList* ps, int pos, SLDataType x) 
{
	assert(ps);

	//判断给出的位置是否合法
	assert(pos >= 0 && pos <= ps->size );
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) 
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

测试效果图：

八、 顺序表删除指定位置元素

//顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
    //判断位置是否合法，注意这里是 小于 ps->size.
    //也就是要在数组范围内
	assert(pos >= 0 && pos < ps->size);
	SLCheckCapacity(ps);
	int begin = pos;    //记录指定位置
	while (begin < ps->size-1) 
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

测试效果图：

【总结】 

线性表的顺序存储方式，顺序表。主要介绍对顺序表的增、删、改、查。

另外

说到线性表 ，可能会想到 数组，因为数组的空间是连续的，数组下标从0 到 n ,显然是有序的。

这里多说一下，数组的下标为什么从0开始呢？原因是 数组的下标表示元素在内存中的偏移量，也就是它相对于数组首地址的距离。而第一个元素相对于首地址的偏移量是0，因此第一个元素的下标为0，还有就是 方便 指针 与 数组 之间转换的自洽，p[0] == *(p+0)。 

 在测试效果中，可能会遇到越界的问题（越界一定会报错吗？）
越界不一定报错，系统对越界的检查是一种抽查

1. 进行读操作时，越界是检查不出来的
2. 进行写操作时，如果是修改到标志位才会检查出来。(比如数组，系统会在数组末尾后设有标志位，越界写时，修改到标志位时，就会被检查出来，进行报错)