首页 > 其他分享 >初阶数据结构之顺序表的实现

初阶数据结构之顺序表的实现

时间：2024-10-26 13:17:41浏览次数：3  
标签：ps 初阶 void assert 顺序 SL 数据结构 size

1 线性表

什么是线性表呢？

线性表是n个具有相同特性的数据元素的有限序列。
常见的线性表：顺序表，链表，栈，队列，字符串。

线性表在逻辑上是线性结构，在物理结构上不一定是线性的。线性表在物理存储时，通常是以数组或链式结构形式存储。

线性表大致分为两种：顺序表和链表。基于这两种最基本的结构才能够实现更复杂的数据结构。今天我们着重来了解顺序表的实现。

2 顺序表

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

在这里插入图片描述

顺序表既然是用数组实现的，那么顺序表和数组有什么区别呢？举个例子大家就明白了。这就好比玉米羹，通过厨师一番操作，给玉米羹加上了料汁，饰品，摆盘等，摇身一变就变成宫廷玉液羹。而在这里，顺序表的底层结构采用数组，对数组进行封装，实现了常用的增删改查等接口，就成为了顺序表。

2.1 顺序表的选择

那么新的问题又来了，我们到底该采用静态顺序表还是动态顺序表？

在这里插入图片描述

可以清楚的看到，静态顺序表能够存储的数据个数是有限的。如果数组满了，就无法对新的数据进行存储。可能会有人说，那简单啊，把数组的容量给大一点不就好了。那如果只是多存储了一个数据呢？那岂不是会有很多空间被浪费掉。

静态顺序表的缺陷：空间给少了不够用，给大了空间浪费。

在这里插入图片描述

动态顺序表可根据数据个数对空间大小进行调整。那么到底该如何调整呢？当数组空间满了的时候，我们到底扩几倍呢？如果倍数太大，有可能会造成空间浪费，倍数太小，空间不够用。我们一般扩两倍，因为这样不仅实现了增容，而且有利于减少空间的浪费。

2.2 顺序表的实现

2.1.1 顺序表的定义

typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int capacity;//顺序表的容量
	int size;//实际存储数据的个数
}SL;

typedef int SLDataType 对int进行类型重命名，如果需要存储
char类型数据，只需要修改这里的int就可以了。十分的方便，
代码也不容易出现错误。

2.1.2 顺序表的接口

//初始化
void SeqListInit(SL* ps);

//打印顺序表
void DisplaySeqList(SL* ps);

//尾插
void SeqListPushBack(SL* ps, SLDataType x);

//尾删
void SeqListPopBack(SL* ps);

//头插
void SeqListPushFront(SL* ps, SLDataType x);

//头删
void SeqListPopFront(SL* ps);

//顺序表查找
int SeqListFind(SL* ps, SLDataType x);

//从指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x);

//从指定位置删除数据
void SeqListErase(SL* ps, int pos);

//从指定位置修改数据
void SeqListModify(SL* ps, int pos, SLDataType x);

//销毁空间
void SeqListDestroy(SL* ps);

2.1.3 顺序表的初始化

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

assert(ps!=NULL);断言ps不能为空指针，否则将导致野指针的出现，
同时会对有问题的文件和行号进行报错。

2.1.4 顺序表的打印

//打印顺序表
void DisplaySeqList(SL* ps)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		printf("%d ", ps->a[i]);
		i++;
	}
	printf("\n");
}

ps->size是顺序表的有效数据的个数。数组下标从0开始，对i进行初
始化为0，使用下标引用操作符[]对顺序表进行访问，循环打印。

2.1.5 检查顺序表的容量

//检查容量
void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//初始化时顺序表的容量是0，没有空间，因此无法存储数
		//据，使用三目操作符给顺序表一个初始的容量,同时当顺
		//序表容量满的时候，进行增容
		SLDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->capacity = newcapacity;
		//开辟newcapacity*sizeof(SLDataType)个字节空间
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		//如果开辟失败，则退出程序
		if (NULL == tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		//开辟成功，将新空间的地址交给ps->a进行维护
		ps->a = tmp;
	}
}

在这里插入图片描述

检查顺序表的容量，当容量满了的时候就进行增容。

2.1.6 顺序表尾插

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	//检查顺序表的容量，满了就增容
	SeqListCheckCapacity(ps);
	//插入数据
	ps->a[ps->size] = x;
	//记录顺序表有效数据的个数
	ps->size++;
}

在这里插入图片描述

2.1.7 顺序表尾删

//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//顺序表不能为空，为空意味着顺序表中没有数据，不需要删除
	assert(ps->size > 0);
	ps->size--;
}

这里需要注意的是assert(ps->size>0)(断言顺序表不能为空)，如果没
有这段代码，顺序表会无限制的删除，极易造成越界。

在这里插入图片描述

2.1.8 顺序表头插

//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	//end记录数组最后一个元素的下标
	int end = ps->size - 1;
	//将数组元素整体向后移
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//插入数据
	ps->a[0] = x;
	//更新数组有效数据的个数
	ps->size++;
}

在这里插入图片描述
每次插入数据之前都要先判断顺序表容量是否足够。

2.1.9 顺序表头删

//头删
void SeqListPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//开始挪动数据的起始位置
	int start = 1;
	//将数组元素整体向前移
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	//每删除一次数据，顺序表有效数据个数-1
	ps->size--;
}

在这里插入图片描述

assert(ps->size>0)说明顺序表中有数据才可以删除，否则不需要删除

2.1.10 顺序表查找

//顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}

对数组进行遍历，如果与查找的数字相等，则返回下标，否则继续查找。循环结束之后还未找到，说明顺序表中没有该数据，返回-1。

2.1.11 从指定位置之前插入数据

//从指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断pos的有效性
	assert(pos >= 0 && pos < ps->size);
	//检查顺序表的容量
	SeqListCheckCapacity(ps);
	//记录数组最后一个元素的下标
	int end = ps->size - 1;
	//挪动数据
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//插入数据
	ps->a[pos] = x;
	//更新顺序表有效数据的个数
	ps->size++;
}

在这里插入图片描述

插入数据之前先判断顺序表的容量和pos位置的有效性，再将元素往后移，为pos位置腾出空位，最后插入元素，更新ps->size。

2.1.12 从指定位置删除数据

//从指定位置删除数据
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//顺序表为空的情况
	assert(ps->size > 0);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表至少有一个数据
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}

在这里插入图片描述

删除数据之后，一定不能忘记ps->size--

2.1.13 从指定位置修改顺序表

//从指定位置修改顺序表
void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表为空的情况
	assert(ps->size > 0);
	ps->a[pos] = x;
}

使用下标引用操作符[]去访问数组，直接修改就可以了。

2.1.14 销毁顺序表

//销毁空间
void SeqListDestroy(SL* ps)
{
	assert(ps);
	//ps->a有可能是NULL
	if(ps->a!=NULL)
	{
		free(ps->a);
		ps->a = NULL;
	}
	ps->capacity = 0;
	ps->size = 0;
}

数组是动态开辟出来的空间，程序结束之后要还给操作系统。否则会
造成内存泄漏。因为计算机内存空间也是有限的，如果不还给操作系
统，内存就会越来越少。

3 完整代码的实现

seqlist.h头文件

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

typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int capacity;//顺序表的容量
	int size;//实际存储数据的个数
}SL;


//初始化
void SeqListInit(SL* ps);

//打印顺序表
void DisplaySeqList(SL* ps);

//尾插
void SeqListPushBack(SL* ps, SLDataType x);

//尾删
void SeqListPopBack(SL* ps);

//头插
void SeqListPushFront(SL* ps, SLDataType x);

//头删
void SeqListPopFront(SL* ps);

//顺序表查找
int SeqListFind(SL* ps, SLDataType x);

//从指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x);

//从指定位置删除数据
void SeqListErase(SL* ps, int pos);

//从指定位置修改顺序表
void SeqListModify(SL* ps, int pos, SLDataType x);

//销毁空间
void SeqListDestroy(SL* ps);

seqlist.c源文件

#define _CRT_SECURE_NO_WARNINGS
#include"seqlist.h"


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

//打印顺序表
void DisplaySeqList(SL* ps)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		printf("%d ", ps->a[i]);
		i++;
	}
	printf("\n");
}

//检查容量
void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->capacity = newcapacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (NULL == tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
	}
}

//销毁空间
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//顺序表为空的情况
	assert(ps->size > 0);
	ps->size--;
}

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

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

//顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}
//从指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	assert(pos >= 0 && pos < ps->size);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

//从指定位置删除数据
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//顺序表为空的情况
	assert(ps->size > 0);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表至少有一个数据
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}

//从指定位置修改顺序表
void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表为空的情况
	assert(ps->size > 0);
	ps->a[pos] = x;
}

test.c测试文件

#define _CRT_SECURE_NO_WARNINGS
#include"seqlist.h"

void TestSeqList1()
{
	SL s1;

	SeqListInit(&s1);

	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListPushBack(&s1, 5);

	DisplaySeqList(&s1);

	//SeqListDestroy(&s1);

	SeqListPopBack(&s1);
	SeqListPopBack(&s1);
	SeqListPopBack(&s1);

	DisplaySeqList(&s1);

	SeqListPushFront(&s1, 10);
	SeqListPushFront(&s1, 20);
	SeqListPushFront(&s1, 30);
	SeqListPushFront(&s1, 40);

	DisplaySeqList(&s1);

	SeqListPopFront(&s1);
	SeqListPopFront(&s1);

	DisplaySeqList(&s1);

	SeqListInsert(&s1, 3, 50);
	SeqListInsert(&s1, 2, 60);
	SeqListInsert(&s1, 5, 70);

	DisplaySeqList(&s1);

	int ret = SeqListFind(&s1, 10);
	if (ret >= 0)
	{
		printf("找到了,下标是%d\n", ret);
	}

	SeqListErase(&s1, 0);
	SeqListErase(&s1, 0);

	DisplaySeqList(&s1);

	SeqListModify(&s1, 3, 80);

	DisplaySeqList(&s1);

	SeqListDestroy(&s1);

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

总结：今天的顺序表到这里就结束了。觉得还ok的伙伴点点关注，收藏和点赞吧。

标签：ps,初阶,void,assert,顺序,SL,数据结构,size
From： https://blog.csdn.net/2402_84532723/article/details/143235161

相关文章

  • 数据结构：学生成绩管理系统（链表方法）〈可直接使用〉
    本代码比较完善，有登录模块和菜单模块，拥有很高的可操控性和可观性。代码所包含的功能有很多：成绩输入与删除，按位置查询学生，按姓名查找学生，求表的长度，求最高分学生信息，显示全部学生信息，保存与读取文件......本代码的文件读取和文件保存是一大亮点，可以灵活的存取，启动一次可以切换......
  • Redis基础知识（学习笔记1--五种基础数据结构）
    Redis，Remote Dictionary Server，远程字典服务。Redis的性能极高：其读的速度可以达到11W/s,写的速度可以到达8W/s。高性能的原因（1）操作在内存中发生；（2）C语言开发；（3）源码简单精细（集性能与优雅于一身），早期版本源码只有2W行左右，从3.0版本（开始支持cluster），代码变成了5W左右。Redis有5种......
  • 【数据结构初阶】单链表接口实现超详解
    1.顺序表问题与思考上一篇博客中我们介绍了顺序表，那么顺序表有什么缺点呢？中间/头部的插入删除，时间复杂度为O(N)增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数......
  • C语言顺序表基本操作
    线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常⻅的线性表：顺序表、链表、栈、队列。顺序表一般由一个数组构成，每个元素都连续存放。头文件#include<iostream>#include<stdio.h>#include<stdlib.h>#include<conio.h>#......
  • 数据结构前置知识
    想要成为一名真正的高手，会写会读代码真的只是起步而已，能明白程序的底层运行逻辑，才是神中神。数据结构正是让我们进入代码逻辑世界的钥匙......
  • 【JavaEE初阶】网络原理(1)
    欢迎关注个人主页：逸狼创造不易，可以点点赞吗~如有错误，欢迎指出~互联网中最主流的时TCP/IP五层协议(应用层,传输层,网络层,数据链路层,物理层),应用层是程序员日常开发中最常用到的一层(可以使用已经开发好的协议,也可以自己定义应用层协议),其他层则操作系统/硬件/......
  • 初阶数据结构【3】--单链表（比顺序表还好的一种数据结构！！！）
    本章概述前情回顾单链表实现单链表彩蛋时刻！！！前情回顾咱们在上一章博客点击：《顺序表》的末尾，提出了一个问题，讲出了顺序表的缺点——有点浪费空间。所以，为了解决这个问题，我们今天就要讲解链表，咱们在讲结构体的时候有提到过链表，链表的最大优点——一点空间也不浪费，用多少......
  • 关系型数据库（1）----MySQL(初阶)
    目录1.mysql2.mysqld3.mysql架构1.连接层2.核心服务层3.存储引擎层4.数据存储层4.SQL分类5.MySQL操作库6.MySQL数据类型1.数值类型2.日期和时间类型3.字符串类型4.空间类型5.JSON数据类型7.MySQL表的约束1.主键约束（PRIMARYKEY）2.非空约束（NOTNULL）3.......
  • 雷池社区版有多个防护站点监听在同一个端口上，匹配顺序是怎么样的
    如果域名处填写的分别为IP与域名，那么当使用进行IP请求时，则将会命中第一个配置的站点以上图为例，如果用户使用IP访问，命中example.com。如果域名处填写的分别为域名与泛域名，除非准确命中域名，否则会命中泛域名，不论泛域名第几个配置。以上图为例，如果用户使用a.examp......
  • 【数据结构和算法】一、算法复杂度：时间复杂度和空间复杂度）
    目录1、算法复杂度1.1概念1.2评价指标1.3时间复杂度1.3.1什么是时间复杂度1.3.2常数阶O(1)1.3.3  线性阶O(n)1.3.4 对数阶O(logN)1.3.5  线性对数阶O(nlogN)1.3.6 平方阶O(n²)1.3.7  立方阶O(n³)、K次方阶O(n^k)1.4 空间复杂度1.4.1 空间复......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99