您现在的位置是：首页 > 其他

当前栏目

追梦之旅【数据结构篇】——详解C语言动态实现顺序表

语言数据结构

2023-04-18 15:45:32 时间

详解C语言动态实现顺序表~😎

前言🙌
顺序表概念及结构🙌
功能函数的具体实现分析：🙌
头文件全部源码分享🙌
功能文件全部源码分享🙌
测试文件代码🙌
总结撒花💞

😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，手把手带领大家学习C语言动态实现顺序表~ 都是精华内容，可不要错过哟！！！😍😍😍

顺序表概念及结构🙌

在实现顺序表之前，我们先要了解一下什么是顺序表，它的大概结构是怎么样的？其实顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
在这里插入图片描述

顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。
动态顺序表：使用动态开辟的数组存储。

其实静态实现和动态实现的方法都差不多，但是相比而言动态实现的顺序表的性能更优，实际应用的价值更大，比较灵活。

实现大概思路分析：

首先在头文件先定义结构体和各个功能函数的声明，并把有关的头文件包含上去。各个函数如何实现的，主要是对各个函数的实现，用到realloc动态开辟新节点的空间，用assert断言确保指针有效，通过画图来帮助理清代码实现的思路，指针的指向如何，要考虑哪些情况。然后再测试代码中，将上述代码都进行测试，显示结果。

功能函数的具体实现分析：🙌

尾插函数具体实现：

设计思路分析：

首先设计一个检查容量的函数，保证有空间才能进行插入操作。
将size为下标的元素改为x，别忘了将size++。
或者实现任意插函数之后，而尾插作为其一种特殊情况，可以通过调用任意插函数来实现尾插的功能

//尾插
void SeqListPushBack(SL* p, DataSeqList x)
{
	/*SeqListCheckCapacity(p);
	p->arr[p->size] = x;
	p->size++;*/
	SeqListInsert(p, p->size, x);
}

尾删函数具体实现：

设计思路分析：

先assert检查顺序表的元素个数，如果没有元素就不用再删了
直接将size减减即可。这样其有效个数就少了一个，十分简单。
或者实现任意删函数之后，而尾删作为其一种特殊情况，可以通过调用任意删函数来实现尾删的功能

//尾删
void SeqListPopBack(SL* p)
{
	/*assert(p->size);
	p->size--;*/
	SeqListEraes(p, p->size - 1);
}

头插函数具体实现：

设计思路分析：

首先设计一个检查容量的函数，保证有空间才能进行插入操作。
注意挪动数据如何挪，将控制条件控制好即可。
将首元素改为x，别忘了将size++。
或者实现任意插函数之后，而头插作为其一种特殊情况，可以通过调用任意插函数来实现头插的功能

//头插
void SeqListPushFront(SL* p, DataSeqList x)
{
	//SeqListCheckCapacity(p);
	挪动数据
	//int end = p->size - 1;
	//while (end >= 0)
	//{
	//	p->arr[end + 1] = p->arr[end];
	//	end--;
	//}
	//p->arr[0] = x;
	//p->size++;
	SeqListInsert(p,0, x);
}

头删插函数具体实现：

设计思路分析：

先assert检查顺序表的元素个数，如果没有元素就不用再删了。
注意数据挪动，可以采用画图分析的方法控制挪动数据的控制条件。
不要忘了将size-减减。
或者实现任意删函数之后，而头删作为其一种特殊情况，可以通过调用任意删函数来实现头删的功能

//头删
void SeqListPopFront(SL* p)
{
	删完就不用删了
	//assert(p->size);
	//int begin = 1;
	//while (begin < p->size)
	//{
	//	p->arr[begin - 1] = p->arr[begin];
	//	begin++;
	//}
	//p->size--;
	SeqListEraes(p, 0);
}

任意插函数具体实现：

设计思路分析：

先判断容量，有空间才进行插入操作。
检查插入的合法性，在pos >= 0 && pos <= p->size 的范围才能进行插入
注意数据挪动，可以采用画图分析的方法控制挪动数据的控制条件。
别忘了将size加加

//任意插
void SeqListInsert(SL* p,int pos ,DataSeqList x)
{
	SeqListCheckCapacity(p);
	assert(pos >= 0 && pos <= p->size);
	int end = p->size - 1;
	while (end >= pos)
	{
		p->arr[end + 1] = p->arr[end];
		end--;
	}
	p->arr[pos] = x;
	p->size++;

}

任意删函数具体实现：

设计思路分析：

先判断顺序表有没有数据，没有就不用删了。
检查删的位置的合法性，在pos >= 0 && pos < p->size的范围才能进行删除。
注意数据挪动，可以采用画图分析的方法控制挪动数据的控制条件。
别忘了将size减减。

//任意删
void SeqListEraes(SL* p, int pos)
{
	//删完就不用删了
	assert(p->size);
	//删的合法性判断
	assert(pos >= 0 && pos < p->size);
	int begin = pos+1;
	while (begin < p->size)
	{
		p->arr[begin - 1] = p->arr[begin];
		begin++;
	}
	p->size--;
}

销毁顺序表函数具体实现：

设计思路分析：
因为顺序表的空间建立是动态开辟的，动态开辟的空间需要手动free释放。

/销毁
void SeqListDestory(SL* p)
{
	free(p->arr);
	p->arr = NULL;
	p->capacity = p->size = 0;
}

查找函数具体实现：

设计思路分析：
这个比较简单，直接写个循环遍历一遍，找到了x就返回它的下标，找不到返回-1.

//查找
int SeqListFind(SL* p, DataSeqList x)
{
	assert(p);
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

检查容量函数具体实现：

设计思路分析：

分为没有空间和空间满了两种情况进行。
如果没有空间，就显动态分配四个数据大小的空间。
如果空间存储满了，就动态扩容到原来的2倍空间。

//检查容量
void SeqListCheckCapacity(SL* p)
{
	if (p->size == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		DataSeqList* tem = realloc(p->arr, newcapacity * sizeof(DataSeqList));
		assert(tem);
		p->arr = tem;
		p->capacity = newcapacity;
	}
}

初始化函数具体实现：

设计思路分析：
将p->arr = NULL;p->capacity = p->size = 0;

//初始化
void SeqListInit(SL* p)
{
	assert(p);
	p->arr = NULL;
	p->capacity = p->size = 0;
}

打印函数具体实现：

设计思路分析：
这个比较简单，直接写个循环遍历一遍打印即可。

//打印
void SeqListPrintf(SL* p)
{
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		printf("%d ", p->arr[i]);
	}
	printf("
");
}

头文件全部源码分享🙌

这里负责函数功能的声明和库函数头文件的包含，写任何一个项目时，可以先把头文件编写好，也就是理清一下项目需要实现哪些功能函数，整理一下项目的整体思路。

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

#define DataSeqList int

typedef struct SeqList
{
	DataSeqList* arr;
	int size;
	int capacity;
}SL;

//初始化
void SeqListInit(SL* p);
//尾插
void SeqListPushBack(SL* p, DataSeqList x);
//尾删
void SeqListPopBack(SL* p);
//头插
void SeqListPushFront(SL* p, DataSeqList x);
//头删
void SeqListPopFront(SL* p);
//任意插
void SeqListInsert(SL* p, int pos, DataSeqList x);
//任意删
void SeqListEraes(SL* p, int pos);
//打印
void SeqListPrintf(SL* p);
//销毁
void SeqListDestory(SL* p);
//查找
int SeqListFind(SL* p, DataSeqList x);
//检查容量
void SeqListCheckCapacity(SL* p);

功能文件全部源码分享🙌


#include"SeqList.h"

//初始化
void SeqListInit(SL* p)
{
	assert(p);
	p->arr = NULL;
	p->capacity = p->size = 0;
}

//尾插- 会遇到三种情况
// 1 - 没有空间    2 - 空间不足，要扩容（查容量）  3 - 空间足够，插入数据

//检查容量
void SeqListCheckCapacity(SL* p)
{
	if (p->size == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		DataSeqList* tem = realloc(p->arr, newcapacity * sizeof(DataSeqList));
		assert(tem);
		p->arr = tem;
		p->capacity = newcapacity;
	}
}

//打印
void SeqListPrintf(SL* p)
{
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		printf("%d ", p->arr[i]);
	}
	printf("
");
}

//尾插
void SeqListPushBack(SL* p, DataSeqList x)
{
	/*SeqListCheckCapacity(p);
	p->arr[p->size] = x;
	p->size++;*/
	SeqListInsert(p, p->size, x);
}

//尾删
void SeqListPopBack(SL* p)
{
	/*assert(p->size);
	p->size--;*/
	SeqListEraes(p, p->size - 1);
}
//头插
void SeqListPushFront(SL* p, DataSeqList x)
{
	//SeqListCheckCapacity(p);
	挪动数据
	//int end = p->size - 1;
	//while (end >= 0)
	//{
	//	p->arr[end + 1] = p->arr[end];
	//	end--;
	//}
	//p->arr[0] = x;
	//p->size++;
	SeqListInsert(p,0, x);
}
//头删
void SeqListPopFront(SL* p)
{
	删完就不用删了
	//assert(p->size);
	//int begin = 1;
	//while (begin < p->size)
	//{
	//	p->arr[begin - 1] = p->arr[begin];
	//	begin++;
	//}
	//p->size--;
	SeqListEraes(p, 0);
}

//任意插
void SeqListInsert(SL* p,int pos ,DataSeqList x)
{
	SeqListCheckCapacity(p);
	assert(pos >= 0 && pos <= p->size);
	int end = p->size - 1;
	while (end >= pos)
	{
		p->arr[end + 1] = p->arr[end];
		end--;
	}
	p->arr[pos] = x;
	p->size++;

}
//任意删
void SeqListEraes(SL* p, int pos)
{
	//删完就不用删了
	assert(p->size);
	//删的合法性判断
	assert(pos >= 0 && pos < p->size);
	int begin = pos+1;
	while (begin < p->size)
	{
		p->arr[begin - 1] = p->arr[begin];
		begin++;
	}
	p->size--;
}

//销毁
void SeqListDestory(SL* p)
{
	free(p->arr);
	p->arr = NULL;
	p->capacity = p->size = 0;
}

//查找
int SeqListFind(SL* p, DataSeqList x)
{
	assert(p);
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

测试文件代码🙌

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void test1()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrintf(&s);
	SeqListPopBack(&s);
	SeqListPopBack(&s);
	SeqListPrintf(&s);

	SeqListPushFront(&s, 10);
	SeqListPushFront(&s, 20);
	SeqListPushFront(&s, 30);
	SeqListPushFront(&s, 40);
	SeqListPrintf(&s);

	SeqListPopFront(&s);
	SeqListPopFront(&s);
	SeqListPrintf(&s);
	SeqListDestory(&s);



}

void test2()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrintf(&s);
	SeqListInsert(&s, 3, 30);
	SeqListPrintf(&s);
	SeqListEraes(&s, 3);
	SeqListEraes(&s, 2);
	SeqListPrintf(&s);

	SeqListDestory(&s);
}
void test3()
{
	SL s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrintf(&s);
	SeqListInsert(&s, 3, 30);
	SeqListEraes(&s, 2);
	SeqListPrintf(&s);
	SeqListDestory(&s);
}

void test4()
{
	SL s;
	printf("尾插数据1,2,3,4,5
");
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrintf(&s);
	printf("头插数据10， 20 ， 30
");
	SeqListPushFront(&s, 10);
	SeqListPushFront(&s, 20);
	SeqListPushFront(&s, 30);
	SeqListPrintf(&s);
	SeqListDestory(&s);
}

int main()
{

	//test1();
	//test2();
	//test3();
	test4();
	return 0;
}

部分功能测试结果图：
在这里插入图片描述

总结撒花💞

本篇文章旨在分享详解C语言动态实现顺序表。希望大家通过阅读此文有所收获！😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘

猜你喜欢

Jease 2.6发布 Java开源内容框架
EasyCVR对接华为iVS订阅摄像机和用户变更请求接口介绍
JVM调优总结：反思
【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
JVM调优总结：调优方法
前端面试【JavaScript】— typeof 是否能正确判断类型？
JVM调优总结：新一代的垃圾回收算法
前端面试【JavaScript】— instanceof 能否判断基本数据类型？
JVM调优总结：典型配置举例
前端面试【JavaScript】— 能不能手动实现一下 instanceof 的功能？
前端面试【JavaScript】— Object.is和=== 有什么区别？
JVM调优总结：分代垃圾回收详述
前端面试【JavaScript】— JS中类型转换有哪几种？
WPF开发入门尝试
前端面试【JavaScript】— == 和 ===有什么区别？
一个Java程序员对2011年的回顾
前端面试【JavaScript】— 对象转原始类型是根据什么流程运行的？
JVM调优总结：垃圾回收面临的问题
直接在代码里面对list集合进行分页
JVM调优总结：基本垃圾回收算法

zl程序教程