顺序表的构造及功能
定义
顺序表是一种随机存储都结构,其特点是表中的元素的逻辑顺序与物理顺序相同。
假设线性表L存储起始位置为L(A),sizeof(ElemType)是每个数据元素所占的存储空间的大小,则线性表L所对应的顺序存储如下图。

顺序表的优缺点
优点:
随机存储表中的任意元素,其存储位置可以用一个简单、直观的公式来表示。
存储密度高,每个结点只存储数据元素。
缺点:
在做插入或删除元素时,需要移动大量元素。
操作相对复杂,必然导致空间的浪费。
静态顺序表的构建
在静态分配时,由于数组的大小和空间事先已经固定好,一旦空间占满,再加入新的数据就会产生溢出,进而导致进程崩溃。
#define MaxSize 100 //顺序表可能达到的最大长度
typedef int ElemType;
typedef struct{ElemType data[MaxSize]; //顺序表的元素int length; //当前的长度
}List; //顺序表的类型定义
注意:线性表中元素的位置是从1开始的,而数组中的元素的下标是从0开始的。
动态顺表的构建
#define MaxSize 100 //顺序表可能达到的最大长度
typedef int ElemType;
typedef struct{ElemType* data; //存储空间的基址int length; //当前的长度
}List; //顺序表的结构类型为List
C的初始动态分配语句
list.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize); //动态开辟空间 (c语言)
C++的初始动态分配语句
list.data = new ElemType[MaxSize]; //动态开辟空间 (c++)
注意:动态分配并不是链式存储,它同样属于顺序存储结构,,物理结构没有变化,依然是随机存储方式,只是分配的空间大小可以在运行时动态决定。
动态顺序表的常见操作
插入
插入新元素的图解

void Insert(List *list, int index, int value){ //插入(在第index位置插入value)if (index < 1 || index > list->length + 1){ //判断范围是否有效printf("插入失败(位置输入错误)!\n");return;}if (list->length >= MaxSize){ //空间已满,无法插入printf("插入失败(顺序表已满)!\n");return;}for (int i = list->length; i >= index; i--){ //将第index个元素及之后的元素后移list->data[i] = list->data[i - 1];}list->data[index - 1] = value; //将位置index放入valuelist->length++; //线性表长度加一printf("插入成功!\n");return;
}
线性表插入算法的平均时间复杂度为O(N)。
取值
根据下标来查找元素
void GetElem(List list, int index){ //取值(用下标找元素)if (index >= 0 && index < list.length){printf("要查找的第%d个元素是:%d\n", index, list.data[index - 1]);}else{printf("输入的值有误!!\n");}
}
查找
根据所给的元素来遍历顺序表来寻找
void LocateElem(List list, int value){ //查找(用值找下标)for (int i = 0; i < list.length; i++){if (value == list.data[i]){printf("%d是本表中的第%d元素\n", value, i + 1);return;}}printf("找不到该元素\n");return;
}
线性表按值查找算法的平均时间复杂度为O(N)。
删除
删除元素的图解

void Delete(List *list, int index){ //删除(删除指定的第几个元素)if (index < 1 || index > list->length) { //判断index的范围是否有效printf("删除失败(输入的数值有误)!\n");return;}for (int i = index - 1; i < list->length - 1; i++){ //将第index个位置后的元素前移list->data[i] = list->data[i + 1];}list->length--; //线性表长度减一printf("删除成功!\n");return;
}
线性表删除算法的平均时间复杂度为O(N)。
销毁
void Clear(List *list){ //销毁list->length = 0; //将顺序表的长度设为0free(list->data); //释放malloc申请的空间printf("顺序表已销毁!\n");
}
划分
已第一个元素为界,比它小的元素放在它的前面,比它大的元素放在它的后面
void ListSort(List *list){ //划分(已第一个元素为界,前面比它小,后面比它大)int i = 0, j = 0;int temp, k;temp = list->data[0];for (i = 1; i < list->length; i++){if (temp > list->data[i]){k = list->data[i];for (j = i; j > 0; j--){list->data[j] = list->data[j - 1];}list->data[0] = k;}}printf("划分成功!\n");return;
}
单值化
单值化类似与去掉顺序表中重复的元素
void DeleteSame(List *list){ //单值化(去掉重复的元素)int i = 0;while (i < list->length){for (int j = i + 1; j <= list->length; j++)while (list->data[i] == list->data[j]){for (int k = j; k <= list->length; k++)list->data[k] = list->data[k + 1];list->length--;}i++;}printf("单值化完成!\n");return;
}
源码
SeqList.h
#include <stdio.h>
#include <windows.h>
#include <malloc.h>#define MaxSize 100
typedef int ElemType;
typedef struct{ElemType* data; //动态顺序表int length;
}List;void menu();
void PutList();
void GetElem();
void LocateElem();
void Insert();
void Delete();
void DeleteSame();
void ListSort();
void Clear();
SeqList.c
#include "SeqList.h"void PutList(List list){ //输出(遍历线性表)for (int i = 0; i < list.length; i++){printf("%d ", list.data[i]);}printf("\n");
}void GetElem(List list, int index){ //取值(用下标找元素)if (index >= 0 && index < list.length){printf("要查找的第%d个元素是:%d\n", index, list.data[index - 1]);}else{printf("输入的值有误!!\n");}
}void LocateElem(List list, int value){ //查找(用值找下标)for (int i = 0; i < list.length; i++){if (value == list.data[i]){printf("%d是本表中的第%d元素\n", value, i + 1);return;}}printf("找不到该元素\n");return;
}void Insert(List *list, int index, int value){ //插入(在第index位置插入value)if (index < 1 || index > list->length + 1){printf("插入失败(位置输入错误)!\n");return;}if (list->length >= MaxSize){printf("插入失败(顺序表已满)!\n");return;}for (int i = list->length; i >= index; i--){list->data[i] = list->data[i - 1];}list->data[index - 1] = value;list->length++;printf("插入成功!\n");return;
}void Delete(List *list, int index){ //删除(删除指定的第几个元素)if (index < 1 || index > list->length) {printf("删除失败(输入的数值有误)!\n");return;}for (int i = index - 1; i < list->length - 1; i++){list->data[i] = list->data[i + 1];}list->length--;printf("删除成功!\n");return;
}void DeleteSame(List *list){ //单值化(去掉重复的元素)int i = 0;while (i < list->length){for (int j = i + 1; j <= list->length; j++)while (list->data[i] == list->data[j]){for (int k = j; k <= list->length; k++)list->data[k] = list->data[k + 1];list->length--;}i++;}printf("单值化完成!\n");return;
}void ListSort(List *list){ //划分(已第一个元素为界,前面比它小,后面比它大)int i = 0, j = 0;int temp, k;temp = list->data[0];for (i = 1; i < list->length; i++){if (temp > list->data[i]){k = list->data[i];for (j = i; j > 0; j--){list->data[j] = list->data[j - 1];}list->data[0] = k;}}printf("划分成功!\n");return;}void Clear(List *list){ //销毁list->length = 0;free(list->data);printf("顺序表已销毁!\n");
}void menu(){ //菜单printf("顺序表操作:< P-输出 G-取值 L-查找 I-插入 D-删除 S-单值化 F-划分 X-销毁 Q-退出 >\n");
}
Test.c
#include "SeqList.h"int main(){List list;list.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize); //动态开辟空间 (c语言)//list.data = new ElemType[MaxSize]; //动态开辟空间 (c++)printf("线性表中元素的个数:");int n = 0;scanf("%d", &n);list.length = n;printf("请输入元素:");for (int i = 0; i < n; i++){int t = 0;//cin >> list.data[i]; //c++输入scanf("%d", &t);list.data[i] = t;}while (1){menu();char key;//cin >> key; //c++输入int t = 0;scanf("%c", &key);switch (key){case 'P':PutList(list); //输出break;case 'G':printf("要查找第几个元素:");scanf("%d", &t);GetElem(list,t); //取值break;case 'L':printf("要查找元素的值为:");scanf("%d", &t);LocateElem(list,t); //查找break;case 'I':printf("输入要插入的位置和数值:");int index, value;scanf("%d %d", &index,&value);Insert(&list, index, value); //插入break;case 'D':printf("输入要删除第几个元素:");scanf("%d", &t);Delete(&list, t); //删除break;case 'S':DeleteSame(&list); //单值化break;case 'F':ListSort(&list); //划分break;case 'X':Clear(&list); //销毁break;case 'Q':exit(0); //退出break;}}system("pause");
}
相关文章:

顺序表的构造及功能
定义顺序表是一种随机存储都结构,其特点是表中的元素的逻辑顺序与物理顺序相同。假设线性表L存储起始位置为L(A),sizeof(ElemType)是每个数据元素所占的存储空间的大小,则线性表L所对应的顺序存储如下图。顺序表的优缺点优点:随机…...

cesium: 绘制线段(008)
第008个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中绘制线段,左键点击开始绘制,右键点击取消绘制 直接复制下面的 vue+cesium源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共139行)相关API参考:专栏目标示例效果 配置方式 1)…...

HTML、CSS学习笔记4(3D转换、动画)
目录 一、空间转换(3D转换) 1.空间位移 语法: 取值:(正负均可) 透视: 2.空间旋转 3.立体呈现 二、动画(animation) 1.动画的使用 先定义动画 再调用定义好的动画 …...
java的分布式锁
什么是分布式锁 分布式锁是指分布式环境下,系统部署在多个机器中,实现多进程分布式互斥的一种锁。为了保证多个进程能看到锁,锁被存在公共存储(比如 Redis、Memcache、数据库等三方存储中),以实现多个进程并…...

17- TensorFlow实现手写数字识别 (tensorflow系列) (项目十七)
项目要点 模型创建: model Sequential()添加卷积层: model.add(Dense(32, activationrelu, input_dim100)) # 第一层需要 input_dim添加dropout: model.add(Dropout(0.2))添加第二次网络: model.add(Dense(512, activationrelu)) # 除了first, 其他层不要输入shape添加输出…...

Polkadot 基础
Polkadot Polkadot联合并保护了一个不断增长的专业区块链生态系统,称为parachains。Polkadot上的应用程序和服务可以安全地跨链通信,形成真正可互操作的去中心化网络的基础。 真正的互操作性 Polkadot支持跨区块链传输任何类型的数据或资产,…...

spring源码编译
spring源码编译1、安装gradle2、拉取源码3、配置gradle文件来源及镜像仓库4、预编译5、验证6、可能遇到的报错6.1、jdk.jfr不存在6.2、checkstyleMain6.3、org.gradle.api.artifacts.result.ComponentSelectionReason.getDescription()Ljava/lang/String6.4、其他jdk࿱…...
防盗链是什么?带你了解什么是防盗链
目录 什么是防盗链 防盗链的定义 防盗链的产生 防盗链的实现 什么是防盗链 防盗链其实就是采用服务器端编程,通过url过滤技术实现的防止盗链的软件。 比如:photo.abc.com/video.mp4 这个下载地址,如果没有装防盗链,别人就能轻…...

Linux基础命令-fdisk管理磁盘分区表
文章目录 fdisk 命令介绍 命令格式 基本参数 1)常用参数 2)fdisk菜单操作说明 创建一个磁盘分区 1)创建分区 2)创建交换分区 参考实例 1) 显示当前分区的信息 2) 显示每个磁盘的分区信息 命令…...

(四)K8S 安装 Nginx Ingress Controller
ingress-nginx 是 Kubernetes 的入口控制器,使用NGINX作为反向代理和负载均衡器 版本介绍 版本1:Ingress NGINX Controller(k8s社区的ingres-nginx) 以 NGINX 开源技术为基础(kubernetes.io),可在GitHub的 kubernet…...
高频面试题
MyISAM和InnoDB是MySQL两种常见的存储引擎,它们之间有以下几点区别: 事务支持:MyISAM不支持事务处理,而InnoDB支持事务处理。 行级锁:MyISAM只支持表级锁,而InnoDB支持行级锁,可以避免并发访问…...
js 字节数组操作,TCP协议组装
js字节数组,进制转换js基础知识数组 Array扩展操作符三个点(...)ArrayBufferslice() 数组复制reduce 对数组中的每个元素执行一个提供的函数,将其结果汇总为单个返回值splice 数组删除,添加,替换js 字节数组转数字以及…...
JavaScript的引入并执行-包含动态引入与静态引入
JavaScript的引入并执行-包含动态引入与静态引入 JavaScript引入方式 html文件需要引入JavaScript代码,才能在页面里使用JavaScript代码。 静态引入 行内式 直接在DOM标签上使用 <!DOCTYPE html> <html lang"en"> <head><meta ch…...

第四阶段01-酷鲨商城项目准备
1. 关于csmall-product项目 这是“酷鲨商城”大项目中的“商品管理”项目,是一个后台管理项目(给管理员,或运营人员使用的项目,并不是普通用户使用的),并且,只会涉及与发布商品可能相关的功能开…...

Uncaught ReferenceError: jQuery is not defined
今天在拉取项目部署到本地的时候遇到了一个问题特此记录一下 (以后闭坑) 我和同事同时拉取了一样的代码,结果同事的页面加载正常而我的页面像被狗啃了一样,知道是js的问题但是不知道问题出在哪里?后来还是同事帮我解决…...

面试阿里测开岗,被面试官针对,当场翻脸,把我的简历还给我,疑似被拉黑...
好家伙,金三银四一到,这奇葩事可真是多,前两天和粉丝聊天,他说前段时间面试阿里的测开岗,最后和面试官干起来了。 我问他为什么,他说没啥,就觉得面试官太装了,就爱问一些虚而不实的…...

2. 驱动开发--驱动开发环境搭建
文章目录前言一、Linux中配置编译环境1.1 linux下安装软件的方法1.2 交叉编译工具链的安装1.2.1 测试是否安装成功1.3 设置环境变量1.3.1 将工具链导出到环境变量1.4 为工具链创建arm-linux-xxx符号链接二、 搭建运行开发环境2.1 tftp网络方式加载内核和设备树文件2.2 nfs网络方…...

《数据库系统概论》学习笔记——第四章 数据库安全
教材为数据库系统概论第五版(王珊) 这一章简单记一下那几条sql的用法和两种存取控制和审计(今年期末考了)吧,不知道有啥好考的 数据库安全性 问题的提出 数据库的一大特点是数据可以共享数据共享必然带来数据库的安全…...

山洪径流过程模拟及洪水危险性评价
目录 1.洪水淹没危险性评价方法及技术讲解 2.GIS水文信息提取与分析(基于ArcGIS软件) 3.洪水淹没模拟水文分析:洪峰流量估算 4.洪水淹没模拟水力学分析:Hec-RAS实例操作 GIS水文分析(ArcHydro、Spatial Anlysist等模块)是流域…...

LeetCode HOT100 (23、32、33)
目录 23、合并K个升序链表 32、最长有效括号 33、搜索旋转排序数组 23、合并K个升序链表 思路:采用顺序合并的方法,用一个变量 ans 来维护以及合并的链表,第 i 次循i 个链表和 ans合并,答案保存到 ans中。 代码: …...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...