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

  🌈个人主页: 会编辑的果子君

💫个人格言:“成为自己未来的主人~”  

 

目录

数据结构相关概念

顺序表

顺序表的概念和结构

线性表

顺序表分类

顺序表和数组的区别

顺序表分类

静态顺序表

动态顺序表

 头插和尾插

尾插


数据结构相关概念

数据结构是由“数据”和“结构”两词组合而来。

什么是数据?常见的数值1,2,3,4.....,教务系统里保存的用户信息,(姓名,性别,年龄,学历等),网页里肉眼可以看到的信息(文字,图片,视频等等),这些都是数据。

什么是结构?

当我们想要使用大量使用同一类型的数据时,通过手动定义大量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将大量的数据组织在一起,结构也可以理解为组织数据方式。

概念:数据结构是计算机存储,组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的元素的集合,数据结构反映数据的内部构成,即数据由哪部分构成,以什么方式构成,以及数据元素之间呈现的结构。

总结:

1)能够存储数据结构(如顺序表,链表等结构)

2)存储的数据能够方便查找

数据结构需要用到结构体,指针(一级指针,二级指针,指针传参),结构体指针,动态内存管理

顺序表

顺序表的概念和结构

线性表

线性表是N个具有相同特性的数据元素的有限序列,线性表是一种是实际中极其有用的数据结构,常用的线性表:顺序表,链表,栈,队列,字符串.....

线性表在逻辑上是线性结构,也就是说是连续的一条直线,但是在物理结构上并不一定是连续的

线性表在物理上存储时,通常是以数组和链式结构的形式存储。

顺序表:逻辑结构是线性的,物理结构是连续的

顺序表分类

顺序表和数组的区别

顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口

顺序表分类

静态顺序表

使用定长数组存储元素

typedef int SLDataType;
#define N 10
struct SeqList {
	SLDataType a[N];//定长数组
	int size; //有效数组个数

}SL;

静态顺序表的缺陷:空间给少了不够用,给多了造成空间浪费

在上面的代码中,还有一个优点在于 int 可以立即替换而不影响下面的代码执行

动态顺序表

//动态顺序表-按需申请
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* arr;//存储数据的底层逻辑
	int capacity;   //记录顺序表的空间
	int size;       //记录顺序表的当前的有效存储
}SL;

动态顺序表,可增容

静态顺序表,给定的数组长度,若不够,会导致后续的数据保存失败,数据丢失是非常严重的技术事故

给多了,会导致空间的大量浪费

//初始化和销毁
void SLInit(SL* ps) {
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//检查
void SLChectCapacity(SL* ps) {
	if (ps->size = ps->capacity) {
		int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
		SLDataType tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性

 头插和尾插

尾插

空间足够,直接插入

空间不够,扩容

扩容的原则:

一次扩充一个空间,插入一个元素还不会造成看空间浪费,程序执行效率低

一次扩容固定大小的空间(10,100)

小了造成频繁扩容

大了造成空间浪费

成倍数的增加(1.5倍,2倍)

数据插入的越多,扩容的大小越来越大

#define _CRT_SECURE_NO_WARNINGS
#include"code.2.26.h"
//初始化和销毁
void SLInit(SL* ps) {
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//检查
void SLCheckCapacity(SL* ps) {
	if (ps->size == ps->capacity) {
		int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
		SLDataType tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//顺序表的头插/尾插
void SLPushBack(SL* ps, SLDataType x) {
	//断言,粗暴的解决办法
	//assert(ps!=NULL);
	assert(ps);
	//if判断--温柔的解决办法
	/*if (ps == NULL) {
		return;
	}*/
	//空间不够,扩容
	SLCheckCapacity(ps);
	//空间足够,直接插入
	ps->arr[ps->size++] = x;
}
void SLDestroy(SL* ps) {

}
void SLPrint(SL* ps) {
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
#define _CRT_SECURE_NO_WARNINGS
#include"code.2.26.h"
void slTest01() {
	SL s1;
	SLInit(&s1);
	//测试尾插
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPrint(&s1); //1 2 3 4
}

int main() {
	slTest01();

	return 0;
}
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//静态顺序表

//typedef int SLDataType;
//#define N 10
//struct SeqList {
//	SLDataType a[N];//定长数组
//	int size; //有效数组个数
//
//}SL;

//动态顺序表-按需申请
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* arr;//存储数据的底层逻辑
	int capacity;   //记录顺序表的空间
	int size;       //记录顺序表的当前的有效存储
}SL;

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性
//顺序表的头部/尾部插入
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

//打印顺序表
void SLPrint(SL* ps);
#define _CRT_SECURE_NO_WARNINGS
#include"code.2.26.h"
void slTest01() {
	SL s1;
	SLInit(&s1);
	//测试尾插
	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);

	SLErase(&s1, 1);
	SLPrint(&s1); //1 2 3 4

}

int main() {
	slTest01();

	return 0;
}
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//静态顺序表

//typedef int SLDataType;
//#define N 10
//struct SeqList {
//	SLDataType a[N];//定长数组
//	int size; //有效数组个数
//
//}SL;

//动态顺序表-按需申请
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* arr;//存储数据的底层逻辑
	int capacity;   //记录顺序表的空间
	int size;       //记录顺序表的当前的有效存储
}SL;

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性
//顺序表的头部/尾部插入
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//顺序表的头部/尾部删除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//指定位置之前插入数据
//删除指定位置数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//打印顺序表
void SLPrint(SL* ps);
#define _CRT_SECURE_NO_WARNINGS
#include"code.2.26.h"
//初始化和销毁
void SLInit(SL* ps) {
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//检查
void SLCheckCapacity(SL* ps) {
	if (ps->size == ps->capacity) {
		int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;
		SLDataType tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//顺序表的头插/尾插
void SLPushBack(SL* ps, SLDataType x) {
	//断言,粗暴的解决办法
	//assert(ps!=NULL);
	assert(ps);
	//if判断--温柔的解决办法
	/*if (ps == NULL) {
		return;
	}*/
	//空间不够,扩容
	SLCheckCapacity(ps);
	//空间足够,直接插入
	ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否扩容
	SLCheckCapacity(ps);
	//旧数据往后挪动一位
	for (int i = ps->size; i > 0; i++)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
//顺序表的头部/尾部删除
void SLPopBack(SL* ps) {
	assert(ps);
	assert(ps->size);

	//顺序表不为空
	ps->size--;
}
void SLPopFront(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 SLInsert(SL* ps, int pos, SLDataType x) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);
	//pos及之后的数据往后挪动一位,pos空出来
	for (int i = ps->size; i > pos; i--)
	{
		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--;
}
void SLDestroy(SL* ps) {

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

 

 

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

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

相关文章

逆向案例二:关键字密文解密,自定义的加密解密。基于企名片科技的爬取。

import requests import execjsfor i in range(4):i i1url https://vipapi.qimingpian.cn/Activity/channelInformationByChannelNamedata {channel_name: 24新声,page: f{i},num: 20,unionid: W9wLD4rHIZrB3GLTUncmHgbZcEepR78xJa5Zit6XTMtata86DehdxDt/fDbcHeeJWqqIs6k…

Golang Redis:构建高效和可扩展的应用程序

利用Redis的闪电般的数据存储和Golang的无缝集成解锁协同效应 在当前的应用程序开发中&#xff0c;高效的数据存储和检索的必要性已经变得至关重要。Redis&#xff0c;作为一个闪电般快速的开源内存数据结构存储方案&#xff0c;为各种应用场景提供了可靠的解决方案。在这份完…

PHP请求示例获取淘宝商品详情数据API接口(按关键词搜索商品列表)

请求示例&#xff0c;API接口接入Anzexi58 item_get-获得淘宝商品详情 taobao.item_get 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥WeChat18305163218api_nameString是API接口名称&#xff08;包…

nodejs 实现pdf与图片互转

PDF转图片 效果图 代码 const path require(path); const pdf require(pdf-poppler); const fs require(fs); // PDF文件路径 const pdfFilePath ./path/test.pdf; // 转换选项 const opts { format: png, // 输出图片格式&#xff0c;可以是 jpeg, png, ppm…

东芝工控机维修东芝电脑PC机维修FA3100A

TOSHIBA东芝工控机维修电脑控制器PC机FA3100A MODEL8000 UF8A11M 日本东芝TOSHIBA IA controller维修SYU7209A 001 FXMC12/FXMC11;BV86R-T2GKR-DR7YF-8CPPY-4T3QD; CPU处理单元是可编程逻辑控制器的控制部分。它按照可编程逻辑控制器系统程序赋予的功能接收并存储从编程器键入…

组合模式(Composite Pattern)C++

上一节&#xff1a;桥接模式&#xff08;Bridge Pattern&#xff09; C 文章目录 0.理论1.目的与应用场景2.实现方式 1.实践 0.理论 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;用于将对象组合成树形结构以表示“部分-整体”的层次结…

CodeSys中调用C语言写的动态库

文章目录 1.前言2.前期准备3.创建CodeSys库工程3.1.函数名必须包含_cext3.2.生成m4、c文件 4.搭建编译环境&#xff0c;编译出动态库*.so4.1.将ExtensionSDK文件夹拷贝到板子的一个目录中。4.2.创建工程目录&#xff0c;且将前面生成的m4、c文件拷贝到这个工程目录下4.3.执行ma…

亚信安慧AntDB数据库与流式处理的有机融合

流式处理的概念 2001年9月11日&#xff0c;美国世贸大楼被袭击&#xff0c;美国国防部第一次将“主动预警”纳入国防的宏观战略规划。而IBM作为当时全球最大的IT公司&#xff0c;承担了大量基础支撑软件研发的任务。其中2009年正式发布的IBM InfoSphere Streams&#xff0c;就是…

R语言——条形图数据可视化的多种方式

本文章将会介绍如何使用R语言中的ggplot2包使用条形图进行数据可视化。将会使用一个“生产企业原材料的订购与运输”的订单数据&#xff0c;该数据来自2021数学建模国赛C题。 某建筑和装饰板材的生产企业所用原材料主要是木质纤维和其他植物素纤维材料总体可分为 A B C 三种类…

密码学系列(四)——对称密码2

一、RC4 RC4&#xff08;Rivest Cipher 4&#xff09;是一种对称流密码算法&#xff0c;由Ron Rivest于1987年设计。它以其简单性和高速性而闻名&#xff0c;并广泛应用于网络通信和安全协议中。下面是对RC4的详细介绍&#xff1a; 密钥长度&#xff1a; RC4的密钥长度可变&am…

影像仪激光扫描功能,无缝连接2D/3D混合测量

在现代工业生产领域&#xff0c;影像仪用于质量控制和产品检测&#xff0c;是一个不可或缺的工具。它通过高精度的成像和图像处理技术&#xff0c;可以及时发现产品的缺陷和异常&#xff0c;以保证产品质量的稳定性和一致性。 影像仪的重要性及其面临的挑战 在工业生产方面&a…

分段与分页,LDT与GDT,页目录表与页表简单的认识

综合四篇文章看下分段与分页机制&#xff1a; 分段&#xff1a;LDT与GDT 分页&#xff1a;页目录表与页表 首先明确两个结论&#xff1a; 1.cr3里保存页目录表的基址的地址类型为物理地址&#xff0c;页目录表里的每一项也是页表的物理地址。 2.gdtr的地址和gdt里的描述符里的…

MySQL:开始深入其数据(一)DML

在上一章初识MySQL了解了如何定义数据库和数据表&#xff08;DDL&#xff09;&#xff0c;接下来我们开始开始深入其数据,对其数据进行访问&#xff08;DAL&#xff09;、查询DQL&#xff08;&#xff09;和操作(DML)等。 通过DML语句操作管理数据库数据 DML (数据操作语言) …

Vue3列表触底请求(上手体验hooks新特性)

今天我们来聊一聊业务开发中的触底请求&#xff0c;其实就是分页的一种&#xff0c;只不过传统的分页感觉很丑而已&#xff0c;正好我的小博客最近在做触底分页&#xff0c;借此机会来说一说具体怎么实现的&#xff0c;以及来带领大家使用一下Vue3中的新特性hooks函数。 案例和…

uniapp小程序uView自定义tabbar

两年没接触小程序&#xff0c;又重新拾请来 前言 工具&#xff1a;HBuilder X 3.99版本 微信开发者工具 1.06 语言&#xff1a;vue2 uView 一、创建项目 先使用HBuilder X工具创建一个空白uni-app项目 uviewTest 二、安装和配置 HBuilder X找到工具-》插件安装-》插件市场 u…

Flutter中高级JSON处理:使用json_serializable进行深入定制

Flutter中高级JSON处理 使用json_serializable库进行深入定制 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at: https://jclee95.blog.csdn.netEmail: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28550263/article/details/1363…

vscode不能远程连接ubuntu18.04.6

目录 问题解决Portable Mode 安装vscode 补充说明学习资料 问题 vscode远程ssh连接ubuntu18.04.6时&#xff0c;出现如下提示框&#xff0c;单击Learn More后&#xff0c;定位到问题。Can I run VS Code Server on older Linux distributions? 原始是&#xff1a;需要glibc …

Mac 配置Clion Qt 调试显示变量值

背景 使用Clion开发Qt程序&#xff0c;在进行调试时&#xff0c;会看不到Qt类的变量值&#xff0c;只有指针形式&#xff0c;对于调试很不方便。 环境&#xff1a; Macbook ProCPU&#xff1a;M3Qt 5.15.13CLion 2023.3.4 解决方案 为了让Clion能显示Qt类的值&#xff0c;…

Ubuntu常用状态命令

目录 一、温度 1&#xff0c;查看CPU温度 2&#xff0c;查看硬盘温度 二、CPU状态 1&#xff0c;显示CPU的详细信息&#xff0c;包括型号、频率、缓存等 2&#xff0c;显示CPU架构、CPU核心数、线程数、频率等信息 三、登录状态 1&#xff0c;查看成功登录的用户 2&am…

4核8g服务器能支持多少人访问?

腾讯云4核8G服务器支持多少人在线访问&#xff1f;支持25人同时访问。实际上程序效率不同支持人数在线人数不同&#xff0c;公网带宽也是影响4核8G服务器并发数的一大因素&#xff0c;假设公网带宽太小&#xff0c;流量直接卡在入口&#xff0c;4核8G配置的CPU内存也会造成计算…