超详细！！！顺序表的实现

news/2024/5/20 9:50:47 标签: 数据结构, c语言, 顺序表

顺链表的实现

  • 顺序表的概念及结构
  • 动态顺序表的实现
  • 头文件 "SeqList.h"
    • 定义结构体 SL
  • 源文件
    • 顺列表的实现
      • 初始化顺列表 void SLInit(SL* ps)
      • 检查顺列表空间大小 void SLCheckCapacity(SL* ps)
      • 尾插数据 void SLPushBack(SL* ps,SLDataType x)
      • 头插数据 void SLPushFront(SL* ps, SLDataType x)
      • 打印顺序表 void SLPrint(SL* ps)
      • 数组指定位置插入 void SLInsert(SL* ps, int pos, SLDataType x)
      • 销毁顺列表 void SLDestroy(SL* ps)
    • 测试插入
      • 判断有效数据的存在 bool SLIsEmpty(SL* ps)
      • 头删数据 void SLPopFront(SL* ps)
      • 尾删数据 void SLPopBack(SL* ps)
      • 指定数组下标删除 void SLErase(SL* ps, int pos)
    • 测试删除
      • 判断该数据是否存在 bool SLFind(SL* ps, SLDataType x)
      • 查找并返回数据的位置 int SLFindPos(SL* ps, SLDataType x)
      • 修改数据 void SLRevise(SL* ps, int pos, SLDataType x)
    • 测试查找与修改
        • 结束语

顺序表的概念及结构

概念

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

顺序表与数组的区别

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝，并且顺序表的存储一定是连续的，只能从头开始连续存储。

顺序表的结构

  • 静态顺序表：
    使用定长数组存储元素，缺点是空间不好分配，空间给少了不够用，给多了造成空间浪费。
  • 动态顺序表：
    与静态顺序表相比，动态顺序表的空间可以自主申请空间，大大改善了静态顺序表空间难以分配的情况。

动态顺序表的实现

头文件 “SeqList.h”

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

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

#define SLDataType int

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

void SLInit(SL* ps);
void SLDestroy(SL* ps);

void SLPushBack(SL* ps,SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);

void SLErase(SL* ps, int pos);
void SLInsert(SL* ps, int pos, SLDataType x);

bool SLFind(SL* ps, SLDataType x);
int SLFindPos(SL* ps, SLDataType x);
void SLRevise(SL* ps, int pos, SLDataType x)；

void SLPrint(SL* ps);
bool SLIsEmpty(SL* ps);

定义结构体 SL

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

SLDataType* arr;用来存放顺列表的主体数据，SLDataType是我们利用define宏定义所定义的变量，为以后更好的利用顺序表做准备；
size表示有效数据空间个数；
capacity表示总的数据空间个数；
好，下面让我们一 一实现下面头文件中的函数。

源文件

顺列表的实现

初始化顺列表 void SLInit(SL* ps)

void SLInit(SL* ps)
{
	ps->arr=NULL;
	ps->size=ps->capacity=0;
}

将顺列表置为空的状态。

检查顺列表空间大小 void SLCheckCapacity(SL* ps)

void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		assert(tmp);
		ps->arr = tmp;
		tmp = NULL;
		ps->capacity = newcapacity;
	}
}

如果满足ps->capacity == ps->size 那么说明空间不足，因为有效数据个数等于总的ps->arr空间存放数据个数，所以这个时候就需要为ps->arr开辟扩展新的空间，一般情况下，空间的扩展倍数是1.5倍或者2倍，这里以2倍为例。

int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

如果ps->capacity的值为0，我们就不能利用倍数去扩展，而是为他直接开辟空间，所以ps->capacity == 0成立时，放回值为4，否则返回值为ps->capacity。

SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
assert(tmp);
ps->arr = tmp;

新建一个SLDataType*的tmp变量防止realloc开辟空间失败，返回空指针而导致ps->arr被置为NULL。

ps->capacity = newcapacity;

最后将新ps->arr的空间大小赋值给ps->capacity。

尾插数据 void SLPushBack(SL* ps,SLDataType x)

void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

我们在这里只需判断空间大小是否合适，再将数据插入即可，ps->size也要加一。

头插数据 void SLPushFront(SL* ps, SLDataType x)

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int i = 0;
	for (i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->size++;
	ps->arr[0] = x;
}

这里先判断空间大小，再将所有数据再数组中向后移动一位，再将所要添加的值x放到数组的首元素地址处，此时ps->size要记得加一。

打印顺序表 void SLPrint(SL* ps)

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

游历数组arr逐个打印。

数组指定位置插入 void SLInsert(SL* ps, int pos, SLDataType x)

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	if (pos < 0 || pos > ps->size)
	{
		printf("输入错误！！！");
		return;
	}
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

先判断pos值是否输入正确，与顺序表空间是否足够。
这里我们只需要将要插入的数组坐标pos之后的数据向后移动一位，再将要插入的数据x放到arr[pos]即可。
在这里插入图片描述

销毁顺列表 void SLDestroy(SL* ps)

void SLDestroy(SL* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

if (ps->arr) free(ps->arr);将顺序表内arr所申请空间释放，并将ps->size,ps->capacity置为0.

测试插入

#include"SeqList.h"
int main()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);//1 2
	SLPushFront(&s, 0);
	SLPushFront(&s, -1);//-1 0 1 2
	SLInsert(&s, 0, -2);//-2 -1 0 1 2
	SLInsert(&s, s.size, 3);//-2 -1 0 1 2 3
	SLInsert(&s, 3, 0);//-2 -1 0 0 1 2 3

	SLPrint(&s);
	SLDestroy(&s);
	return 0;
}

先尾插1，2再头插0，-1 此时顺序表为-1 0 1 2，再将-2插入到arr[0]此时顺序表为-2 -1 0 1 2，再将3插入到arr[5]此时顺序表为-2 -1 0 1 2 3，最后将0插入到arr[3]此时顺序表为-2 -1 0 0 1 2 3，程序运行结果如下：
在这里插入图片描述

判断有效数据的存在 bool SLIsEmpty(SL* ps)

bool SLIsEmpty(SL* ps)
{
	assert(ps);
	return (ps->size == 0);
}

若有效值ps->size为0，则返回1.

头删数据 void SLPopFront(SL* ps)

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

我们在处理头删数据的时候，assert(!SLIsEmpty(ps))先判断是否数据存在，若存在，可以让后面的数据对前面进行覆盖，再让ps->size减一即可，覆盖示意图如下：
在这里插入图片描述

尾删数据 void SLPopBack(SL* ps)

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	ps->size--;
}

我们尾删数据只需判断数据是否可删，若可删，我们也只要将ps->size--即可，因为我们在访问的时候，数组arr从0开始向后访问，而我们利用ps->size限制了arr数组从0访问的距离。

指定数组下标删除 void SLErase(SL* ps, int pos)

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

这里我们只需要在满足删除条件的时候，找到pos的位置并将后面的数据向前推移即可，再将ps->size - - 。

测试删除

#include"SeqList.h"
int main()
{
	SL s;
	SLInit(&s);
	for (int i = 0; i < 8; i++)
	{
		SLPushBack(&s, i);//0 1 2 3 4 5 6 7 
	}
	SLPopBack(&s);
	SLPrint(&s);//0 1 2 3 4 5 6
	SLPopFront(&s);
	SLPrint(&s);//1 2 3 4 5 6
	SLErase(&s, 0);
	SLPrint(&s);//2 3 4 5 6
	SLErase(&s, s.size - 1);
	SLPrint(&s);//2 3 4 5
	SLErase(&s, 1);
	SLPrint(&s);//2 4 5
	SLDestroy(&s);
	return 0;
}

先利用SLPushBack(&s, i)循环十次来添加顺序表数据，在进行测试以上代码运行结果如下：
在这里插入图片描述

判断该数据是否存在 bool SLFind(SL* ps, SLDataType x)

bool SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if(ps->arr[i]==x)
			return true;
	}
	return false;
}

遍历顺序表中的整个数组，若存在则返回true，否则返回false。

查找并返回数据的位置 int SLFindPos(SL* ps, SLDataType x)

int SLFindPos(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if(ps->arr[i]==x)
			return i;
	}
	return -1;
}

遍历顺序表中的整个数组，当顺序表中的数组元素与查找值相同时，返回数组此时的下标i，若不存在则返回-1。

修改数据 void SLRevise(SL* ps, int pos, SLDataType x)

void SLRevise(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	if (pos >= ps->size && ps < 0)
	{
		printf("输入错误，无法修改\n");
		return;
	}
	ps->arr[pos] = x;
}

先判断pos是否合理，若合理，则通过pos直接进行修改。

测试查找与修改

#include"SeqList.h"
int main()
{
	SL s;
	SLInit(&s);
	for (int i = 0; i < 8; i++)
	{
		SLPushBack(&s, i);//0 1 2 3 4 5 6 7 
	}
	printf("%d\n", SLFind(&s,0));//1
	printf("%d\n", SLFind(&s,7));//1
	printf("%d\n", SLFind(&s,8));//0
	printf("%d\n", SLFindPos(&s, 0));//0
	printf("%d\n", SLFindPos(&s, 3));//3
	printf("%d\n", SLFindPos(&s, 7));//7
	printf("%d\n", SLFindPos(&s, 8));//-1
	printf("修改前：");
	SLPrint(&s);
	SLRevise(&s, SLFindPos(&s, 3), -3);//将3改为-3
	SLRevise(&s, SLFindPos(&s, 7), -7);//将7改为-7
	SLRevise(&s, SLFindPos(&s, 0), 10);//将0改为10
	printf("修改后：");
	SLPrint(&s);
	return 0;
}

运行结果如下：
在这里插入图片描述

结束语

本期是顺序表的基本功能实现，下期小编将为大家带来基于本期的顺序表所实现的可存储通讯录程序的实现。
那么，喜欢请多多关照把！！！
在这里插入图片描述


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

相关文章

火山引擎ByteHouse：如何用OLAP引擎提升数字营销效果？

火山引擎ByteHouse：如何用OLAP引擎提升数字营销效果？

更多技术交流、求职机会&#xff0c;欢迎关注字节跳动数据平台微信公众号&#xff0c;回复【1】进入官方交流群 随着市场竞争的加剧&#xff0c;企业对数字营销投入的效果监测和优化需求日益增强&#xff0c;营销实时监控也成为企业提升运营效率的重要手段。在数字化营销中&…
阅读更多...
LeetCode----76. 最小覆盖子串

LeetCode----76. 最小覆盖子串

 题目 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串，我们保…
阅读更多...
php 低版本getenv 无法获取变量值的替换方案

php 低版本getenv 无法获取变量值的替换方案

正常 7 的版本可以获取环境变量&#xff0c;getenv() 即可,但是到了低版本的&#xff0c;可能只能获取计算机的环境变量&#xff0c;在根目录的.env 文件中无法获取。 只能通过代码简单的转化获取 function env($variableName) {$dotenvFile file_get_contents(.env);$lines …
阅读更多...
TensorRT加速的原因：量化+网络结构优化

TensorRT加速的原因：量化+网络结构优化

文章目录 1. TensorRT 简介2. TensorRT 加速的原理量化网络结构优化 3. TensorRT 的 工作流程TensorRT引擎的构建&#xff1a;BuildTensorRT引擎的推理&#xff1a;Infer 1. TensorRT 简介 TensorRT可以帮助你把训练好的AI模型&#xff0c;部署到边端Nvidia的设备&#xff0c;…
阅读更多...
性能测试计划注意事项

性能测试计划注意事项

在做任何事情之前，唯有进行了良好的计划，方可收到好的效果，性能测试 也是如此，一份定义明确的测试计划将为我们的测试提供良好的保证。下面和大 家讨论一下制定性能测试计划时的一些注意事项。 1. 分析应用程序 测试人员应当对系统的软硬件以及配置情况非常熟悉，这样模…
阅读更多...
成为java高手的八个条件

成为java高手的八个条件

成为java高手的八个条件 1、扎实的基础 数据结构、离散数学、编译原理&#xff0c;这些是所有计算机科学的基础&#xff0c;如果不掌握它们&#xff0c;很难写出高水平的程序。程序人人都会写&#xff0c;但当你发现写到一定程度很难再提高的时候&#xff0c;就应该想想是不…
阅读更多...
No qualifying bean of type [com.rjhc.application.organAccess.service.xxxx]

No qualifying bean of type [com.rjhc.application.organAccess.service.xxxx]

必须要有实现impl &#xff0c;不然 在控制层 无法使用 Autowired。
阅读更多...
中国电子云-隐私计算-云原生安全可信计算，物理-硬件-系统-云产品-云平台，数据安全防护

中国电子云-隐私计算-云原生安全可信计算，物理-硬件-系统-云产品-云平台，数据安全防护

目录 联邦学习的架构思想 中国电子云-隐私计算-云原生安全 可信计算&#xff0c;物理-硬件-系统-云产品-云平台&#xff0c;数据安全防护 全栈国产信创的意义 1. 提升科技创新能力 2. 推动经济发展 3. 加强信息安全与自主可控 全栈国产信创的重要领域 1. 人工智能 2.…
阅读更多...
最新文章

Copyright @ 2022~2023