首页 > 其他分享 >顺序表的实现和操作

顺序表的实现和操作

时间:2024-07-26 18:27:48浏览次数:14  
标签:顺序 实现 元素 int length SqList 操作 define

目录

一.前言

二. 顺序表的优缺点

三. 顺序表的定义和初始化

四.顺序表的相关操作


一.前言

        首先介绍下线性表的定义,线性表是具有相同特性的数据元素的一个有限序列。而我们的顺序表就是线性表的一种,是线性表的顺序存储结构。所谓顺序存储就是把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

二. 顺序表的优缺点

        顺序表的优点就是能够以物理位置相邻表示逻辑关系,任一元素均可随机存取。原因就在于它占用一片连续的存储空间。并且知道了其中第一个元素的存储位置之后,就能得到其它数据元素的存储位置。如下所示:

        

 

但它也同样存在一些缺点问题:首先第一个就是存储空间分配的不灵活,第二个就是运算的空间复杂度高。也就是说,如果我要找的数据元素在最后一位,它就要从开头一直查找到最后一位。为了解决上面这些问题,我们可以使用链式存储,现在我们主要学习顺序存储。

三. 顺序表的定义和初始化

        我们可以知道,顺序表中的每个位置都存储了对应的数据结构,因此我们在定义顺序表的时候,就要包含两个因素,一个是顺序表实际占用的长度。另外一个就是对应长度上存储的数据。如下所示即为我们顺序表的定义:

#define LIST_INIT_SIZE 100   //定义整个线性表存储空间的初始分配量
    
typedef struct{              //定义一个结构体类型
    ElemType elem[LIST_INIT_SIZE];       //用来存储数据
    int length;                //顺序表实际当前的长度
}SqList;               //起一个别名,命名为SqList

  在得到了顺序表的定义之后,我们还得用它来修饰一个变量名,再对这个进行初始化或者赋值。就像C语言中的数据类型一样,知道了数据类型,还得用它来修饰变量并给变量进行赋值等相关操作。我们定义一个顺序表就是SqList L。表示L就是SqList类型的顺序表。

下面我们来了解下顺序表的初始化:

#define MAXSIZE 100
#define OVERFLOW -2
#define OK 1
typedef int Status;
typedef char ElemType;

int InitList_Sq(SqList &L){
    L.elem=new ElemType[MAXSIZE];    //为顺序表分配空间
    if(!L.elem) exit(OVERFLOW);      //分配空间失败,则退出并返回OVERFLOW对应的数值,也就是-2
    L.length=0;        //空顺序表里面没有元素,实际长度也就为0;
    return OK;        
}

值得注意的是:这里面形参的格式为SqList &L表示的是我们数据结构使用类C语言的一种参数引用形式,表示直接修改顺序表L中的数据,而不是单单的一个数据。以后一出现&都表示引用。

其中的MAXSIZE和OVERFLOW以及OK都是代表着某个数字,在函数的开头有声明。其中的Status和ElemType也都表示一种数据类型。为了后面操作的方便,我在这里全部列举出来,如下所示:

//定义函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

//再定义两个函数类型
typedef int Status;
typedef char ElemType;

四.顺序表的相关操作

1.顺序表的取值

如下所示,顺序表的取值就是根据位置i来获取相应位置数据元素的内容。

Status 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个数据,并通过e返回取值结果
    return OK;
}

2. 顺序表的查找

如下所示,顺序表的查找就是在线性表中查找值为e的数据元素,并返回其序号(是第几个元素)。

Status LocateElem(SqList L,ElemType e){
    for(int i=0;i<L.length;i++){
        if(L.elem[i]==e) return i+1;   //查找成功则返回它的序号,是第几个元素
     }
    return 0;        //上面查找失败,则返回0
}

3.  顺序表的插入

如下所示,顺序表的插入运算就是在表的第i个位置上,插入一个新结点e,使长度为n的顺序表变成长度为n+1的顺序表。值得注意的是,需要先判断插入位置是否合法。

Status ListInsert_Sq(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1) return ERROR; //插入的位置i不合法的情况,就返回ERROR
    if(L.length==MAXSIZE) return ERROR; //当前顺序表的存储空间已经满了,也是不能存储的
    for(int j=L.length-1;j>=i=1;j--){
         L.elem[j+1]=L.elem[j];         //将要插入的位置及之后的元素都进行后移操作
    }
L.elem[i-1]=e;                    //将新的元素e放入第i个位置
L.length++;                  //顺序表的表长加一
return OK;
}

4. 顺序表的删除

如下所示,顺序表的删除就是删除顺序表中第i个元素,并且将被删除元素的后面元素都前移,保证顺序表存储空间的连续性。

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

 

        

         

      

 

 

 

        

标签:顺序,实现,元素,int,length,SqList,操作,define
From: https://blog.csdn.net/2303_78660417/article/details/140708601

相关文章

  • 单链表的实现和操作
    目录一.前言二.单链表的定义和结构三.单链表的操作一.前言    线性表的链式表示又称为非顺序映像或链式映像。简而言之,链表可以理解为由指针链连接的n个结点组成的。其中每一个结点包括数据域和指针域。值得注意的是,与顺序表不同,链表中的逻辑次序与物理次序不......
  • es6中对数组的常用操作方法-普通数组
    参考https://www.jianshu.com/p/856f4200d3c0最近,经常操作数组,可是数组中的一些常用操作方法很迷糊,看了上面一篇文章之后,茅塞顿开。于是自己按照上面文章的用法,自己全部从头到尾写了一遍,分为普通的数组以及对象数组的操作。//定义数组constarr=[1,2,3,4,5]......
  • es6中对数组的常用操作方法-对象数组
    //定义对象数组constarrayObject=[{name:'name1',title:'title1'},{name:'name2',title:'title2'},{name:'name3',title:'title3'}];//数组对象......
  • 限时10分钟,你会怎么实现这段async/await代码?
    ......
  • GraalVM 静态编译下 OTel Java Agent 的自动增强方案与实现
    作者:望陶、铖朴随着OpenTelemetry在可观测领域影响力的不断提升,其项目以极快的速度不断演进。阿里云作为国内最广泛使用Java的厂商之一,深度参与OTelJava Instrumentation演进与社区活动,贡献、Review各类PR(pullrequest)合计超过100 余个,参与Issues讨论58个,在Op......
  • 实战篇-FPGA实现RGMII数据接收
        RGMII时序        前面讲到关于关于ARP的理论知识,该章节主要通过FPGA接收以太网数据,并作数据分析。    首先关于以太网RGMII接收时序如下图所示:                                 ......
  • 二叉树及其存储实现C语言(附上源码)
    1.什么是二叉树        二叉树是一种特殊的树型结构,其特点是每个结点至多只有两棵子树(即二叉树不存在度大于二的结点),并且二叉树的子树有左右之分,次序不可颠倒【有序树】。 2.二叉树的定义二叉树T:一个有穷的结点集合。    -这个集合可以为空;    -......
  • Nginx服务器无法实现伪静态化,在后台设置不成功
    错误提示:Nginx服务器无法实现伪静态化,在后台设置不成功解决方案:这主要是nginx的rewrite没有设置导致的在nginx.conf里找到网站的server配置段,一般我们推荐如下的配置     server {        listen          80;        server_name   ......
  • Python Selenium 操作链可以工作,但会停止我在 Firefox 中的程序
    我有时使用ActionsChains时遇到任何问题,今天它不起作用,你知道为什么吗?scrolling_bar=driver.find_element(By.CSS_SELECTOR,"#scrolling_bar")start=scrolling_bar.locationActionChains(driver)\.drag_and_drop_by_offset(scrolling_bar,start......
  • 操作系统杂项(十)
    目录一、简述socket中select、epoll的使用场景和区别1、使用场景2、区别二、epoll水平触发和边缘触发的区别三、简述Reactor和Proactor模式1、Reactor2、Proactor3、区别四、简述同步和异步的区别,阻塞和非阻塞的区别1、同步与异步2、阻塞与非阻塞五、简述BIO和NIO......