首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >线性表的顺序存储结构

线性表的顺序存储结构

作者头像
Originalee
发布2018-08-30 10:25:07
8500
发布2018-08-30 10:25:07
举报
文章被收录于专栏:编程之旅编程之旅

顺序存储定义

今天来总结一下线性表的顺序存储结构。首先来看下顺序存储结构的定义。

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

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10个学生,连续的安排在教室的前两排之内,每个人都有自己的同桌,连续的10个座位,那么这10个学生所占用的就是一片连续的座位。相当于内存中有50个数据元素的空间,而10个学生只占用了中间的连续十个大小的空间。

因为线性表中,存储的数据元素的类型都相同,而存储空间又是连续的,那么我们可以用一维数组来实现线性表的存储结构。

因为班上一共有50个座位,所以蔺老师在安排座位时,也没必要一定从第一个座位开始安排,可以从第二排或者第三排来安排座位,选定座位之后,学生一个挨一个的坐进去就可以了。所以选定线性表时,在内存中找一块地,于是这块地的第一个位置就非常关键,它为存储空间的起始位置。

每天放学回家,蔺老师会要求这10个学生排队走出校门,而并不是每个学生每天都会上学,比如彤彤这样的学生,每天放学要去等蔺老师下班,那么队伍里可能只有九个人,而这九个人还是排成了一列,谁在前谁在后关系依旧很明确,只是少了彤彤而已。而这个例子,就表示了线性表一一对应的特点,就像排队,在整队的时候随着每天的放学排队,大家很清楚自己该出现在哪个位置。

顺序存储结构的代码

我们来看线性表顺序存储结构的结构代码:

#define MAXSIZE 10          //存储空间的初始化分配

typedef int ElementType;    //定义线性表元素数据类型 这里假设为int

typedef struct
{
    ElementType data[MAXSIZE];      //线性表存储数据元素
    
    int length;                     //线性表的长度
    
}SqList;

这里我们能看到顺序存储结构所需要的三个属性:

  • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置
  • 线性表的最大容量,数组长度MAXSIZE
  • 线性表的当前长度: length

我们对每个线性表位置的存入或取出的数据,对于计算机来说都是相等的时间,也就是一个常数。因此用上一次讨论的算法时间复杂度的概念来说,线性表的时间复杂度为O(1)。我们通常把具有这一特点的存储结构称为随机存储结构。

顺序存储结构的插入或删除

在讨论顺序存储结构的实现方式之前,我们先来定义一下函数运行的状态代码,用来返回线性表运行的状态。

/**
 *  函数运行的状态代码
 *
 *
 */
#define SUCCESS 1
#define ERROR   0

typedef int Status;  //状态代码的类型

这段代码我们定义了Status为状态代码的类型,返回SUCCESS代表1,返回ERROR代表0。本文之后的所有状态代码就不再详述了。

创建线性表(初始化)

在上面我们已经定义好了线性表的属性,并确定了线性表的最大存储容量,那么我们在刚开始时,对线性表进行初始化,创建一个线性表。

/**
 线性表的初始化 并分配存储单元
 
 - returns: SqList*
 */
SqList * initSqList()
{
    SqList * list = (SqList *)malloc(sizeof(SqList));
    
    list->length = 0 ;
    
    return list;
}

在这里我们还是用C语言来操作,创建了一张线性表,用malloc分配存储空间,定义当前线性表长度为0,最后返回值为本张线性表。

获得元素操作
//获取线性表中的元素
Status GetElem (SqList * L , int i , ElementType e)
{
    if (L->length == 0 || i < 1 || i > L->length ) {
        return ERROR;
    }
    
    e = L->data[i-1];
    return SUCCESS;
}

在获取元素的操作中呢,我们定义了一个e,用来返回L中第i个元素的值。

插入操作

在这里先不放代码,先来讨论一下线性表的插入概念。比如我在火车站排队等着取票,排了很久的队终于快轮到我了,这时候有一个很漂亮的姑娘过来,可怜兮兮的对我说:帅哥,我的车还有几分钟 就开了,能让我先取一下么。可能我会“以貌取人”,答应了这个漂亮姑娘的要求,于是这个姑娘排到了我的前面,可是我毕竟有女朋友,再加上男女授受不亲,我又不想回家跪键盘,于是我得往后退一步,让出一个空间给姑娘排在我前面,我后面的人也得跟着我的步伐往后退一步。这时候,就类似于线性表的插入算法的思路:

  • 如果插入的位置不合理,抛出异常
  • 如果线性表的长度大于数组长度,抛出异常或者动态增加存储空间
  • 从最后一个元素,向前遍历到第i个位置,分别将它们都向后移动一个位置。
  • 将要插入的元素插入到位置i
  • 表长+1

代码的话,我用了两种方式,一种是线性表以栈的方式加入数据元素,即为每一次都加在队列的最后面,一种是按照要求,添加到指定的位置中。

栈的方式插入数据元素的实现代码:

//线性表以栈的方式加入数据
Status pushElement(ElementType e, SqList * list)
{
    int length = list->length;
    if (length < 0 || length > MAXSIZE) {
        return ERROR;
    }
    
    list->data[length] = e;
    list->length++;
    
    return SUCCESS;
}

在指定位置插入数据元素的代码实现如下:

/**
 *  在线性表中的第i个位置插入之前新的元素数据e,线性表的长度+1
 *
 */
Status insertElementWithLocation(ElementType e, SqList * list, int i)
{
    int k;
    //判断线性表的存储空间是否已满
    if (list->length == MAXSIZE) {
        return ERROR;
    }
    
    //判断i的合理性
    if (i < 1 || i > list->length) {
        return ERROR;
    }
    
    //将要插入的位置后面的数据向后移动一位
    if (i <= list->length) {
        for (k = list->length - 1; k >= i-1; k--) {
            list->data[k+i] = list->data[k];
        }
    }
    
    list->data[i-1] = e;  //插入新元素
    list->length++;
    return SUCCESS;
    
}
删除操作

讲完了插入的概念以及实现,应该对删除操作的行为也有了理解,即为从指定位置,删除需要删除的元素。

所以删除算法的思路:

  • 如果删除位置不合理,抛出异常
  • 取出删除元素
  • 从删除元素开始,之后的元素至最后一个元素的存储位置向前挪动一个位置
  • 表长-1

我们同样用栈的删除模式和指定位置删除的模式来实现代码。

栈的方式删除元素,即为每次都删除最后一个元素的代码实现:

/**
 *  按照栈的方式删除元素 e用来接收删除出来的值
 */

Status popElement(ElementType e, SqList *list)
{
    int length = list->length;
    
    //判断线性表的合法性
    if (length < 0 || length > MAXSIZE) {
        return ERROR;
    }
    
    e = list->data[length - 1];
    list->length -- ;
    return SUCCESS;
}

在指定位置删除元素的代码实现如下:

/**
 *  在线性表中的第i个位置删除元素 线性表的长度减一
 */

Status deleteElementWithLocation(ElementType e, int i , SqList * list)
{
    //判断线性表的合法性
    if (list->length < 0 || list->length > MAXSIZE ) {
        return ERROR;
    }
    
    //判断删除位置的合法性
    if (i < 1 || i > list->length) {
        return ERROR;
    }
    
    e = list->data[i-1];
    
    if (i < list->length) {
        //将删除位置的后继元素前移
        for (int k = i; k < list->length; k++) {
            list->data[k-1] = list->data[k];
        }
    }
    
    list->length -- ;
    
    return SUCCESS;
}
遍历线性表

最后为了方便我们等下来验证代码的正确性,我们写一个函数来遍历线性表,代码如下:

/**
 *  遍历线性表
 */

Status displayList(SqList * list)
{
    if (list->length < 0 || list->length > MAXSIZE) {
        return ERROR;
    }
    
    printf("***************************\n");
    
    for (int i = 0; i < list->length; i++) {
        printf("数值 = %d , 地址 = %p\n",list->data[i], &list->data[i]);
    }
    printf("***************************\n");
    
    return SUCCESS;
}
验证代码正确性

在验证代码的正确性时,我用了Objective-C语言来写,大体思路如果是使用C语言的程序员,也是能完全看懂的。

我先创建了一个线性表,并且遍历它,打印地址来验证顺序结构存储空间的连续性。

 //把1-8按顺序入栈
        SqList * list = initSqList();

        NSLog(@"把1-8按顺序入栈");
        int j = 1;
        for (int i = 0; i <8  ; i++) {
            pushElement(j, list);
            ++j;
        }

        displayList(list);

因为存储空间总大小为10个元素单位,而我要求把1-8共8个数按顺序存入线性表中。打印结果如下:

***************************
数值 = 1 , 地址 = 0x1002014d0
数值 = 2 , 地址 = 0x1002014d4
数值 = 3 , 地址 = 0x1002014d8
数值 = 4 , 地址 = 0x1002014dc
数值 = 6 , 地址 = 0x1002014e0
数值 = 7 , 地址 = 0x1002014e4
数值 = 8 , 地址 = 0x1002014e8
***************************

我们可以看到,数值以及存储空间都是连续的,说明我们用栈的方式插入线性表是创建成功的。

我又要求往第八个位置插入724这个数字

        //往第8个位置插入724;
        
        insertElementWithLocation(724, list, 8);

运行结果如下,可以清楚的看到第八位是724,而原先的元素后移一位。

第八位增加724
***************************
数值 = 1 , 地址 = 0x100101320
数值 = 2 , 地址 = 0x100101324
数值 = 3 , 地址 = 0x100101328
数值 = 4 , 地址 = 0x10010132c
数值 = 5 , 地址 = 0x100101330
数值 = 6 , 地址 = 0x100101334
数值 = 7 , 地址 = 0x100101338
数值 = 724 , 地址 = 0x10010133c
数值 = 8 , 地址 = 0x100101340
***************************

验证删除操作的时候,我们命令把第五位的数据删除(以原始数据为例)

//        把第五位的数据删除
        deleteElementWithLocation(0, 5, list);

得到结果如下:

删除第五位
***************************
数值 = 1 , 地址 = 0x1002014d0
数值 = 2 , 地址 = 0x1002014d4
数值 = 3 , 地址 = 0x1002014d8
数值 = 4 , 地址 = 0x1002014dc
数值 = 6 , 地址 = 0x1002014e0
数值 = 7 , 地址 = 0x1002014e4
数值 = 8 , 地址 = 0x1002014e8
***************************

至此,我们可以得出结论我们创建的线性表是正确的,连续的,具备线性表的属性的。而我们在对线性表的顺序存储结构的插入和删除的操作也是正确的,实现了功能。所以今天的线性表的顺序存储结构,就讲到这里,以上代码我已经上传到Github上,若有讲的不清楚的地方,也可以下载Github上的代码来参考。

线性表的顺序存储结构Demo

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016.03.21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 顺序存储定义
  • 顺序存储结构的代码
  • 顺序存储结构的插入或删除
    • 创建线性表(初始化)
      • 获得元素操作
        • 插入操作
          • 删除操作
            • 遍历线性表
              • 验证代码正确性
              相关产品与服务
              对象存储
              对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档