数据结构----顺序表

在学习顺序表之前,我们先来了解一下数据结构。

数据是什么呢?

我们在生活中常见的名字,数字,性别等都属于数据。

结构又是什么呢?

在计算机中,结构就是用来保存数据的方式。

总的来说,数据结构就是计算机存储和组织数据的方式。

1.顺序表

顺序表是数据结构中的一种,也就是说顺序表是一种用来存储和组织数据的一种结构,并且顺序表的底层本质就是数组,只不过顺序表是在数组的的基础上,增加了增删查改的方法,也就是说顺序表里面已经提供了对数据进行增删查改的现成的方法。只不过顺序表里面的增删查改的方法需要我们通过代码来实现,实现顺序表里面的增删查改的代码之后,以后我们实现对通讯录里面数据的增删查改的操作直接用就行了。

同时顺序表是线性表的一种。

1.1线性表

线性表就是具有相同特性的的数据结构的集合。

数据结构是否具有相同特性是从物理结构和逻辑结构来判断。

物理结构:数据在内存中存储的样子。由于我们无法得知计算机是如何给数据分配内存的,所以数据结构有连续和不连续的两种。

逻辑结构:逻辑结构一定是连续的。逻辑结构是我们抽象想象的。

比如排队的时候,我们排对的时候可能排的不是一条直线,但是我们还是得一个一个按序付钱,虽然看起来是不连续的,但在逻辑上我们将其抽象想象成线性的。

前面我们提到,顺序表的底层结构就是数组,而数据又是一块连续的空间,所以顺序表在物理结构和逻辑结构上都是连续的。

 

2.顺序表的分类

我们将顺序表分为了两种,分别为静态顺序表动态顺序表。

2.1 静态顺序表

静态顺序表简单来说就是一个定长的数组。

如下图

1255d2824f2c4bb0af1ed8d5b340029a.png

此时Seqlist就是一个静态顺序表,该顺序表能储存的数据个数大小已经确定,其只能存储100个数据。

2.1动态顺序表

动态顺序表就是一个未定长的数组,也就是动态顺序表里面的数组能存储数据的个数是未定的,但是动态顺序表能存储的数据个数是可以根据实际情况实现动态改变的。

d73fc86872a74f9581c4c3e79924a40d.png

那上面两种顺序表哪种更好用呢?

肯定是动态顺序表。因为它能够根据实际情况来动态实现增容或删除数据。

3.动态顺序表的的实现

由于顺序表的属性有点多,所以我们要用结构体来实现顺序表。

当我们实现动态顺序表的时候我们要分多个文件来实现。如下图

1594fdd1785540ceb1043213e09e269c.png

3.1 动态顺序表的创建和声明

typedef int SLDataType;  //方便以后修改要存储的数据类型
struct SeqList
{
	SLDataType* arr;
	int size;  //有效的数据个数顺序表里面
	int capacity;  //顺序表的总大小
};
typedef struct SeqList SL; 

在一个头文件里面实现动态顺序表的声明。这里我们要将顺序表里面要存储的数据类型重命名为SLDataType,是为了以后方便修改要存储的数据类型,并且也将顺序表重命名为SL,方便后面的操作。

3.2动态顺序表的初始化

在.c源文件实现初始化

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

ec01091d4d25487b99bf074eaf2240bc.png

需要注意的是,我们进行传参的时候要将sl的地址传过去。我们知道形参是实参的拷贝,我们对形参的改变是不会影响实参的,不会影响实参,初始化就会失败所以我们要将sl的地址传过去,通过指针来实现初始化 。

8ffdfe40345e49adba5f2798db992441.png

通过调试,我们发现顺序表初始化成功了。

3.2 销毁动态顺序表

因为后面涉及到扩容等问题,要用到realloc函数,申请空间,完成程序之后我们要将申请的空间还给计算机,我们这里先把顺序表的销毁讲了,方便以后操作。

void SLBreak(SL* sl)
{
	if (sl->arr)
	{
		free(sl->arr);
	}
	sl->size = 0;
	sl->capacity = 0;
}

3.3 数据插入

将数据插入顺序表中有两种方法,分别是尾插和头插。

3.3.1 尾插

什么是尾插呢?

尾插就是从顺序表的尾部插入数据。如下图

63fc300e4f8548609e1fb5c35d602782.png

此时的size==4,我们可能就会想到所以只要将ps->arr[size]改为想要插入的之就行了 。写出以下代码

void SLPushBack(SL* sl, SLDataType x)
{
	sl->arr[sl->size] = x;
}

但事情并没有那么简单。

我们要知道插入数据时,首先要清楚顺序表内有没有足够的空间来存储插入的数据呢?一开始我们已经将顺序表的内存大小设置为0,这时侯肯定是没有空间插入数据的,所以这时候我们要向内存申请空间,并且以后我们要根据实际情况来实现扩容,所以这时候最好的选择是通过realloc函数来申请空间。

接着再来分析,我们要申请多大的空间呢?

一搬来说,是原来capacity的两倍或者三倍是最好的的选择。

但原来的capacity为0,所以这时候要用上三目操作符。

尾插代码如下

void SLPushBack(SL* sl, SLDataType x)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		//实现扩容
		int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;
		SLDataType* tmp =(SLDataType*) realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));
         //判断空间是否申请成功
		if (tmp==NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//代码运行到这里,空间就申请成功了
		sl->arr = tmp;
		sl->capacity = SLNewCapacity;
	}
	sl->arr[sl->size] = x;
	sl->size++;
}

易错点:扩容那里后面是两个==。

 我们需要注意的是我们申请空间成功时返回的地址不能直接传给原来顺序表的数组,因为申请空间会存在失败的情况,空间申请失败就会退出程序,并销毁该空间了。假设我们之前的顺序表已经存有数据,但因为空间申请失败也把原来的空间释放掉,那么原来的数据也没了,这就功亏一篑了,所以我们要设计一个中间变量存储申请空间返回的地址,有这个中间变量来判断空间是否申请成功。

由于我们插入了数据,不要忘了让size的个数进行增加。

3.3.2 头插

什么是头插呢?

头插就是从顺序表的头部插入一个数据。

下面来分析一下如何实现头插。

59731d29ed6244f49c61eaa16f847859.png

假设上图是我们要进行头插的一个数组?

我们要将一个数据插入1的位置,那么我们就要将原有的数据向后移一位。如下图

2a69ca80fd8e4aaab72e8a5a79e65afa.png

既然插入数据,我们就涉及到空间申请了,这里的空间申请于尾插的一莫一样,既然一样,那我们干脆把空间申请的那部分代码单独写为一个函数,需要的时候调用这个函数就行了。

空间申请的代码如下

void SLSpace(SL* sl)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		//实现扩容
		int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;
		SLDataType* tmp = (SLDataType*)realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//代码运行到这里,空间就申请成功了
		sl->arr = tmp;
		sl->capacity = SLNewCapacity;
	}
}

尾插代码

void SLPushHead(SL* sl, SLDataType x)
{
	assert(sl);
	//调用空间申请函数
	SLSpace(sl);
	//实现顺序表原数据向后移1位
	for (int i = sl->size; i > 0; i--)
	{
		sl->arr[i] = sl->arr[i - 1];//arr[1]=arr[0]
	}
	sl->arr[0] = x;
	sl->size++;
}

运行效果如下图,头插的数据为5。

4b6c1f2b18a745ffb76c090d28b52099.png

3.4.数据删除

既然有数据的插入,那么就有数据的删除。删除我们也分为尾删头删的两种。

3.4.1 尾删

什么是尾删?

尾删就是将顺序表里面的的最后一个元素删除掉。

465d00ffed8f4f8389eb8f20bb27e750.png

如上图,尾删将4给除掉了。

代码实现

void SLPopBack(SL* sl)
{
	assert(sl);
	assert(sl->size);  //检测顺序表不为空
	sl->size--;
}

尾删我们直接让size( 顺序表中的有效个数)减减就行了。我们没必要将要尾删的数据改为其他,我们只要求尾删的操作不影响后面的增删查改的操作就行了。

运行效果

c4d2832165374ad595bdc6f56d295d42.png

3.4.2 头删

什么是头删呢?

头删就是将顺序表的第一个元素删除掉 。

eb4632f13a9b4a068f8da951c8fb4764.png

头删如上图所示,也就是将第一个元素除外其他元素向前移动一位。

代码实现 

void SLPopHead(SL* sl)
{
	assert(sl);
	assert(sl->size);
	//实现数据向前移动一位
	for (int i = 0; i<sl->size-1; i++)
	{
		sl->arr[i] = sl->arr[i + 1];  //arr[2]=arr[3]
	}
	sl->size--;
}

运行效果

30b1ec68d75a449db11afb822975d488.png

3.5 在指定位置插入数据

分析如何实现?

思路:将指定位置的数据及以从后向前的顺序向后移动一位。

如下图

4cd8c68bfc26492596a41558b1a42245.png

代码实现

 

void SLPopPos(SL* sl, int pos, SLDataType x)
{
	assert(sl);
	assert(sl->size && pos <= sl->size);
	//插入数据之前要申请空间
	SLSpace(sl);
	for (int i = sl->size; i > pos; i--)
	{
		sl->arr[i] = sl->arr[i - 1];
	}
	sl->arr[pos] = x;
	sl->size++;
}

运行效果

31b8e5fdbb4f44fb9bba6ace53a2b049.png

3.6 在指定位置删除数据

 思路

将指定位置之后的数据向前移动一位。

如下图

195180e0bd55478a92ad80eaaacb2731.png

代码实现

void SLPopPos(SL* sl, int pos)
{
	assert(sl&&sl->size);
	assert(pos && pos < sl->size);
	for (int i = pos; i<sl->size-1; i++)
	{
		sl->arr[pos] = sl->arr[pos + 1];
	}
	sl->size--;
}

运行效果

84665d2439864f168b556732e63dd126.png

3.7 查找数据

代码实现

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

}

运行效果

a6e21b25e3fe44cfbb2d3e58974795de.png

 这里就结束了对顺序表的介绍

下面给大家列处全部代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
int main()
{
	SL sl;  //创建一个结构体变量
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);
	SLPushHead(&sl, 5);
	SLPrint(sl);
	SLPopBack(&sl);
	SLPrint(sl);
	SLPopHead(&sl);
	SLPrint(sl);
	SLPushPos(&sl, 1, 3);
	SLPrint(sl);
	SLPopPos(&sl, 2);
	SLPrint(sl);
	int find = SLFind(&sl, 3);
	if (find < 0)
	{
		printf("不存在");
	}
	else
	{
		printf("数据位于下标为%d",find);
	}
	//要在顺序表销毁之前完成增删查改的操作
	SLBreak(&sl);
	
	return 0;
}

SeqList.h

#include <assert.h>
typedef int SLDataType;  //方便以后修改要存储的数据类型
struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
};
typedef struct SeqList SL; 
void SLInit(SL* sl);
void SLPrint(SL sl);
void SLBreak(SL* sl);
void SLPushHead(SL* sl, SLDataType x);
void SLPushBack(SL* sl, SLDataType x);
void SLPopBack(SL* sl);
void SLPopHead(SL* sl);
void SLPushPos(SL* sl, int pos, SLDataType x);
void SLPopPos(SL* sl, int pos);
int SLFind(SL* sl, SLDataType x);

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLInit(SL* sl)
{
	sl->arr = NULL;
	sl->size = 0;
	sl->capacity = 0;
}
void SLSpace(SL* sl)
{
	assert(sl);
	if (sl->size == sl->capacity)
	{
		//实现扩容
		int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;
		SLDataType* tmp = (SLDataType*)realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		//代码运行到这里,空间就申请成功了
		sl->arr = tmp;
		sl->capacity = SLNewCapacity;
	}
}
void SLPrint(SL sl)
{
	for (int i = 0; i < sl.size; i++)
	{
		printf("%d ", sl.arr[i]);
	}
	printf("\n");
}
void SLBreak(SL* sl)
{
	if (sl->arr)
	{
		free(sl->arr);
	}
	sl->arr = NULL;
	sl->size = 0;
	sl->capacity = 0;
}
void SLPushBack(SL* sl, SLDataType x)
{
	SLSpace(sl);
	sl->arr[sl->size] = x;
	sl->size++;
}
void SLPushHead(SL* sl, SLDataType x)
{
	assert(sl);
	//调用空间申请函数
	SLSpace(sl);
	//实现顺序表原数据向后移1位
	for (int i = sl->size; i > 0; i--)
	{
		sl->arr[i] = sl->arr[i - 1];//arr[1]=arr[0]
	}
	sl->arr[0] = x;
	sl->size++;
}
void SLPopBack(SL* sl)
{
	assert(sl);
	assert(sl->size);  //检测顺序表不为空
	sl->size--;
}
void SLPopHead(SL* sl)
{
	assert(sl);
	assert(sl->size);
	//实现数据向前移动一位
	for (int i = 0; i<sl->size-1; i++)
	{
		sl->arr[i] = sl->arr[i + 1];  //arr[2]=arr[3]
	}
	sl->size--;
}
void SLPushPos(SL* sl, int pos, SLDataType x)
{
	assert(sl);
	assert(sl->size && pos <= sl->size);
	//插入数据之前要申请空间
	SLSpace(sl);
	for (int i = sl->size; i > pos; i--)
	{
		sl->arr[i] = sl->arr[i - 1];
	}
	sl->arr[pos] = x;
	sl->size++;
}
void SLPopPos(SL* sl, int pos)
{
	assert(sl&&sl->size);
	assert(pos && pos < sl->size);
	for (int i = pos; i<sl->size-1; i++)
	{
		sl->arr[pos] = sl->arr[pos + 1];
	}
	sl->size--;
}
int SLFind(SL* sl, SLDataType x)
{
	assert(sl);
	for (int i = 0; i < sl->size; i++)
	{
		if (sl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;

}

 感谢观看。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/562004.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

anaconda配置的环境对应的地址查看,环境安装位置

打开conda指令窗口 这个和上面的都一样&#xff0c;哪个都行 点开后&#xff0c;输入 conda env list 这里显示的就是自己的每个环境对应的地址了

OpenCV杂记(1):绘制OSD(cv::getTextSize, cv::putText)

1. 简述 我们使用OpenCV时&#xff0c;有时会在图像的某个位置绘制OSD信息&#xff0c;如绘制一些字符串作为指示信息。 本文将简要介绍在图像&#xff08;cv::Mat&#xff09;上绘制固定的字符串信息。 2. 使用的API &#xff08;1&#xff09;cv::getTextSize() CV_EXPORT…

C++模板template(二十一)

在C的模板体现了一种泛型编程的思想&#xff0c;当我们不确定要传入的参数是何种数据类型时我们可以写一个模板类型来代替&#xff0c;当传入参数时才将类型告诉它。模板也是属于一种静态多态&#xff0c;&#xff0c;模板的不同类型发生在编译时。泛型编程&#xff1a;不是针对…

react中useState的值没有改变,而是旧的数值

问题背景 想实现点击按钮就改变数据的效果&#xff0c;但是在控制台的打印结果&#xff0c;总是上一次的修改情况&#xff0c;并不是最新的修改后的数据 代码&#xff1a; import { useState, useRef } from "react";// 实现sonA的数据传递给sonB const SonA () …

排序之插入排序:从斗地主到插入排序

目录 1.斗地主如何摸牌 2.从摸牌想到插入排序 3.完成插入排序 4.结束语 1.斗地主如何摸牌 不知道各位是否玩过几乎人人都玩过的斗地主游戏呢&#xff1f;相必各位或多或少都玩过一点&#xff0c;再没玩过也看别人打过。今天博主就将从这个游戏为大家讲解我们的插入排序。 在…

Zabbix监控Oracle归档日志空间

1、oracle查看归档日志空间的sql语句 select sum(PERCENT_SPACE_USED) from v$recovery_area_usage; 2、交互式查看oracle归档日志空间的命令&#xff0c;可以手动执行一下&#xff0c;注意要用oracle用户 sqlplus -S "/ as sysdba" << EOF select sum(PER…

攻防世界---misc---[中等] QR1

1.下载附件&#xff0c;是一张空白图片&#xff0c;打开看看&#xff0c;仔细看会发现有黑色小点点 2.图片太大了&#xff0c;我们缩小图片的宽高比例 3.将修改后的图片&#xff0c;用Stegsolve打开&#xff0c;切换图层&#xff0c;得到二维码 4.用QR进行二维码扫描 5.得到fla…

Spring之CGLIB和JDK动态代理底层实现

目录 CGLIB 使用示例-支持创建代理对象&#xff0c;执行代理逻辑 使用示例-多个方法&#xff0c;走不同的代理逻辑 JDK动态代理 使用示例-支持创建代理对象&#xff0c;执行代理逻辑 ProxyFactory 如何自动在CGLIB和JDK动态代理转换 使用示例-使用CGLIB代理方式 使用示…

OpenCV基本图像处理操作(十一)——图像特征Sift算法

图像尺度空间 在一定的范围内&#xff0c;无论物体是大还是小&#xff0c;人眼都可以分辨出来&#xff0c;然而计算机要有相同的能力却很难&#xff0c;所以要让机器能够对物体在不同尺度下有一个统一的认知&#xff0c;就需要考虑图像在不同的尺度下都存在的特点。 尺度空间的…

浏览器渲染流程中的 9 个面试点

记得 08 年以前&#xff0c;打开网页的时候一个页面卡死整个浏览器凉凉。 这是因为当时浏览器是单进程架构&#xff0c;一个页面或者插件卡死&#xff0c;整个浏览器都会崩溃&#xff0c;非常影响用户体验。 经过了一代代工程师的设计&#xff0c;现代浏览器改成了多进程架构&…

AD高速板设计-DDR(笔记)

【一】二极管 最高工作频率&#xff1a; 定义&#xff1a;二极管的最高工作频率&#xff0c;即二极管在电路中能够正常工作的最高频率。常见的硅二极管的最高工作频率通常在几十MHz到几百MHz之间。在高频下&#xff0c;二极管可能无法有效地阻止反向电流&#xff0c;但也不会…

Redis入门到通关之数据结构解析-Dict

文章目录 概述构成Dict的扩容Dict的rehash总结 概述 我们知道Redis是一个键值型&#xff08;Key-Value Pair&#xff09;的数据库&#xff0c;我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。 Dict由三部分组成&#xff0c;分别是&#xff1a;哈…

数据输入输出流(I/O)

文章目录 前言一、数据输入输出流是什么&#xff1f;二、使用方法 1.DataInputStream类2.DataOutoutStream类3.实操展示总结 前言 数据输入输出流也是将文件输入输出流打包后使用的对象。相比于文件输入输出流&#xff0c;数据输入输出流提供了简单易用的方法去操作不同类型的数…

IDEA安装JAVA_HOME报错、启动界面卡死的解决方案

1、起因 在使用一段时间社区版的IDEA后&#xff0c;发现有些功能无法正常使用&#xff0c;于是打算安装正版旗舰版IDEA&#xff08;狗头&#xff09;。 2、JAVA_HOME报错 结果发现安装完后&#xff0c;经过一段操作&#xff0c;IDEA无法正常启动&#xff0c;报错如下&#x…

oracle一次sql优化笔记

背景&#xff1a;两个百万级数据量表需要连接&#xff0c;加全索引的情况下速度仍不见改善&#xff0c;苦查一下午解决问题未遂。 解决&#xff1a;经大佬指点了解到oracle优化器提示&#xff0c;使用/* USE_HASH(table1 table2) */或者/* USE_MERGE(table1 table2) */来指导优…

Adobe Acrobat DC 2022:全方位PDF编辑利器,解锁文档处理新境界

在当今信息爆炸的时代&#xff0c;PDF格式因其跨平台性、稳定性以及易读性而备受欢迎&#xff0c;成为办公、学习和交流的常用格式。Adobe Acrobat DC 2022作为专业的PDF编辑软件&#xff0c;凭借其卓越的性能和丰富的功能&#xff0c;赢得了众多用户的青睐。 Adobe Acrobat D…

Java web应用性能分析之性能指标【响应时间】

前面几篇发出来&#xff0c;发现漏了一个标准说明。当我们谈论应用慢时&#xff0c;这个慢的指标是啥&#xff1f;怎么衡量的&#xff1f;从用户体验来讲&#xff0c;一个页面展示在3秒完成&#xff0c;用户还能接受&#xff0c;超过3秒就会影响用户体验&#xff0c;用户就会感…

107页 | 企业数字化转型规划设计(免费下载)

【1】关注本公众号&#xff0c;转发当前文章到微信朋友圈 【2】私信发送 【企业数字化转型规划设计】 【3】获取本方案PDF下载链接&#xff0c;直接下载即可。 如需下载本方案PPT原格式&#xff0c;请加入微信扫描以下方案驿站知识星球&#xff0c;获取上万份PPT解决方案&…

深入理解Java IO流:字节流

深入理解Java IO流&#xff1a;字节流 引言 在Java中&#xff0c;IO&#xff08;输入/输出&#xff09;操作是程序与外部世界交互的重要方式。 其中&#xff0c;File类是进行文件操作的基础&#xff0c;而字节流和字符流则是数据传输的两种主要方式。 本文将深入探讨这些概念及…

C#到底属于编译型语言还是解释型语言?

C#是一种编译型语言&#xff0c;也称为静态类型语言&#xff0c;这意味着C#代码在运行之前需要经过编译器的编译处理&#xff0c;并生成一个可执行的本地代码文件&#xff08;通常是.exe或.dll文件&#xff09;。相反&#xff0c;解释型语言将代码转换为低级代码后直接执行&…