【数据结构】顺序表详解

当我们写完通讯录后，顺序表肯定难不倒你，跟着小张一起来学习顺序表吧！

线性表

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

在这里插入图片描述

顺序表

概念及结构

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

  1. 静态顺序表：使用定长数组存储元素。
    在这里插入图片描述
  2. 动态顺序表：使用动态开辟的数组存储。
    在这里插入图片描述

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef struct pro
{
	int* p;// 指向动态开辟的数组
	int size;// 有效数据个数
	int capcity;// 容量空间的大小

}pro;
void  SeqListInit(pro* ps );//初始化顺序表
void CheckCapacity(pro* ps);//判断是否空间不够，进行扩容
void  SeqListPushBack(pro* ps,int x);//尾插
void  SeqListPushFront(pro* ps, int x);//头插
void SeqListPopBack(pro* ps);//尾删
void  SeqListPopFront(pro* ps);//头删
void  SeqListPrint(pro* ps);//打印顺序表
void SeqListInsert(pro* ps, int pos, int x);//随意插
void SeqListErase(pro* ps, int pos);//随意删
void SeqListFind(pro* ps, int pos);//查找
void SeqListmodify(pro* ps, int x,int y);//修改
void SeqListDestory(pro* ps);//销毁

结构体定义和创建一个结构体变量

typedef struct pro
{
	int* p;// 指向动态开辟的数组
	int size;// 有效数据个数
	int capcity;// 容量空间的大小

}pro;
int main()
{
	pro info;//定义一个结构体变量
}

初始化顺序表

void  SeqListInit(pro* ps )//初始化顺序表
{
	ps->p = NULL;
	ps->size = 0;
	ps->capcity = 0;
	
}

初始化顺序表，有效数据个数为0，容量空间大小为0，还未给数据动态开辟空间，指向动态开辟空间的指针指向空地址

扩容顺序表

void CheckCapacity(pro* ps)//判断是否空间不够，进行扩容
{
	if (ps->size == ps->capcity)
	{
		int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;
		int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);
		if (tmp == NULL)
		{
			perror("realloc fail!!");

        }
		ps->p = tmp;
		ps->capcity = newcapcity;

   }


}

什么时候需要扩容顺序表呢？？当顺序表刚被初始化，你要进行插入数据时，发现容量空间已经满了，此时必须要扩容空间，当你要插入第一个数据时，在此之前，顺序表没有任何数据，容量空间为0，然后要插入数据的话，也必须扩容。
条件判断如果有效数据个数等于容量大小时，分两种情况，第一种，刚开始的时候，有效数据个数和容量大小都为0的时候，第二种，当要插入数据时，发现此时的有效数据个数和容量大小相等时，且不等于0.对空间进行扩容， newcapcity变量是新的容量大小，当需要扩容的时候，直接新容量为原来的2倍，刚开始，他的容量是0，采用三目运算符，如果容量是0的话，就给四个空间大小，如果不是就开原来容量的2倍。将realloc来的空间的地址存放在tmp指针里面，如果realloc失败就返回空指针，打印错误信息，realloc成功的话就将tmp中存放扩容的地址交给指针p,然后容量大小更新为newcapcity。

尾插

void  SeqListPushBack(pro* ps,int x)//尾插
{
	CheckCapacity(ps);
    ps->p[ps->size] = x;
	ps->size++;}

每次插入都要判断是否需要扩容
在这里插入图片描述
然后有效数据+1.

头插

void  SeqListPushFront(pro* ps, int x)//头插
{
	CheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->p[end + 1] = ps->p[end];
		end--;


    }

	ps->p[0] = x;
	ps->size++;



}

头插一个数据，必须将后面的数据向后面移动，移动的过程中可能超过容量大小，所以在插入时都需要进行扩容判断
在这里插入图片描述
如果按这个顺序移动数据当1挪到2的位置的时候，2这个数据就会被覆盖，所以我们必须从后往前面挪
在这里插入图片描述
在这里插入图片描述当数据挪到后面之后，然后在第一个位置填入x,第一个位置也就是下标为0的位置。
在这里插入图片描述

在下标为0的地方填入 插入的数据x,然后ps->size+1;

尾删

void SeqListPopBack(pro* ps)//尾删
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;

}

尾巴要删除一个数据的话，我们需要将删除的数据改为0吗？如果要删除的数据本来就是0呢？所以我们只需要将ps->size–;因为打印的时候只打印到下标为ps->size-1的位置，打印出来看起来就像 我们删除了这个数据，注意这里用断言是因为在删除的时候ps->size–,当ps->size<0的时候，在添加数据时
ps->p[-1]=x;这个是不合理的，在ps->size<0时，直接报错，第一个断言是为了防止空指针。

头删

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

}

这里的断言和上面是一个道理，然后相比尾删向后挪动数据，头删是往前挪数据，吸取尾删的教训，我们可以直到移动的顺序是
在这里插入图片描述
定义一个变量begin=1,首先是要将数据2移动到数据1的位置，对应的操作是
ps->p[begin - 1] = ps->p[begin];然后begin++,依次将数据3挪到数据2的位置，数据4挪到数据3的位置。循环最后一次是将数据5挪到数据4的位置，也就是begin=4,ps->size=5.则循环判断条件为beginsize,循环结束后将
ps->size–;

顺序表的打印

void  SeqListPrint(pro* ps)//打印顺序表
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->p[i]);



	}

}

循环遍历顺序表，将每个数据打印出来

随意插

void SeqListInsert(pro* ps, int pos, int x)//随意插
{
	CheckCapacity(ps);
	assert(pos>=0&&pos<=ps->size);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->p[end + 1] = ps->p[end];
		end--;

    }
	ps->p[pos] = x;
	ps->size++;
}

断言是为了检查插入的位置是否合理
在这里插入图片描述
当有5个数据时，pos的可能取值如图所示，推广到一般
就是pos>=0&&pos<=ps->size,如果我们想在pos=2的位置插入一个x,我们应该怎么做呢？
1.插入一个x,我们需要将3，4，5向后移动，必须先移动5，定义一个变量end,
在这里插入图片描述
end变量的初值给ps->size-1，也就是4，要想将数据5向后挪动，对应的操作是ps->p[end + 1] = ps->p[end];然后end–;循环分别将4，3向后挪动，循环结束后，将数据x插入到pos=2的位置，对应操作为ps->p[pos] = x;然后有效数据大小ps->size++；

随意删

void SeqListErase(pro* ps, int pos)//随意删
{
	int begin = pos;

	assert(pos >= 0 && pos <= ps->size);
	while (begin<ps->size-1)
	{


		ps->p[begin] = ps->p[begin+1];
		begin++;

    }
	ps->size--;
}

断言判断删除的数据的位置是否合理，和随意插的那里一样
在这里插入图片描述
如果我们要删除数3，然后数据3后面的数据向前挪动，第一步就是将数据4移动到数据3的位置，定义一个变量begin=pos=2;对应的操作为
ps->p[begin] = ps->p[begin+1];，然后begin++;将数据5移动到最开始数据4的地方。最后一次循环是将数据5移动到数据4的地方，也就是begin最后等于3，ps->size=5，则循环判断条件是begin< ps->size-1,循环结束将ps->size–;

顺序表的查找

void SeqListFind(pro* ps, int pos)//查找
{
	assert(pos >= 0 && pos < ps->size);



	printf("你查找的下标是%d,对应的数据是%d", pos, ps->p[pos]);
}

断言保证查找位置的合理性，因为函数传参pos 刚好是要查找数据的下标，直接打印出来

顺序表的修改

void SeqListmodify(pro* ps, int x,int y)//修改
{
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->p[i])
		{
			ps->p[i] = y;
		}


  }

}

x为修改前的值，y是修改之后的值，循环遍历顺序表，将顺序表中所有的x都修改成y

顺序表的销毁

void SeqListDestory(pro* ps)//销毁
{
	ps->capcity = 0;
	ps->size = 0;
	free(ps->p);
	ps->p = NULL;





}

销毁一个顺序表，将顺序表的容量置为0，顺序表的有效数据个数置为0，将p指针所指向的动态开辟的内存空间释放了，由于释放了动态开辟的内存空间，所有p指向的空间未初始化，p成为野指针，为了防止野指针，将p置为空指针。

整体代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct pro
{
	int* p;// 指向动态开辟的数组
	int size;// 有效数据个数
	int capcity;// 容量空间的大小

}pro;
void  SeqListInit(pro* ps )//初始化顺序表
{
	ps->p = NULL;
	ps->size = 0;
	ps->capcity = 0;
	
}
void CheckCapacity(pro* ps)//判断是否空间不够，进行扩容
{
	if (ps->size == ps->capcity)
	{
		int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;
		int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);
		if (tmp == NULL)
		{
			perror("realloc fail!!");



		}
		ps->p = tmp;
		ps->capcity = newcapcity;






	}


}
void  SeqListPushBack(pro* ps,int x)//尾插
{
	CheckCapacity(ps);
    ps->p[ps->size] = x;
	ps->size++;



}
void  SeqListPushFront(pro* ps, int x)//头插
{
	CheckCapacity(ps);
	int end = ps->size - 1;
	while (end>=0)
	{
		ps->p[end + 1] = ps->p[end];
		end--;


    }

	ps->p[0] = x;
	ps->size++;



}
void SeqListPopBack(pro* ps)//尾删
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;

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

}
void  SeqListPrint(pro* ps)//打印顺序表
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->p[i]);



	}

}
void SeqListInsert(pro* ps, int pos, int x)//随意插
{
	CheckCapacity(ps);
	assert(pos>=0&&pos<=ps->size);
	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->p[end + 1] = ps->p[end];
		end--;

    }
	ps->p[pos] = x;
	ps->size++;
}
void SeqListErase(pro* ps, int pos)//随意删
{
	int begin = pos;

	assert(pos >= 0 && pos <= ps->size);
	while (begin<ps->size-1)
	{


		ps->p[begin] = ps->p[begin+1];
		begin++;

    }
	ps->size--;








}
void SeqListFind(pro* ps, int pos)//查找
{
	assert(pos >= 0 && pos < ps->size);



	printf("你查找的下标是%d,对应的数据是%d", pos, ps->p[pos]);
}
void SeqListmodify(pro* ps, int x,int y)//修改
{
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->p[i])
		{
			ps->p[i] = y;
		}





	}






}
void SeqListDestory(pro* ps)//销毁
{
	ps->capcity = 0;
	ps->size = 0;
	free(ps->p);
	ps->p = NULL;





}
int main()
{
	pro info;
	SeqListInit(&info);
	printf("尾插:");
	SeqListPushBack(&info, 1);
	SeqListPushBack(&info, 2);
	SeqListPushBack(&info, 3);
	SeqListPushBack(&info, 4);
	SeqListPrint(&info);
	printf("\n");
	printf("头插:");
	SeqListPushFront(&info, 7);
	SeqListPushFront(&info, 6);
	SeqListPushFront(&info, 5);
	SeqListPushFront(&info, 5);
	SeqListPrint(&info);
	printf("\n");
	printf("尾删:");
	SeqListPopBack(&info);
	SeqListPrint(&info);
	printf("\n");
	printf("头删:");
	SeqListPopFront(&info);
	SeqListPrint(&info);
	printf("\n");
	printf("随意插:");
	SeqListInsert(&info, 1, 1);
	SeqListPrint(&info);
	printf("\n");
	printf("随意删:");
	SeqListErase(&info,1,1);
	SeqListPrint(&info);
	printf("\n");
	printf("查找:");
	SeqListFind(&info, 3);
	printf("\n");
	printf("修改:");
	SeqListmodify(&info, 1, 2);
	SeqListPrint(&info);
	printf("\n");
	printf("销毁:");
	SeqListDestory(&info);
    SeqListPrint(&info);
}

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

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

相关文章

【SpringCloud】SpringCloud整合openFeign

【SpringCloud】SpringCloud整合openFeign

文章目录 前言1. 问题分析2. 了解Feign3. 项目整合Feign3.1 引入依赖3.2 添加注解3.3 编写Feign客户端3.4 测试3.5 总结 4. 自定义配置4.1 配置文件方式4.2 Java代码方式 5. Feign使用优化5.1 引入依赖5.2 配置连接池 6. Feign最佳实践6.1 继承方式6.2 抽取方式 前言 微服务远…
阅读更多...
OpenCV

OpenCV

文章目录 OpenCV学习报告读取图片和网络摄像头1.1 图片读取1.2 视频读取1.1.1 读取视频文件1.1.2读取网络摄像头 OpenCV基础功能调整、裁剪图像3.1 调整图像大小3.2 裁剪图像 图像上绘制形状和文本4.1 图像上绘制形状4.2图像上写文字 透视变换图像拼接颜色检测轮廓检测人脸检测…
阅读更多...
Spring Boot集成MyBatis Plus

Spring Boot集成MyBatis Plus

文章目录 一、前言二、步骤2.1、步骤 1&#xff1a;创建 Spring Boot 项目2.2、添加依赖2.2.1、基本的Spring和Spring MVC功能2.2.2、MySQL驱动依赖2.2.3、 MyBatis Plus 的依赖 2.3、配置数据库连接2.4、创建实体类2.5、创建 Mapper 接口2.6、编写 Service 层2.7、编写 Contro…
阅读更多...
ubuntu20.04+ROS noetic在线运行单USB双目ORB_SLAM

ubuntu20.04+ROS noetic在线运行单USB双目ORB_SLAM

双目摄像头主要有以下几种&#xff0c;各有优缺点。 1.单USB插口&#xff0c;左右图像单独输出2.双USB插口&#xff0c;左右图像单独输出&#xff08;可能存在同步性问题&#xff09;3.双USB插口&#xff0c;左右图像合成输出4.单USB插口&#xff0c;左右图像合成输出 官方版…
阅读更多...
XSS漏洞及分析

XSS漏洞及分析

目录 1.什么是xss漏洞 1&#xff09;存储型XSS漏洞 2&#xff09;反射型XSS漏洞 3&#xff09;DOM型XSS漏洞 2.什么是domcobble破环 3.案例一 1&#xff09;例题链接 2&#xff09;代码展示 3&#xff09;例题分析 4.案例二 1&#xff09;例题链接 2&#xff09;代…
阅读更多...
Java-泛型

Java-泛型

文章目录 Java泛型什么是泛型&#xff1f;在哪里使用泛型&#xff1f;设计出泛型的好处是什么&#xff1f;动手设计一个泛型泛型的限定符泛型擦除泛型的通配符 结论 Java泛型 什么是泛型&#xff1f; Java泛型是一种编程技术&#xff0c;它允许在编译期间指定使用的数据类型。…
阅读更多...
重磅OpenAI发布ChatGPT企业版本

重磅OpenAI发布ChatGPT企业版本

8月29日凌晨&#xff0c;Open AI官网发布ChatGPT企业版本&#xff01; 企业版简介&#xff1a; ChatGPT企业版提供企业级安全和隐私、无限的高速 GPT-4 访问、用于处理更长输入的更长上下文窗口、高级数据分析功能、自定义选项等等。人工智能可以协助和提升我们工作生活的各个…
阅读更多...
魏副业而战：他全职网络创业了

魏副业而战：他全职网络创业了

我是魏哥&#xff0c;与其躺平&#xff0c;不如魏副业而战&#xff01; 社群小X今年全职创业&#xff0c;加入社群一个月&#xff0c;就直接做了徒弟&#xff0c;并且进入合伙人的团队。 玩社群&#xff0c;就要做核心。 小X不到两个月就做到了。 看来他蛮有悟性的。 吃过…
阅读更多...
Redis的数据结构与单线程架构

Redis的数据结构与单线程架构

"飞吧&#xff0c;去寻觅红色的流星" Redis中的五种数据结构和编码 Redis是一种通过键值对关系存储数据的软件&#xff0c;在前一篇中&#xff0c;我们可以使用type命令实际返回当前键所对应的数据结构类型&#xff0c;例如: String\list\hash\set等等。 但…
阅读更多...
R语言入门——line和lines的区别

R语言入门——line和lines的区别

目录 0 引言一、 line()二、 lines() 0 引言 首先&#xff0c;从直观上看&#xff0c;lines比line多了一个s&#xff0c;但它们还是有很大的区别的&#xff0c;下面将具体解释这个两个函数的区别。 一、 line() 从R语言的帮助文档中找到&#xff0c;line()的使用&#xff0c…
阅读更多...
学习笔记230827--vue项目中，子组件拿不到父组件异步获取数据的问题

学习笔记230827--vue项目中，子组件拿不到父组件异步获取数据的问题

&#x1f9cb; 问题描述 父组件的数据是请求后台所得&#xff0c;因为是异步数据&#xff0c;就会出现&#xff0c;父组件的值传递过去了&#xff0c;子组件加载不到&#xff0c;拿不到值的问题。 下面从同步数据传递和异步数据传递开始论述问题 &#x1f9cb;&#x1f9cb;1…
阅读更多...
【逻辑回归-银行客户】

【逻辑回归-银行客户】

逻辑回归&#xff1a;从理论到实践 在本文中&#xff0c;我们将介绍一种被广泛用于二分类问题的机器学习模型——逻辑回归。我们将通过一个实例&#xff0c;深入解析如何在 Python 环境中实现逻辑回归。 源数据下载链接 1. 什么是逻辑回归&#xff1f; 逻辑回归是一种用于解…
阅读更多...
华为 连接OSPF和RIP网络---OSPF和RIP网络相互引入

华为 连接OSPF和RIP网络---OSPF和RIP网络相互引入

路由引入简介 不同路由协议之间不能直接共享各自的路由信息&#xff0c;需要依靠配置路由的引入来实现。 获得路由信息一般有3种途径&#xff1a;直连网段、静态配置和路由协议。可以将通过这3种途径获得的路由信息引入到路由协议中&#xff0c;例如&#xff0c;把直连网段引入…
阅读更多...
【python爬虫】9.带着小饼干登录（cookies）

【python爬虫】9.带着小饼干登录（cookies）

文章目录 前言项目&#xff1a;发表博客评论post请求 cookies及其用法session及其用法存储cookies读取cookies复习 前言 第1-8关我们学习的是爬虫最为基础的知识&#xff0c;从第9关开始&#xff0c;我们正式打开爬虫的进阶之门&#xff0c;学习爬虫更多的精进知识。 在前面几…
阅读更多...
Databricks 入门之sql（二）常用函数

Databricks 入门之sql（二）常用函数

1.类型转换函数 使用CAST函数转换数据类型&#xff08;可以起别名&#xff09; SELECTrating,CAST(timeRecorded as timestamp) FROMmovieRatings; 支持的数据类型有&#xff1a; BIGINT、BINARY、BOOLEAN、DATE 、DECIMAL(p,s)、 DOUBLE、 FLOAT、 INT、 INTERVAL interva…
阅读更多...
Linux服务器部署JavaWeb后端项目

Linux服务器部署JavaWeb后端项目

适用于&#xff1a;MVVM前后台分离开发、部署、域名配置 前端&#xff1a;Vue 后端&#xff1a;Spring Boot 这篇文章只讲后端部署&#xff0c;前端部署戳这里 目录 Step1&#xff1a;服务器上搭建后端所需环境1、更新服务器软件包2、安装JDK83、安装MySQL4、登录MySQL5、修…
阅读更多...
Hadoop Yarn 核心调优参数

Hadoop Yarn 核心调优参数

文章目录 测试集群环境说明Yarn 核心配置参数1. 调度器选择2. ResourceManager 调度器处理线程数量设置3. 是否启用节点功能的自动检测设置4. 是否将逻辑处理器当作物理核心处理器5. 设置物理核心到虚拟核心的转换乘数6. 设置 NodeManager 使用的内存量7. 设置 NodeManager 节点…
阅读更多...
「操作系统」1. 基础

「操作系统」1. 基础

前言&#xff1a;操作系统基础八股文 文章目录 一 、操作系统基础1.1 什么是操作系统&#xff1f;1.2 什么是系统调用1.3 什么是中断 &#x1f680; 作者简介&#xff1a;作为某云服务提供商的后端开发人员&#xff0c;我将在这里与大家简要分享一些实用的开发小技巧。在我的职…
阅读更多...
Matlab(画图进阶)

Matlab(画图进阶)

目录 大纲 1.特殊的Plots 1.1 loglog(双对数刻度图) ​1.3 plotyy(创建具有两个y轴的图形) 1.4yyaxis(创建具有两个y轴的图) 1.5 bar 3D条形图(bar3) 1.6 pie(饼图) 3D饼图 1.7 polar 2.Stairs And Ste阶梯图 3.Boxplot 箱型图和Error Bar误差条形图 3.1 boxplot 3.2 …
阅读更多...
sap 一次性供应商 供应商账户组 临时供应商

sap 一次性供应商 供应商账户组 临时供应商

sap中有一次性供应商这个名词&#xff0c;一次性供应商和非一次性供应商又有什么区别呢&#xff1f; 有如何区分一次性供应商和非一次性供应商呢&#xff1f; 1 区分一次性供应商和非一次性供应商的标志 在供应商的表LFA1中有个字段标示XCPDK&#xff08;一次性科目&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023