C语言数据结构初阶-顺序表

什么是数据结构

数据结构是由数据和结构两个词结合而来，
那么数据由是什么
就比如我们日常生活中的1，2，3，4，5，a,b,c,d,e文字信息图片等，这些就是数据
那么结构又是什么？
想像一下如果我们有大量数据要管理，举一个例子就像我们计算机电脑硬盘里面的东西，如果我们在硬盘里面对于那些文件随便防止任何类型的文件都放在一堆，如果我们要想找某一个文件那将会非常困难，可读性非常差。
如果我们把他们提前整理好，同类型的文件放在一起，形成一个结构这样查找起来就方便多了。
数据结构是计算机存储，组织数据的方式

什么是顺序表

顺序表是一种数据结构它使用计算机内存中的一组地址连续的存储单元来存储线性表的元素。这种存储方式使得线性表中逻辑上相邻的数据元素在物理存储位置上也相邻，通过这种方式，顺序表可以高效地执行插入、删除、查找等操作。顺序表的主要优点包括动态分配空间、支持随机访问元素，以及逻辑顺序与物理顺序的一致性。顺序表可以分为静态和动态两种形式，静态顺序表适用于元素数量固定的情形，而动态顺序表的大小可以根据需要调整。

根据上面的内容我们了解到顺序表是一种数据结构，在计算机内存一组连续的地址可以用来存放东西，提到内存中连续的地址，我们就很容易想到一个东西，叫数组，其实顺序表的底层逻辑就是数组，只是对数组进行了封装，实现了常用的查增删改等接口。

顺序表的分类

顺序表分为静态顺序表和动态顺序表
静态顺序表
顾名思义静态顺序表是静态的，大小是不可改变的，像这张图片
在这里插入图片描述
动态顺序表
顾名思义动态顺序表是动态的大小是可以改变的，像这张图片
在这里插入图片描述根据这两个顺序表的对比，我们可以对比出他们谁好谁坏，可以很明显的看到动态顺序表要明显优于静态顺序表动态顺序表的一个很明显的优势是可以动态增容，而静态顺序表不能，想象一下如果我们要存放数据，使用静态顺序表那么一次性必须申请非常大的空间才能防止空间不够用，而动态顺序表就不用，他可以根据需要数据的大小随意调整，这里我们主要讲动态顺序表。

动态顺序表的C语言实现

如果我们要创建一个顺序表，我们首先想到的就是创建一个结构体用来存放动态顺序表里面的一些信息，像可以空间大小，或者实际使用空间，下面是代码

typedef int Data_type
struct seqlist
{
  Data_type* arr;//数组地址
  int size;//实际使用空间
  int memespace//总空间大小
 };
 typedef struct seqlist sl;//重定义方便书写代码

这里我们创建了一个结构体用来存放整形数据的顺序表相关信息，又重定义了一下，这样有助于我们书写代码。
现在我们来说一下具体思路

具体思路

我们创建了一个int size和int memespace来维护我们的arr数组顺序表
在这里插入图片描述
在他们的基础之上我们来实现增删查改功能，在写完一个功能的时候在测试一下这就是思路。

初始化

首先我们先来看看初始化

void Initseqlist(sl*ps)
{
 ps->arr = NULL;
 ps->size = 0;
 ps->memespace = 0;
 }

这里我们用了一个指针来接收seqlist结构体，为什么要采用地址传递，那是因为这样可以减少内存的占用将结构体的指针作为参数传递给函数，这样函数内部的操作是指向原始结构体的指针，可以直接修改结构体这里我们把顺序表数组和实际使用空间，和总共大小空间都初始化了一下赋值为0和空指针NULL，同样也可以在初始化的时候也可以分配内存大小空间，像这样

(int*)malloc(2*sizeof(Data_type));//申请了两个大小为int的空间就

我们来看看主函数
我们后续的测试功能全在这个主函数里面；

int main()
{
  sl SL;//通过结构体创建了一个名为SL的变量，前面定义过的
  Initseqlist(&SL);//初始化这个SL变量
  return 0;
 }

申请空间

下面是代码

void cheakmemory(sl* ps)
{
  if(ps->memespace == ps->size)
  {
     int new_memespace = ps->memespace == 0?4;2*ps->memespace;
     Data_type*temp = (Data_type*)realloc(ps->arr,new_memespace*sizeof(Data_type));
     if(temp == NULL)
     {
       perror("realloc");
       printf("申请空间失败\n");
      }
      ps->memespace = new_memepace;
     ps->arr = temp;
   }

这里我们首先用了个if来判断是否需要新增空间如果实际使用空间和总共大小空间相等的话就代表空间满了需要申请空间，就进入if语句

int new_memespace = ps->memespace == 0?4;2*ps->memespace;

这段代码的意思是如果总共大小空间等于0的话就预备申请4个空间如果不等于0就预备申请原来大小的两倍空间，为什么要申请两倍的空间呢，那是一个数学问题，在数学中得到如果大小不够申请原来的两到三倍空间是最合理的，就像手机存储一样最开始8g到16g到现在的128，256g都是成倍提升的。为什么这里是预备申请，是因为在下一行代码

 Data_type*temp = (Data_type*)realloc(ps->arr,new_memespace*sizeof(Data_type));

这里才是在实际申请空间，这里用了realloc函数来申请空间如果不知道realloc内存函数怎么用详见这篇文章
动态内存管理
这里的判断都是和realloc函数相关的，这里就不过多说明了

 if(temp == NULL)
     {
       perror("realloc");
       printf("申请空间失败\n");
      }
      ps->memespace = new_memepace;
     ps->arr = temp;
   }

这里将新申请的空间大小重新赋值给原始空间大小，把新空间的地址重新赋值给原始空间地址

尾部插入数据

下面是代码

void slpushback(sl*ps,Data_type x)
{
  assert(ps);
  cheakmemory(ps);//看看空间够不够用
  ps->arr[ps->size] = x;
  ps->size++;
 }

这里我们来画个图就好理解了
在这里插入图片描述增加完之后一定要让size有效数据自增1

头部插入数据

我们了解了尾插，我们来看看头查，头部插入数据要难一点，总的来说头查就是要让所用数据向后面挪动一位，我们画图看看
在这里插入图片描述下面是代码

void slpushfront(sl *ps,Data_type x)
{
  assert(ps);
  cheakmemroy(ps);
  for(int i = ps->size;i<0;i++)
  {
    ps->arr[i] = ps->arr[i-1];
  }
  ps->arr[0] = x;//结束后0下标处就空闲下来了，就可以写入数据了
  size++;
 }

尾部删除数据

尾删挺简单的，就是让实际空间大小减一就行了，不用去实际去删除就像机械硬盘删除数据一样，不会去实际删除，只是告诉系统这里可以写入东西了，下一次写入的时候直接覆盖写入上去，下面是代码

void del_Databack(sl*ps)
{
  assert(ps);//断言一下指针不能为空
  ps->size--;
 }

头部删除数据

这里和头部插入数据的思想方法有点类似就是把后面的元素往前移动一位，我们来看看图片
在这里插入图片描述下面是代码。

void del_Datafront(sl*ps)
{
  assert(ps);
  assert(ps->size);//要删除的有效数据大小不能为0
  for(int i = 0;i<ps->size-1;i++)
  {
    ps->arr[i] = ps->arr[size+1];
   }
  ps->size--;
 }

任意位置删除

关于任意位置删除，我们只需要把要删除数据后面的元素往前面移动覆盖就行了，像这样
在这里插入图片描述
下面是代码

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

任意位置添加数据

在任意位置添加数据，我们只需要把指定添加位置后面的数据整体往后面移动一位就可以了，像这样
在这里插入图片描述下面是代码

void add_angwhere(sl*ps,int pos,intnumber)
{
  assert(ps);
  assert(pos!=0 && pos<ps->size);
  for(int i = ps->size;i>pos;i--)
  {
    ps->arr[i] = ps->arr[i-1];
   }
   ps->arr[pos] = number;
   ps->size++;
  }

任意位置查找

void find_number(sl* ps, int number)
{
	for (int i = 0; i <= ps->size - 1; i++)
	{
		if (ps->arr[i] == number)
		{
			printf("找到了下标是%d", i);
		}
	}
  printf("没找到\n");
}

这里就是下表访问查找了，通过下表访问一个一个去找,如果for循环都走完了就是没找到。

释放空间

void freespace(sl* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->memespace = 0;    
	ps->size = 0;
}

这样运行完程序之后要把占用空间全部还给操作系统才安全
下面是整体实现代码

#pragma once
# include<stdio.h>
# include<stdlib.h>
# include<assert.h>
typedef int Data_type;
struct seqlist
{
	Data_type* arr;
	int size;//数据实际容量
	int memespace;//总共空间大小
};
typedef struct seqlist sl;//重定义
void Initseqlist(sl* ps);//初始化
void cheakmemory(sl* ps);//检测空间够不够
void slpushback(sl* ps, Data_type x);//尾插
void slpushfront(sl* ps, Data_type x);//头插
void del_Databack(sl* ps);//尾删
void del_Datafront(sl* ps);//头删
void del_anywhere(sl* ps, int pos);//任意位置删除
void add_anywhere(sl* ps, int pos, int number);//任意位置添加
void find_number(sl* ps, int number);//查找

void Initseqlist(sl* ps)//初始化
{
	ps->arr = NULL;//(int*)malloc(2*sizeof(Data_type));也可以在初始化就申请空间
	ps->memespace = 0;//2;
	ps->size = 0;

}
void freespace(sl* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->memespace = 0;
	ps->size = 0;
}
void slprint(sl* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}
void cheakmemory(sl* ps)//创建空间
{
	if (ps->memespace == ps->size)
	{
		int new_memspace = ps->memespace == 0 ? 4 : 2 * ps->memespace;
		Data_type* temp = (Data_type*)realloc(ps->arr, new_memspace * sizeof(Data_type));
		if (temp == NULL)
		{
			perror("realloc");
			printf("\n申请空间失败");
		}
		ps->memespace = new_memspace;
		ps->arr = temp;
	}
}
void slpushback(sl* ps, Data_type x)//尾插
{
	assert(ps);
	cheakmemory(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}
void slpushfront(sl* ps, Data_type x)//头插
{
	assert(ps);
	cheakmemory(ps);  
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
void del_Databack(sl* ps)//尾删
{
	assert(ps);
	ps->size--;
}
void del_Datafront(sl* ps)//头删
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
void del_anywhere(sl* ps, int pos)//任意位置删除
{
	assert(ps);
	assert(pos != 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1]; 
	}
	ps->size--;
}
void add_anywhere(sl* ps, int pos, int number)//任意位置添加
{
	assert(ps);
	assert(pos != 0 && pos < ps->size);
	cheakmemory(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = number;
	ps->size++;
}
void find_number(sl* ps, int number)
{
	for (int i = 0; i <= ps->size - 1; i++)
	{
		if (ps->arr[i] == number)
		{
			printf("找到了下标是%d", i);
		}
	}
}
int main()
{
	sl SL;  
	Initseqlist(&SL);
	cheakmemory(&SL);
	slpushback(&SL, 1);
	slpushback(&SL, 2);
	slpushfront(&SL, 3);
	slpushfront(&SL, 4);
	slpushfront(&SL, 3);
	slpushfront(&SL, 5);
	slprint(&SL);
	printf("\n");
	del_Databack(&SL);
	slprint(&SL);
	printf("\n");
	del_Datafront(&SL);
	slprint(&SL); 
	printf("\n");
	del_anywhere(&SL,1);
	slprint(&SL);
	printf("\n");
	add_anywhere(&SL, 2, 10);
	slprint(&SL);
	printf("\n");
	find_number(&SL, 10);
	freespace(&SL);         
	return 0;
}

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

以上就是关于顺序表的讲解了，如果有错误欢迎指正。

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

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

相关文章

Collection与数据结构 Stack与Queue(一): 栈与Stack

Collection与数据结构 Stack与Queue(一): 栈与Stack

1. 栈 1.1 概念 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。 压栈&…
阅读更多...
【029】基于ssm+小程序实现的理发店预约系统

【029】基于ssm+小程序实现的理发店预约系统

作者主页&#xff1a;Java码库 主营内容&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app等设计与开发。 收藏点赞不迷路 关注作者有好处 文末获取源码 技术选型 【后端】&#xff1a;Java 【框架】&#xff1a;ssm 【…
阅读更多...
Hadoop: word count,并将reduce结果写入ES

Hadoop: word count,并将reduce结果写入ES

一、依赖&#xff0c;其中ES版本为7.6.2 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http…
阅读更多...
[StartingPoint][Tier0]Mongod

[StartingPoint][Tier0]Mongod

Task 1 How many TCP ports are open on the machine? (机器上打开了多少个 TCP 端口&#xff1f;) Example: $ sudo nmap -sS -T4 10.129.222.112 -p 27017,22 2 Task 2 Which service is running on port 27017 of the remote host? (哪个服务正在远程主机的端口 270…
阅读更多...
Hippo4j线程池实现技术

Hippo4j线程池实现技术

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容部署运行模式集成线程池监控配置参数默认配置 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家…
阅读更多...
基于Java课程选课系统设计与实现（源码+部署文档）

基于Java课程选课系统设计与实现（源码+部署文档）

博主介绍&#xff1a; ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ &#x1f345; 文末获取源码联系 &#x1f345; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅 &#x1f447;&#x1f3fb; 不然下次找不到 Java项目精品实…
阅读更多...
KIl5：Stm32L071下载出现flash download faild “cortex-m0+“的解决方法

KIl5：Stm32L071下载出现flash download faild “cortex-m0+“的解决方法

首先看看有没有芯片&#xff0c;没有芯片下载一下 下载并在device选择对应的芯片 选择调试器 选择flash
阅读更多...
gpt4.0中文版

gpt4.0中文版

我愿把这个网站成为全球最强AI网站&#xff01;弄100多个AI伺候你&#xff1f;&#xff1f; 家人们&#xff0c;你们猜我发现了什么牛逼的AI网站&#xff1f;&#xff1f; 直接上图&#xff1a; 编辑 这个网站&#xff0c;聚合了国内外100多个顶尖的AI&#xff0c;包括了Op…
阅读更多...
入门用Hive构建数据仓库

入门用Hive构建数据仓库

在当今数据爆炸的时代&#xff0c;构建高效的数据仓库是企业实现数据驱动决策的关键。Apache Hive 是一个基于 Hadoop 的数据仓库工具&#xff0c;可以轻松地进行数据存储、查询和分析。本文将介绍什么是 Hive、为什么选择 Hive 构建数据仓库、如何搭建 Hive 环境以及如何在 Hi…
阅读更多...
我认识的Git-史上最强的版本控制系统

我认识的Git-史上最强的版本控制系统

大家好&#xff01; 欢迎大家来一起交流Git使用心得&#xff0c;相信很多同事对Git都很熟悉了&#xff0c;如果下面说的有错误的“知识点”&#xff0c;欢迎批评指正。 初识Git 我认识Git已经很多年了&#xff08;我在有道云笔记里面“Git”文件夹的创建时间是&#xff1a; …
阅读更多...
sky06笔记下

sky06笔记下

1.边沿检测 检测输入信号din的上升沿&#xff0c;并输出pulse module edge_check ( clk, rstn, din, pulse ); input wire clk,rstn; input wire din; output reg pulse;wire din_dly;always (posedge clk or negedge rstn)beginif(!rstn)din_dly < 1b0;elsedin_dly < d…
阅读更多...
JS-11A/11时间继电器 板前接线 JOSEF约瑟

JS-11A/11时间继电器 板前接线 JOSEF约瑟

系列型号&#xff1a; JS-11A/11集成电路时间继电器&#xff1b;JS-11A/12集成电路时间继电器&#xff1b; JS-11A/13集成电路时间继电器&#xff1b;JS-11A/136集成电路时间继电器&#xff1b; JS-11A/137集成电路时间继电器&#xff1b;JS-11A/22集成电路时间继电器&#…
阅读更多...
【C语言】_文件内容操作：随机读写

【C语言】_文件内容操作：随机读写

目录 1. fseek 1.1 随机读文件 1.2 随机写文件 2. ftell 3. rewind 当以读方式打开一个存在且存有内容的文件时&#xff0c;文件指针会默认指向第一个元素。以在test4.txt文件中存储abcdef为例&#xff1a; int main() {//打开文件FILE* pf fopen("E:\\C_文件操作…
阅读更多...
数学知识--（质数，约数）

数学知识--（质数，约数）

本文用于个人算法竞赛学习&#xff0c;仅供参考 目录 一.质数的判定 二.分解质因数 三.质数筛 1.朴素筛法 2.埃氏筛法 3.线性筛法 四.约数 1.求一个数的所有约数 2.约数个数和约数之和 3.欧几里得算法&#xff08;辗转相除法&#xff09;-- 求最大公约数 一.质数的判定 …
阅读更多...
JWT--study

JWT--study

JWT 1、简介 2、结构 头部 载荷 签证 应用 <dependency><groupId>io.jsonwebtoken</groupId><artifactId>jjwt</artifactId><version>0.9.1</version> </dependency>Token 生成 解析token package com.wang.utils;import io.…
阅读更多...
【QT+QGIS跨平台编译】056：【pdal_lepcc+Qt跨平台编译】（一套代码、一套框架，跨平台编译）

【QT+QGIS跨平台编译】056：【pdal_lepcc+Qt跨平台编译】（一套代码、一套框架，跨平台编译）

点击查看专栏目录 文章目录 一、pdal_lepcc介绍二、pdal下载三、文件分析四、pro文件五、编译实践一、pdal_lepcc介绍 pdal_lepcc 是 PDAL（Point Data Abstraction Library）的一个插件，用于点云数据的压缩。它基于 EPCC（Entwine Point Cloud Compression）算法，提供了对点…
阅读更多...
Linux-4 gcc和makefile

Linux-4 gcc和makefile

Linux编译器-gcc/g使用 1.设计样例 c语言&#xff1a;linux中用的stdc99版本--可能会出现其他问题 c&#xff1a;Linux中用的stdc11--使用c11版本 Linux没有文件格式的区分&#xff0c;但是编译器区分 gcc编译器的文件格式是filename.c g编译器的文件格式是filename.cc或者fil…
阅读更多...
利用Spark将Kafka数据流写入HDFS

利用Spark将Kafka数据流写入HDFS

利用Spark将Kafka数据流写入HDFS 在当今的大数据时代&#xff0c;实时数据处理和分析变得越来越重要。Apache Kafka作为一个分布式流处理平台&#xff0c;已经成为处理实时数据的事实标准。而Apache Spark则是一个强大的大数据处理框架&#xff0c;它提供了对数据进行复杂处理…
阅读更多...
可行性研究报告模板（套用）

可行性研究报告模板（套用）

1业务需求可行性分析 2技术可行性分析 2.1规范化原则 2.2高度的兼容性和可移植性 2.3人性化、适用性 2.4标准化统一设计原则 2.5先进安全可扩展性原则 3开发周期可行性分析 4人力资源可行性分析 5成本分析 6收益分析 7结论 所有资料获取进主页或本文末个人名片直接…
阅读更多...
【OSTEP】并发：线程与多线程

【OSTEP】并发：线程与多线程

" A flow of control within a process that consists of a PC, a register set and a stack space" 本章将介绍为单个运行进程提供的新抽象 —— 线程 (thread) 线程是 调度的一个基本单位&#xff08;basic unit of CPU scheduling&#xff09;一个单独的线程至…
阅读更多...
最新文章

Copyright @ 2022~2023