线性表的定义和基本操作

线性表的定义和基本操作

一、线性表的定义

线性表（Linear List）是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为

L = (a1,a2,...,ai,ai+1,...,an)

ai是线性表中的“第i个”元素线性表中的位序

a1是表头元素；an是表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱；出最后一个元素外，每个元素有且仅有一个直接后继；

二、线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占有的内存空间。

ListInsert(&L,i,e)：插入操作。在表L中的第i个位序（位置）上插入制定元素e。

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位序（位置）的元素，并用e返回删除元素的值。

LocateElem(L,e)：按值查找操作。在表L中查找具体给定关键字值的元素。

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作：

Length(L)：求表长操作。返回线性表L的长度，即L中数据元素的个数。

PrinList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

Tips：

①对数据的操作（记忆思路）——创（Init）销（Destroy）、增（Insert）删（Delete）改（Alter）查（Query）

②C语言函数的定义

③实际开发中，可根据实际需求定义其他的基本操作

④函数名和参数的形式、命令都可改变

⑤什么时候需要传入“&”——对参数的修改结果需要“带回来”

三、初始化代码实践

1、顺序表静态分配
#include <stdio.h>
// 顺序表存储空间静态分配
#define MaxSize 10      // 定义最大长度
typedef int ElemType;   // int类型重命名为ElemType，方便后续调整
typedef struct{         // 定义结构体
    ElemType data[MaxSize];         // 用静态的数组存放数据元素
    ElemType length;                // 数组长度
}SqList;
void InitList(SqList &L){           // 初始化顺序表
    L.length=0;                     // 长度赋值,没有设置数据元素的默认值
}
int main() {
    SqList L;           // 声明一个顺序表
    InitList(L);    // 初始化顺序表
    for (int i = 0; i < MaxSize; i++) {
        // 尝试违规打印整个data数组
        printf("data[%d]=%d\n", i, L.data[i]);
    }
    return 0;
}

在这里插入图片描述

#include <stdio.h>
// 顺序表存储空间静态分配
#define MaxSize 10      // 定义最大长度
typedef int ElemType;   // int类型重命名为ElemType，方便后续调整
typedef struct{         // 定义结构体
    ElemType data[MaxSize];         // 用静态的数组存放数据元素
    ElemType 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 < L.length; i++) {    //按照数据长度进行打印
        // 尝试违规打印整个data数组
        printf("data[%d]=%d\n", i, L.data[i]);
    }
    return 0;
}
2、顺序表动态分配
#include <stdio.h>
#include <stdlib.h>
// 顺序表存储空间动态分配
#define InitSize 10      // 顺序表初始长度
typedef int ElemType;   // int类型重命名为ElemType，方便后续调整
typedef struct{         // 定义结构体
    ElemType *data;     // 用静态的数组存放数据元素
    ElemType MaxSize;   // 顺序表最大容量
    ElemType length;    // 顺序表数据长度
}SqList;
void InitList(SqList &L){           // 初始化顺序表
    // 用malloc函数申请一片连续的存储空间
    L.data = (ElemType *) malloc(InitSize * sizeof(ElemType));
    L.MaxSize = InitSize;
    L.length = 0;
}
void IncreaseSize(SqList &L, ElemType len){
    ElemType *p=L.data;
    L.data = (int *) malloc((L.MaxSize + len) * sizeof(ElemType));
    for (ElemType i = 0; i < L.length; i++) {
        L.data[i]=p[i];     // 将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;    // 顺序表最大长度增加len
    free(p);            // 释放原来的内存空间
}
int main() {
    SqList L;           // 声明一个顺序表
    InitList(L);    // 初始化顺序表
    IncreaseSize(L, 5);
    return 0;
}
3、特点

随机访问：即可以在O(1)时间内找到第i个元素。

存储密度高：每个节点只存储数据元素。

扩展容量不方便：即便采取动态分配的方式实现，拓展长度的时间复杂度也比较高。

插入、删除操作不方便：需要移动大量的元素。

四、插入和删除

1、顺序表插入实践
#include <stdio.h>

#define MaxSize 10      // 指定大小
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    ElemType length;
}SqList;

bool InsertList(SqList &L, ElemType position, ElemType element){
    if (position < 1 || position > L.length + 1) {      // 判断插入是否合理
        return false;
    }
    if (L.length >= MaxSize) {          // 判断插入是否合理
        return false;
    }
    for (ElemType i = L.length; i >= position; i--) {   // 循环从最后一位开始，到插入的位序，减减
        L.data[i] = L.data[i-1];        // 将前一位值向后移一位
    }
    L.data[position-1] = element;       // 插入的位置附上要插入的值，注意数组下标和位序是相差一位的
    L.length++;                         // 插入一个元素之后，数组的长度是要加1
    return true;
}

void PrintList(SqList L){
    for (ElemType i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n",i,L.data[i]);
    }
}
int main() {
    SqList L;   // 初始化
    for (ElemType i = 0; i < 6; i++) {      // 数组赋值
        L.data[i]=i*2;
    }
    L.length=6;
    bool ret;
    ret = InsertList(L, 6, 20); // 调用插入
    if (ret) {          // 判断是否正常插入
        printf("insert element success\n");
        PrintList(L);
    } else {
        printf("insert element failed\n");
    }
    return 0;
}

在这里插入图片描述

插入操作的时间复杂度

最好情况：新元素插入到表尾，按照以上例子为插入位序为6的位置，不需要移动元素，循环0次，最好时间复杂度=O(1)

最坏情况：新元素插入到表头，需要将原有的n个元素全部都向后移动，循环n次，最坏时间复杂度=O(n)

平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3,…,length+1的概率都是
p = 1 n + 1 p=\frac{1}{n+1} p=n+11​
i=1,循环n次，i=2，循环n-1，…，i=n+1，循环0次
平均循环次数 = n p + ( n − 1 ) p − ( n − 2 ) p + . . . + 1. p = n ( n + 1 ) 2 ⋅ 1 n + 1 = n 2 平均循环次数=np+(n-1)p-(n-2)p+...+1.p=\frac{n(n+1)}{2}·\frac{1}{n+1}=\frac{n}{2} 平均循环次数=np+(n−1)p−(n−2)p+...+1.p=2n(n+1)​⋅n+11​=2n​
平均时间复杂度=O(n)

2、顺序表删除实践
#include <stdio.h>

#define MaxSize 10      // 指定大小
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    ElemType length;
}SqList;

bool DeleteList(SqList &L, ElemType position, ElemType &element){
    if (position < 1 || position > L.length + 1) {      // 判断删除是否合理
        return false;
    }
    element = L.data[position-1];       // 删除的数据，注意数组的下标和位序的关系
    for (ElemType i = position; i <L.length; i++) {   // 循环从要删除的位序开始，结束条件为到数组长度减一位的位置
        L.data[i-1] = L.data[i];        // 将删除位序的值向前移动
    }
    L.length--;                         // 删除一个元素之后，数组的长度是要减1
    return true;
}

void PrintList(SqList L){
    for (ElemType i = 0; i < L.length; i++) {
        printf("data[%d]=%d\n",i,L.data[i]);
    }
}
int main() {
    SqList L;   // 初始化
    for (ElemType i = 0; i < 6; i++) {      // 数组赋值
        L.data[i]=i*2;
    }
    L.length=6;
    ElemType num;
    bool ret;
    ret = DeleteList(L, 2, num); // 调用插入
    if (ret) {          // 判断是否正常插入
        printf("delete element success!delete element is %d\n",num);
        PrintList(L);
    } else {
        printf("insert element failed\n");
    }
    return 0;
}

在这里插入图片描述

最好情况：删除表尾元素，不需要移动元素，循环0次，最好时间复杂度=O(1)

最坏情况：删除表头元素，需要将后续n-1个元素全部向前移动，循环n-1次，最坏时间复杂度=O(n)

平均情况：假设删除任何一个元素的概率相同，即i=1,2,3,…,length+1的概率都是
p = 1 n p=\frac{1}{n} p=n1​
i=1,循环n-1次，i=2，循环n-2，…，i=n，循环0次
平均循环次数 = ( n − 1 ) p − ( n − 2 ) p + . . . + 1. p = n ( n − 1 ) 2 ⋅ 1 n = n − 1 2 平均循环次数=(n-1)p-(n-2)p+...+1.p=\frac{n(n-1)}{2}·\frac{1}{n}=\frac{n-1}{2} 平均循环次数=(n−1)p−(n−2)p+...+1.p=2n(n−1)​⋅n1​=2n−1​
平均时间复杂度=O(n)

3、顺序表查询实践
#include <stdio.h>

// 静态分配
#define MaxSize 10		// 定义最大长度

typedef int Element;

typedef struct{
    Element data[MaxSize];		// 用静态的“数组”存放数据元素
    int length;
}SqList;
	
int GetList(SqList L,int position){		// 查询该位序的值
    return L.data[position - 1];		// 位序和数组下标少一位
}

int LocateList(SqList L,int num){		// 查询值在数据哪个位序
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == num) {
            return i+1;					// 返回位序和数组下标相差一位
        }
    }
}
int main() {
    SqList L;
    for (int i = 0; i < 5; i++) {
        L.data[i] = i*2;
    }
    L.length=5;
    int ret;
    ret = GetList(L, 3);
    printf("Get List num is %d\n", ret);

    ret = LocateList(L,4);
    printf("Locate List position is %d\n", ret);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
// 动态分配
#define InitSize 10

typedef int Element;

typedef struct{
    Element *data;
    int MaxSize;
    int length;
}SqList;

void InitList(SqList &L){               // 初始化
    L.data = (int *) malloc(InitSize*sizeof(int));
    L.MaxSize = InitSize;
    L.length = 0;
}

int GetList(SqList L,int position){		// 查询该位序的值
    return L.data[position - 1];		// 位序和数组下标少一位
}

int LocateList(SqList L,int num){		// 查询值在数据哪个位序
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == num) {
            return i+1;					// 返回位序和数组下标相差一位
        }
    }
}
int main() {
    SqList L;
    InitList(L);
    for (int i = 0; i < 5; i++) {
        L.data[i] = i*2;
    }
    L.length=5;
    int ret;
    ret = GetList(L, 3);
    printf("Get List num is %d\n", ret);

    ret = LocateList(L,4);
    printf("Locate List position is %d\n", ret);
    return 0;
}

时间复杂度：

按位查找：O(1)

按值查找：最好时间复杂度：O(1)，在第一个位置

​ 最坏时间复杂度：O(n)，在最后一个位置

​ 平均时间复杂度：O(n)，目标元素在每个位置的概率相同
O = ( 1 + 2 + . . . + n ) 1 n = n ( n + 1 ) 2 ⋅ 1 n = n + 1 2 = O ( n ) O=(1+2+...+n)\frac{1}{n}=\frac{n(n+1)}{2}·\frac{1}{n}=\frac{n+1}{2}=O(n) O=(1+2+...+n)n1​=2n(n+1)​⋅n1​=2n+1​=O(n)

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JMeter + Ant + Jenkins持续集成-接口自动化测试

JMeter + Ant + Jenkins持续集成-接口自动化测试

需要安装的工具&#xff1a; jdk1.8jmeter3.2ant1.9jenkins2.1 1、Jdkwin7系统如何安装jdk及环境变量的配置-百度经验 安装包安装设置环境变量验证是否安装正确 Java -version检查&#xff0c;如下就代表安装成功了&#xff0c;环境变量设置就去搜索了&#xff0c;网上很多…
阅读更多...
TimeGPT:时间序列预测的第一个基础模型

TimeGPT:时间序列预测的第一个基础模型

时间序列预测领域在最近的几年有着快速的发展&#xff0c;比如N-BEATS、N-HiTS、PatchTST和TimesNet。 大型语言模型(llm)最近在ChatGPT等应用程序中变得非常流行&#xff0c;因为它们可以适应各种各样的任务&#xff0c;而无需进一步的训练。 这就引出了一个问题:时间序列的…
阅读更多...
File相关方法2

File相关方法2

一.获取当前目录下所有一级文件名称 1.代码 package org.example;import java.io.File;public class day03 {public static void main(String[] args) {//获取当前目录下所有一级文件名称final File f1 new File("d:/temp");final String[] name f1.list();for (…
阅读更多...
VDA到Excel方案介绍之自定义邮件接收主题

VDA到Excel方案介绍之自定义邮件接收主题

VDA标准是德国汽车工业协会&#xff08;Verband der Automobilindustrie&#xff0c;简称VDA&#xff09;制定的一系列汽车行业标准。这些标准包括了汽车生产、质量管理、供应链管理、环境保护、安全性能等方面的规范和指南。VDA标准通常被德国和国际上的汽车制造商采用&#x…
阅读更多...
学习笔记：二分图

学习笔记：二分图

二分图 引入 二分图又被称为二部图。 二分图就是可以二分答案的图。 二分图是节点由两个集合组成&#xff0c;且两个集合内部没有边的图。换言之&#xff0c;存在一种方案&#xff0c;将节点划分成满足以上性质的两个集合。 性质 如果两个集合中的点分别染成黑色和白色&am…
阅读更多...
目录和文件操作

目录和文件操作

在自己电脑任一盘符中新建以OS_Test命名的文件夹&#xff0c;并在该文件夹中新建新建3个以.txt&#xff0c;3个 .xlsx为扩展名的文件&#xff08;文件名由代码随机生成&#xff0c;长度为8&#xff0c;由字母数字组成&#xff09;。&#xff0c;请写一个程序&#xff0c;删除掉…
阅读更多...
stm32的ADC采样率如何通过Time定时器进行控制

stm32的ADC采样率如何通过Time定时器进行控制

ADC采样率是个跟重要的概念. 手册上说可以通过Timer定时器进行触发ADC采样. 可我这边悲剧的是, 无论怎么样. ADC都会进行采样. 而且就算是TIM停掉也是一样会进行采样. 这就让我摸不着头脑了… 我想通过定时器动态更改ADC的采样频率. 结果不随我愿… 这到底是什么问题呢? 一…
阅读更多...
el-table(vue2中）滚动条被固定列盖住

el-table(vue2中）滚动条被固定列盖住

一、项目场景&#xff1a; vue2 el-table 二、问题描述 1、现场图片&#xff1a; 2、全局css环境配置了滚动条高度为6px /* 全局滚动条配置 */ ::-webkit-scrollbar {width: 6px;height: 6px; }::-webkit-scrollbar-track {background-color: #f1f1f1; }::-webkit-scrollbar-…
阅读更多...
STM32 定时器配置不当导致误差(精度)偏大的问题发现与解决

STM32 定时器配置不当导致误差(精度)偏大的问题发现与解决

通用定时器TIM2/3/4/5&#xff0c;PWM输出1Khz的波形 一开始初始化代码如下&#xff1a; void MX_TIM2_Init(void)//1kHz {TIM_ClockConfigTypeDef sClockSourceConfig {0};TIM_MasterConfigTypeDef sMasterConfig {0};TIM_OC_InitTypeDef sConfigOC {0};htim2.Instance T…
阅读更多...
AI与Prompt：解锁软件开发团队的魔法咒语，在复杂任务上生成正确率更高的代码

AI与Prompt：解锁软件开发团队的魔法咒语，在复杂任务上生成正确率更高的代码

AI与Prompt&#xff1a;解锁软件开发团队的魔法咒语 写在最前面论文&#xff1a;基于ChatGPT的自协作代码生成将团队协作理论应用于代码生成的研究自协作框架原理1、DOL任务分配2、共享黑板协作3、Instance实例化 案例说明简单任务&#xff1a;基本操作&#xff0c;生成的结果1…
阅读更多...
【MySQL架构篇】逻辑架构

【MySQL架构篇】逻辑架构

逻辑架构 文章目录 逻辑架构1. 服务器处理客户端请求2. Connectors3. 第一层&#xff1a;连接层4. 第二层&#xff1a;服务层5. 第三层&#xff1a;存储引擎6. 存储层7. 小结 1. 服务器处理客户端请求 首先 MySQL 是典型的 C/S 架构&#xff0c;即 Client/Server 架构&#xf…
阅读更多...
Python深度学习实战-基于tensorflow原生代码搭建BP神经网络实现分类任务（附源码和实现效果）

Python深度学习实战-基于tensorflow原生代码搭建BP神经网络实现分类任务（附源码和实现效果）

实现功能 前面两篇文章分别介绍了两种搭建神经网络模型的方法&#xff0c;一种是基于tensorflow的keras框架&#xff0c;另一种是继承父类自定义class类&#xff0c;本篇文章将编写原生代码搭建BP神经网络。 实现代码 import tensorflow as tf from sklearn.datasets import…
阅读更多...
在CentOS 7中手工打造和运行xml文件配置的Servlet，然后使用curl、浏览器、telnet等三种工具各自测试

在CentOS 7中手工打造和运行xml文件配置的Servlet，然后使用curl、浏览器、telnet等三种工具各自测试

下载Openjdk并配置环境变量 https://jdk.java.net/java-se-ri/11-MR2是官网下载Openjdk 11的地方。 sudo wget https://download.java.net/openjdk/jdk11.0.0.1/ri/openjdk-11.0.0.1_linux-x64_bin.tar.gz下载openjdk 11。 sudo mkdir -p /usr/openjdk11创建目录&#xff…
阅读更多...
一张图系列 - “kv cache“

一张图系列 - “kv cache“

我觉得回答这个问题需要知道3个知识点&#xff1a; 1、multi-head-attention是如何计算的&#xff1f;attention的数学公式&#xff1f; kv cache是如何存储和传递的&#xff1f; 2、kv cache 的原理步骤是什么&#xff1f;为什么降低了消耗&#xff1f; 3、kv cache 代码模…
阅读更多...
C++：stl中set(multiset)和map(multimap)的介绍和使用

C++：stl中set(multiset)和map(multimap)的介绍和使用

本文主要从概念、常用接口和使用方法方面介绍set(multiset)和map(multimap)。 目录 一、概念介绍 1.关联式容器 2.键值对 3. 树形结构的关联式容器 二、set和multiset 1.set的介绍 2.set使用 1. set模板参数列表 2. set构造 3. set迭代器 4. set容量 5. set修改操…
阅读更多...
正则表达式包含数字和字符匹配

正则表达式包含数字和字符匹配

至少6位。 pattern : (?.[0-9])(?.[A-Za-z])[0-9A-Za-z]{6,} 正则表达式中的“?”是一个正向预查字符&#xff0c;它的意思是匹配前一个字符出现的最少一次。具体来说&#xff0c;当一个匹配出现时&#xff0c;它会检查前一个字符是否符合要求&#xff0c;如果符合&#xf…
阅读更多...
使用一个Series序列减去另一个Series序列Series.subtract()

使用一个Series序列减去另一个Series序列Series.subtract()

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 求两个序列中对应位置 的各元素的差 a.subtract(b) [太阳]选择题 关于以下代码的说法中正确的是? import pandas as pd a pd.Series([1,2,3]) print("【显示】a:\n",a) b pd.Seri…
阅读更多...
Windows下安装Anaconda、Pycharm以及iflycode插件图解

Windows下安装Anaconda、Pycharm以及iflycode插件图解

目录 一、下载Anaconda、Pycharm以及iflycode插件 二、创建相关文件夹 三、Pycharm社区版安装详细步骤 四、Anaconda安装详细步骤 五、配置Pycharm 六、安装iflycode插件 Anaconda是一款集成的Python环境&#xff0c;anaconda可以看做Python的一个集成安装&#xff0c;安…
阅读更多...
人工智能基础_机器学习007_高斯分布_概率计算_最小二乘法推导_得出损失函数---人工智能工作笔记0047

人工智能基础_机器学习007_高斯分布_概率计算_最小二乘法推导_得出损失函数---人工智能工作笔记0047

这个不分也是挺难的,但是之前有详细的,解释了,之前的文章中有, 那么这里会简单提一下,然后,继续向下学习 首先我们要知道高斯分布,也就是,正太分布, 这个可以预测x在多少的时候,概率最大 要知道在概率分布这个,高斯分布公式中,u代表平均值,然后西格玛代表标准差,知道了 这两个…
阅读更多...
由于找不到emp.dll无法继续执行此代码问题的五个解决方法

由于找不到emp.dll无法继续执行此代码问题的五个解决方法

在玩游戏的过程中&#xff0c;我们常常会遇到一些错误提示&#xff0c;其中最常见的就是“找不到emp.dll”&#xff0c;这个问题我们的游戏无法启动运行。本文将分享我在解决这一问题过程中的方法&#xff0c;希望能对遇到类似问题的玩家有所帮助。 emp.dll是一个动态链接库文件…
阅读更多...
最新文章

Copyright @ 2022~2023