我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

热门文章

当前位置: article > 正文

数据结构之顺序表及其实现！

作者：我家小花儿 | 2024-03-21 10:56:31

赞

踩

数据结构之顺序表及其实现！

目录

1. 顺序表的概念及结构

2. 接口的实现

2.1 顺序表的初始化

2.2 检查顺序表容量是否已满

2.3 顺序表的尾插

2.4 顺序表的尾删

2.5 顺序表的头插

2.6 顺序表的头删

2.7 顺序表在pos位置插入

2.8 顺序表在pos位置删除

2.9 顺序表的查找

2.10 顺序表的销毁

2.11 顺序表的打印

3. 我在实现顺序表时的测试代码

4. 完结散花

悟已往之不谏，知来者犹可追

创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟~

1. 顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元以此存储数据的线性结构，一般情况下用数组存储。在数组上完成数据的增删查改~

1. 静态顺序表:用指定长度数组存储元素~

2. 动态顺序表:用动态开辟的数组存储~

2. 接口的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

我们创建一个Test.h里面包含了所有的接口函数声明和各种头文件的声明~

这样我们一个一个实现，正所谓天下难事必做于细~


#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件的多次包含
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDataType;//便于类型的改动
 
//定义一个动态顺序表的结构体变量
typedef struct SeqList
{
	SLDataType* arr;
	size_t num;//记录有效数据的个数
	size_t capacity;//该顺序表的容量大小
}SL;//将该结构体类型重命名为SL
 
//加入增删查改接口
 
//1. 顺序表初始化
void SeqListInit(SL* p);
 
//2. 检查顺序表容量是否已满
void CheckSeqList(SL* p);
 
//3. 顺序表的尾插
void SeqListPushBack(SL* p, SLDataType x);
 
//4. 顺序表的尾删
void SeqListPopBack(SL* p);
 
//5. 顺序表的头插
void SeqListPushFront(SL* p, SLDataType x);
 
//6. 顺序表的头删
void SeqListPopFront(SL* p);
 
//7. 顺序表在pos位置插入
void SeqListInsert(SL* p, size_t pos,SLDataType x);
 
//8. 顺序表在pos位置删除
void SeqListErase(SL* p, size_t pos);
 
//9. 顺序表的查找
int SeqListFind(SL* p,SLDataType x);//如果该数字存在则返回该数字的下标，否则返回-1
 
//10 顺序表的销毁
void SeqListDestory(SL* p);
 
//11. 顺序表的打印
void SeqListPrint(SL* p);

我们将所有函数的实现放在SeqList.c文件中~

2.1 顺序表的初始化

(1) 代码实现


//1. 顺序表初始化
void SeqListInit(SL* p)
{
	assert(p);//判断指针的有效性
	p->arr = NULL;
	p->capacity = 0;
	p->num = 0;
}

(2) 复杂度分析

时间复杂度：由于没有其他未知数的引入，所以所需时间是个常数，也就是O(1)。
空间复杂度：动态开辟N个空间，所以空间复杂度为O(N)。

注意我们这里一定要传址调用~

2.2 检查顺序表容量是否已满

(1) 代码实现

注释写的很详细了，这里就不做过多的解释~


//2. 检查顺序表容量是否已满
void CheckSeqList(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == p->capacity)
	{
		 size_t newcapacity=p->capacity == 0 ? p->capacity = 4 : p->capacity * 2;
		//如果原来没有空间，就给上4，有的话就扩大为原来的两倍
		 SLDataType* ptr = (SLDataType*)realloc(p->arr, newcapacity * sizeof(SLDataType));//动态扩容
		 if (ptr == NULL)
		 {
			 perror("realloc fail;");
			 return;
		 }
		 //也可以用assert断言一下
		 p->arr = ptr;//开辟成功将地址传给arr
		 p->capacity = newcapacity;//更新容量
	}
}

2.3 顺序表的尾插

(1) 代码实现


//3. 顺序表的尾插
void SeqListPushBack(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//尾插前先判断有没有容量或容量够不够
	p->arr[p->num] = x;//尾部插入数据
	p->num++;//有效数加一
}

(2) 复杂度分析

时间复杂度：没有变量影响时间，时间复杂度为O(1)。
空间复杂度：以最坏的情况考虑，会进行扩容，空间复杂度为O(N)。

2.4 顺序表的尾删

(1) 代码实现


//4. 顺序表的尾删
void SeqListPopBack(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//断言存在有效数据
	p->num--;//尾删一个数据
}

(2) 复杂度分析

时间复杂度：没有变量影响时间，时间复杂度为O(1)。
空间复杂度：没有变量影响空间，空间复杂度为O(1)。

2.5 顺序表的头插

(1) 代码实现


//5. 顺序表的头插
void SeqListPushFront(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//先判断容量是否满了
	size_t end = p->num;
	while (end)
	{
		p->arr[end] = p->arr[end - 1];//整体向后移动
		end--;
	}
	p->arr[0] = x;//头插
	p->num++;//有效数据加一
}

(2) 复杂度分析

时间复杂度：因为从头部插入数据，后续数据需要依次覆盖，所以时间复杂度为O(N)。
空间复杂度：因为可能会进行扩容，按最坏的情况来算，空间复杂度为O(N)。

2.6 顺序表的头删

(1) 代码实现


//6. 顺序表的头删
void SeqListPopFront(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//有数据才删除
	size_t begin = 1;
	while (begin<p->num)
	{
		p->arr[begin - 1] = p->arr[begin];//整体向前移动
		begin++;
	}
	p->num--;// 有效数据减一
 
}

整体往前挪，把头覆盖~

(2) 复杂度分析

时间复杂度：因为需要往前覆盖数据，所以时间复杂度自然为O(N)。
空间复杂度：因为并没有开辟其他空间，所以空间复杂度为O(1)。

2.7 顺序表在pos位置插入

(1) 代码实现


//7. 顺序表在pos位置插入
void SeqListInsert(SL* p, size_t pos, SLDataType x)
{
	assert(p);//判断指针的有效性
	assert(pos >= 0 && pos < p->num);//pos必须小于num并且大于等于0
	CheckSeqList(p);//判断容量是否满了
	for (int i = p->num; i >pos-1 ; i--)
	{
		p->arr[i] = p->arr[i - 1];//将pos后面的元素往后挪
	}
	p->arr[pos - 1] = x;//在pos位置加入数据
	p->num++;//有效个数加一
}

(2) 复杂度分析

时间复杂度：需要依次覆盖，时间复杂度为O(N)。
空间复杂度：可能需要扩容，空间复杂度为O(N)。

2.8 顺序表在pos位置删除

(1) 代码实现


//8. 顺序表在pos位置删除
void SeqListErase(SL* p, size_t pos)
{
	assert(p);//判断指针的有效性
	assert(pos>=0&&pos<p->num );//pos必须小于num并且大于等于0
	assert(p->num > 0);//有数据才能删除
	for (int i = pos; i <p->num; i++)
	{
		p->arr[i-1] = p->arr[i];//将pos后面的元素往后挪
	}
	p->num--;//有效个数减一
}

(2) 复杂度分析

时间复杂度：需要依次覆盖，时间复杂度为O(N)。
空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

2.9 顺序表的查找

(1) 代码实现

遍历数组查找~


//9. 顺序表的查找
int SeqListFind(SL* p, SLDataType x)//如果该数字存在则返回该数字的下标，否则返回-1
{
	assert(p);//断言
	for (int i = 0; i < p->num; i++)
	{
		if (p->arr[i] == x)
		{
			return i;//查到返回下标
		}
	}
	return -1;//没有查到
}

(2) 复杂度分析

时间复杂度：以最坏的情况分析，时间复杂度为O(N)。
空间复杂度：并没有格外的空间消耗，空间复杂度为O(1)。

2.10 顺序表的销毁

(1) 代码实现


//10 顺序表的销毁
void SeqListDestory(SL* p)
{
	assert(p);//判断指针的有效性
	free(p->arr );//释放动态内存开辟的空间
	p->arr = NULL;
	p->capacity = 0;//容量置为0
	p->num = 0;//有效个数置为0
}

(2) 复杂度分析

时间复杂度：没有额外的时间消耗，时间复杂度为O(1)。
空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

2.11 顺序表的打印

(1) 代码实现


//11. 顺序表的打印
void SeqListPrint(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == 0)
	{
		printf("顺序表为空！\n");
		return;
	}
	for (int i = 0; i < p->num; i++)
	{
		printf("%d ", p->arr[i]);//打印数据
	}
	printf("\n");
}

(2) 复杂度分析

时间复杂度：因为会打印顺序表中的所有数据，所以时间复杂度为O(N)。
空间复杂度：打印顺序表并不需要开辟格外的空间，所以空间复杂度为O(1)。

3. 完整代码

SeqList.c


#define _CRT_SECURE_NO_WARNINGS
#include"Test.h"
 
 
//接口函数的实现
 
//1. 顺序表初始化
void SeqListInit(SL* p)
{
	assert(p);//判断指针的有效性
	p->arr = NULL;
	p->capacity = 0;
	p->num = 0;
}
 
//2. 检查顺序表容量是否已满
void CheckSeqList(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == p->capacity)
	{
		 size_t newcapacity=p->capacity == 0 ? p->capacity = 4 : p->capacity * 2;
		//如果原来没有空间，就给上4，有的话就扩大为原来的两倍
		 SLDataType* ptr = (SLDataType*)realloc(p->arr, newcapacity * sizeof(SLDataType));//动态扩容
		 if (ptr == NULL)
		 {
			 perror("realloc fail;");
			 return;
		 }
		 //也可以用assert断言一下
		 p->arr = ptr;//开辟成功将地址传给arr
		 p->capacity = newcapacity;//更新容量
	}
}
 
//3. 顺序表的尾插
void SeqListPushBack(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//尾插前先判断有没有容量或容量够不够
	p->arr[p->num] = x;//尾部插入数据
	p->num++;//有效数加一
}
 
//4. 顺序表的尾删
void SeqListPopBack(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//断言存在有效数据
	p->num--;//尾删一个数据
}
 
//5. 顺序表的头插
void SeqListPushFront(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//先判断容量是否满了
	size_t end = p->num;
	while (end)
	{
		p->arr[end] = p->arr[end - 1];//整体向后移动
		end--;
	}
	p->arr[0] = x;//头插
	p->num++;//有效数据加一
}
 
//6. 顺序表的头删
void SeqListPopFront(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//有数据才删除
	size_t begin = 1;
	while (begin<p->num)
	{
		p->arr[begin - 1] = p->arr[begin];//整体向前移动
		begin++;
	}
	p->num--;// 有效数据减一
 
}
 
//7. 顺序表在pos位置插入
void SeqListInsert(SL* p, size_t pos, SLDataType x)
{
	assert(p);//判断指针的有效性
	assert(pos >= 0 && pos < p->num);//pos必须小于num并且大于等于0
	CheckSeqList(p);//判断容量是否满了
	for (int i = p->num; i >pos-1 ; i--)
	{
		p->arr[i] = p->arr[i - 1];//将pos后面的元素往后挪
	}
	p->arr[pos - 1] = x;//在pos位置加入数据
	p->num++;//有效个数加一
}
 
//8. 顺序表在pos位置删除
void SeqListErase(SL* p, size_t pos)
{
	assert(p);//判断指针的有效性
	assert(pos>=0&&pos<p->num );//pos必须小于num并且大于等于0
	assert(p->num > 0);//有数据才能删除
	for (int i = pos; i <p->num; i++)
	{
		p->arr[i-1] = p->arr[i];//将pos后面的元素往后挪
	}
	p->num--;//有效个数减一
}
 
//9. 顺序表的查找
int SeqListFind(SL* p, SLDataType x)//如果该数字存在则返回该数字的下标，否则返回-1
{
	assert(p);//断言
	for (int i = 0; i < p->num; i++)
	{
		if (p->arr[i] == x)
		{
			return i;//查到返回下标
		}
	}
	return -1;//没有查到
}
 
//10 顺序表的销毁
void SeqListDestory(SL* p)
{
	assert(p);//判断指针的有效性
	free(p->arr );//释放动态内存开辟的空间
	p->arr = NULL;
	p->capacity = 0;//容量置为0
	p->num = 0;//有效个数置为0
}
 
//11. 顺序表的打印
void SeqListPrint(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == 0)
	{
		printf("顺序表为空！\n");
		return;
	}
	for (int i = 0; i < p->num; i++)
	{
		printf("%d ", p->arr[i]);//打印数据
	}
	printf("\n");
}

4. 完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/280691

推荐阅读

相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

闽ICP备14008679号