【初阶数据结构】2.顺序表

文章目录

  • 1.线性表
  • 2.顺序表
    • 2.1 概念与结构
    • 2.2 分类
      • 2.2.1 静态顺序表
      • 2.2.2 动态顺序表
    • 2.3 动态顺序表的实现
    • 2.4 顺序表算法题
      • 2.4.1 移除元素
      • 2.4.2 删除有序数组中的重复项
      • 2.4.3 合并两个有序数组
    • 2.5 顺序表问题与思考

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

逻辑上：线性

物理上：不一定线性

2.顺序表

逻辑上：线性

物理上：线性（因为底层是数组）

2.1 概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

在这里插入图片描述

顺序表和数组的区别？

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

在这里插入图片描述

2.2 分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

//定义前知道数组的大小
int arr[3] = { 1,2,3 };

struct SeqList {
	int arr[1000];//定长数组
	int size;//记录当前顺序表中有效数据的个数

};

2.2.2 动态顺序表

//定义前不知道数组的大小------动态内存管理
int* arr1;

struct SeqList {
	int* arr;
	int capacity;//顺序表空间大小
	int size;//记录当前顺序表中有效数据的个数
};

2.3 动态顺序表的实现

尾插：

  1. 空间充足：将数据插入到size指向的位置，size++

    在这里插入图片描述

  2. 空间不足：先增容，再插入在这里插入图片描述

头插：

原数据依次往后移动一位，然后把数据插到第一位

增容：

  1. 连续空间足够，直接增容

  2. 连续空间不够：

    1）：重新找一块地址，分配足够的内存

    2）：拷贝数据到新的地址

    3）：销毁旧地址

增容一般是成倍数的增加，比如2->4->8->16

为什么不一个一个增加呢?

因为增容的操作本身就有一定的程序性能的消耗，若频繁的增容会导致程序效率低下。

SeqList.h

#pragma once
#include <stdio.h>
//定义顺序表结构，声明要提供的操作

//定义动态顺序表结构
typedef int SLDatatype;

typedef struct SeqList {
	SLDatatype* arr;
	int capacity;//空间大小
	int size;//有效数据大小
}SL;

//typedef struct SeqList SL;//两种方式都可以


//顺序表的初始化
void SLInit(SL* ps);

//顺序表的销毁操作
void SLDestory(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, SLDatatype x, int pos);
//删除指定位置的数据
void SLErase(SL* ps, int pos);

//顺序表的查找
int SLFind(SL* ps, SLDatatype x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "SeqList.h"

//具体实现各种操作

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

//销毁
void SLDestory(SL* ps) {
	if (ps->arr)//相当于ps->arr!=NULL
	{
		free(ps->arr);
	}
	ps->arr == NULL;
	ps->size = ps->capacity = 0;
}

void SLCheckCapcity(SL* ps) {
	//判断空间是否充足
	if (ps->size == ps->capacity) {
		//增容
		//若capacity为0，给个默认值，否则乘2倍
		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;
	}
}

//插入数据
//尾插
//时间复杂度O(1)
void SLPushBack(SL* ps, SLDatatype x) {
	温柔的解决方式
	//if (ps == NULL) {
	//	return;
	//}

	//粗暴的解决方式
	assert(ps);//等价于assert(ps!=NULL)
	//判断空间是否充足
	SLCheckCapcity(ps);
	ps->arr[ps->size++] = x;//x插到最后
}
//头插
//时间复杂度O(n)
//原数据依次往后移动一位，然后把数据插到第一位
void SLPushFront(SL* ps, SLDatatype x) {
	assert(ps);
	//判断空间是否足够
	SLCheckCapcity(ps);

	//数据整体后移一位
	for (int i = ps->size; i > 0; i--) {
		ps->arr[i] = ps->arr[i - 1];
	}
	//下标为0的位置空出来了
	ps->arr[0] = x;//x插到最前面

	ps->size++;//增加了一个数据，size要加1个空间
	//之所以不在之前++,是因为size指的是有效数据大小，例如size=3，那么就有3个元素arr[0]~arr[size-1]，假设arr里面放了1 2 3，要插入4
	// 后来我们使用arr[0]~arr[size]，一共4个元素，刚好四个元素，四个位置。4 1 2 3
	//那为什么要++呢？如果按照上面的例子，size一开始是指向第3个元素末尾的位置，也就是说原来没有arr[size]，只有arr[size-1]里面存的是3
	// 因为挪动元素，原来的第3个元素到了后面一个位置。arr[size]里面存的就是3了
	// size指向的位置不变，我们通过size++来使得size重新指向第4个元素末尾的位置，防止后续调用元素产生误判，误以为还是只有arr[0]~arr[size-1]个元素
}

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

//删除
//尾删
//时间复杂度O(1)
void SLPopBack(SL* ps) {
	assert(ps);
	assert(ps->size);//顺序表为空不可以删
	
	//ps->arr[ps->size - 1] = -1;//多余了
	ps->size--;//少了一个元素自然size--

}

//头删
//时间复杂度O(n)
//将第一个数据往后的数据整体往前挪一位
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--;//少了一个元素自然size--
}

//指定位置之前插入数据(空间足够才能直接插入数据）
void SLInsert(SL* ps, SLDatatype x, int pos) {//x是插入的数据，pos是插入的位置
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//前半部分头插，后半部分尾插
	//首先pos肯定是在0~size之间的，pos=0的时候，就相当于头插，pos=size的时候，就相当于尾插

	//检查空间够不够
	SLCheckCapcity(ps);

	//pos及之后的数据整体向后移动一位
	for (int i = ps->size; i > pos; i--) {
		ps->arr[i] = ps->arr[i - 1];

	}
	ps->arr[pos] = x;//插入x
	ps->size++;//多了一个元素自然size++
}

//删除指定位置的数据
void SLErase(SL* ps, int pos) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//前半部分头删，后半部分尾删
	//首先pos肯定是在0~size之间的，pos=0的时候，就相当于头删，pos=size的时候，就相当于尾删

	for (int i = pos; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];

	}
	ps->size--;//少了一个元素自然size--
}

//顺序表的查找
int SLFind(SL* ps, SLDatatype x) {
	assert(ps);
	for (int i = 0; i < ps->size; i++) {
		if (ps->arr[i] == x) {
			return i;
		}
	}
	//没有找到返回一个无效的下标
	return -1;
}

test.c

//测试程序
#include "SeqList.h"

void SLtest01() {
	SL s;
	SLInit(&s);

	//尾插
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	
	//SLPushBack(NULL, 1);//不行，会报错

	//头插
	/*SLPushFront(&s, 1);
	SLPushFront(&s, 2);
	SLPushFront(&s, 3);
	SLPushFront(&s, 4);

	SLPrint(&s);*/

	//SLPopBack(&s);//尾删
	//SLPopFront(&s);//头删

	//SLInsert(&s, 11, 0);//指定位置插入
	//SLPrint(&s);
	//SLInsert(&s, 22, s.size);//指定位置插入
	/*SLPrint(&s);*/

	/*SLPrint(&s);*/

	//SLErase(&s, 0);//指定位置删除
	//SLPrint(&s);
	//SLErase(&s, s.size-1);//指定位置删除
	//SLPrint(&s);

	SLPrint(&s);
	int find = SLFind(&s, 222);
	if (find < 0) {
		printf("没有找到！\n");
	}
	else {
		printf("找到了！\n");
	}
	
	SLDestory(&s);
}

int main() {
	SLtest01();
	return 0;
}

编写代码过程中要勤测试，避免写出大量代码后再测试而导致出现问题，问题定位无从下手。

2.4 顺序表算法题

2.4.1 移除元素

在这里插入图片描述

思路：定义两个变量指向数组第一个位置，判断nums[src]是否等于val

  1. 相等，src++
  2. 不相等，nums[dst] = nums[src],src++,dst++

在这里插入图片描述

int removeElement(int* nums, int numsSize, int val) {
    int src = 0,dst = 0;
    while(src < numsSize){
        if(nums[src] == val){
            src++;
        }
        else{
            nums[dst] = nums[src];
            dst++;
            src++;
        }
    }
    //此时dst指向的位置就是要返回的有效个数
    return dst;
}

2.4.2 删除有序数组中的重复项

在这里插入图片描述

思路：定义两个指针变量。dst指向数组第一个位置，src指向数组第二个位置。判断nums[dst]是否等于nums[src]

  1. 相等，src++
  2. 不相等，dst++,nums[dst] = nums[src],src++

在这里插入图片描述

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

2.4.3 合并两个有序数组

在这里插入图片描述

思路：定义三个指针变量。L1指向nums1数组第一个位置，L2指向nums2数组第一个位置,L3指向nums1数组最后一个位置。

比较L1和L2位置的数据，谁大，谁就往L3位置放数据。

结束条件：要么L1<0，要么L2<0

  1. L1<0：要处理nums2中的数据，循环放到nums1中
  2. L2<0：不需要处理，因为nums2中的数据已经有序的放到nums1中了。

在这里插入图片描述

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
	int L1 = m - 1;
	int L2 = n - 1;
	int L3 = m + n - 1;

	//L1>=0 L2>=0
	while (L1 >= 0 && L2 >= 0) {
		if (nums1[L1] > nums2[L2]) {
			nums1[L3--] = nums1[L1--];
		}
		else {
			//L2> = L1
			nums1[L3--] = nums2[L2--];
		}
	}
	//跳出while循环有两种情况：要么L1<0（需要处理），要么L2<0（不需要处理）
	while (L2 >= 0) {
		nums1[L3--] = nums2[L2--];
	}
}

2.5 顺序表问题与思考

  • 中间/头部的插入删除，时间复杂度为O(N)

  • 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

  • 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们 再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

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

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

相关文章

JavaFx+MySql学生管理系统

JavaFx+MySql学生管理系统

前言: 上个月学习了javafx和mysql数据库,于是写了一个学生管理系统,因为上个月在复习并且有一些事情,比较忙,所以没有更新博客了,这个项目页面虽然看着有点简陋了,但是大致内容还是比较简单的,于是现在跟大家分享一下我的学生管理系统,希望对这方面有兴趣的同学提供一些帮助 &a…
阅读更多...
19185 01背包问题

19185 01背包问题

解决这个问题的关键是使用动态规划的方法。我们可以创建一个二维数组dp[i][j]&#xff0c;其中i表示考虑前i件物品&#xff0c;j表示背包的容量。dp[i][j]的值表示在考虑前i件物品&#xff0c;且背包容量为j时能获得的最大价值。 ### 算法步骤 1. 初始化一个二维数组dp&#x…
阅读更多...
Qt常用基础控件总结—容器部件(QGroupBox类)

Qt常用基础控件总结—容器部件(QGroupBox类)

五、容器部件 按钮框控件QDialogButtonBox 类（很少用） 按钮组控件QButtonGroup 类（很少用） 组框控件QGroupBox 类 QGroupBox 类介绍 QGroupBox(组框)，直接继承自 QWidget 类，因此使用该类创建的对象，可作为窗口使用，组框在外观上是可见的。 QGroupBox 类(组框)，…
阅读更多...
数据平滑处理（部分）

数据平滑处理（部分）

一、 移动平均&#xff08;Moving Average&#xff09; 是一种最简单的数据平滑方法&#xff0c;用于平滑时间序列数据。它通过计算一定窗口内数据点的平均值来减少噪音&#xff0c;同时保留数据的趋势。移动平均包括简单移动平均&#xff08;SMA&#xff09;或指数加权移动平均…
阅读更多...
【爬虫】爬虫基础

【爬虫】爬虫基础

目录 一、Http响应与请求1、Http请求2、Http响应3、状态码 二、Requests库1、发起GET请求2、发起POST请求3、处理请求头 三、BeautifulSoup库1、解析HTML文档2、查找和提取数据Ⅰ、查找单个元素Ⅱ、查找所有元素Ⅲ、使用CSS选择器Ⅳ、获取元素属性 四、爬取豆瓣电影榜 一、Http…
阅读更多...
YOLOv10训练自己的数据集（交通标志检测）

YOLOv10训练自己的数据集（交通标志检测）

YOLOv10训练自己的数据集&#xff08;交通标志检测&#xff09; 前言相关介绍前提条件实验环境安装环境项目地址LinuxWindows 使用YOLOv10训练自己的数据集进行交通标志检测准备数据进行训练进行预测进行验证 参考文献 前言 由于本人水平有限&#xff0c;难免出现错漏&#xff…
阅读更多...
【Linux】日志

【Linux】日志

日志是记录软件运行过程中发生的事件的一种手段&#xff0c;通常包含以下内容&#xff1a; 时间戳&#xff1a;记录日志条目创建的确切时间。这对于追踪事件发生的时间顺序至关重要。日志级别&#xff1a;表示日志信息的严重性或重要性&#xff0c;常见的级别包括 DEBUG、INFO…
阅读更多...
RisingWave 用例：流式 ETL、实时分析、事件驱动应用

RisingWave 用例：流式 ETL、实时分析、事件驱动应用

RisingWave 非常适合以下类别的用例。 流式 ETL实时分析事件驱动应用 流式 ETL 是实时分析和事件驱动应用的基础。实时分析通过引入数据看板&#xff0c;扩展了流式 ETL&#xff0c;而事件驱动应用则在实时分析的基础上增加了逻辑&#xff0c;以评估条件是否触发后续行动。 …
阅读更多...
【测开能力提升-fastapi框架】fastapi模版引擎简单使用

【测开能力提升-fastapi框架】fastapi模版引擎简单使用

1.6 通过模版引擎返回HTM页面 import uvicorn from fastapi import FastAPI, Request from fastapi.templating import Jinja2Templatesapp FastAPI()# 初始化模版引擎存放位置 templates Jinja2Templates(directory"templates")app.get("/") async def…
阅读更多...
2024年西安铁一中集训DAY1---- 杂题选讲

2024年西安铁一中集训DAY1---- 杂题选讲

文章目录 牛客练习赛125 E 联谊活动&#xff08;枚举&#xff0c;分讨&#xff09;牛客练习赛125 F 玻璃弹珠&#xff08;类莫队&#xff0c;离线询问&#xff0c;数据结构&#xff09;2024ccpc长春邀请赛 D Parallel Lines&#xff08;随机化&#xff09;2024ccpc长春邀请赛 E…
阅读更多...
分布式应用系统设计：即时消息系统

分布式应用系统设计：即时消息系统

即时消息(IM)系统&#xff0c;涉及&#xff1a;站内消息系统 组件如下&#xff1b; 客户端&#xff1a; WEB页面&#xff0c;IM桌面客户端。通过WebSocket 跟ChatService后端服务连接 Chat Service&#xff1a; 提供WebSocket接口&#xff0c;并保持跟“客户端”状态的维护。…
阅读更多...
彻底解决找不到d3dcompiler_43.dll问题，总结几种有效的方法

彻底解决找不到d3dcompiler_43.dll问题，总结几种有效的方法

运行软件时提示找不到d3dcompiler_43.dll无法继续执行代码&#xff0c;如何解决&#xff1f;解决这个问题的方法有很多&#xff0c;但具体问题需要具体分析&#xff0c;有些方法可能并不适用于解决d3dcompiler_43.dll的问题。因此&#xff0c;需要根据实际情况来选择合适的方法…
阅读更多...
8627 数独

8627 数独

为了判断数独解是否合法&#xff0c;我们需要遵循以下步骤&#xff1a; 1. **检查每一行**&#xff1a;确保1到9每个数字在每一行中只出现一次。 2. **检查每一列**&#xff1a;确保1到9每个数字在每一列中只出现一次。 3. **检查每个3x3的宫**&#xff1a;确保1到9每个数字在…
阅读更多...
模式物种葡萄基因组（T2T）--文献精读29

模式物种葡萄基因组（T2T）--文献精读29

The complete reference genome for grapevine (Vitis vinifera L.) genetics and breeding 葡萄&#xff08;Vitis vinifera L.&#xff09;遗传学和育种的完整参考基因组 摘要 葡萄是全球最具经济重要性的作物之一。然而&#xff0c;以往版本的葡萄参考基因组通常由成千上万…
阅读更多...
星辰考古：TiDB v4.0 进化前夜

星辰考古：TiDB v4.0 进化前夜

前情回顾TiDB v4 时间线TiDB v4 新特性 TiDBTiKVPDTiFlashTiCDCTiDB v4 兼容性变化 TiDBTiKVPD其他TiDB 社区互助升级活动TiDB 3.0.20 升级到 4.0.16 注意事项升级速览直观变化总结素材来源&#x1f33b; 往期精彩 ▼ 前情回顾 在前面的章节中&#xff0c;我们共同梳理了 TiDB …
阅读更多...
【刷题汇总 -- 最长回文子串、买卖股票的最好时机(一)、[NOIP2002 普及组] 过河卒】

【刷题汇总 -- 最长回文子串、买卖股票的最好时机(一)、[NOIP2002 普及组] 过河卒】

C日常刷题积累 今日刷题汇总 - day0101、最长回文子串1.1、题目1.2、思路1.3、程序实现 2、买卖股票的最好时机(一)2.1、题目2.2、思路2.3、程序实现2.4、程序实现 -- 优化 3、[NOIP2002 普及组] 过河卒3.1、题目3.2、思路3.3、程序实现 -- dp 4、题目链接 今日刷题汇总 - day0…
阅读更多...
一个便捷的web截图库~【送源码】

一个便捷的web截图库~【送源码】

随着时间的发展&#xff0c;前端开发的范围越来越广&#xff0c;能够实现的功能也越来越多&#xff0c;要实现的功能也五花八门&#xff0c;今天就给大家介绍一个web截图库,让前端也能实现截图功能—— js-web-screen-shot js-web-screen-shot js-web-screen-shot 是一个基于 …
阅读更多...
Linux服务器CPU占用率达到100%排查思路

Linux服务器CPU占用率达到100%排查思路

1、找到最耗CPU的进程pid&#xff0c;执行命令 top 2、找到最耗CPU的线程tid // 执行 top -Hp [pid] 定位应用进程对应的线程 tid // 按shift p 组合键&#xff0c;按照CPU占用率排序 > top -Hp 14246 3、将线程pid转化为16进制 // printf "%x\n" [tid] 将tid…
阅读更多...
Redis+Caffeine 实现两级缓存实战

Redis+Caffeine 实现两级缓存实战

RedisCaffeine 实现两级缓存 背景 ​ 事情的开始是这样的&#xff0c;前段时间接了个需求&#xff0c;给公司的商城官网提供一个查询预计送达时间的接口。接口很简单&#xff0c;根据请求传的城市仓库发货时间查询快递的预计送达时间。因为商城下单就会调用这个接口&#xff…
阅读更多...
camunda最终章-springboot

camunda最终章-springboot

1.实现并行流子流程 1.画图 2.创建实体 package com.jmj.camunda7test.subProcess.entity;import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;import java.io.Serializable; import java.util.ArrayList; import java.util.List;Data …
阅读更多...
最新文章

Copyright @ 2022~2023