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

顺序表的构造及功能

定义

顺序表是一种随机存储都结构,其特点是表中的元素的逻辑顺序与物理顺序相同。

假设线性表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");
}

相关文章:

顺序表的构造及功能

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

cesium: 绘制线段(008)

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

HTML、CSS学习笔记4(3D转换、动画)

目录 一、空间转换&#xff08;3D转换&#xff09; 1.空间位移 语法&#xff1a; 取值&#xff1a;&#xff08;正负均可&#xff09; 透视&#xff1a; 2.空间旋转 3.立体呈现 二、动画&#xff08;animation&#xff09; 1.动画的使用 先定义动画 再调用定义好的动画 …...

java的分布式锁

什么是分布式锁 分布式锁是指分布式环境下&#xff0c;系统部署在多个机器中&#xff0c;实现多进程分布式互斥的一种锁。为了保证多个进程能看到锁&#xff0c;锁被存在公共存储&#xff08;比如 Redis、Memcache、数据库等三方存储中&#xff09;&#xff0c;以实现多个进程并…...

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

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&#xff1…...

防盗链是什么?带你了解什么是防盗链

目录 什么是防盗链 防盗链的定义 防盗链的产生 防盗链的实现 什么是防盗链 防盗链其实就是采用服务器端编程&#xff0c;通过url过滤技术实现的防止盗链的软件。 比如&#xff1a;photo.abc.com/video.mp4 这个下载地址&#xff0c;如果没有装防盗链&#xff0c;别人就能轻…...

Linux基础命令-fdisk管理磁盘分区表

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

(四)K8S 安装 Nginx Ingress Controller

ingress-nginx 是 Kubernetes 的入口控制器&#xff0c;使用NGINX作为反向代理和负载均衡器 版本介绍 版本1&#xff1a;Ingress NGINX Controller(k8s社区的ingres-nginx) 以 NGINX 开源技术为基础&#xff08;kubernetes.io&#xff09;&#xff0c;可在GitHub的 kubernet…...

高频面试题

MyISAM和InnoDB是MySQL两种常见的存储引擎&#xff0c;它们之间有以下几点区别&#xff1a; 事务支持&#xff1a;MyISAM不支持事务处理&#xff0c;而InnoDB支持事务处理。 行级锁&#xff1a;MyISAM只支持表级锁&#xff0c;而InnoDB支持行级锁&#xff0c;可以避免并发访问…...

js 字节数组操作,TCP协议组装

js字节数组&#xff0c;进制转换js基础知识数组 Array扩展操作符三个点&#xff08;...&#xff09;ArrayBufferslice() 数组复制reduce 对数组中的每个元素执行一个提供的函数,将其结果汇总为单个返回值splice 数组删除&#xff0c;添加&#xff0c;替换js 字节数组转数字以及…...

JavaScript的引入并执行-包含动态引入与静态引入

JavaScript的引入并执行-包含动态引入与静态引入 JavaScript引入方式 html文件需要引入JavaScript代码&#xff0c;才能在页面里使用JavaScript代码。 静态引入 行内式 直接在DOM标签上使用 <!DOCTYPE html> <html lang"en"> <head><meta ch…...

第四阶段01-酷鲨商城项目准备

1. 关于csmall-product项目 这是“酷鲨商城”大项目中的“商品管理”项目&#xff0c;是一个后台管理项目&#xff08;给管理员&#xff0c;或运营人员使用的项目&#xff0c;并不是普通用户使用的&#xff09;&#xff0c;并且&#xff0c;只会涉及与发布商品可能相关的功能开…...

Uncaught ReferenceError: jQuery is not defined

今天在拉取项目部署到本地的时候遇到了一个问题特此记录一下 &#xff08;以后闭坑&#xff09; 我和同事同时拉取了一样的代码&#xff0c;结果同事的页面加载正常而我的页面像被狗啃了一样&#xff0c;知道是js的问题但是不知道问题出在哪里&#xff1f;后来还是同事帮我解决…...

面试阿里测开岗,被面试官针对,当场翻脸,把我的简历还给我,疑似被拉黑...

好家伙&#xff0c;金三银四一到&#xff0c;这奇葩事可真是多&#xff0c;前两天和粉丝聊天&#xff0c;他说前段时间面试阿里的测开岗&#xff0c;最后和面试官干起来了。 我问他为什么&#xff0c;他说没啥&#xff0c;就觉得面试官太装了&#xff0c;就爱问一些虚而不实的…...

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网络方…...

《数据库系统概论》学习笔记——第四章 数据库安全

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

山洪径流过程模拟及洪水危险性评价

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

LeetCode HOT100 (23、32、33)

目录 23、合并K个升序链表 32、最长有效括号 33、搜索旋转排序数组 23、合并K个升序链表 思路&#xff1a;采用顺序合并的方法&#xff0c;用一个变量 ans 来维护以及合并的链表&#xff0c;第 i 次循i 个链表和 ans合并&#xff0c;答案保存到 ans中。 代码&#xff1a; …...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

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

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...