数据结构初阶（C语言）-顺序表

一，线性表

在进行顺序表的介绍之前，我们先来了解下什么是线性表：

         线性表是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

二，顺序表

2.1概念与其逻辑及物理结构

         概念：顺序表是用⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。

         这里我们可以得知顺序表的逻辑结构（人为想象的结构）呈线性，同时它的物理结构是由连续的数组构成，所以它的物理结构也为线性。

2.2静态顺序表

概念：使用已经确定长度的数组存储元素，这里我们用代码来表示静态顺序表的结构：

#define N 7
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType arr[N];
	int size;//有效的数据个数
};

         数组的长度我们无法改变，也就意味着我们无法随意的增加和删除数据，更不能在数据量变大时对储存数据的顺序表进行扩容，所以我们主要使用的顺序表为动态顺序表。

2.3动态顺序表

概念：使用可变长度的数组存储元素，这里我们使用代码来表示动态顺序表的基本结构：

typedef int SLDataType;

typedef struct SepList
{
	SLDataType* arr;
	int capacity;
	int size;
}SL,*PSL;

三，动态顺序表的功能实现

         顺序表的目的是为了存储数据，所以我们这里所说的实现主要有头，尾插法。头，尾删法。定位插，删法。不过在此之前，如果空间的大小不够，我们将无法对数据进行增加，所以在进行所有的实现之前，我们需要先对空间大小进行检查：

3.1检查内存空间大小是否足够

         我们在扩充内存空间时，经常以原空间大小的倍数来扩充，这是因为随着我们扩充的次数增多，我们所需要存储的数据量也会按倍数增大，所以当我们以倍数来扩充内存空间时，正好与数据的增长量成线性关系，浪费的空间也将最大化的被缩小。通常情况下，储存空间我们以上次纯村空间的大小的二倍来增加，当然在此之前我们要对顺序表进行初始化：

void SepInit(PSL ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

对空间的大小检查的代码如下： 

void CheckSpace(PSL ps)
{
	if (ps->capacity == ps->size)
	{
		int excapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, excapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("SLInsertEnd,tmp:");
			return 1;
		}
		ps->arr = tmp;
		ps->capacity = excapacity;
	}
}

         这里我们需要对源顺序表进行检验，若它刚经过初始化，我们为它付一个初始值为4的容量（为什么不在初始化中对其进行赋值，我个人认为是因为后续对数据的增删可能会使顺序表变为空，在这里对其容量进行改动是为了避免这种情况），剩下就是正常的开辟顺序表的空间（使用realloc，因为realloc在对空指针增加空间后会返回一个新的地址对应开辟的空间，后续我们也需要对内存进行扩充，所以使用realloc最合适）。

3.2尾删法

顾名思义就是从尾部减少有效数据的个数，实现代码非常简单：

void SLDeltEnd(PSL ps)
{
	assert(ps);
	ps->size--;
}

3.3头删法

         这里我们需要从头部删除数据，其实就是把除了第一个数据外的所有数据整体向前移动一格，进而覆盖第一个数据，达到头删的目的，实现代码如下：

void SLDeltBeg(PSL ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

当然我们需要判断有效数据的个数，如果为0就没有删除的必要了。 

3.4尾插法

         从尾部插入，其实就是向数组中的第size个位置插入数据，但如果数据在此之前已满，我们则需要扩充空间，具体实现代码如下：

void SLInsertEnd(PSL ps,SLDataType x)
{

	assert(ps);
	CheckSpace(ps);
	ps->arr[ps->size++] = x;
}

3.5头插法

         有了上面头删法的帮助，其实我们这里也就不难理解头删法是如何实现的，其实就是将现有数据整体向后移动一个位置，然后在首元素位置插入我们的数据，实现代码如下：

void SLInsertBeg(PSL ps,SLDataType x)
{
	assert(ps);
	CheckSpace(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

3.6定位删除法

         在这里我们需要注意，定位的方式删除与增加其实基本上沿用了头删与头插的思想，无非就是在传参时我们需要多传一个参数--需要删除或增加的位置，删除则将除了当前位置之后的所有元素整体向前移动一个位置，而增加则是将当前指定位置数据及之后的数据整体向后移动一个位置，然后再在当前位置放上我们的目标数据：

void SLDeltDes(PSL ps, int pos)
{
	assert(ps);
	assert(pos>=0 && pos<ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

3.7定位插入法

有了上面3.6的介绍，我们这里也不废话，直接上实现代码：

void SLDeltDes(PSL ps, int pos)
{
	assert(ps);
	assert(pos>=0 && pos<ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

         当然删除肯定要有数据才能删，有那个位置的空间才能定位增加数据，这也是我们上面使用assert断言的原因。 

四，实现功能后的善后处理

4.1打印顺序表内容

void SLPrintf(PSL ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ",ps->arr[i]);
	}
	printf("\n");
}

4.2释放顺序表

void SLDestory(PSL ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->capacity = 0;
	ps->size = 0;
	ps->arr = NULL;
}

4.3动态顺序表功能实现的完整代码

//头文件SepList.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLDataType;

typedef struct SepList
{
	SLDataType* arr;
	int capacity;
	int size;
}SL,*PSL;

void SepInit(PSL ps);//顺序表空间的初始化

void SLInsertEnd(PSL ps,SLDataType x);//尾插法

void SLPrintf(PSL ps);//检验打印

void SLDestory(PSL ps);//释放开辟的动态内存

void CheckSpace(PSL ps);//检查空间是否足够

void SLInsertBeg(PSL ps,SLDataType x);//头插法

void SLDeltBeg(PSL ps);//头删法

void SLDeltEnd(PSL ps);//尾删法

void SLDeltDes(PSL ps, int pos);//指定位置删除

void SLInsertDes(PSL ps, int pos, SLDataType x);//指定位置增加数据

//顺序表功能实现代码SepList.c
#include "Seplist.h"

void SepInit(PSL ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void CheckSpace(PSL ps)
{
	if (ps->capacity == ps->size)
	{
		int excapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, excapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("SLInsertEnd,tmp:");
			return 1;
		}
		ps->arr = tmp;
		ps->capacity = excapacity;
	}
}

void SLInsertEnd(PSL ps,SLDataType x)
{

	assert(ps);
	CheckSpace(ps);
	ps->arr[ps->size++] = x;
}

void SLInsertBeg(PSL ps,SLDataType x)
{
	assert(ps);
	CheckSpace(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

void SLPrintf(PSL ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ",ps->arr[i]);
	}
	printf("\n");
}

void SLDestory(PSL ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->capacity = 0;
	ps->size = 0;
	ps->arr = NULL;
}

void SLDeltBeg(PSL ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

void SLDeltEnd(PSL ps)
{
	assert(ps);
	ps->size--;
}

void SLDeltDes(PSL ps, int pos)
{
	assert(ps);
	assert(pos>=0 && pos<ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

void SLInsertDes(PSL ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckSpace(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}


//顺序表功能测试代码

#include "Seplist.h"

//顺序表的头插尾插以及头删尾删

void test()
{
	SL s;
	SepInit(&s);
	SLInsertEnd(&s,4);
	SLInsertEnd(&s,5);
	SLInsertEnd(&s,3);
	SLInsertEnd(&s,2);
	SLInsertEnd(&s,1);
	SLInsertBeg(&s, 1);
	SLInsertBeg(&s, 2);
	SLInsertBeg(&s, 3);
	SLInsertBeg(&s, 4);
	SLDeltBeg(&s);
	SLDeltEnd(&s);
	SLDeltDes(&s, 2);
	SLInsertDes(&s, 4, 2);
	SLPrintf(&s);
	SLDestory(&s);
}


int main()
{
	test();
	return 0;
}


http://www.niftyadmin.cn/n/5556512.html

相关文章

如何在 C# 中实现高效的内存管理，避免内存泄漏和提高性能？

如何在 C# 中实现高效的内存管理，避免内存泄漏和提高性能？

在C#中实现高效的内存管理和提高性能可以采取以下几个方法&#xff1a; 使用对象池&#xff1a;对象池是一种重复使用对象的技术&#xff0c;可以减少内存分配和释放的开销。可以使用 ObjectPool 类或者自定义一个简单的对象池来管理对象的创建和回收。 及时释放资源&#xff…
阅读更多...
实验二：图像灰度修正

实验二：图像灰度修正

目录 一、实验目的 二、实验原理 三、实验内容 四、源程序和结果 源程序（python）： 结果： 五、结果分析 一、实验目的 掌握常用的图像灰度级修正方法，包括图象的线性和非线性灰度点运算和直方图均衡化法，加深对灰度直方图的理解。掌握对比度增强、直方图增强的原理，…
阅读更多...
JVM和类加载机制-01[JVM底层架构和JVM调优]

JVM和类加载机制-01[JVM底层架构和JVM调优]

JVM底层 Java虚拟机内存模型JVM组成部分五大内存区域各自的作用虚拟机栈(线程栈)栈帧内存区域 本地方法栈程序计数器为什么jvm要设计程序计数器&#xff1f; 堆方法区 JVM优化-堆详解JVM底层垃圾回收机制jvm调优工具jvisualvm.exeArthas工具使用 Java虚拟机内存模型 JVM跨平台原…
阅读更多...
QQ频道导航退出

QQ频道导航退出

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/140413538 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…
阅读更多...
Netty ChannelPipeline/ChannelHandler

Netty ChannelPipeline/ChannelHandler

在Netty中&#xff0c;ChannelPipeline和ChannelHandler是处理网络事件的核心组件。ChannelPipeline是一个处理器链&#xff0c;它负责处理和拦截入站和出站事件&#xff0c;而ChannelHandler则是这个链中的处理器。 ChannelPipeline ChannelPipeline是一个Netty特有的概念&a…
阅读更多...
Mysql：解决CPU飙升至100%问题的系统诊断与优化策略

Mysql：解决CPU飙升至100%问题的系统诊断与优化策略

在服务器运维过程中&#xff0c;CPU使用率飙升到100%是一个常见且棘手的问题。这不仅会严重影响服务器的性能&#xff0c;还可能导致服务中断。当遇到这类情况时&#xff0c;首要任务是快速定位问题源头并采取相应措施。以下是一个基于操作系统命令和MySQL数据库优化的详细解决…
阅读更多...
【全面介绍Pip换源】

【全面介绍Pip换源】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…
阅读更多...
Go语言--广播式并发聊天服务器

Go语言--广播式并发聊天服务器

实现功能 每个客户端上线&#xff0c;服务端可以向其他客户端广播上线信息&#xff1b;发送的消息可以广播给其他在线的客户支持改名支持客户端主动退出支持通过who查找当前在线的用户超时退出 流程 变量 用户结构体 保存用户的管道&#xff0c;用户名以及网络地址信息 typ…
阅读更多...
最新文章

Copyright @ 2022~2023