【数据结构】线性表 顺序表(动态、静态分配,插入删除查找基本操作)解析+完整代码

1.线性表的基本概念

  • 定义

    线性表(Linear List)是具有相同数据类型的n个数据元素的有限序列

    • n为表长,n=0时线性表是个空表
  • 前驱、后继

    • 前驱:其中一个数据元素的前一个元素。第一个元素没有前驱。
    • 后继:其中一个数据元素的后一个元素。最后一个元素没有后继。
  • 存储/物理结构

    • 顺序表(顺序存储)
    • 链表(链式存储)

2.顺序表

2.1 顺序表的定义

  • 顺序表定义

    用顺序存储方式实现线性表的储存。

    是用一组地址连续的存储单元依次存储线性表中的数据元素。

    • 特点:

      1.表中元素的逻辑顺序与物理顺序相同。

      2.可以随机存取——知道顺序表起始位置LOC(A)和每个元素所占内存的大小sizeof(ElemType)后,可知道任意一个元素的位置。

  • 优点

    1.可随机访问,O(1)时间内找到指定元素;

    2.存储密度高,每个结点只存储数据元素。

  • 缺点

    1.元素的插入和删除要移动大量数据元素。

    2.需要连续存储空间,不够灵活。

2.1.1 静态分配
//静态分配结构存储
#define MaxSize 10 //最大长度
typedef struct{int data[MaxSize]; //静态数组存放数据元素int length; //顺序表当前长度
}SqList; //顺序表类型定义//静态分配初始化
void InitList(SqList &L){L.Length=0;
}
  • 如果数组存满怎么办?

    没办法了,因为顺序表表长刚开始确定后就无法改变,∴有了动态分配

2.1.2 动态分配
//动态分配结构存储
#define InitSize 100 //表长度的初始定义
typedef struct{ElemType *data; //指示动态分配数组的指针int MaxSize; //最大容量int length; //当前个数
}SeqList;//动态分配初始化
void InitList(SeqList &L){L.data=(ElemType*)malloc(MaxSize*sizeof(ElemType));L.length=0;L.MaxSize=InitSize;
}

C动态分配语句

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
free(L.data);

C++动态分配语句

L.data=new ElemType[InitSize];
delete[]指针变量名;
或
delete 指针变量名;
  • 增加动态数组长度

    void IncreaseSize(SeqList &L,int len){int *p=L.data; //将表中数据存储到p中L.data=(int*)malloc((L.MaxSize+len)*sizeof(int)); //开辟新空间for(int i=0;i<L.length;i++){L.data[i]=p[i]; //数据复制到新区域}L.MaxSize=L.MaxSize+len;free(p);
    }
    
  • 注:动态分配不是链式存储,同样顺序存储,只是空间大小可变。

2.2 顺序表的插入

  • 原理

    在线性表L的第i个位置插入元素e:

    将第i个元素及其后面的所有元素向后移一位,腾出空位插e。

    >

//在L的位序i处插入元素e
bool ListInsert(SqList &L,int i,int e){//判i范围是否有效if(i<1||i>L.length+1)return false;//判存储空间是否已满if(L.length>=MaxSize)return false;//将第i个元素及之后元素后移for(int j=L.length;j>=i;j--) {L.data[j]=L.data[j-1]; //注意:位序和数组下标的关系,并从后面元素依次移动}L.data[i-1]=e;L.length++;return true;
}
  • 时间复杂度

    • 最好情况:在表尾插入,元素后移不用执行,O(1)。
    • 最坏情况:在表头插入,元素后移执行n次,O(n)。
    • 平均情况:O(n/2),即O(n)。

2.3 顺序表的删除

  • 原理

    删除顺序表L中的第i个元素:

    将被删元素赋给引用变量e,将第i+1个元素及其后的所有元素往前移一位。

//删除L中的第i个元素,并用返回
bool ListDelete(SqList &L,int i,ElemType &e){if(i<1||i>L.length)return false;e=L.data[i-1]; //被删元素给引用变量//被删元素后的元素依次后移for(int j=i;j<L.length;j++){L.data[j-1]=L.data[j];}L.length--;return true;
}
  • 时间复杂度

    • 最坏情况:删除表尾元素,无需移动元素,O(1)。
    • 最好情况:删除表头元素,需移动除表尾外的所有元素,O(n)。
    • 平均情况:O(n/2),即O(n)。

2.4 顺序表的查找

2.4.1 按位查找
ElemType GetElem(SqList L,int i){return L.data[i-1];
}
  • 时间复杂度:O(1)
2.4.2 按序查找
int LocateElem(SqList L,ElemType e){int i;for(i=0;i<L.length;i++){if(L.data[i]==e)return i+1; //找到了返回位序}return 0; //没找到返回0
}
  • 时间复杂度:O(n)

*完整代码 顺序表静态存储

//顺序表 静态分配 线性表下标从0开始
#include<stdio.h>#define ElemType int//静态结构体
#define MaxSize 99
typedef struct {ElemType data[MaxSize];int length;
}SqList;//初始化
void InitList(SqList &L)
{L.length = 0;
}//求表长
int Length(SqList &L) 
{return L.length;
}//按值查找
int LocateElem(SqList &L,ElemType e) 
{for (int i = 0; i < L.length; i++) {if (L.data[i] == e) {return i + 1;}}return 0;
}//按位查找
int GetItem(SqList& L, int i) 
{return L.data[i-1]; //i是位序,而顺序表从0开始存的,所以i要-1
}//插入操作
bool ListInsert(SqList& L, int i, ElemType e) 
{if (i<1 || i>L.length)return false;if (L.length >= MaxSize)return false;for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];}L.data[i-1] = e; L.length++;return true;
}//删除操作
bool ListDelete(SqList& L, int i, ElemType& e) 
{if (i<1 || i>L.length)return false;e = L.data[i-1];for (int j = i; j <L.length; j++) {L.data[j-1] = L.data[j];}L.length--;return true;
}//判空操作
bool Empty(SqList& L)
{if (L.length == 0)return true;elsereturn false;
}//销毁操作
void DestroyList(SqList &L)
{L.length = 0;
}//输出
void PrintList(SqList& L) 
{for (int i = 0; i < L.length; i++){printf("%d ", L.data[i]);}printf("\n");
}int main()
{SqList L;InitList(L);//赋值for (int i = 0; i < 10; i++){L.data[i] = i;L.length++;}PrintList(L);printf("插入:\n");int e = -1, pos = 4;ListInsert(L, pos , e);PrintList(L);printf("删除:\n");int a;ListDelete(L, pos, a);PrintList(L);printf("%d\n", a);printf("按值查找:\n");pos = LocateElem(L, 5);printf("%d\n", pos);printf("按位查找:\n");printf("%d", GetItem(L, 3));
}

请添加图片描述

*完整代码 顺序表动态存储

//顺序表 动态分配 
#include<stdio.h>
#include <stdlib.h>#define ElemType int//静态结构体
#define InitSize 2
typedef struct {ElemType *data;int length;int MaxSize;
}SeqList;//初始化
void InitList(SeqList& L)
{L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));L.length = 0;L.MaxSize = InitSize;
}//增加动态数组长度
void IncreaseSize(SeqList& L, int len) {int* p = L.data; //将表中数据存储到p中L.data = (int*)malloc((L.MaxSize + len) * sizeof(int)); //开辟新空间for (int i = 0; i < L.length; i++){L.data[i] = p[i]; //数据复制到新区域}L.MaxSize = L.MaxSize + len;free(p);
}//求表长
int Length(SeqList& L)
{return L.length;
}//按值查找
int LocateElem(SeqList& L, ElemType e)
{for (int i = 0; i < L.length; i++){if (L.data[i] == e){return i + 1;}}return 0;
}//按位查找
int GetItem(SeqList& L, int i)
{return L.data[i - 1]; //i是位序,而顺序表从0开始存的,所以i要-1
}//插入操作
bool ListInsert(SeqList& L, int i, ElemType e)
{if (i<1 || i>L.length)return false;if (L.length >= L.MaxSize)return false;for (int j = L.length; j >= i; j--){L.data[j] = L.data[j - 1];}L.data[i - 1] = e; L.length++;return true;
}//删除操作
bool ListDelete(SeqList& L, int i, ElemType& e)
{if (i<1|| i>L.length)return false;e = L.data[i - 1];for (int j = i; j < L.length; j++){L.data[j - 1] = L.data[j];}L.length--;return true;
}//判空操作
bool Empty(SeqList& L)
{if (L.length == 0)return true;elsereturn false;
}//销毁操作
void DestroyList(SeqList& L)
{free(L.data);L.data = NULL; // 避免悬挂指针L.length = 0;
}//输出
void PrintList(SeqList& L)
{for (int i = 0; i < L.length; i++){printf("%d ", L.data[i]);}printf("\n");
}int main()
{SeqList L;InitList(L);IncreaseSize(L, 9);//赋值for (int i = 0; i < 10; i++){L.data[i] = i;L.length++;}PrintList(L);printf("插入:\n");int e = -1, pos = 5;ListInsert(L, pos, e);PrintList(L);printf("删除:\n");int a;ListDelete(L, pos, a);PrintList(L);printf("%d\n", a);printf("按值查找:\n");pos = LocateElem(L, 5);printf("%d\n", pos);printf("按位查找:\n");printf("%d", GetItem(L, 3));DestroyList(L);
}

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Internet协议

文章目录 Internet协议网络层协议IPV4协议IP地址&#xff1a;IPv4数据报格式IP数据报的封装和分片 Internet路由协议路由信息协议RIP开放最短路径优先协议OSPF外部网关协议BGP组播协议PIM和MOSPF ARP和RARPARP协议&#xff1a;RARP协议&#xff1a; Internet控制报文协议ICMPIP…

redis八股

文章目录 数据类型字符串实现使用场景 List 列表实现使用场景 Hash 哈希实现使用场景 Set 集合实现使用场景 ZSet 有序集合实现使用场景 BitMap实现使用场景 Stream使用场景pubsub为什么不能作为消息队列 数据结构机制SDS 简单动态字符串压缩列表哈希表整数集合跳表quicklistli…

数学建模论文、代码百度网盘链接

1.[2018中国大数据年终总决赛冠军] 金融市场板块划分与轮动规律挖掘与可视化问题 2.[2019第九届MathorCup数模二等奖] 数据驱动的城市轨道交通网络优化策略 3.[2019电工杯一等奖] 露天停车场停车位的优化设计 4.[2019数学中国网络数模一等奖] 基于机器学习的保险业数字化变革…

MapGIS农业信息化解决方案(2)

农业资源采集与调查 农业各项生产活动与农业资源息息相关,对农业资源进行调查,摸清农业家底, 为构筑农业“一张图”核心数据库奠定数据基础。MapGIS 农业资源采集与调查系统集成遥感、手持终端等调查技术,为农业资源采集提供实用、简捷的采集调查和信息录入工具,实现农田…

线激光转台拼接重建

单线激光在进行三维重建的时候每次只能重建一条激光线,为了得到一个完整的物体需要借助外部结构。而基于转台的方式可以很好的完成这一操作。整个系统包括了相机标定、激光线标定与重建、转台标定、转台拼接。将相机和激光器固定在特定位置&#xff0c;然后让转台带动物体进行旋…

消息中间件篇之Kafka-数据清理机制

一、Kafka文件存储机制 Kafka文件存储结构&#xff1a;一个Topic有多个分区。每一个分区都有多个段&#xff0c;每个段都有三个文件。 为什么要分段&#xff1f;1. 删除无用文件方便&#xff0c;提高磁盘利用率。 2. 查找数据便捷。 二、数据清理机制 1.日志的清理策略方案1 根…

运维管理制度优化:确保IT系统稳定运行的关键策略

1、总则 第一条&#xff1a;为保障公司信息系统软硬件设备的良好运行&#xff0c;使员工的运维工作制度化、流程化、规范化&#xff0c;特制订本制度。 第二条&#xff1a;运维工作总体目标&#xff1a;立足根本促发展&#xff0c;开拓运维新局面。在企业发展壮大时期&#x…

服务器被黑该如何查找入侵痕迹以及如何防御攻击

当公司的网站服务器被黑&#xff0c;被入侵导致整个网站&#xff0c;以及业务系统瘫痪&#xff0c;给企业带来的损失无法估量&#xff0c;但是当发生服务器被攻击的情况&#xff0c;作为服务器的维护人员应当在第一时间做好安全响应&#xff0c;对服务器以及网站应以最快的时间…

Java 学习和实践笔记(22):package(包机制)、JDK常见的包、类的导入

前面学的类&#xff0c;每创建一个类&#xff0c;在电脑上就是创建了一个对应的类文件。而package 相当于文件夹对文件的管理作用。主要用于管理类、用于解决类的重名问题。这个含义很简单。因为实际的程序&#xff0c;类可能有成千上万个&#xff0c;这样就需要把不同功能的类…

Vue3 isProxy,isReactive,isReadonly 三者解析

1、isProxy 作用&#xff1a;判断当前数据是否为代理数据。 注意&#xff1a;它只对通过 reactive&#xff0c;readonly&#xff0c;shallowReactive&#xff0c;shallowReadonly 这四个方法包裹的数据返回true&#xff0c;对于 ref 以及通过 new Proxy 代理的数据返回都是fal…

如何使用ArcGIS Pro为栅格图添加坐标信息

在某些时候&#xff0c;我们从网上获取的资源是一张普通的栅格图&#xff0c;没有任何的坐标信息&#xff0c;如果想要和带坐标信息的数据一起使用就需要先添加坐标信息&#xff0c;在GIS上&#xff0c;我们把这个过程叫做地理配准&#xff0c;这里为大家介绍一下地理配准的方法…

【惠友小课堂】骨质疏松≠老年人“专利”,年轻人也不能忽视(文末附自我测试)

虽说现在大家对于骨质疏松并不陌生&#xff0c;许多中老年人甚至年轻人都开始认识到“维护骨骼要趁早”&#xff0c;但依旧有人对骨质疏松存在一些“误解”&#xff0c;今天就来一一解开。&#xff08;PS&#xff1a;文末有骨质疏松自我测试哦~&#xff09; 某在读大学生 “我这…

指针数组,模拟二维指针

arr[i] *(arri) arr为数组首地址&#xff0c;地址后移再解引用等于此地址内容。 模拟二维指针 arr[i][j] *(*(arri)j) 存放数组的指针叫指针数组&#xff0c;先指针后数组

构建高效人才招聘系统:源码开发与技术实践

随着互联网的发展&#xff0c;传统的招聘方式已经无法满足企业快速获取人才的需求。因此&#xff0c;利用现代技术手段构建一套高效的人才招聘系统成为了迫切需要解决的问题。下文&#xff0c;小编将从源码开发与技术实践的角度&#xff0c;为读者呈现如何构建一款高效人才招聘…

通胀变化央行如何应对?Anzo Capital昂首资本只看一个指标

通胀变化央行如何应对&#xff1f;Anzo Capital昂首资本认为通常情况下&#xff0c;如果通胀预期上升&#xff0c;央行会收紧货币政策&#xff0c;而如果通胀压力下降&#xff0c;央行会放松货币政策&#xff0c;从而调节银行体系的流动性&#xff0c;从而因货币贬值而刺激经济…

【Excel PDF 系列】EasyExcel + iText 库

你知道的越多&#xff0c;你不知道的越多 点赞再看&#xff0c;养成习惯 如果您有疑问或者见解&#xff0c;欢迎指教&#xff1a; 企鹅&#xff1a;869192208 文章目录 前言转换前后效果引入 pom 配置代码实现定义 ExcelDataVo 对象主方法EasyExcel 监听器 前言 最近遇到生成 …

Acwing周赛记录

很难得参加一次周赛hhhhh这次参加的是第144场周赛&#xff0c;一共有三道题 AcWing 5473. 简单数对推理 给定两个整数数对&#xff0c;每个数对都包含两个 1∼9 之间的不同整数。 这两个数对恰好包含一个公共数&#xff0c;即恰好有一个整数同时包含于这两个数对。 给定这两…

DB-GPT:大模型 + 数据库,全流程自动化

DB-GPT&#xff1a;大模型 数据库&#xff0c;全流程自动化 提出背景DB-GPT 结构具体问题与解法背景分析对比其他工具DB-GPT系统设计 提出背景 论文&#xff1a;https://arxiv.org/pdf/2312.17449.pdf 代码&#xff1a;https://github.com/eosphoros-ai/DB-GPT 本文介绍了D…

C#区域医院云LIS信息管理系统源码 标本管理、两癌筛查、数据分析、试剂管理

目录 ​编辑 区域医院云LIS系统功能亮点&#xff1a; 云LIS系统功能&#xff1a; 一、 基础管理 二、 前处理&#xff08;实验室&#xff09; 三、 标本处理 四、 样本检验 五、 统计报表 六、 质控管理 七、 基本工作流程 区域LIS系统特点&#xff1…

shell自定义日志输出函数log

Background 在编写比较复杂的脚本时&#xff0c;需要输出相关日志信息&#xff0c;方便知悉脚本的执行情况以及问题的排查。 源码 log.sh # 自定义日志函数 function log(){if [[ $1 "i" || $1 "info" ]]; thenecho -ne "\033[1;34mINFO: \033[0m&…