数据结构 - 线性表(顺序表)

线性表是什么

线性表是包含若干数据元素的一个线性序列,记为: L = (a0,…ai-1,ai,ai+1,…an-1)

  • L为表名,ai(0≤ i ≤n-1)为数据元素;
  • n为表长,n>0时,线性表 L 为非空表,否则为空表。

线性表L可用二元组形式描述(程序员间的表述):
L = (D,R)
即线性表 L 包含数据元素集合 D 和关系集合 R
D = {ai | ai ∈ datatype ,i=0,1,2, …n-1 ,n≥0}
R = {<ai, ai+1> | ai,ai+1∈D,0 ≤ i ≤ n-2}

  • 关系符<ai,ai+1>在这里称为有序对
  • 表示任意相邻的两个元素之间的一种先后关系
  • ai 是 ai+1直接前驱,ai+1 是 ai直接后继

在这里插入图片描述

线性表的特征

  • 对非空表,a0是表头,无前驱;
  • an-1是表尾,无后继;
  • 其它的每个元素 ai 有且仅有一个直接前驱 ai-1 和 一个直接后继 ai+1

线性表 - 顺序表

顺序存储结构的表示1

若将线性表 L = (a0,a1,…,an-1) 中的各元素依次存储于计算机一片连续的存储空间。

设 Loc(ai) 为 ai 的地址,Loc(a0) = b,每个元素占 d 个单元, 则:Loc(ai) = b + i*d

顺序存储结构的特点

  • 逻辑上相邻的元素 ai,ai+1,其存储位置也是相邻的
  • 对数据元素 ai 的存取为随机存取按地址存取
  • 存储密度高
    • 存储密度 D = (数据结构中元素所占存储空间)/ (整个数据结构所占空间)
  • 不足:对表的插入和删除等运算的时间复杂度较差

顺序存储结构的表示2

在 C 语言中,可借助于一维数组类型来描述线性表的顺序存储结构:

#define N 100
typedef int data_t;
typedef struct
{data_t data[N]; //表的存储空间;int last;
} sqlist, *sqlink;

在这里插入图片描述
上面的代码可以这么理解:

  • typedef struct sqlist 可以看作是整个图书馆,而这里的 data[N] 是图书馆里的书,结构体里的 last 就可以看作是一共有多少本书,虽然叫作 last 是因为它是顺序表里最后一个元素的下标,但是这个下标也可以标识一共有多少本书,只要可以代表总数,也可以换成别的。
  • 那为什么要用 typedef 定义变量和结构体?因为这样可以复用代码,比如这里的 data_t 可以换成 char ,也可以换成别的类型,它可以是书,也可以是餐具等等,结构体 typedef 同理

线性表的基本运算

设线性表 L = (a0,a1,…,an-1) , 对 L 的基本运算有:
1)建立一个空表:list_create(L)
2)置空表:list_clear(L)。若成功返回1,失败返回0。
3)判断表是否为空:list_empty(L)。若表为空,返回值为 0,否则返回 -1
4)求表长:length(L)
5)取表中某个元素:GetList(L,i),即ai。要求0≤ i ≤ length(L) - 1
6)定位运算:Locate(L,x)。确定元素 x 在表 L 中的位置(或序号)
L o c a t e ( L , x ) = { i 当元素 x = a i ∈ L ,且 a i 是第一个与 x 相等时 − 1 当 x 不属于 L 时 Locate(L,x)=\left\{ \begin{array}{rcl} i & & {当元素x=a_i∈L,且a_i是第一个与x相等时}\\ -1 & & {当x不属于L时}\\ \end{array} \right. Locate(L,x)={i1当元素x=aiL,且ai是第一个与x相等时x不属于L
7)插入:Insert(L,x,i)。将元素 x 插入到表 L 中第 i 个元素 ai 之前,且表长 +1。

线性表运算的实现

我们在实现时一般会写三个文件(顺序表):
1、sqlist.h 定义数据结构,定义线性表运算
2、sqlist.c 实现线性表运算
3、 test.c 实现实际功能,调 sqlist.h 接口
这样写的好处是:①结构清晰; ②代码复用性高:自己可以反复用,不管是现在的项目,还是以后的项目都可以用;同事也可以用。③给外包公司接口,实现部分给他们二进制 .so 文件,这样以后业务升级还找你

分文件编写以后怎么编译运行呢?

  • 可以一条一条的把 .c 汇编为 .o ,最后链接 .o 和 库文件 运行:
    例如:

    gcc -c sqlist.c -o sqlist.o
    
    gcc -c test.c -o test.o
    
    gcc test.o sqlist.o -o test
    
  • 利用简洁的命令进行编译执行:

    gcc *.c -o test
    
  • 利用 Makefile 进行编译

    SRC=sqlist.c
    SRC+=test.ctest:$(SRC)gcc $^ -o $@.PHONY:cleanclean:rm *.o
    

sqlist.c 中线性表运算具体实现

  • 创建顺序表 list_create()

    • 思路:
      1. 分配内存空间(一定要注意检查分配成功没有)
      2. 初始化
      3. 返回顺序表指针
    • 代码:
    sqlink list_create()
    {//mallocsqlink L;L = (sqlink)malloc(sizeof(sqlist));if(L == NULL){printf("list malloc failed!\n");return L;}//initmemset(L, 0, sizeof(sqlist));L->last = -1;//returnreturn L;
    }
    
  • 清空顺序表 list_clear(sqlink L)

    • 思路:
      1. 先检查表原来是否是空表(如果是空表的话清空也没啥意义)(有疑问??)
      2. 然后给表空间置0,给表尾元素挪到初始位置(-1)
    • 代码:
     int list_clear(sqlink L){if(L == NULL){printf("the list is null!\n");return -1;}memset(L, 0, sizeof(sqlist));L->last = -1;return 0;}
    
  • 判断顺序表是否为空表 list_empty(sqlink L)

    • 思路:
      1. 判断指针 L 是否为空,避免非法操作
      2. 判断表尾元素是否还在初始位置(-1),如果在初始位置证明是空表,返回 0,如果不是的话就返回 1
    • 代码:
    int list_empty(sqlink L)
    {if (L == NULL){printf("illegal operation!\n");return -1;}if (L->last == -1){return 0;}else{return 1;}
    }
    
  • 计算顺序表长度 list_length(sqlink L)

    • 思路:
      1. 判断指针 L 是否为空,避免非法操作
      2. 顺序表长度可以看作是表尾元素下标 + 1
    • 代码:
    int list_length(sqlink L)
    {if (L == NULL){return -1;}return (L->last + 1);
    }
    
  • 向顺序表中插入元素

    • 思路:
      1. 判断顺序表满不满,如果已经满了就不能再插入元素了
      2. 判断元素插入位置是否合法(插入位置不能小于下标 0 ,也不能大于顺序表末尾元素下标 L->last 的后一位)
      3. 如果以上两条都通过,那么开始新增元素,新增元素按照下图的箭头所示,依次从后往前的每个元素都向后移动一位给新增元素腾地方。比如插入元素位置在下标为 1 的地方,那么就先移动下标 4 的元素 9 到下标 5 ,然后移动下标 3 的元素 4 到 下标 4,······以此类推,把下标 1 的元素移动到下标 2 后,就可以进行下一步了
      4. 把要新增的值赋给数组的新增元素
      5. 末尾元素下标加一
        在这里插入图片描述
    • 代码:
    int list_insert(sqlink L, data_t value, int pos)
    {int i;if (L->last == N - 1){printf("the list is full!\n");return -1;}if (pos < 0 || pos > L->last + 1){printf("the insertion position is invalid\n");return -1;}for (i = L->last; i <= pos ; i--){L->data[i+1] = L->data[i];}L->data[pos] = value;L->last++;return 0;
    }
    
  • 打印顺序表 list_show(sqlink L)

    • 思路:
      1. 判断表指针 L 是否为空,避免非法操作
      2. 判断表尾元素是否在初始位置,给予空表提示
      3. 打印顺序表
    • 代码:
    int list_show(sqlink L)
    {int i;if (L == NULL){printf("invalid!\n");return -1;}if (L->last == -1){printf("the list is null!\n");return 0;}for (i = 0; i <= L->last; i++){printf("%d ", L->data[i]);}printf("\n");
    
  • 销毁顺序表 list_free(sqlink L) ,因为有时候程序并不能主动释放顺序表内存空间,一直占用内存会造成浪费

    • 思路:
      1. 判断表指针 L 是否为空,如果为空那么这个表就没有建立起来,也没必要销毁
      2. 释放 L 内存空间
      3. 把表指针 L 置空,不再让其指向这段已经被释放的内存空间
    • 代码:
    int list_delete(sqlink L)
    {if (L == NULL){printf("invalid!\n");return -1;}free(L);L = NULL;return 0;
    }    
    

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL全局优化与Mysql8.0新增特性

Mysql全局优化总结 ​ 从上图可以看出SQL及索引的优化效果是最好的&#xff0c;而且成本最低&#xff0c;所以工作中我们要在这块花更多时间。 补充一点配置文件my.ini或my.cnf的全局参数&#xff1a; 假设服务器配置为&#xff1a; CPU&#xff1a;32核内存&#xff1a;6…

vue+express、gitee pm2部署轻量服务器

一、代码配置 前后端接口都保持 127.0.0.1:3000 vue创建文件 pm2.config.cjs module.exports {apps: [{name: xin-web, // 应用程序的名称script: npm, // 启动脚本args: run dev, // 启动脚本的参数cwd: /home/vue/xin_web, // Vite 项目的根目录interpreter: none, // 告诉…

burpsuite+proxifier小程序抓包

burpsuiteproxifier小程序抓包 安装bp证书到系统 配置

推荐一款可以快速抽取sap数据的ETL工具

使用SAP在数据分析上面临的问题 SAP Enterprise Resource Planning (ERP) 是国内最广泛使用的ERP系统之一。然而&#xff0c;使用SAP ERP系统面临着一些数据分析不方便&#xff0c;数据导出困难等问题&#xff1a; 数据集成困难&#xff1a;将SAP中的数据整合到其他系统或本地…

局部变量,全局变量与内存

本文会使用IDA分析局部变量&#xff0c;全局变量在内存的存储 目录 使用IDA分析局部变量 使用IDA分析全局变量 总结 使用IDA分析局部变量 #include <stdio.h>int main() {int nNum 1;float fNum 2.5;char ch A;printf("int %d, float %f, char %c", nNu…

opencv dnn模块 示例(16) 目标检测 object_detection 之 yolov4

博客【opencv dnn模块 示例(3) 目标检测 object_detection (2) YOLO object detection】 测试了yolov3 及之前系列的模型&#xff0c;有在博客【opencv dnn模块 示例(15) opencv4.2版本dnn支持cuda加速&#xff08;vs2015异常解决&#xff09;】 说明了如何使用dnn模块进行cuda…

vue2中年份季度选择器(需要安装element)

调用 <!--父组件调用--><QuarterCom v-model"quart" clearable default-current/> 组件代码 <template><div><span style"margin-right: 10px">{{ label }}</span><markstyle"position:fixed;top:0;bottom:0…

路由器ip地址设置

当你使用路由器时&#xff0c;你可以按照以下步骤设置路由器的IP地址。这样可以确保你的网络连接正常并允许其他设备连接到你的路由器。 **步骤一&#xff1a;登录路由器管理界面** 首先&#xff0c;你需要登录到路由器的管理界面。打开你的浏览器&#xff0c;并输入路由器的…

本地Docker Registry远程连接,为你带来高效便捷的镜像管理体验!

Linux 本地 Docker Registry本地镜像仓库远程连接 文章目录 Linux 本地 Docker Registry本地镜像仓库远程连接1. 部署Docker Registry2. 本地测试推送镜像3. Linux 安装cpolar4. 配置Docker Registry公网访问地址5. 公网远程推送Docker Registry6. 固定Docker Registry公网地址…

ChatGLM Pytorch从0编写Transformer算法

预备工作 # !pip install http://download.pytorch.org/whl/cu80/torch-0.3.0.post4-cp36-cp36m-linux_x86_64.whl numpy matplotlib spacy torchtext seaborn import numpy as np import torch import torch.nn as nn import torch.nn.functional as F import math, copy, tim…

【漏洞复现】企望制造 ERP命令执行

漏洞描述 由于企望制造 ERP comboxstore.action接口权限设置不当&#xff0c;默认的配置可执行任意SQL语句&#xff0c;利用xp_cmdshell函数可远程执行命令&#xff0c;未经认证的攻击者可通过该漏洞获取服务器权限。 免责声明 技术文章仅供参考&#xff0c;任何个人和组织…

golang入门笔记——pprof性能分析

文章目录 简介runtime/pprof的使用命令行交互网络服务性能分析pprof与性能测试结合压测工具go-wrk 简介 golang性能分析工具pprof的8个指标 1.性能分析的5个方面&#xff1a;CPU、内存、I/O、goroutine&#xff08;协程使用情况和泄漏检查&#xff09;、死锁检测以及数据竟态…

ETHERCAT转MODBUS TCP/IP协议网关

产品介绍 JM-ECT-TCPIP是自主研发的一款EtherCAT从站功能的通讯网关。该产品主要功能是将EtherCAT网络和 TCP/IP 网络连接起来。 本网关连接到EtherCAT总线中做为从站使用&#xff0c;连接到 TCP/IP 网络中做为服务器或客户端使用。 产品参数 技术参数 u 网关做为EtherCAT网…

淘天集团联合爱橙科技开源大模型训练框架Megatron-LLaMA

9月12日&#xff0c;淘天集团联合爱橙科技正式对外开源大模型训练框架——Megatron-LLaMA&#xff0c;旨在让技术开发者们能够更方便地提升大语言模型训练性能&#xff0c;降低训练成本&#xff0c;并保持和LLaMA社区的兼容性。测试显示&#xff0c;在32卡训练上&#xff0c;相…

八、数据类型转换

数据类型转换 1.数据类型转换1.1.隐式类型转换1.2.显式类型转换1.3.训练11.4.训练2 —————————————————————————————————————————————————— 1.数据类型转换 类型转换是将一个值从一种类型更改为另一种类型的过程。例如&…

Haproxy负载均衡群集

HAproxy搭建Web群集一、Web集群调度器1、常见的Web集群调度器2、常用集群调度器的优缺点&#xff08;LVS ,Nginx,Haproxy)2.1 Nginx2.2 LVS2.3 Haproxy 3、LVS、Nginx、HAproxy的区别 二、Haproxy1、简介2、Haproxy应用分析3、HAProxy的主要特性4、Haproxy调度算法&#xff08;…

有了Spring为什么还需要SpringBoot呢

目录 一、Spring缺点分析 二、什么是Spring Boot 三、Spring Boot的核心功能 3.1 起步依赖 3.2 自动装配 一、Spring缺点分析 1. 配置文件和依赖太多了&#xff01;&#xff01;&#xff01; spring是一个非常优秀的轻量级框架&#xff0c;以IOC&#xff08;控制反转&…

命令提示符cmd查询IP地址ipconfig, linux 系统中查看ip地址ifconfig

1.windowR 2.输入cmd----》确定 3.在命令行中输入ipconfig然后按回车。IPv4地址就是电脑的IP地址。 linux系统中查看ip地址 &#xff1a; ifconfig

vue内置组件Transition的详解

1. Transition定义 Vue 提供了两个内置组件&#xff0c;可以帮助你制作基于状态变化的过渡和动画&#xff1a; <Transition>会在一个元素或组件进入和离开 DOM 时应用动画。 <TransitionGroup> 会在一个 v-for 列表中的元素或组件被插入&#xff0c;移动&#xff0…

使用企业订货系统的原因和考虑|网上APP订单管理软件

使用企业订货系统的原因和考虑|网上APP订单管理软件 企业要用订货系统主要如下原因&#xff1a; 第一、在线订货系统能让销售即时看到商品信息。商品售价多少&#xff0c;进货价多少&#xff0c;上次跟客户的成交价是多少&#xff0c;最低可以卖多少钱&#xff0c;用个本子记录…