数据结构-顺序表详解专题

目录

顺序表

1.简单了解顺序表

2.顺序表的分类

2.1静态顺序表

2.2动态顺序表

2.3typedef命名作用

3.动态顺序表的实现

SeqList.h

SeqList.c

test.c

顺序表

1.简单了解顺序表

顺序表是线性表的一种，线性表是在逻辑上是线性结构，在物理逻辑上并不是一定连续的。

顺序表的低层结构是数组，对数组的封装，实现了对数据的增删查改等功能。

2.顺序表的分类

顺序表可以分为静态顺序和动态顺序表

2.1静态顺序表

#define MAX 100
typedef int SLDataType;
//静态顺序表
typedef struct SeqList
{
	SLDataType a[MAX];//这个是开辟100大小的空间，而不是已经使用有效的空间
	int size; //计算存放的有效数据
}SL;

静态顺序表缺陷：空间给少了不够用会造成数据丢失，给多了造成空间浪费。

2.2动态顺序表

//动态顺序表
typedef struct SeqList
{
	SLDataType * arr; //类似于数组指针，作为存储数据的低层结构
	int capacity;//容量，记录顺序表的空间大小，也就是要开辟的空间大小
	int size;//就是记录当前存放了多少有效数据。
}SL;
//两种相同的命名写法。
//typedef sturuct SeqLits SL;

动态顺序表能够实现需要使用空间时候开辟，这样更方便数据的管理，所以推荐用动态顺序表。

2.3typedef命名作用

为什么要用typedef呢

因为当你写int的一堆代码，如果想要把int改成char类型的时候，如果没用到typedeff的话，就要一个一个的改，如果使用了typedef的话直接修改int 换成char就可以了。

3.动态顺序表的实现

分成了三个板块，分别为SeqList.h , SeqList.c ,test.c

SeqList.h

//动态顺序表
typedef struct SeqList
{

	SLDataType * arr; //类似于数组指针，作为存储数据的低层结构
	int capacity;//容量，记录顺序表的空间大小，也就是要开辟的空间大小
	int size;//就是记录当前存放了多少有效数据。
}SL;
//两种相同的命名写法。
//typedef sturuct SeqLits SL;
void SLinit(SL *ps);
void SLPrint(SL* ps); //打印

void SLPushBack(SL * ps ,SLDataType x);  //尾插 
void SLPushFront(SL* ps, SLDataType x);  //头插
void SLCheckcapacity(SL* ps); //扩容

void SLPopBack(SL* ps); //尾删
void SLPopFront(SL* ps); //头删

void SLInsert(SL* ps, int pos, SLDataType x);//指定位置插入
void SLErase(SL* ps, int pos);//指定位置删除

SeqList.c

#include "Sqlist.h"
//初始化
void SLinit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;

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

/扩容放在这里，因为等下头插也会用到，设置成公共的，减少代码
void SLCheckcapacity(SL *ps)
{
	//扩容
	//先判断是不是空间满了
	if (ps->size == ps->capacity)
	{
		//扩容先给arr申请开劈空间 SLDataType * arr; 
		//realloc头文件 stdlib.h,  void  realloc (这是要在已有的空间情况下继续扩容，扩容的大小)
		//ps->arr = (SLDataType*)realloc(ps->arr,2* ps ->capacity  );//扩容2倍2* ps ->capacity
		//但是上面这个是不可取的，因为ps ->capacity刚刚被初始化现在为0。
		//因此要事先判断当 ps ->capacity为0 时，要先赋值,如果不为0 那么开辟2倍的空间
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //三目运算符
		/*ps->arr = (SLDataType*)realloc(ps->arr, newcapacity);*/
		//这样写还是不够准确，这个时候newcapacity是比特大小，不是字节，
		//这个时候要* 一个sizeof(SLDataType),因为要类型的大小字节不同
		/*ps->arr = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));*/
		//即使这样还是不行，因为你不知道是否申请成功，所以还要创建一个临时变量，然后进行判断realloc是否成功
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		//判断realloc是否申请空间成功
		if (tmp == NULL)//如果没空那么是没成功
		{
			perror("realloc fail!"); //这个为啥这么写还真不知道
			exit(1); //扩容失败直接中断程序
		}
		//到这步说明已经申请空间成功
		//free(ps->arr);//不需要这个，realloc他会自己销毁
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//尾插
//参数列表中有一个指向SL结构体的指针ps，
//和一个用来存储数据的参数x。
//函数内部先用assert函数判断st是否为空，
//然后判断栈是否已经满了。如果栈满了，
//就进行扩容操作，将原数组大小翻倍(如果原来大小是0则扩容为4)，
//然后利用realoc函数重新分配内存空间，并将原数组中的数据拷贝到新的空间中。,拷贝的时候要销毁空间
//最后将数据x压入栈的顶部，并将栈顶指针top加一。
void SLPushBack(SL* ps, SLDataType x) //用来存储数据的参数x，x是用来插入数据的内容
{
	//assert 如果不成立那么会直接中断报错，并且会说明在哪里错误。
	//assert(ps);
	assert(ps != NULL); 
	//温柔的判断解决，不会报错
	/*if (ps != NULL)
	{
		return;
	}*/
	//尾插分为情况
	//1.第一个是空间已经满了需要扩容
	//2.第二个是还有空间，直接在尾部，也就是ps -> size 位置插入即可。
	//空间不够
	SLCheckcapacity(ps);
	//空间没有满，直接进行尾插
	ps->arr[ps->size] = x; //为啥存放到arr里面，那capacity干嘛的
	//arr是结构体指针指向的是地址然后用来存放内容的，capacity只是用来存放目前空间大小的容量而已
	ps->size++;


}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
	//头插也是两种情况，一种是满了要开空间，另一种是没满，要把旧数据往后移动，然后留首位置插入
	assert(ps != NULL);
	SLCheckcapacity(ps);

	//将旧数据往后移动，从后面开始移动
	for (int  i = ps->size ; i > 0 ; i--) //让i指向size位置。
	{
		ps->arr[i] = ps->arr[i - 1]; //让i-1位置移动到i位置，就是往后移动一个位置。
	}
	ps->arr[0] = x; //首位置放新元素，头插
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	//两种情况，第一种是全为空，无法删除，第二种是直接可以删尾部数据
	assert(ps != NULL);
	assert(ps->size != 0);//顺序表不能为空

	//进行第二种情况
	//ps->arr[ps->size - 1] = NULL; 
	//当size --，那么即使size位置里面有数据，也不会影响打印，插入，删除
	//因为默认size位置是不进行处理的。相当于看不见等于没有
	ps->size--;

}

void SLPopFront(SL* ps)
{
	//两种情况，第一种是全为空，无法删除，第二种是删除头部，把数据往前移动
	assert(ps != NULL);
	assert(ps->size != 0);//顺序表不能为空

	for (int i = 0 ; i < ps ->size -1 ; i++) //因为size要往前移动一个，i最大只能说ps ->size-2
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//在指定位置插入元素
void SLInsert(SL* ps, int pos, SLDataType x)
{
	
	assert(ps);
	//要限制pos的大小，不然会出错，pos要小于size，也要大于0
	assert(pos >= 0 && pos <= ps->size);
	//扩容
	SLCheckcapacity(ps);

	//首先要知道要插入的pos位置，然后把pos后面的数据往后移动，留pos位置插入
	for (int i = ps->size; i > pos; i--)
	{
		//最后一位size，所以从size开始
		ps->arr[i] = ps->arr[i - 1];//固定句式前面丢给后面
	}
	ps->arr[pos] = x;
	ps->size++;

}

//指定位置删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size );
	//让pos后面的数据往前移动
	for (int i = pos ; i < ps->size - 1 ; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

test.c

#include "Sqlist.h"
void slinit()
{
	SL sl;
SLinit(&sl);//ctrl +d 快速复制

SLPushBack(&sl, 1); //因为是int类型，一开始空间是四个
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
/*SLPushBack(&sl, 1);
SLPushBack(&sl, 1);*/
SLPrint(&sl);
//当传过去的是null空地址
//SLPushBack(NULL, 4); //传空地址乱码，要用accert判断
/*SLPushBack(&sl, 5);
SLPrint(&sl);*/
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);

/*SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);*/

SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);

SLInsert(&sl, 0, 102);
SLInsert(&sl, 3, 15);
SLInsert(&sl, 4, 22);
SLPrint(&sl);

SLErase(&sl, 0);
SLErase(&sl, 2);
SLPrint(&sl);
}
int main()
{
	slinit();
	return 0;
}

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

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

相关文章

【数据结构】栈、队列、数组、列表

【数据结构】栈、队列、数组、列表

数据结构是什么&#xff1f; 数据结构是计算机存储、组织数据的方式 是指数据相互之间是以什么方式排列在一起的。 数据结构是为了更加方便的管理和使用数据&#xff0c;需要结合具体的业务场景来进行选择。一般情况下&#xff0c;精心选择的数据结构可以带来更高的运行或者…
阅读更多...
【CSS】实现鼠标悬停图片放大的几种方法

【CSS】实现鼠标悬停图片放大的几种方法

1.背景图片放大 使用css设置背景图片大小100%&#xff0c;同时设置位置和过渡效果&#xff0c;然后使用&#xff1a;hover设置当鼠标悬停时修改图片大小&#xff0c;实现悬停放大效果。 <!DOCTYPE html> <html lang"en"> <head><meta charset…
阅读更多...
LVGL入门

LVGL入门

一.GUI简介 GUI&#xff0c;全称为图形用户界面&#xff08;Graphical User Interface&#xff09;&#xff0c;是一种通过图形方式与计算机操作系统进行交互的界面。它通过在屏幕上显示图形元素如窗口、按钮、菜单等来代表计算机程序的功能和操作。 GUI的主要特点包括&#…
阅读更多...
phpstudy安装mysql5.7后在my.ini文件中无法修改sql_mode

phpstudy安装mysql5.7后在my.ini文件中无法修改sql_mode

如标题&#xff0c;windows环境下使用phpstudy安装mysql5.7后需要修改mysql中的sql_mode配置&#xff0c;但是在phpstudy中打开mysql配置文件my.ini后&#xff0c; 通过查找找不到sql_mode或sql-mode&#xff0c; 此时无法在my.ini文件中直接进行修改&#xff0c;可以使用mysq…
阅读更多...
系统架构设计师教程（十八）安全架构设计理论与实践

系统架构设计师教程（十八）安全架构设计理论与实践

安全架构设计理论与实践 18.1 安全架构概述18.1.1 信息安全面临的威胁18.1.2 安全架构的定义和范围18.1.3 与信息安全相关的国内外标准及组织18.2 安全模型18.2.1 状态机模型18.2.2 Bell-LaPadula模型18.2.3 Biba模型18.2.4 Clark-Wilson模型18.2.5 Chinese Wall模型18.3 系统安…
阅读更多...
汇编led驱动的代码编写以及ubuntu下的烧录

汇编led驱动的代码编写以及ubuntu下的烧录

文章目录 前言一、实验代码详解二、编译1、arm-linux-gnueabihf-gcc 编译文件2、arm-linux-gnueabihf-ld 链接文件3、arm-linux-gnueabihf-objcopy 格式转换4、arm-linux-gnueabihf-objdump 反汇编5、编写Makefile文件 三、代码烧写1、将 imxdownload 拷贝到工程根目录下2、给予…
阅读更多...
【C语言刷题系列】交换两个变量的三种方式

【C语言刷题系列】交换两个变量的三种方式

文章目录 1.使用临时变量&#xff08;推荐&#xff09; 2.相加和相减的方式&#xff08;值较大时可能丢失数据&#xff09; 3.按位异或运算 本文所属专栏C语言刷题_倔强的石头106的博客-CSDN博客 两个变量值的交换是编程中最常见的问题之一&#xff0c;以下将介绍三种变量的…
阅读更多...
数仓治理-计算资源治理

数仓治理-计算资源治理

注&#xff1a;文章参考: 数据治理实践 | 网易某业务线的计算资源治理从计算资源治理实践出发&#xff0c;带大家清楚认识计算资源治理到底该如何进行&#xff0c;并如何应用到其他项目中https://mp.weixin.qq.com/s/w6d5zhDaaavNhW_DMEkPsQ 目录 一、计算资源治理的背景 二…
阅读更多...
代码随想录算法训练营第15天| Leetcode 104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

代码随想录算法训练营第15天| Leetcode 104.二叉树的最大深度、559.n叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

目录 Leetcode 104.二叉树的最大深度 Leetcode 559.n叉树的最大深度 Leetcode 111.二叉树的最小深度 Leetcode 222.完全二叉树的节点个数 Leetcode 104.二叉树的最大深度 题目链接&#xff1a;Leetcode 104.二叉树的最大深度 题目描述&#xff1a;给定一个二叉树&#xff0c;…
阅读更多...
【驱动系列】C#获取电脑硬件显卡核心代号信息

【驱动系列】C#获取电脑硬件显卡核心代号信息

欢迎来到《小5讲堂》&#xff0c;大家好&#xff0c;我是全栈小5。 这是《驱动系列》文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点…
阅读更多...
Python笔记12-多线程、网络编程、正则表达式

Python笔记12-多线程、网络编程、正则表达式

文章目录 多线程网络编程正则表达式 多线程 现代操作系统比如Mac OS X&#xff0c;UNIX&#xff0c;Linux&#xff0c;Windows等&#xff0c;都是支持“多任务”的操作系统。 进程&#xff1a; 就是一个程序&#xff0c;运行在系统之上&#xff0c;那么便称之这个程序为一个运…
阅读更多...
Linux进程间通信（IPC）机制之一：管道（Pipes）详解

Linux进程间通信（IPC）机制之一：管道（Pipes）详解

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;Nonsense—Sabrina Carpenter 0:50━━━━━━️&#x1f49f;──────── 2:43 &#x1f504; ◀️ ⏸ ▶️ …
阅读更多...
关于session每次请求都会改变的问题

关于session每次请求都会改变的问题

这几天在部署一个前后端分离的项目&#xff0c;使用docker进行部署&#xff0c;在本地测试没有一点问题没有&#xff0c;前脚刚把后端部署到服务器&#xff0c;后脚测试就出现了问题&#xff01;查看控制台报错提示跨域错误&#xff1f;但是对于静态资源请求&#xff0c;包括登…
阅读更多...
数据结构.线性表

数据结构.线性表

1.静态分配 #include<iostream> using namespace std; const int N 10; typedef struct {int data[N];int length;}SqList; void InitList(SqList &L) {for (int i 0; i < N; i){L.data[i] 0;}L.length 0; }int main() {SqList L;InitList(L);return 0; }2.动…
阅读更多...
2024年AI全景预测

2024年AI全景预测

欢迎来到 2024 年人工智能和技术的可能性之旅。 在这里&#xff0c;每一个预测都是一个潜在的窗口&#xff0c;通向充满创新、变革、更重要的是类似于 1950 年代工业革命的未来。 20 世纪 50 年代见证了数字计算的兴起&#xff0c;重塑了行业和社会规范。 如今&#xff0c;人工…
阅读更多...
运行adprep /forestprep扩展Active Directory架构

运行adprep /forestprep扩展Active Directory架构

运行 adprep /forestprep 是为了扩展Active Directory架构&#xff0c;以便为整个林添加新版本Windows Server所支持的新类、属性和其他目录对象。在升级到更高版本的Windows Server并提升林功能级别之前&#xff0c;通常需要执行此操作。 以下是详细步骤&#xff1a; 确认环境…
阅读更多...
flask框架制作前端网页作为GUI

flask框架制作前端网页作为GUI

一、语法和原理 &#xff08;一&#xff09;、文件目录结构 需要注意的问题&#xff1a;启动文件命名必须是app.py。 一个典型的Flask应用通常包含以下几个基本文件和文件夹&#xff1a; app.py&#xff1a;应用的入口文件&#xff0c;包含了应用的初始化和配置。 requirem…
阅读更多...
【C++入门到精通】特殊类的设计 |只能在堆 ( 栈 ) 上创建对象的类 |禁止拷贝和继承的类 [ C++入门 ]

【C++入门到精通】特殊类的设计 |只能在堆 ( 栈 ) 上创建对象的类 |禁止拷贝和继承的类 [ C++入门 ]

阅读导航 引言一、特殊类 --- 不能被拷贝的类1. C98方式&#xff1a;2. C11方式&#xff1a; 二、特殊类 --- 只能在堆上创建对象的类三、特殊类 --- 只能在栈上创建对象的类四、特殊类 --- 不能被继承的类1. C98方式2. C11方法 总结温馨提示 引言 在面向对象编程中&#xff0…
阅读更多...
Nginx与keepalived实现集群

Nginx与keepalived实现集群

提醒一下&#xff1a;下面实例讲解是在mac虚拟机里的Ubuntu系统演示的&#xff1b; Nginx与keepalived实现集群实现的效果 两台服务器都安装Nginx与keepalived&#xff1a; master服务器的ip(192.168.200.2) backup服务器的ip(192.168.200.4) 将 master服务器Nginx与keepalive…
阅读更多...
【Mybatis的一二级缓存】

【Mybatis的一二级缓存】

缓存是什么&#xff1f; 缓存其实就是存储在内存中的临时数据&#xff0c;这里的数据量会比较小&#xff0c;一般来说&#xff0c;服务器的内存也是有限的&#xff0c;不可能将所有的数据都放到服务器的内存里面&#xff0c;所以&#xff0c; 只会把关键数据放到缓存中&#x…
阅读更多...
最新文章

Copyright @ 2022~2023