当前位置： 首页 > news >正文

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

news 来源：原创 2024/5/14 6:57:23

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

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

 

目录

数据结构相关概念

顺序表

顺序表的概念和结构

线性表

顺序表分类

顺序表和数组的区别

顺序表分类

静态顺序表

动态顺序表

 头插和尾插

尾插

数据结构相关概念

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

什么是数据？常见的数值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");
}

 

 

相关文章：

  • react useContext 用法
  • HP笔记本电脑如何恢复出厂设置？这里提供几种方法
  • 桥接模式（Bridge Pattern）
  • QT GUI编程常用控件学习
  • cesium相机视角跳转和缩放至entity方法汇总
  • redis的限流器都有哪些方式
  • 【kubernetes】关于k8s集群的声明式管理资源
  • 4核8G服务器并发数多少？性能如何？
  • MySQL-七种SQL优化
  • Spring篇----第十一篇
  • Java面试——锁
  • Vue 3, TypeScript 和 Element UI Plus：前端开发的高级技巧与最佳实践
  • 数据分析之数据预处理、分许建模、可视化
  • MacOS开发环境搭建详解
  • spring boot集成redis
  • 【跃迁之路】【463天】刻意练习系列222（2018.05.14）
  • 002-读书笔记-JavaScript高级程序设计 在HTML中使用JavaScript
  • 2018天猫双11|这就是阿里云！不止有新技术，更有温暖的社会力量
  • Android路由框架AnnoRouter：使用Java接口来定义路由跳转
  • create-react-app做的留言板
  • CSS实用技巧
  • Debian下无root权限使用Python访问Oracle
  • IDEA常用插件整理
  • java2019面试题北京
  • Kibana配置logstash，报表一体化
  • python_bomb----数据类型总结
  • SQLServer之创建显式事务
  • Vue全家桶实现一个Web App
  • 百度小程序遇到的问题
  • 电商搜索引擎的架构设计和性能优化
  • 让你的分享飞起来——极光推出社会化分享组件
  • 入职第二天：使用koa搭建node server是种怎样的体验
  • 验证码识别技术——15分钟带你突破各种复杂不定长验证码
  • 用jquery写贪吃蛇
  • 东超科技获得千万级Pre-A轮融资，投资方为中科创星 ...
  • 微龛半导体获数千万Pre-A轮融资，投资方为国中创投 ...
  • ​ ​Redis（五）主从复制：主从模式介绍、配置、拓扑（一主一从结构、一主多从结构、树形主从结构）、原理（复制过程、​​​​​​​数据同步psync）、总结
  • ​草莓熊python turtle绘图代码（玫瑰花版）附源代码
  • ​一帧图像的Android之旅 :应用的首个绘制请求
  • #{}和${}的区别？
  • #单片机（TB6600驱动42步进电机）
  • （pytorch进阶之路）CLIP模型 实现图像多模态检索任务
  • （附源码）springboot 房产中介系统 毕业设计 312341
  • （附源码）springboot社区居家养老互助服务管理平台 毕业设计 062027
  • (一)基于IDEA的JAVA基础10
  • (转) Android中ViewStub组件使用
  • .NET 药厂业务系统 CPU爆高分析
  • .NETCORE 开发登录接口MFA谷歌多因子身份验证
  • .NET程序员迈向卓越的必由之路
  • .net对接阿里云CSB服务
  • .net开发时的诡异问题，button的onclick事件无效
  • .NET中统一的存储过程调用方法(收藏)
  • .Net组件程序设计之线程、并发管理（一）
  • ?
  • []常用AT命令解释（）