数据结构篇——线性表

ops/2025/3/16 23:23:02/

一、引入


        线性结构是数据结构中最为重要的一种数据存储结构之一,同时也是其他数据结构的基础。今天我们就来学学数据结构中的一种基础类型——线性表。

二、线性表的定义和特点


        线性表的定义:用数据元素的有限序列表示。具体情况如下图所示:

        在日常生活中 ,线性表的例子比比皆是,例如,26个英文字母的字母表:

(A,B,C,D.......,Z)

线性表的几个特点如下:

①只有一个首结点和尾结点;

② 除首尾结点外,其他结点只有一个直接前驱和一个 直接后继。

        Tips:线性结构反映结点间的逻辑关系是 一对一 的。线性结构包括线性表、堆栈、队列、字符串、数组等。

三、线性表的顺序表示和实现


线性表的顺序表示又称为顺序存储结构,在这里,我们就要先了解以下两个概念了:

        顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。(逻辑上相邻,物理上也相邻)。

        顺序存储方法:用一组地址连续的存储单元依次存储 线性表的元素,可通过数组V[n]来实现。 

顺序表的类型定义 :

        基本类型的定义:构建出顺序表的基础架构,分别有最大长度、指向首地址的指针、记录长度的变量等组成元素。

#define  MAXSIZE 100     //最大长度
typedef  struct {ElemType *elem;     //指向数据元素的首地址int  length;         //线性表的当前长度
}SqList;

       下面用一个图书表的顺序存储结构类型定义来作为例子展示顺序表定义的步骤与效果:

#define MAXSIZE 10000     //图书表可能达到的最大长度
typedefstruct     //图书信息定义
{ char no[20];     //图书ISBNchar name[50];     //图书名字float price;     //图书价格
}Book;         //数据元素的类型定义typedefstruct{ Book*elem;     //存储空间的基地址int length;     //图书表中当前图书个数
}SqList;     //图书表的顺序存储结构类型为SqList

四、线性表的重要基本操作与算法实现 


4.1、 初始化线性表L


        线性表的初始化和一般数据类型的初始化相似,在构建该数据结构的时候得先进行空间分配、赋值等操作。在这其中我们要先了解这样一个自定义函数类型——Status。

        Status是用户自定义的一种函数类型,其基础架构和功能与bool类型相似,只是在返回值上做出了些改变。例如:

为了方便直观的表示算法,常用Status类型来封装。例如下面对线性表L的初始化操作:

Status InitList_Sq (SqList &L)
{    //构造一个空的顺序表LL.elem=new ElemType[MAXSIZE];   //为顺序表分配空间if(!L.elem){exit(OVERFLOW);      //存储分配失败}L.length=0;    //空表长度为0   return OK;
}

4.2、取值(根据位置i获取相应位置数据元素的内容) 


        取值操作主要用来获取线性表L中的某个数据元素的内容:

int GetElem(SqList L, int i, ElemType &e)
{if (i<1||i>L.length){return ERROR;     //判断i值是否合理,若不合理,返回ERROR}e=L.elem[i-1];     //第i-1的单元存储着第i个数据return OK;
}

4.3、查找(根据指定数据获取数据所在的位置) 


        由于涉及到指针操作,所以下面给出一个示意图来帮助大家理解:

        如果想要在线性表L中查找值为e的数据元素,用代码该如何表示呢?

代码描述:

int LocateELem(SqListL, ElemTypee){for (i=0;i< L.length;i++){if (L.elem[i]==e){ return i+1;                }}return 0;}

 4.4、插入(在第i个位置上插入)


        算法示意图表示:

【算法步骤】:

  1. 判断顺序表的存储空间是否已满,满了就不能插入新元素了。
  2. 判断插入位置i 是否合法。[1, L.length+1]
  3. 将第n至第i 位的元素依次向后移动一个位置,空出第i个位置。
  4. 将要插入的新元素e放入第i个位置。
  5. 表长加1,插入成功返回OK。 

若想在线性表L中第i个数据元素之前插入数据元素e ,也就是成 为第i个元素,用代码做如下操作:

Status ListInsert_Sq(SqList &L, int i , ElemType e)
{if(i<1 || i>L.length+1){return ERROR;      //i值不合法  }         if(L.length==MAXSIZE){     return ERROR;    //当前存储空间已满}for(j=L.length-1; j>=i-1; j--){   //L.length-1是最后一个元素, i-1是第i个元素L.elem[j+1]=L.elem[j];    //插入位置及之后的元素后移}L.elem[i-1]=e; //将新元素e放入第i个位置             ++L.length;//表长增1return OK;
}

Tips:线性表的长度为L.length,j=L.length-1 因为数组的下标从0开始 。

4.5、删除(删除第i个结点)


算法示意图表述:

【算法步骤】:

  1. 判断表是不是空(L.length=0 )。
  2. 判断删除位置i 是否合法(合法值为1≤i≤n)。
  3. 将欲删除的元素保留在e中。
  4. 将第i+1至第n 位的元素依次向前移动一个位置。
  5. 表长减1,删除成功返回OK。 

代码描述将线性表L中第i个数据元素删除:

Status ListDelete_Sq (SqList &L, int i)
{if(L.length==0){return ERROR; //表为空}if((i<1)||(i>L.length)) return ERROR; //i值不合法}    for (j=i; j<=L.length-1;j++){                   L.elem[j-1]=L.elem[j];     //被删除元素之后的元素前移--L.length;         //表长减1 }     
return OK;
}

4.6、其他操作:


清空线性表:

void ClearList(SqList&L) 
{L.length=0;                //将线性表的长度置为0
}

求线性表L的长度:

intGetLength(SqListL){return (L.length);             
}

求线性表是否满了:

intGetLength(SqListL){if(L.length==MAXSIZE){     return 1;}else{ return 0;}}

判断线性表L是否为空:

intIsEmpty(SqListL){if (L.length==0){ return 1;    }  else{ return 0;}}

   至此。关于线性表的基本学习我们就已经完成的差不多了。 如果我的内容对你有帮助,在下就厚着脸皮讨个点赞关注。如果你有更好的想法,还望留在评论区让我来参考学习。我将不胜感激并努力创作出更好的内容。


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

相关文章

HarmonyOS学习第20天:让应用“找准方向”的地图与定位秘籍

引言&#xff1a;开启 HarmonyOS 应用的位置感知之旅 在这个信息爆炸的时代&#xff0c;我们的生活与地理位置信息紧密相连。无论是寻找一家心仪的餐厅&#xff0c;规划一次完美的旅行&#xff0c;还是追踪快递的实时位置&#xff0c;地图与定位服务都扮演着至关重要的角色。对…

idea maven 编译报错Java heap space解决方法

1.增加 Maven 编译的堆内存 我是用这个方法修改成功的 Maven 编译时使用的 JVM 堆内存可以通过设置 MAVEN_OPTS 环境变量来调整。 在 IntelliJ IDEA 中设置&#xff1a; 打开 IntelliJ IDEA 的设置&#xff08;File -> Settings 或 Ctrl Alt S&#xff09;。 导航到 Bui…

【DevOps】Backstage介绍及如何在Azure Kubernetes Service上进行部署

【DevOps】Backstage介绍及如何在Azure Kubernetes Service上进行部署 推荐超级课程: 本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录 【DevOps】Backstage介绍及如何在Azure Kubernetes Service上…

MySQL小练习

要求&#xff1a; 新建产品库mydb6_product&#xff0c;新建4张表如下&#xff1a; oemployees表 列1&#xff1a;id&#xff0c;整型&#xff0c;主键 列2&#xff1a;name&#xff0c;字符串&#xff0c;最大长度50&#xff0c;不能为空 列3&#xff1a;age&#xff0c;整型 …

【Go学习】04-3-Gorm框架-初识模型定义

【Go学习】04-3-Gorm框架-初识模型定义 初识Gorm创建工作区数据准备操作数据 模型定义模型定义模型标签表名映射Model数据库连接DSN连接数据库调试模式连接池配置 初识Gorm gorm地址&#xff1a;https://github.com/go-gorm/gorm 对开发者友好的gorm库&#xff0c;目前使用最…

Node.js REPL 深入解析

Node.js REPL 深入解析 引言 Node.js 作为一种流行的 JavaScript 运行环境,在服务器端开发中扮演着重要角色。REPL(Read-Eval-Print Loop,读取-求值-打印循环)是 Node.js 的一个核心特性,它允许开发者在一个交互式环境中执行 JavaScript 代码。本文将深入探讨 Node.js R…

DeepSeek 助力 C++ 开发:探索智能编程新境界

这篇文章就会详细讲讲 DeepSeek 在 C 开发里到底能怎么用&#xff0c;从上面说的写代码、找错误、优化性能&#xff0c;到管理项目这些方面&#xff0c;还会给出好多实际的代码例子&#xff0c;讲讲实际用起来是啥情况。目的就是给那些做 C 开发的人&#xff0c;一份全面又详细…

IDEA Reformat Code 避免将多行参数或多行方法链调用合并成一行

在 IntelliJ IDEA 中&#xff0c;如果你希望在进行代码格式化&#xff08;Reformat Code&#xff09;时&#xff0c;避免将多行参数或多行方法链调用合并成一行&#xff0c;可以通过以下步骤进行设置&#xff1a; 1. 打开设置 在 IntelliJ IDEA 中&#xff0c;点击 File 菜单…