顺序表 (C语言版)

ops/2024/11/19 19:25:17/

顺序存储:

 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。

顺序表的特点:

  1. 能在O(1)的时间内找到第i个元素
  2. 存储密度高
  3. 拓展容量不方便
  4. 插入,删除操作不方便

C语言中可使用:sizeof(ElemType) 来查询数据元素的大小

顺序表的实现:

静态分配:

#include <stdio.h>
#define MaxSize 10    //宏定义最大长度为10
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++)L.data[i] = 0;L.length = 0;
}int main() {SqList L;InitList(L);for(int i=0; i<MaxSize; i++)printf("data[%d]=%d\n",i,L.data[i]);
}

动态分配:

#include <stdlib.h>
#define InitSize 10 //默认最大长度为10
typedef struct{     //定义一个顺序表int *date;      //指示动态分配的指针int MaxSize;    //顺序表的最大容量int length;     //顺序表当前长度
}SeqList;void InitList(SeqList &L){  //初始化一个顺序表L.date = (int *)malloc( InitSize*sizeof(int) );     //用malloc申请一片连续的存储空间L.length = 0;L.MaxSize = InitSize;
}void IncreaseSize(SeqList &L, int len){     //动态增加顺序表的长度int *p = L.date;        //将旧数据保存L.date = (int *)malloc((L.MaxSize + len) * sizeof(int));    //开辟更大的存储空间for(int i = 0; i < L.length; i++){      //循环将旧数据复制到新区域L.date[i] = p[i];}L.MaxSize = L.MaxSize + len;        //最大长度增加lenfree(p);        //释放原来的存贮空间
}int main(){SeqList L;      //声明一个顺序表InitList(L);    //初始化顺序表//...此处省略部分代码,在顺序表中随便插入几个元素...IncreaseSize(L, 5);     //增加长度为5return 0;
}

顺序表的插入和删除:

插入:

将元素e插入到第i个位置

平均时间复杂度为O(n)

#include <stdio.h>
#define MaxSize 10    //宏定义最大长度为10
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++)L.data[i] = 0;L.length = 0;
}bool ListInsert(SqList &L, int i, int 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;
}int main() {SqList L;InitList(L);//此处省略一些代码,随便向顺序表中插入几个元素ListInsert(L, 3, 3);for(int i=0; i<MaxSize; i++)printf("data[%d]=%d\n",i,L.data[i]);
}

删除:

将第i个元素删除,并用e返回

平均时间复杂度为O(n)

#include <stdio.h>
#define MaxSize 10    //宏定义最大长度为10
typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++)L.data[i] = 0;L.length = 0;
}bool ListDelete(SqList &L, int i, int &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;
}int main() {SqList L;   InitList(L);//此处省略一些代码,随便向顺序表中插入几个元素int e = -1;if (ListDelete(L, 1, e))printf("已删除第3个元素,删除的元素值=%d", e);elseprintf("删除失败");return 0;       
}

查找元素:

按位查找:

平均时间复杂度O(1)

int GetElen(SqList L, int i){return L.data[i-1];
}

 按值查找:

平均时间复杂度O(n)

int LocateElem(SqList L, int e){for(int i=0; i<L.length; i++)if(L.data[i] == e)return i+1;return 0
}


http://www.ppmy.cn/ops/17264.html

相关文章

大数据分析:使用Spark和Hadoop的实用指南

Apache Spark 和 Apache Hadoop 是两个在大数据生态系统中非常流行的框架。Hadoop 主要用于数据存储和处理大规模数据集的批处理作业&#xff0c;而 Spark 是一个强大的计算框架&#xff0c;提供了更快的计算速度和更高效的数据处理能力。这里提供一个实用指南&#xff0c;帮助…

R可视化:桑基图展示数据层流动

介绍 以桑基图形式展示数据分布情况 加载R包 knitr::opts_chunk$set(message = FALSE, warning = FALSE) library(tidyverse) library(ggalluvial)# rm(list = ls()) options(stringsAsFactors = F) options(future.globals.maxSize = 10000 * 1024^2) 导入数据 metadata…

.NET/C#汇总 —— 数据库SQL查询(附建表语句)

1.⽤⼀条SQL 语句 查询出每⻔课都⼤于80 分的学⽣姓名 建表语句: create table tableA ( name varchar(10), kecheng varchar(10), fenshu int(11) )DEFAULT CHARSET = utf8;插⼊数据 insert into tableA values (张三,语⽂,81); insert into tableA values (张三,数学,75)…

[Flutter3] 记录Dio的简单封装(一)

文章目录 效果使用ResponseEntity类DioManager封装_onResponse / _onDioException 的设计Response的处理catch处理 效果 请求成功/失败/异常的日志输出效果 成功: 失败:500 失败:404 网络异常: 使用 举个使用的例子, 在调用 DioManager的时候, 直接通过返回值的状态, 来…

网络安全数字孪生:一种新颖的汽车软件解决方案

摘要 随着汽车行业转变为数据驱动的业务&#xff0c;软件在车辆的开发和维护中发挥了核心作用。随着软件数量的增加&#xff0c;相应的网络安全风险、责任和监管也随之增加&#xff0c;传统方法变得不再适用于这类任务。相应的结果是整车厂和供应商都在努力应对汽车软件日益增加…

【Mysql】mysql表设计时字段类型的选择建议

目录 1. 整数类型 2. 小数类型 选择建议 例子 在 MySQL 中设计表时选择字段的数据类型&#xff0c;特别是当你知道该字段的值将仅包含数字时&#xff0c;你应根据数据的性质和范围来选择最适合的类型。以下是几种常见的数字类型及其适用场景&#xff1a; 1. 整数类型 TIN…

数仓开发LAG 和 LEAD 函数详细解析和用例

在做Iot大数据开发时&#xff0c;需要用到lag和lead函数来计算设备故障。下面详细解析lag和lead函数的作用和例子。 LAG 和 LEAD 函数是用于在 Spark SQL 中进行窗口函数操作时常用的两个函数&#xff0c;它们用于获取某一行在分组内的前一行或后一行的数值。下面详细解释它们…

基于spring boot开发的快递管理系统开题报告

快递公司管理系统开题报告 一、研究背景与意义 随着电子商务的蓬勃发展&#xff0c;快递物流行业迎来了前所未有的增长机遇。然而&#xff0c;快递公司在面对日益增长的业务量时&#xff0c;也面临着管理效率低下、资源分配不合理、客户服务体验不佳等问题。开发一套高效、智…