【数据结构】顺序表详解

文章目录

前言

一、顺序表是什么

二、顺序表的基本操作

1.初始化

实现思想：

代码如下（示例）：

2.顺序表扩容函数

实现思想：

代码如下（示例）：

3.顺序表头插

实现思想：

代码如下（示例）：

代码实现图（示例）：

4.顺序表尾插

实现思想：

代码如下（示例）：

代码实现图（示例）：

5.顺序表尾删

实现思想：

代码如下（示例）：

代码实现图（示例）：

6.顺序表头删

实现思想：

代码如下（示例）：

代码实现图（示例）：

7.顺序表查找

实现思想：

代码如下（示例）：

代码实现图（示例）：

8.顺序表任意位置插入

实现思想：

代码如下（示例）：

代码实现图（示例）：

9.顺序表任意位置删除

实现思想：

代码如下（示例）：

代码实现图（示例）：

10.销毁顺序表

实现思想：

代码如下（示例）：

11.顺序表打印

实现思想：

代码如下（示例）：

代码实现图（示例）：

12.顺序表修改

实现思想：

代码如下（示例）：

代码实现图（示例）：

总结

---

前言

本文详细的介绍了数据结构当中的最基础的顺序表，可以让初学者对顺序表进行深刻的的理解

---

一、顺序表是什么

顺序表是一种线性结构，它的逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。顺序表可以分配一段连续的存储空间。顺序表上的基本操作有：初始化、顺序表头插、尾插、头删、尾删、查找、插入、删除、修改、销毁顺序表。

二、顺序表的基本操作

1.初始化

一个程序要进行首先一个功能，首先要保证要进行初始化。对数据的初始化就如同汽车的车架子相同。

实现思想：

主体思想：为程序开辟所需要的内存空间，并对开辟的结构体进行初始化

顺序表的初始化，首先要保证头节点地址不为空，然后使用malloc函数开辟一个固定大小结构体的空间，使结构体的当中的指针至指向该空间，并且判断是否开辟失败，如果失败perror函数返回开辟失败的原因，并将结构体的其他的变量进行初始化

代码如下（示例）：

void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType)*4);
	if (ps->a == NULL)
	{
		perror("malloc failed");
		return;
	}
	ps->size = 0;
	ps->capacity = 4;
}

2.顺序表扩容函数

扩容函数主要是为满足增加功能在使用时的内存不足的情况，而该函数可以帮助函数进行空间的扩大

实现思想：

主体思想：先判断该结构体指向的地址不为空，然后进行数据存放数量和空间大小进行比较，如果有效存储空间满了就进行空间的增补，使用realloc函数进行在原来的空间的后面开辟空间，开辟失败就返回原因，并结束程序，开辟成功就在对指针进行重新的赋值有效空间同样进行跟改。

代码如下（示例）：

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	// 满了要扩容
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

3.顺序表头插

顺序表的头插的通俗理解：

就像在超市结账时一条长长的，尽然有序的买完东西人们正在排着队，突然来了一个人，以非常豪横的态度要第一个结账，大家看这个人不好惹，不想自找麻烦，就默认让这个人插了队，这个人插了队不要紧，因为他一个的插队造成第一个位置原本只能一个人的位置，现在两个人站着那里，就比较拥挤，这个时候，那个豪横的人就向后面的人说往后退一个位置，后面的人就和他后面的人说让个位置，就这样一个人的插入让整个队伍向后退了一个位置。

实现思想：

主体思想：判断结构体地址不为空。在判断空间是否足够，不够就扩容，然后利用数据的下标写一个循环进行数据向后移动，循环完的顺序表就可以利用下标在数组头部进行插入，再让有效数据的大小进行加一位

代码如下（示例）：

void SLPushFront(SL* 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++;
}

代码实现图（示例）：

4.顺序表尾插

实现思想：

主体思想：就数值的末端添加一个数据

先判断传的地址是否为空，在进行扩容判断，在通过下标添加数据

代码如下（示例）：

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
	
}

代码实现图（示例）：

5.顺序表尾删

实现思想：

主体思想：将最后一个数值释放控制权

确保传的地址和有效大小不为空，再对有效大小减少一位，这样就删除了尾数据。因为数据在空间当中的存储是比特，释放控制权就是让空间可以被其他人利用，我们不要了，不对其进行访问。

代码如下（示例）：

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

代码实现图（示例）：

6.顺序表头删

实现思想：

主体思想：让数据此前往后的进行打印复制

代码如下（示例）：

void SLPopFront(SL* ps)
{
	assert(ps);
 
	assert(ps->size > 0);
 
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
 
	ps->size--;
}

代码实现图（示例）：

7.顺序表查找

实现思想：

主体思想：通过下标指向的值进行判断来寻找

代码如下（示例）：

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
 
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

代码实现图（示例）：

8.顺序表任意位置插入

实现思想：

主体思想：通过查找函数找到下标，将下标及后面的数据进行移动，再将新的数值通过下标插入进去。

代码如下（示例）：

void SLInsert(SL* 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++;
}

代码实现图（示例）：

9.顺序表任意位置删除

实现思想：

主体思想：通过下标来找到那个位置的值，让后面的数值向前面进行覆盖。

代码如下（示例）：

void SLErase(SL* ps, int pos)
{
	assert(ps);
 
	assert(pos >= 0 && pos < ps->size);
 
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
 
	ps->size--;
}

代码实现图（示例）：

10.销毁顺序表

实现思想：

主体思想：将指针指向的空间释放，然后在将该空间赋为空。

代码如下（示例）：

void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

11.顺序表打印

实现思想：

主体思想：和打印数组相同

代码如下（示例）：

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

代码实现图（示例）：

12.顺序表修改

实现思想：

主体思想：通过下标找到该元素，对该元素进行再次赋值

代码如下（示例）：

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

代码实现图（示例）：

---

总结

以上就是数据结构当中的顺序表的全部功能的实现，通过思想和代码实现，和效果图让初学者也可以快速上手。