[数据结构与算法]数据结构--动态储存顺序表(含完整代码)

💨 动态储存顺序表

💢引语

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储,即静态顺序表静态顺序表，静态顺序表我已经写好了，这次我主要来介绍 动态存储顺序表。
静态和动态的对比：静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

🌊顺序表的基本功能

💦1.初始化

//动态顺序存储--按需存储空间
typedef int SLDataType;   //SLDataType的类型根据实际存储的数据类型而定
typedef struct SqList
{
	SLDataType* a;  
	int size;      //记录存储多少个有效数据
	int capacity;  //空间容量的大小
}SL;

//初始化
void SLInit(SL* ps)
{
	assert(ps);    //断言，判断是否为空
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

代码解释：

• 定义一个SLDataType类型指针a记录动态开辟的数组初始地址
• size记录多少个有效数据，capacity为动态数组暂时性的空间大小，当size与capacity相等时，空间需要扩容。

💦2.销毁

//销毁
void SLDestroy(SL* ps)
{
	assert(ps);      //断言
	if(ps->a!=NULL)
	{
		free(ps->a);      //释放创建的动态数组
		ps->a = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}

代码解释：
开辟的动态空间不用了要记得释放，如果不释放将导致严重后果！
如果程序结束，动态开辟的空间会被操作系统回收！
如果程序不结束，动态开辟的空间是不会被自动回收的，就会形成内存泄漏问题！
释放完的指针也要置空，不置空的话，这个指针就是野指针，如果你以后万一对这个指针进行解引用，就会造成非法访问！

💦3.打印

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

打印功能的实现比较简单，我就不做过多的赘述了

💦4.扩容

//扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)  //先判断是否有空间
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		//ps->a=(SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));  不要这样接收，扩容失败会返回空指针
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));

		if (tmp == NULL)
		{  //扩容失败
			perror("realloc fail");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
}

当size等于capacity时，动态开辟数组空间容量已经存满，需要扩容。

💦5.尾插尾删

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);  //先检查空间容量是否存满，存满需扩容
	ps->a[ps->size] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	//暴力检查
	assert(ps->size > 0);
	ps->size--;
}

尾插尾删功能的测试

void TestSeqList1()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	SLPushBack(&sl, 1); //尾插
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 7);
	SLPushBack(&sl, 8);
	SLPushBack(&sl, 9);
	SLPrint(&sl);

	SLPopBack(&sl); //尾删
	SLPrint(&sl);

	SLPushBack(&sl, 9);
	SLPrint(&sl);
	SLDestroy(&sl);    //用完销毁
}
int main()
{
	TestSeqList1();  //尾插功能的测试
	return 0;
}

💦6.头插头删

//头插
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++;
}

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

头插头删功能测试

void TestSeqList2()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	
	SLPushFront(&sl, 1);//头插
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
	SLPrint(&sl);
	
	SLPopFront(&sl); //头删
	SLPrint(&sl);
	
	SLDestroy(&sl);

}

int main()
{
	//TestSeqList1();   //尾插尾删测试
	TestSeqList2();  //头插头删测试
	return 0;
}

💦7.中间插入和删除

//中间插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0);
	assert(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++;
}

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

中间插入和删除的测试

void TestSeqList3()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLInsert(&sl, 2, 20);
	SLPrint(&sl);

	SLErase(&sl, 2);
	SLPrint(&sl);

	SLDestroy(&sl);
}

int main()
{
	//TestSeqList1();   //尾插尾删测试
	//TestSeqList2();  //头插头删测试
	TestSeqList3();    //中间插入和删除的测试
	return 0;
}

💦8.查找

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

查找功能的测试

void TestSeqList4()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLInsert(&sl, 2, 200);
	SLPrint(&sl);

	SLInsert(&sl, 4, 200);
	SLPrint(&sl);

	SLInsert(&sl, 0, 20);
	SLPrint(&sl);

	int pos=SLFind(&sl, 200,0); //删除数值200，开始时从下标0开始查找
	while (pos != -1)
	{
		SLErase(&sl, pos);
		pos = SLFind(&sl, 200, pos);
	}
	SLPrint(&sl);

	SLDestroy(&sl);
}

int main()
{
	//TestSeqList1();   //尾插尾删测试
	//TestSeqList2();  //头插头删测试
	//TestSeqList3();    //中间插入和删除的测试
	TestSeqList4();    //查找功能的测试
	return 0;
}

🌊动态顺序表的完整代码

需要创建三个文件，两个源文件，一个头文件

1.头文件SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//动态顺序存储--按需存储空间
typedef int SLDataType;
typedef struct SqList
{
	SLDataType* a;
	int size;  //记录存储多少个有效数据
	int capacity;  //空间容量的大小
}SL;


//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);

//打印
void SLPrint(SL* ps);

//判断空间是否满了
void SLCheckCapacity(SL* ps);

//尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);

//头插头删
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//中间的插入和删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SLDataType x, int begin);

2.SeqList.c

#include "SqLList.h"

//初始化
void SLInit(SL* ps)
{
	assert(ps);    //断言，判断是否为空
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//销毁
void SLDestroy(SL* ps)
{
	assert(ps);      //断言
	if (ps->a != NULL)
	{
		free(ps->a);      //释放创建的动态数组
		ps->a = NULL;
		ps->size = 0;
		ps->capacity = 0;
	}
}


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


//扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)  //先判断是否有空间
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		//ps->a=(SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));  不要这样接收，扩容失败会返回空指针
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));

		if (tmp == NULL)
		{  //扩容失败
			perror("realloc fail");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
}


//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);  //先检查空间容量是否存满，存满需扩容
	ps->a[ps->size] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	//暴力检查
	assert(ps->size > 0);
	ps->size--;
}

//头插
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++;
}

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


//中间插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0);
	assert(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++;
}

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

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

3.test.c

#include "SqLList.h"

void TestSeqList1()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	SLPushBack(&sl, 1); //尾插
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushBack(&sl, 6);
	SLPushBack(&sl, 7);
	SLPushBack(&sl, 8);
	SLPushBack(&sl, 9);
	SLPrint(&sl);

	SLPopBack(&sl); //尾删
	SLPrint(&sl);

	SLPushBack(&sl, 9);
	SLPrint(&sl);
	SLDestroy(&sl);    //用完销毁
}

void TestSeqList2()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址

	SLPushFront(&sl, 1);//头插
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
	SLPrint(&sl);

	SLPopFront(&sl); //头删
	SLPrint(&sl);

	SLDestroy(&sl);

}

void TestSeqList3()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLInsert(&sl, 2, 20);
	SLPrint(&sl);

	SLErase(&sl, 2);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSeqList4()
{
	SL sl;
	SLInit(&sl);       //注意初始化传的是实参的地址
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLInsert(&sl, 2, 200);
	SLPrint(&sl);

	SLInsert(&sl, 4, 200);
	SLPrint(&sl);

	SLInsert(&sl, 0, 20);
	SLPrint(&sl);

	int pos = SLFind(&sl, 200, 0); //删除数值200，开始时从下标0开始查找
	while (pos != -1)
	{
		SLErase(&sl, pos);
		pos = SLFind(&sl, 200, pos);
	}
	SLPrint(&sl);

	SLDestroy(&sl);
}

int main()
{
	//TestSeqList1();   //尾插尾删测试
	//TestSeqList2();  //头插头删测试
	//TestSeqList3();    //中间插入和删除的测试
	TestSeqList4();    //查找功能的测试
	return 0;
}