顺序表的实现

标签：顺序 psl SLPushBack PrintSL 实现 pos sl size

在顺序表的实现中我们不会再像之前通讯录一样写菜单来调试了，而是用test函数来直接调用接口调试，因为菜单调试起来过于繁琐，而我们在写数据结构的时候是需要很多次调试函数功能的。

所有接口

#pragma once

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

#define N 10

typedef int SLDataType;

//typedef struct SeqList
//{
//	SLDataType a[N];//存储数据的数组
//	int size;//数据个数
//}SL;


#define INIT_CAPACITY 10//初始的容量和每次增长的容量

typedef struct SeqList
{
	SLDataType* a; //维护动态数组
	size_t size;		//数据个数
	size_t capacity;	//数组容量
}SL;



//初始化顺序表
void InitSL(SL* psl);

//销毁顺序表
void DestroySL(SL* psl);

//打印顺序表
void PrintSL(const SL* psl);

//扩容检查
void CheckCapacity(SL* psl);

//尾插
void SLPushBack(SL* psl, SLDataType x);

//头插
void SLPushFront(SL* psl, SLDataType x);

//头删
void SLPopFront(SL* psl);

//尾删
void SLPopBack(SL* psl);

//查找数据
int SLFind(SL* psl, SLDataType x);

//指定位置删除
void SLErase(SL* psl, size_t pos);

//指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x);

//指定位置修改
void SLModify(SL* psl, int pos, SLDataType x);

顺序表的定义


#define INIT_CAPACITY 10//初始的容量和每次增长的容量

typedef struct SeqList
{
	SLDataType* a; //维护动态数组
	size_t size;		//数据个数
	size_t capacity;	//数组容量
}SL;

初始化顺序表

//初始化顺序表
void InitSL(SL* psl)
{
	assert(psl);
	psl->size = 0;
	psl->capacity = 0;
	psl->a = NULL;
}

初始化顺序表的时候我们把所有的量都置为0或空。我们是在主函数里面创建了一个结构体变量s，由于要对s的内容进行修改，所以我们需要传址调用。

销毁顺序表

为了后续函数的测试，我们需要先把销毁函数也写出来。

//销毁顺序表
void DestroySL(SL* psl)
{
	assert(psl);
	assert(psl->a);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

销毁函数首先也是要判断传过来的psl是否为空指针，然后再判断a是否为空，为了防止数组初始化了但是没有使用的情况，这种情况是不正常的，assert能指出错误的地点，以便测试时发现。

打印顺序表


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

打印顺序表虽然传值也能调用，但是传值的话创建函数栈帧的开销比传址大，而且传址也能实现功能，为了防止对数据的误操作，可以用const修饰。

扩容检查

对于顺序表的增加元素我们都需要用到扩容的函数，所以我们先实现这个函数。

//扩容检查
void CheckCapacity(SL* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		size_t newcapacity = psl->capacity + INIT_CAPACITY;
		SLDataType* ptr = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));
		//检查扩容是否成功
		if (ptr == NULL)
		{
			exit(-1);
		}
		psl->a = ptr;
		psl->capacity = newcapacity;
	}

}

当size与capacity相等的时候就需要扩容了，而每次扩容都扩INIT_CAPACITY个数据的空间，同时我们要注意只要检查psl的有效性，而不用检查psl->a的有效性，因为当size为0时第一次插入数据时，相对于要初始化动态数组，所以psl为空是正常的。

头插尾插

尾插

尾插是最简单的，只要在数组的末尾a[size]放上数据，然后size+1就行了。

//尾插
void SLPushBack(SL* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

我们可以先测试一下尾插函数有没有问题

//测试尾插
void test1()
{
	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
}

顺序表的尾插是很方便的，时间复杂度为O(1)。

头插

相比于尾插，头插的话要先把已有的数据都往后挪一个位置，然后在第一个位置插入数据。要注意挪动数据的时候要从后往前挪，如果从前往后挪的话会覆盖后面的数据。

//头插
void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	int end = psl->size;
	while (end > 0)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

头插写完之后也要进行测试


//测试头插
void test2()
{
	SL sl;
	InitSL(&sl);
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);

	PrintSL(&sl);
}

头删尾删

头删

头删与头插一样，需要挪动数据，直接从前往后遍历，让后面的数据覆盖前面的数据就行，最后那个数据不用管，因为size-1之后后那个数据逻辑来说不是我们顺序表中的数据，而如果后续插入数据时又会对它进行覆盖，所以不要删除。删除数据的时候要判断size是否为零，也要对psl和psl->a的有效性

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

测试头删


//测试头插头删
void test2()
{
	SL sl;
	InitSL(&sl);
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
    SLPrint(&sl);

	SLPopFront(&sl);
	PrintSL(&sl);
	SLPopFront(&sl);
	PrintSL(&sl);
	SLPopFront(&sl);
	PrintSL(&sl);
	SLPopFront(&sl);
	PrintSL(&sl);

	//SLPopFront(&sl);
	//PrintSL(&sl);

}

这时顺序表已经没有数据了，如果我们再删除的话按理来说应该要引发assert报错。

这时候assert的优势就体现出来了，他能直接定位报错的代码行数，很清晰明了

尾删

尾删是很简单的，只要size--就行了，但是要判断顺序表内是否有数据。

//尾删
void SLPopBack(SL* psl)
{
	assert(psl);
	assert(psl->a);
	assert(psl->size);

	psl->size--;
}

测试尾删

//测试尾插尾删
void test1()
{
	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);

	SLPopBack(&sl);
	PrintSL(&sl);
	SLPopBack(&sl);
	PrintSL(&sl);
	SLPopBack(&sl);
	PrintSL(&sl);
	SLPopBack(&sl);
	PrintSL(&sl);

	//SLPopBack(&sl);
	//PrintSL(&sl);
}

测试一步一步把数据删完

此时如果再删除的话assert要报错。

有人可能要说删除数据之后要不要缩容呢？缩容是一个非常错误的做法，因为我们之前讲过了realloc扩容的效率问题，而缩容同样是存在原地缩和异地缩的，也可能导致效率下降，况且缩容是完全没有必要的，我们无法保证删除数据是之后还会不会再插入数据，如果删完立马又插入数据的话，插入的时候又会进行扩容，效率进一步下降，所以千万不要缩容。

查找数据

顺序表的数据查找我们是直接返回下标，如果找不到就返回-1，因为下标不可能是-1，以便区分。

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

测试查找

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);

	int pos = SLFind(&sl, 2);
	printf("%d\n", pos);
	pos = SLFind(&sl, 1);
	printf("%d\n", pos);
	pos = SLFind(&sl, 3);
	printf("%d\n", pos);
	pos = SLFind(&sl, 4);
	printf("%d\n", pos);
	pos = SLFind(&sl, 5);
	printf("%d\n", pos);

查找函数实现没问题。

指定位置删除

指定位置删除就要用到上面的查找函数的返回值pos来进行操作，但是首先也要判断pos的合法性，因为用户在使用这个函数的时候不一定传的是find函数的返回值，所以要对pos进行判断。

而删除的逻辑也很简单，就是直接用这个位置开始的后面的数据依次覆盖前面的，最终size-1就行了。

//指定位置删除
void SLErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(psl->a);
	assert(psl->size);
	assert(pos >= 0 && pos < psl->size);

	//符合条件的pos就进行删除
	int start = pos;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	psl->size--;
}

对于Erase函数我们要测试五种情况，首先是正常场景的删除

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);

	int pos = SLFind(&sl, 2);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLErase(&sl, pos);
	}
	PrintSL(&sl);

没有问题，然后测试两个边界的删除。

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);

	int pos = SLFind(&sl, 1);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLErase(&sl, pos);
	}
	PrintSL(&sl);

	pos = SLFind(&sl, 4);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLErase(&sl, pos);
	}
	PrintSL(&sl);

没有问题，再测试传错误的pos的情况

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	SLErase(&sl, 5);
	PrintSL(&sl);

我们发现他在135行报错了，说明这个场景也可以通过。最后测试顺序表中无数据，这一项其实不用测试也醒了，因为顺序表中无数据的同时，pos也是不满足下标范围的，也就是上面的测试，肯定也是能通过的。

指定位置插入

指定位置插入是指在这个位置之前插入一个数据x，首先要进行扩容检查，然后我们只需要把这个位置及以后的数据依次往后挪一个位置就行了，再将x插入到pos位置，size+1就行了

//指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x)
{

	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	CheckCapacity(psl);
	int end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

首先测试第一个位置插入

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	//SLErase(&sl, 5);
	//PrintSL(&sl);

	int pos = SLFind(&sl, 1);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLInsert(&sl, pos,10);
	}
	PrintSL(&sl);

然后测试最后一个位置插入

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	//SLErase(&sl, 5);
	//PrintSL(&sl);

	int pos = SLFind(&sl, 4);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLInsert(&sl, pos,10);
	}
	PrintSL(&sl);

测试中间位置插入

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	//SLErase(&sl, 5);
	//PrintSL(&sl);

	int pos = SLFind(&sl, 3);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLInsert(&sl, pos,10);
	}
	PrintSL(&sl);

最后测试无数据和pos超范围的插入是否报错

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	SLInsert(&sl, 5,10);
	PrintSL(&sl);

修改指定位置

修改指定位置就比前两个要简单了，只需要对pos为下标的数据修改就完了，但是也要判断pos是否超出范围。

//指定位置修改
void SLModify(SL* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(psl->a);
	assert(psl->size);
	assert(pos >= 0 && pos < psl->size);

	psl->a[pos] = x;

}

先测试中间位置和两个边界的修改

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	//SLInsert(&sl, 5,10);
	//PrintSL(&sl);

	int pos = SLFind(&sl, 3);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLModify(&sl, pos,30);
	}
	PrintSL(&sl);

	pos = SLFind(&sl, 1);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLModify(&sl, pos, 10);
	}
	PrintSL(&sl);

	pos = SLFind(&sl, 4);
	printf("%d\n", pos);
	if (pos != -1)
	{
		SLModify(&sl, pos, 40);
	}
	PrintSL(&sl);

再测试pos超出范围是否报错

	SL sl;
	InitSL(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);

	PrintSL(&sl);
	
	SLModify(&sl, 5,10);
	PrintSL(&sl);

总结

这就是顺序表的简单实现了。其实上面的函数并没有严格按照库里的函数进行实现，比如指定位置插入和指定位置删除会有修改指定位置，库中的函数参数 pos 用的是size_t类型的，而我们实现的是用 int 类型的pos，库中的size_t更符合实际情况，用size_t的pos就要注意控制循环条件，不能用end>=0来作为循环退出条件，因为size_t的数据是不会出现负数的，也就是会死循环。

标签：顺序,psl,SLPushBack,PrintSL,实现,pos,sl,size
From： https://blog.csdn.net/weixin_64099089/article/details/137409379

所有接口

顺序表的定义

初始化顺序表

销毁顺序表

打印顺序表

扩容检查

头插尾插

尾插

头插

头删尾删

头删

尾删

查找数据

指定位置删除

指定位置插入

修改指定位置

总结

相关文章

赞助商

阅读排行

顺序表的实现

所有接口

顺序表的定义

初始化顺序表

销毁顺序表

打印顺序表

扩容检查

头插 尾插

尾插

头插

头删 尾删

头删

尾删

查找数据

指定位置删除

指定位置插入

修改指定位置

总结

相关文章

赞助商

阅读排行

头插尾插

头删尾删