您当前的位置:首页 > 电脑百科 > 数据库 > 百科

线性表的顺序存储结构

时间:2021-03-03 09:51:59  来源:  作者:

1. 线性表的定义

线性表:零个或者多个数据元素的有限序列。

线性表元素的个数n(n≥0)定义为线性表的长度,当n=0时,称为空表。

对于一个非空的线性表或者线性结构,具有以下特点:

  • 存在唯一的一个被称作“第一个”的数据元素。
  • 存在唯一的一个被称作“最后一个”的数据元素。
  • 除了第一个外,结构中的每个数据元素都有一个前驱。
  • 除了最后一个外,结构中的每个数据元素都有一个后继。

2. 线性表的顺序存储结构

2.1 顺序存储定义

线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构

 

线性表顺序存储结构代码如下:

#define MAXSIZE 100
#define OK 1~~~~
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* ElemType类型根据实际情况而定,这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/
//顺序表结构设计
typedef struct {
    ElemType *data; // 数组存储数据元素,最大值为MAXSIZE。
    int length; // 线性表当前长度
}Sqlist;

2.2 顺序存储结构常用操作

2.2.1 顺序表初始化

//1.1 顺序表初始化
Status InitList(Sqlist *L){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data =  malloc(sizeof(ElemType) * MAXSIZE);
    //存储分配失败退出
    if(!L->data) exit(ERROR);
    //空表长度为0
    L->length = 0;
    return OK;
}

2.2.2 顺序表插入与删除

插入算法实现思路:

  1. 如果插入位置不合理,抛出异常。
  2. 如果线性表长度大于等于数组长度,则抛出异常或者动态增加容量。
  3. 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置。
  4. 将要插入的元素填入到第i位置。
  5. 表长度加1。
线性表的顺序存储结构

 

代码实现如下:

/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
 */
Status ListInsert(Sqlist *L,int i,ElemType e){
    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;
    //存储空间已满
    if(L->length == MAXSIZE) return ERROR;
    //插入数据不在表尾,则先移动出空余位置
    if(i <= L->length){
        for(int j = L->length-1; j>=i-1;j--){
            //插入位置以及之后的位置后移动1位
            L->data[j+1] = L->data[j];
        }
    }
    //将新元素e 放入第i个位置上
    L->data[i-1] = e;
    //长度+1;
    L->length++;
    return OK;
}

删除算法实现思路:

  1. 如果删除位置不合理,抛出异常。
  2. 取出删除元素。
  3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置。
  4. 表长度减1。
线性表的顺序存储结构

 

代码实现如下:

/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1。
 */
Status ListDelete(Sqlist *L,int i){
    //线性表为空
    if(L->length == 0) return ERROR;
    //i值不合法判断
    if((i<1) || (i>L->length)) return ERROR;
    for(int j = i; j < L->length; j++){
        //被删除元素之后的元素向前移动
        L->data[j-1] = L->data[j];
    }
    //表长度-1;
    L->length--;
    return OK;
}

2.2.3 顺序表其他操作

1. 获取指定位置的元素

//获取指定位置的元素
Status GetElem(Sqlist L,int i, ElemType *e){
    //判断i值是否合理, 若不合理,返回ERROR
    if(i<1 || i > L.length) return  ERROR;
    //data[i-1]单元存储第i个数据元素.
    *e = L.data[i-1];
    return OK;
}

2. 清空顺序表

// 初始条件:顺序线性表L已存在。操作结果:将L重置为空表 
Status ClearList(Sqlist *L)
{
    L->length=0;
    return OK;
}

3. 判断顺序表是否为空表

/* 初始条件:顺序线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
Status ListEmpty(Sqlist L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

4. 获取顺序表长度

//获取顺序表长度即元素个数 */
int ListLength(Sqlist L)
{
    return L.length;
}

5. 顺序输出顺序表

//顺序输出List
/* 初始条件:顺序线性表L已存在 */
/* 操作结果:依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%dn",L.data[i]);
    printf("n");
    return OK;
}

2.3 线性表顺序存储结构的优缺点

优点:

  • 无需为表示表中元素之前的逻辑关系增加额外的存储空间。
  • 可以快速地存取表中任一位置的元素。

缺点:

  • 插入和删除元素操作需要移动大量的元素。
  • 当线性表长度变化较大时,难以确定存储空间的容量。
  • 造成存储空间的“碎片”。


Tags:线性表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 线性表  点击:(94)  评论:(0)  加入收藏
1. 线性表的定义线性表:零个或者多个数据元素的有限序列。线性表元素的个数n(n&ge;0)定义为线性表的长度,当n=0时,称为空表。对于一个非空的线性表或者线性结构,具有以下特点: 存...【详细内容】
2021-03-03  Tags: 线性表  点击:(163)  评论:(0)  加入收藏
存储结构查找表为线性表,其存储结构为一维结构数组,也即是顺序表,数组的每一个元素对应查找表的一个记录。为简单起见,设记录中只有一个整数关键字,存放记录的结构体类型描述如下...【详细内容】
2019-07-03  Tags: 线性表  点击:(741)  评论:(0)  加入收藏
▌简易百科推荐
1增1.1【插入单行】insert [into] <表名> (列名) values (列值)例:insert into Strdents (姓名,性别,出生日期) values (&#39;开心朋朋&#39;,&#39;男&#39;,&#39;1980/6/15&#3...【详细内容】
2021-12-27  快乐火车9d3    Tags:SQL   点击:(1)  评论:(0)  加入收藏
最近发现还有不少做开发的小伙伴,在写存储过程的时候,在参考已有的不同的写法时,往往很迷茫, 不知道各种写法孰优孰劣,该选用哪种写法,以及各种写法的优缺点,本文以一个简单的查询...【详细内容】
2021-12-23  linux上的码农    Tags:sql   点击:(9)  评论:(0)  加入收藏
《开源精选》是我们分享Github、Gitee等开源社区中优质项目的栏目,包括技术、学习、实用与各种有趣的内容。本期推荐的HasorDB 是一个全功能数据库访问工具,提供对象映射、丰...【详细内容】
2021-12-22  GitHub精选    Tags:HasorDB   点击:(5)  评论:(0)  加入收藏
作者丨Rafal Grzegorczyk译者丨陈骏策划丨孙淑娟【51CTO.com原创稿件】您是否还在手动对数据库执行各种脚本?您是否还在浪费时间去验证数据库脚本的正确性?您是否还需要将...【详细内容】
2021-12-22    51CTO  Tags:Liquibase   点击:(3)  评论:(0)  加入收藏
场景描述:由于生产环境的表比较复杂,字段很多。这里我们做下简化,只为说明今天要聊的问题。有两张表 tab1,tab2: tab1 数据如下: tab2 数据如下: 然后给你看下,我用来统计 name=&#3...【详细内容】
2021-12-20  Bald    Tags:SQL   点击:(5)  评论:(0)  加入收藏
前言知识无底,学海无涯,知识点虽然简单,但是比较多,所以将MySQL的基础写出来,方便自己以后查找,还有就是分享给大家。一、SQL简述1.SQL的概述Structure Query Language(结构化查...【详细内容】
2021-12-16  谣言止于独立思考    Tags:SQL基础   点击:(13)  评论:(0)  加入收藏
前言作为一名测试工程师,工作中在对测试结果进行数据比对的时候,或多或少要和数据库打交道的,要和数据库打交道,那么一些常用的 SQL 查询语法必须要掌握。最近有部分做测试小伙...【详细内容】
2021-12-14  柠檬班软件测试    Tags:SQL   点击:(15)  评论:(0)  加入收藏
话说C是面向内存的编程语言。数据要能存得进去,取得出来,且要考虑效率。不管是顺序存储还是链式存储,其寻址方式总是很重要。顺序存储是连续存储。同质结构的数组通过其索引表...【详细内容】
2021-12-08  小智雅汇    Tags:数据存储   点击:(17)  评论:(0)  加入收藏
概述DBConvert Studio 是一款强大的跨数据库迁移和同步软件,可在不同数据库格式之间转换数据库结构和数据。它将成熟、稳定、久经考验的 DBConvert 和 DBSync 核心与改进的现...【详细内容】
2021-11-17  雪竹聊运维    Tags:数据库   点击:(26)  评论:(0)  加入收藏
一、前言 大家好,我是小诚,《从0到1-全面深刻理解MySQL系列》已经来到第四章,这一章节的主要从一条SQL执行的开始,由浅入深的解析SQL语句由客户端到服务器的完整执行流程,最...【详细内容】
2021-11-09  woaker    Tags:SQL   点击:(35)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条