数据结构学习——线性表、顺序表

1.线性表

线性表 （ linear list ） 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

image-20240331084641957

2.顺序表

2.1概念及结构

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

注：顺序表只能从头开始连续存储。

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储元素

    image-20240304154453711

  2. 动态顺序表：使用动态开辟的数组存储。

    image-20240304154954903

    我们思考一个问题：为什么容量空间不够时候，我们经常扩容是进行2倍扩容呢？而不是其他倍数或者常数呢？

    因为2倍扩容相对合适，越扩频率越低而且c++库里面扩容也是2倍扩容。但是1.5倍扩容或者一倍扩容都可以。

2.2接口实现

2.2.1接口实现代码：

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

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;//数据类型最好typedef下，否则数据类型会有各种变化，变化以后所有都得修改typedef struct SeqList
{//int* a;SLDataType* a; //指向动态开辟的数组int size;      //有效数据int capacity;  //空间容量
}SL;void SLInit(SL* psl);//初始化
void SLDestroy(SL* psl);//释放空间void SLPrint(SL* psl);//打印
void SLCheakCapacity(SL* psl);//检查空间容量是否够用，不够则扩容//头尾插入删除
void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删//任意下标位置的插入删除
void SLInsert(SL* psl, int pos, SLDataType x);//插入
void SLErase(SL* psl, int pos);//删除//找到返回下标
//没有找到返回-1
int SLFind(SL* psl, SLDataType x);

#include"SeqList.h"void SLInit(SL* psl)
{psl->a = NULL;psl->size = 0;psl->capacity = 0;
}void SLDestroy(SL* psl)
{assert(psl);if (psl->a != NULL){free(psl->a);psl->a != NULL;psl->size = 0;psl->capacity = 0;}
}void SLPrint(SL* psl)
{assert(psl);for (int i = 0; i < psl->size ;i++){printf("%d ", psl->a[i]);}printf("\n");
}void SLCheakCapacity(SL* psl)
{assert(psl);if (psl->size == psl->capacity){int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);if (tmp == NULL){perror("ralloc fail");return;}psl->a = tmp;psl->capacity = newCapacity;}
}void SLPushBack(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);psl->a[psl->size] = x;psl->size++;
}void SLPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);int end = psl->size - 1;while (end >= 0){psl->a[end + 1] = psl->a[end];--end;}psl->a[0] = x;psl->size++;
}void SLPopBack(SL* psl)
{assert(psl);if (psl->size == 0){return;}assert(psl->size >0);psl->size--;
}
void SLPopFront(SL* psl)
{assert(psl);assert(psl->size > 0);for (int begin = 0; begin < psl->size; begin++){psl->a[begin] = psl->a[begin+1];}psl->size--;
}void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos <= psl->size);//如果等于则是头插尾插SLCheakCapacity(psl);int end = psl->size;while (end > pos){psl->a[end] = psl->a[end - 1];end--;}psl->a[end] = x;psl->size++;
}//void SLInsert(SL* psl, int pos, SLDataType x)
//{
//	assert(psl);
//	assert(pos >= 0 && pos <= psl->size);
//
//	SLCheakCapacity(psl);
//
//	// 挪动数据
//	int end = psl->size - 1;
//	while (end >= pos)
//	{
//		psl->a[end + 1] = psl->a[end];
//		--end;
//	}
//
//	psl->a[pos] = x;
//	psl->size++;
//}void SLErase(SL* psl, int pos)
{assert(psl);assert(pos >= 0 && pos < psl->size);int begin = pos;for(;begin<psl->size ;begin++){ psl->a[begin] = psl->a[begin + 1];}psl->size--;
}int SLFind(SL* psl, SLDataType x)
{assert(psl);for (int j = 0; j < psl->size; j++){if (psl->a[j] == x){return j;}}return -1;
}

#include"SeqList.h"void TestSL1()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPrint(&sl);SLPushFront(&sl, 10);SLPushFront(&sl, 20);SLPushFront(&sl, 30);SLPrint(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPrint(&sl);SLPopFront(&sl);SLPopFront(&sl);SLPrint(&sl);
}void TestSL2()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLInsert(&sl, 3, 50);SLInsert(&sl, 3, 40);SLPrint(&sl);SLErase(&sl, 5);SLPrint(&sl);int pos = SLFind(&sl, 3);if (pos != -1){SLErase(&sl , pos);}SLPrint(&sl);}int main()
{TestSL2();// 越界一定报错吗？//int a[10];// 越界读基本不会报错//printf("%d\n", a[10]);//printf("%d\n", a[11]);// 越界写可能会报错//a[10] = 1;//a[11] = 1;//因为越界的检查是一种抽查行为return 0;
}

free错误：

1.free位置不对

2.存在越界访问

2.2.2 接口实现思路

SList.c ：

void SLCheakCapacity(SL* psl)；

检查空间是否足够，若不够则：空间为0则开辟4个空间，若不为零，则将原有的空间的大小乘以2

void SLCheakCapacity(SL* psl)
{assert(psl);if (psl->size == psl->capacity){int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);if (tmp == NULL){perror("ralloc fail");return;}psl->a = tmp;psl->capacity = newCapacity;}
}

image-20240319160311346

尾插：

void SLPushBack(SL* psl, SLDataType x)

先判断psl链表是否为空，为空直接结束，不为空继续执行。再检查空间是否够用，不够则开辟，够则把x的值给数组a，然后size＋＋。

void SLPushBack(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);psl->a[psl->size] = x;psl->size++;
}

头插：

void SLPushFront(SL* psl, SLDataType x);

void SLPushFront(SL* psl, SLDataType x)
{assert(psl);SLCheakCapacity(psl);int end = psl->size - 1;while (end >= 0){psl->a[end + 1] = psl->a[end];--end;}psl->a[0] = x;psl->size++;
}

思路如下：

image-20240319163811791

尾删：

void SLPopBack(SL* psl);


void SLPopBack(SL* psl)
{assert(psl);if (psl->size == 0){return;}assert(psl->size >0);psl->size--;
}

image-20240319211228190

头删：

void SLPopFront(SL* psl);

void SLPopFront(SL* psl)
{assert(psl);assert(psl->size > 0);for (int begin = 0; begin < psl->size; begin++){psl->a[begin] = psl->a[begin+1];}psl->size--;
}

image-20240319211511721

任意下标位置的插入：

void SLInsert(SL* psl, int pos, SLDataType x);//插入

void SLInsert(SL* psl, int pos, SLDataType x)
{assert(psl);assert(pos >= 0 && pos <= psl->size);//如果等于则是头插尾插SLCheakCapacity(psl);int end = psl->size;while (end > pos){psl->a[end] = psl->a[end - 1];end--;}psl->a[end] = x;psl->size++;
}

image-20240319212326944

任意下标位置的删除：

void SLErase(SL* psl, int pos);//删除

void SLErase(SL* psl, int pos)
{assert(psl);assert(pos >= 0 && pos < psl->size);int begin = pos;for(;begin<psl->size ;begin++){ psl->a[begin] = psl->a[begin + 1];}psl->size--;
}

image-20240319213303535

找下标：

//找到返回下标
//没有找到返回-1
int SLFind(SL* psl, SLDataType x);

int SLFind(SL* psl, SLDataType x)
{assert(psl);for (int j = 0; j < psl->size; j++){if (psl->a[j] == x){return j;}}return -1;
}

image-20240319213814208

2.3 数组相关面试题

  1. 删除排序数组中的重复项。

    26. 删除有序数组中的重复项 - 力扣（LeetCode）

    代码：

    int removeDuplicates(int* nums, int numsSize) 
{int src=1;int dst=0;while(src<numsSize){if(nums[src]==nums[dst]){src++;}else{dst++;nums[dst]=nums[src];src++;}}return dst+1;
}

    解题思路：

    image-20240305191118302

  2. 合并两个有序数组。

    88. 合并两个有序数组 - 力扣（LeetCode）

    代码如下：

    void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int j = m+n - 1;int n1 = m - 1;int n2 = n - 1;while(n1>=0 && n2>=0){if(nums1[n1]>nums2[n2]){nums1[j--]=nums1[n1--];}else{nums1[j--]=nums2[n2--];}}while(n2>=0){nums1[j--]=nums2[n2--];}
}

    解题思路：

    image-20240305193102132

2.4 顺序表的问题及思考

问题： OJ链接 1. 中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。 思考：如何解决以上问题呢？下面给出了链表的结构来看看。
= m - 1;
int n2 = n - 1;
while(n1>=0 && n2>=0)
{
if(nums1[n1]>nums2[n2])
{
nums1[j–]=nums1[n1–];
}
else
{
nums1[j–]=nums2[n2–];
}
}
while(n2>=0)
{
nums1[j–]=nums2[n2–];
}
}

解题思路：[外链图片转存中...(img-Iu1JfGs6-1712583978516)]## 2.4 顺序表的问题及思考问题： OJ链接 1. 中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。 思考：如何解决以上问题呢？下面给出了链表的结构来看看。

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

项目管理-项目资源管理2/2

项目管理-项目资源管理2/2

项目管理&#xff1a;每天进步一点点~ 活到老&#xff0c;学到老 ヾ(◍∇◍)&#xff89;&#xff9e; 何时学习都不晚&#xff0c;加油 资源管理&#xff1a;6个过程“硅谷火箭管控” ①规划资源管理&#xff1a; 写计划 ②估算活动资源&#xff1a;估算团队资源&…
阅读更多...
渗透之sql盲注（时间/boolean盲注）

渗透之sql盲注（时间/boolean盲注）

sql盲注&#xff1a;sql盲注意思是我们并不能在web页面中看到具体的信息&#xff0c;我们只能通过输入的语句的真假来判断。从而拿到我们想要的信息。 我们通常使用ascii值来进行盲注。 目录 手动注入&#xff1a; 时间盲注&#xff1a; 布尔盲注&#xff1a; python脚本注…
阅读更多...
LabVIEW波浪发电平台浮筒取能效率数据采集系统

LabVIEW波浪发电平台浮筒取能效率数据采集系统

LabVIEW波浪发电平台浮筒取能效率数据采集系统 随着化石能源的逐渐减少以及能源价格的上升&#xff0c;寻找可替代的、可再生的、清洁的能源成为了世界各国的共识。波浪能作为一种重要的海洋能源&#xff0c;因其巨大的潜力和清洁性&#xff0c;近年来受到了广泛关注。开发了一…
阅读更多...
(六)JSP教程——out对象

(六)JSP教程——out对象

out对象是在JSP中经常使用到的对象&#xff0c;它本质上是一个输出流&#xff0c;前面已经多次使用&#xff0c;我们经常使用它的print()和println()方法&#xff0c;这些方法主要用于实现客户端数据的输出。通过out对象也可以直接向客户端发送一个由程序动态生成的HTML文件。 …
阅读更多...
Docker-Compose 容器集群的快速编排

Docker-Compose 容器集群的快速编排

Docker-compose 简介 Docker-Compose项目是Docker官方的开源项目&#xff0c;负责实现对Docker容器集群的快速编排。 Docker-Compose将所管理的容器分为三层&#xff0c;分别是 工程&#xff08;project&#xff09;&#xff0c;服务&#xff08;service&#xff09;以及容器&…
阅读更多...
JavaEE企业级开发中常用的JDK7和JDK8的时间类

JavaEE企业级开发中常用的JDK7和JDK8的时间类

JDK7时间类 全世界的时间有一个统一的计算标准 在同一条经线上的时间是一样的 格林威治时间 简称GMT 计算核心 地球自转一天是24小时 太阳直射正好是12小时 但是误差太大 现在用原子钟来代替 用铯原子震动的频率来计算时间&#xff0c;作为世界的标准时间UTC 中国标准时间…
阅读更多...
在国企分公司做信息宣传新闻投稿的经验分享

在国企分公司做信息宣传新闻投稿的经验分享

作为一名国企分公司的信息宣传工作者,我亲历了从传统投稿方式到数字化转型的全过程,这段经历既充满了挑战,也收获了成长。回首最初的日子,那些用邮箱投稿的时光,至今仍让我感慨万千。 初尝辛酸,邮箱投稿的艰难岁月 刚接手信息宣传工作时,我满腔热情,却很快被现实的冷水浇了个透…
阅读更多...
c语言实现贪吃蛇小游戏————附全代码！！！

c语言实现贪吃蛇小游戏————附全代码！！！

目录 1.Win32 API 1.1控制台应用程序 1.2控制台的名称&#xff0c;控制台窗口大小 1.3设置控制台光标位置 COORD - 光标坐标 GetStdHandle - 获取句柄 SetConsoleCursorPosition - 设置光标位置 封装一个设置光标的函数 1.4设置控制台光标的属性 CONSOLE_CURSOR_INFO …
阅读更多...
栈PART 1

栈PART 1

目录 1. 栈 1.1 栈的概念和结构 1.2 栈的实现 1.2.1 栈的顺序储存结构 1.2.2 栈的基本操作 1.3 有效的括号 1. 栈 1.1 栈的概念和结构 堆栈又名栈&#xff08;stack&#xff09;&#xff0c;它是一种运算受限的线性表。 限定仅在表尾进行插入和删除操作的线性表。这一端…
阅读更多...
C++进阶之路：深入理解编程范式，从面向过程到面向对象（类与对象_上篇）

C++进阶之路：深入理解编程范式，从面向过程到面向对象（类与对象_上篇）

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
java-函数式编程-语法

java-函数式编程-语法

目录 1、函数表现形式 分类 lambda表达式 参数类型可以全写&#xff0c;也可以全不写&#xff0c;但不能一部分写&#xff0c;一部分不写lambda 的省略策略&#xff1a;凡是可推导&#xff0c;都可以省略 方法引用 练习-判断语法正确性 练习-写出与方法引用等价的lambda表达式…
阅读更多...
TCP三次握手四次挥手 UDP

TCP三次握手四次挥手 UDP

TCP是面向链接的协议&#xff0c;而UDP是无连接的协议 TCP的三次握手 三次传输过程是纯粹的不涉及数据&#xff0c;三次握手的几个数据包中不包含数据内容。它的应用层&#xff0c;数据部分是空的&#xff0c;只是TCP实现会话建立&#xff0c;点到点的连接 TCP的四次挥手 第四…
阅读更多...
VMware虚拟机提示内存不足

VMware虚拟机提示内存不足

VMware虚拟机&#xff0c;k8s集群搭建内存不足的问题 疑问&#xff1a;我的电脑是8G8G双通道的内存&#xff0c;当我在搭建k8s集群时给master-2G内存&#xff0c;node1-3G内存&#xff0c;node2-3G内存&#xff1b; 当依次打开虚拟机到node2时VM提示“物理内存不足&#xff0c;…
阅读更多...
【大学物理】双语合集听课笔记

【大学物理】双语合集听课笔记

7.5 angular momentu(角动量)_哔哩哔哩_bilibili 6.4Energy in Rotation Motion 有质量有速度的物体有动能&#xff0c;是不是很有道理 international system&#xff08;from French systeme international&#xff0c;acronym&#xff0c;SI&#xff09;of ineria kg*m^2 转…
阅读更多...
使用 Cython 加密 Python 代码防止反编译

使用 Cython 加密 Python 代码防止反编译

文章目录 前言使用 Cython 加密 Python 代码环境Python 源代码编写 Cython 编译配置文件 编译查看输出文件使用 问题error: Microsoft Visual C 14.0 or greater is requiredpyconfig.h(59): fatal error C1083: 无法打开包括文件: “io.h”: No such file or directorydynamic…
阅读更多...
鸿蒙开发全攻略：华为应用系统如何携手嵌入式技术开启新篇章~

鸿蒙开发全攻略：华为应用系统如何携手嵌入式技术开启新篇章~

鸿蒙操作系统是华为自主创新的成果&#xff0c;打破了传统操作系统的局限。通过结合嵌入式技术&#xff0c;鸿蒙实现了跨平台、跨设备的高度融合&#xff0c;提供了流畅、智能的体验。华为应用系统与嵌入式技术的结合&#xff0c;提升了性能&#xff0c;丰富了用户体验。鸿蒙与…
阅读更多...
嵌入式Linux的QT项目CMake工程模板分享及使用指南

嵌入式Linux的QT项目CMake工程模板分享及使用指南

在嵌入式linux开发板上跑QT应用&#xff0c;不同于PC上的开发过程。最大的区别就是需要交叉编译&#xff0c;才能在板子上运行。 这里总结下嵌入式linux环境下使用CMake&#xff0c;嵌入式QT的CMake工程模板配置及如何使用&#xff0c;分享给有需要的小伙伴&#xff0c;有用到的…
阅读更多...
【C++】---继承

【C++】---继承

【C】---继承 一、继承的概念及定义1、继承的概念2、定义语法格式3、继承基类成员访问方式的变化 二、基类 和 派生类 的对象之间的赋值转换1、赋值规则2、切片&#xff08;1&#xff09;子类对象 赋值 给 父类对象&#xff08;2&#xff09;子类对象 赋值 给 父类指针&#xf…
阅读更多...
数据结构-线性表-链表-2.3-1

数据结构-线性表-链表-2.3-1

设计一个递归算法&#xff0c;删除不带头结点的单链表L中所有值为x的结点。 void del(Linkllist &L&#xff0c;int x){LNode *p;if(LNULL){return;}if(L->datax){pL;LL->next;;free(p);del(L,x);}else{del(L->next,x);} } 时间复杂度为O(n)
阅读更多...
【项目学习01_2024.05.08_Day06】

【项目学习01_2024.05.08_Day06】

学习笔记 5 新增课程5.1 需求分析5.1.1 业务流程5.1.2 数据模型 5.2 接口定义5.3 接口开发5.3.1 保存课程基本信息5.3.2 保存营销信息 5.4 接口测试 5 新增课程 5.1 需求分析 5.1.1 业务流程 5.1.2 数据模型 5.2 接口定义 5.3 接口开发 根据需求分析&#xff0c;新增课程表…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023