线性表的顺序存储结构

顺序存储定义

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

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

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一枝花算不算浪漫

HashMap中的resize以及死链的情况

451120
来自专栏desperate633

LintCode 简化路径题目分析代码

思路比较简单,遇到..就回到上一级,遇到.或者空就不处理。 我们使用一个队列来处理,同时将三个需要特殊处理的字符存到一个set里面

7710
来自专栏趣学算法

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出:数据结构+算法=程序。数据结构是程序的骨架,算法则是程序的灵魂。

10830
来自专栏专注研发

哈夫曼树【最优二叉树】【Huffman】

        在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率。例如,编制一个程序,将百分制转换成五个等级输出。大家...

32510
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

48570
来自专栏mySoul

java队列

队列为特殊的线性表,队列的特点先进先出(FIFO),队列插入为入队,队列删除为出对。

31400
来自专栏企鹅号快讯

什么是B+Tree

推荐阅读 微服务: springboot系列教程学习 源码:Javaweb练手项目源码下载 调优:十五篇好文回顾 面试笔试:面试笔试整理系列 B+Tree的定义...

24460
来自专栏Java技术栈

java程序员被误导的一个概念,90%人不知道

我们经常听说List是有序且重复的,Set是无序不重复的。这里有个误区,这里说的顺序有两个概念,一是按添加的顺序排列,二是按自然顺序a-z排列。Set并不是无序...

34460
来自专栏owent

AC自动机

整个程序的算法思想是看别人的ACM的blog看懂的,感觉确实和KMP很像。但是代码呢就比较工程化一点。顺便回忆了一把ACM的感觉。

9910
来自专栏noteless

【JAVA集合框架一 】java集合框架官方介绍 Collections Framework Overview 集合框架总览 翻译 javase8 集合官方文档中文版

https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html

8820

扫码关注云+社区

领取腾讯云代金券