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

【数据结构】_顺序表

目录

1. 概念与结构

1.1 静态顺序表

1.2 动态顺序表

2. 动态顺序表实现

2.1 SeqList.h

2.2 SeqList.c

2.3 Test_SeqList.c

3. 顺序表性能分析


线性表是n个具有相同特性的数据元素的有限序列。

常见的线性表有:顺序表、链表、栈、队列、字符串等;

线性表在逻辑上是连续的线性结构,在物理结构上并不一定是连续的

线性表在物理上存储时,通常以数组和链式结构的形式存储,分别称之为顺序表和链表。

本文介绍顺序表。

1. 概念与结构

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

要求数据必须从第一个位置开始连续存放;

顺序表在逻辑上是连续的,在物理上也是连续的

1.1 静态顺序表

#define N 100
typedef int SLDataType;
// 静态顺序表
typedef struct SeqList{SLDataType arr[N]; // 定长数组size_t size;  // 有效数据个数
}SeqList;

在定义时使用定长数组,会造成数组大小若太小则导致不够用,数组若太大则导致空间浪费; 

1.2 动态顺序表

#define N 100
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList {SLDataType* arr;size_t size;    // 有效数据个数size_t capacity;  // 空间大小
}SeqList;

在定义时仅给定数组首元素地址,并且基于size和capacity实现动态增容,相较而言更灵活。

注:1、通常会将顺序表的结构体命名为struct SeqList,即Sequence List;

2、建议目录结构:(注意自定义头文件的包含)

.h头文件:顺序表结构、声明顺序表的方法

.c/.cpp源文件:实现顺序表的方法+测试

3、为便于修改程序,通常会将顺序表结构体中的数据类型进行重命名,可命名为SLDataType;

      为便于编写程序,通常也会对顺序表结构体进行重命名,可重命名为SeqList或SL;

2. 动态顺序表实现

2.1 SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;int size;   // 有效数据个数int capacity;  // 空间大小
}SL;
// 空间检查
void SLCheckCapacity(SL* psl);
// 打印
void SLPrint(SL* psl);
// 初始化
void SLInit(SL* psl);
// 销毁
void SLDestory(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);
// 查找
int SLFind(SL* psl, SLDataType x);
// 修改
void SLModify(SL* psl, int pos, SLDataType x);

2.2 SeqList.c

#include "SeqList.h"
// 初始化
void SLInit(SL* psl) {psl->arr = NULL;psl->size = psl->capacity = 0;
}
// 销毁
void SLDestory(SL* psl) {if (psl->arr) {free(psl->arr);}psl->arr = NULL;psl->size = psl->capacity = 0;
}
// 打印
void SLPrint(SL* psl) {assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->arr[i]);}printf("\n");
}
// 空间检查
void SLCheckCapacity(SL* psl) {if (psl->capacity == psl->size) {// 常以2倍增容int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(psl->arr, newCapacity*sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail\n");exit(1);}psl->arr = tmp;psl->capacity = newCapacity;}
}
// 尾插
void SLPushBack(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);// 写法1/*psl->arr[psl->size] = x;psl->size++;*/// 写法2psl->arr[psl->size++] = x;
}
// 头插
void SLPushFront(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);int count = psl->size;// 写法一while (count) {psl->arr[count] = psl->arr[count-1];count--;}// 写法二//for (int i = psl->size; i > 0; i--) {//	psl->arr[i] = psl->arr[i - 1];//}psl->arr[0] = x;psl->size++;
}
// 尾删
void SLPopBack(SL* psl) {assert(psl);assert(psl->size);psl->size--;
}
// 头删
void SLPopFront(SL* psl) {assert(psl);assert(psl->size);for (int i = 0; i < psl->size - 1; i++) {psl->arr[i] = psl->arr[i+1];}psl->size--;
}
// 指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos>=0 && pos<psl->size);SLCheckCapacity(psl);for (int i = psl->size; i >psl->size - pos;i--) {psl->arr[i] = psl->arr[i-1];}psl->arr[pos] = x;psl->size++;
}
// 指定位置删除
void SLErase(SL* psl, int pos) {assert(psl);assert(pos >= 0 && pos < psl->size);for (int i = pos; i < psl->size - 1; i++) {psl->arr[i] = psl->arr[i + 1];}psl->size--;
}
// 查找
int SLFind(SL* psl, SLDataType x) {assert(psl);for (int i = 0; i < psl->size; i++) {if (psl->arr[i] == x)return i;}return -1;
}
// 修改
void SLModify(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos >= 0 && pos < psl->size);psl->arr[pos] = x;
}

2.3 Test_SeqList.c

#include"SeqList.h"
int main() {SL sl1;SLInit(&sl1);printf("Test SLPushBack:PushBack5~10:\n");SLPushBack(&sl1, 5);SLPushBack(&sl1, 6);SLPushBack(&sl1, 7);SLPushBack(&sl1, 8);SLPushBack(&sl1, 9);SLPushBack(&sl1, 10);SLPrint(&sl1);printf("TestPushFront:PushFront 4~2:\n");SLPushFront(&sl1, 4);SLPushFront(&sl1, 3);SLPushFront(&sl1, 2);SLPrint(&sl1);printf("TestPopBack:PopBack 10:\n");SLPopBack(&sl1);SLPrint(&sl1);printf("TestPopFront:PopFront 2:\n");SLPopFront(&sl1);SLPrint(&sl1);printf("TestInsert:Insert arr[4]=99:\n");SLInsert(&sl1, 4, 99);SLPrint(&sl1);printf("TestErase:Erase arr[3]:\n");SLErase(&sl1, 3);SLPrint(&sl1);printf("TestFind: Find 99:\n");int retIndex = SLFind(&sl1, 99);printf("The index of 99 is: %d\n", retIndex);printf("TestModify:Modify 99 to 100:\n");SLModify(&sl1, 3, 100);SLPrint(&sl1);SLDestory(&sl1);
}

测试用例运行结果:

注:1、关于初始化与扩容问题:(方法多样,逻辑完整即可)

上文示例为SLInit使得psl->capacity初值为0,从而在SLCheckCapacity中对于0容量的扩容不能采取一概而论的二倍扩容法,上例使用三目操作符:?使得capacity被赋值为4。

也可在SLInit中就对capacity赋予一个初值,但对应的psl->arr就不可再赋值为NUL了,也需对应malloc相应大小的空间;

2、注意指定位置插入SLInsert与指定位置删除SLErase对pos参数的判定区别:

对于SLInsert,pos可取值size,即实现尾插效果;

对于SLErase,pos不可取值size,arr[psl->size]实际是数组arr最后一个有效数据的下一个位置;

3. 顺序表性能分析

优点:物理空间连续:便于利用下标随机访问

缺点:(1)空间不够需扩容。

① 需要申请新的空间,拷贝数据,释放旧空间,有一定性能消耗;

② 一般增容呈2倍增长,存在空间浪费;

(2)头部或者中间位置的插入删除时涉及数据的移动,时间复杂度为O(N),效率低下

注:越界是不一定报错的,系统对于越界的检查是设岗抽查,以VS为例:

    int a[10];a[10] = 1;a[11] = 1;

当我们运行如上代码,系统会报错:

再运行下文代码:

    int a[10];a[12] = 1;a[13] = 1;

系统不会报错。说明系统只重点检查部分位置的越界情况。

相关文章:

【数据结构】_顺序表

目录 1. 概念与结构 1.1 静态顺序表 1.2 动态顺序表 2. 动态顺序表实现 2.1 SeqList.h 2.2 SeqList.c 2.3 Test_SeqList.c 3. 顺序表性能分析 线性表是n个具有相同特性的数据元素的有限序列。 常见的线性表有&#xff1a;顺序表、链表、栈、队列、字符串等&#xff1b…...

[MySQL]数据库表内容的增删查改操作大全

目录 一、增加表数据 1.全列插入与指定列插入 2.多行数据插入 3.更新与替换插入 二、查看表数据 1.全列查询与指定列查询 2.查询表达式字段 3.为查询结果起别名 4.结果去重 5.WHERE条件 6.结果排序 7.筛选分页结果 8.插入查询的结果 9.group by子句 三、修改表数…...

解决双系统引导问题:Ubuntu 启动时不显示 Windows 选项的处理方法

方法 1&#xff1a;检查 GRUB 引导菜单是否隐藏 启动进入 Ubuntu 系统。打开终端&#xff0c;输入以下命令编辑 GRUB 配置文件&#xff1a;sudo nano /etc/default/grub检查以下配置项&#xff1a; GRUB_TIMEOUT0&#xff1a;如果是 0&#xff0c;将其改为一个较大的值&#x…...

Java面试题2025-Spring

讲师&#xff1a;邓澎波 Spring面试专题 1.Spring应该很熟悉吧&#xff1f;来介绍下你的Spring的理解 1.1 Spring的发展历程 先介绍Spring是怎么来的&#xff0c;发展中有哪些核心的节点&#xff0c;当前的最新版本是什么等 通过上图可以比较清晰的看到Spring的各个时间版本对…...

CentOS7安装使用containerd

一&#xff0c;安装 1.1、安装containerd 下载 https://github.com/containerd/containerd/releases/download/v1.7.24/cri-containerd-cni-1.7.24-linux-amd64.tar.gz wget https://github.com/containerd/containerd/releases/download/v1.7.24/cri-containerd-cni-1.7.24-…...

Redis 集群模式入门

Redis 集群模式入门 一、简介 Redis 有三种集群模式&#xff1a;主从模式、Sentinel 哨兵模式、cluster 分片模式 主从复制&#xff08;Master-Slave Replication&#xff09;: 在这种模式下&#xff0c;数据可以从一个 Redis 实例&#xff08;主节点 Master&#xff09;复…...

WinDBG查找C++句柄泄露

C代码&#xff08;频繁点击About按钮导致Mutex句柄泄露&#xff09; HANDLE _mutexHandle;LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam) {switch (message){case WM_COMMAND:{int wmId LOWORD(wParam);// 分析菜单选择:switch (wmId){c…...

Linux查看服务器的内外网地址

目录&#xff1a; 1、内网地址2、外网地址3、ping时显示地址与真实不一致 1、内网地址 ifconfig2、外网地址 curl ifconfig.me3、ping时显示地址与真实不一致 原因是dns缓存导致的&#xff0c;ping这种方法也是不准确的&#xff0c;有弊端不建议使用&#xff0c;只适用于测试…...

深入MapReduce——引入

引入 前面我们已经深入了HDFS的设计与实现&#xff0c;对于分布式系统也有了不错的理解。 但HDFS仅仅解决了海量数据存储和读写的问题。要想让数据产生价值&#xff0c;一定是需要从数据中挖掘出价值才行&#xff0c;这就需要我们拥有海量数据的计算处理能力。 下面我们还是…...

Oracle之开窗函数使用

Oracle中的开窗函数&#xff08;Window Functions&#xff09;是一种强大的工具&#xff0c;用于在SQL查询中对数据进行复杂的分析和聚合操作&#xff0c;而无需改变原始查询结果的行数或顺序。以下是关于Oracle开窗函数的使用方法和常见示例&#xff1a; 1. 开窗函数的基本语法…...

航空客户价值的数据挖掘与分析(numpy+pandas+matplotlib+scikit-learn)

文章目录 航空客户价值的数据挖掘与分析(numpy+pandas+matplotlib+scikit-learn)写在前面背景与挖掘目标1.1 需求背景1.2 挖掘目标1.3 项目概述项目分析方法规划2.1 RFM模型2.2 LRFMC模型指标2.3 分析总体流程图数据抽取探索及预处理3.1 数据抽取3.2 数据探索分析3.3 数据预处…...

云原生时代,如何构建高效分布式监控系统

文章目录 一.监控现状二.Thanos原理分析SidecarQuerierStoreCompactor 三.Sidecar or ReceiverThanos Receiver工作原理 四.分布式运维架构 一.监控现状 Prometheus是CNCF基金会管理的一个开源监控项目&#xff0c;由于其良好的架构设计和完善的生态&#xff0c;迅速成为了监控…...

什么是CIDR技术? 它是如何解决路由缩放问题的

什么是CIDR技术&#xff1f; 它是如何解决路由缩放问题的 一. 什么是 CIDR&#xff1f;二. CIDR 是如何工作的&#xff1f;1. 高效地址分配2. 路由聚合&#xff08;Route Aggregation&#xff09;3. 精确满足需求 三. CIDR 的计算详解1. 子网掩码计算2. 地址范围计算3. 可用 IP…...

Unity URP 获取/设置 Light-Indirect Multiplier

Unity URP 获取/设置 Light-Indirect Multiplier 他喵的代码的字段名称叫&#xff1a;bounceIntensity ~~~~~~...

用Python和Tkinter标准模块建立密码管理器

用Python和Tkinter标准模块建立密码管理器 创建一个简单的密码管理器应用程序&#xff0c;帮助用户存储和管理他们的密码。使用Python的tkinter模块来创建一个图形用户界面&#xff08;GUI&#xff09;。 本程序支持 添加、查看、搜索、复制、修改、删除 功能。 本程序使用 …...

PyQt5菜单加多页签实现

pyqt tabs标签_哔哩哔哩_bilibili 代码实现 # coding:utf-8 import sys from PyQt5.QtCore import Qt from PyQt5 import QtCore,QtWidgets from PyQt5.QtWidgets import QApplication,QWidget from QhTabs01 import Ui_Form from PyQt5.Qt import *class QhLiangHuaGUI(QWidg…...

关注搜索引擎蜘蛛压力

以前在建站的时候&#xff0c;他们说蜘蛛来抓取的频率越多越好&#xff0c;因为蜘蛛来抓取说明了网站更新速度快&#xff0c;受搜索引擎的欢迎&#xff0c;但是在最近的网站统计中&#xff0c;发现很多蜘蛛爬取的频次非常的高&#xff0c;比如有的蜘蛛一天能来网站几万次&#…...

Python3 OS模块中的文件/目录方法说明三

一. 简介 前面文章简单学习了Python3中 OS模块中的文件/目录的部分函数。 本文继续来学习 OS模块中文件、目录的操作方法&#xff1a;os.fdopen()方法、os.fpathconf() 方法、os.fstat() 方法、os.fstatvfs() 方法。 二. Python3 OS模块中的文件/目录方法说明三 1. os.fdop…...

2024年终总结:技术成长与突破之路

文章目录 前言一、技术成长&#xff1a;菜鸟成长之路1. 学习与实践的结合2. 技术分享与社区交流 二、生活与事业的平衡&#xff1a;技术之外的思考1. 时间管理与效率提升2. 技术对生活的积极影响 三、突破与展望&#xff1a;未来之路1. 技术领域的突破2. 未来规划与目标 四、结…...

mysql-06.JDBC

目录 什么是JDBC: 为啥存在JDBC: JDBC工作原理&#xff1a; JDBC的优势&#xff1a; 下载mysql驱动包&#xff1a; 用java程序操作数据库 1.创建dataSource: 2.与服务端建立连接 3.构造sql语句 4.执行sql 5.关闭连接&#xff0c;释放资源 参考代码&#xff1a; 插…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...