美文网首页数据结构与算法
线性表(一)——顺序表

线性表(一)——顺序表

作者: 风紧扯呼 | 来源:发表于2020-01-19 21:27 被阅读0次

在前一篇文章中我们讲解了线性表的定义以及线性表的特性,知道了线性表的两种存储结构:一种是顺序存储结构,一中是链式存储结构。本文将分析讨论线性表顺序存储结构的实现。

线性表-概述
线性表(一)——顺序表
线性表(二)——单链表的表示和实现
线性表(三)——双向链表的表示和实现

1、顺序表的存储结构

顺序表是线性表中的一种,顺序存储结构的线性表称作顺序表。实现顺序存储结构的方式是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中,这样线性表中逻辑相邻的数据元素在物理存储地址上也是相邻的。数组有静态数组和动态数组两种,不同之处在于前者的存储空间的申请和释放是由系统自动完成的,后者的存储空间的申请和释放是由用户通过调用系统函数自己完成的。不管是静态数组还是动态数组,其功能都是向系统申请一块连续地址的有限空间,只是申请空间的方式不同而已。本文主要讨论静态数组方法实现的顺序表。
如下图所示是顺序表的存储结构示意图。其中a_0,a_1,a_2,···a_{MaxSize-1}表示顺序表中存储的数据元素,list表示用于存储顺序表数据元素的数组,MaxSize表示数组list的最大存储个数,size表示顺序表当前存储数据元素的个数。

用C语言描述上图所示的结构,定义如下:

typedef struct {
    DateType list[MaxSize];
    int size;
}SeqList;

其中DateType表示数据元素的数据类型,MaxSize表示数组的最大容量,list表示顺序表的数组成员,size表示顺序表中当前存储的数据元素的个数,且必须满足size\leqMaxSize。

2、顺序表的操作实现

2.1 初始化ListInitiate(L)

/*初始化列表*/
void ListInitiate(SeqList *L) {
    L->size = 0;
}

2.2 获取顺序表长度ListLength(L)

/*获取列表的长度*/
int ListLength(SeqList L) {
    return L.size;
}

2.3 插入数据ListInsert(L,index,x)

在顺序表L的第index(0\leq index \leq size)个位置前插入数据元素值x,插入成功返回1,插入失败返回0。

/*
 * 插入元素
 * */
int ListInsert(SeqList *L, int index, DataType x) {
    if (L->size >= MaxSize) {
        printf("顺序表结构数据已满");
        return 0;
    } else if (index < 0 || index > L->size) {
        printf("插入数据的位置不合法");
        return 0;
    } else {
//        从后向前依次后移数据,为插入数据做准备
        for (int i = L->size; i > index; i--) {
            L->list[i] = L->list[i - 1];
        }
        L->list[index] = x;//插入x
        L->size++;//元素的个数添加1
        return 1;
    }
}

从上面的程序看,在index正确的前提下,首先把存储单元size-1至存储单元为index中的数据元素依次后移,然后把数据元素x插入到存储单元index中,最后把数据元素个数加1。这个操作称做是前插入,即在顺序表的第index个位置前插入数据元素,还可以有后插入操作,即在顺序表的第index个位置后插入数据元素。

2.4 删除数据ListDelete(L,index,x)

删除顺序表L的第index(0\leq index \leq size-1)个位置上的数据元素并保存到x中,删除成功返回1,删除失败返回0。

int ListDelete(SeqLsit *L, int index, DataType *x) {

    if (L->size <= 0) {
        printf("顺序表中已经没有可以删除的元素");
        return 0;
    } else if (index < 0 || index > L->size - 1) {
        printf("删除数据的位置不合法");
        return 0;
    } else {
        *x = L->list[index];
        for (int i = index + 1; i <= L->size - 1; i++) {
            L->list[i - 1] = L->list[I];
        }
        L->size--;
        return 1;
    }
}

当顺序表非空且参数index正确时,首先把存储单元index中的数据元素存放到x中,然后从前向后依次千亿从存储位置index到存储位置size-1中的数据元素,最后把数据元素个数减1。

2.5 取数据元素ListGet(L,index,x)

取顺序表L中第index个数据元素存与x中,成功返回1,失败返回0。

int ListGet(SeqLsit *L, int index, DataType *x) {
    if (index < 0 || index > L->size - 1) {
        printf("数据的位置不合法");
        return 0;
    } else {
        *x = L->list[index];
        return 1;
    }
}

2、顺序表的操作效率

从上面的分析来看,顺序表的插入和删除是顺序表中时间复杂度最高的操作。在顺序表中插入一个数据元素时,算法中时间复杂度最高的操作是循环移动数据元素。循环移动数据元素的效率和插入数据元素位置i有关,最坏情况是i=0,需移动size个数据元素;最好的情况是i=size,需要移动0个数据元素。设P_i是在第i个位置插入一个数据元素的概率,设顺序表中的数据元素个数为n,当顺序表的任何位置上插入数据元素的概率相等时,有P_i=1/(n+1),则像顺序表插入一个数据元素需要移动的数据元素的平均次数为:
E_{is} = \sum\limits_{i=0}^n P_{i}(n-i) = \frac{1}{n+1} \sum\limits_{i=0}^n (n-i) = \frac{n}{2}

从顺序表中删除一个数据元素时,算法中时间复杂度最高的操作也是循环移动数据元素。循环移动数据元素的效率与删除数据元素的位置i有关,最坏的情况是i=0,需要移动size-1个数据元素;最好的情况是i=size,需要移动0个数据元素。设q_i是删除第i个位置数据元素的概率,设顺序表的数据元素个数为n,当删除顺序表任何位置上数据元素的概率相等时,有q_i=1/n,则删除顺序表任意位置数据元素所需要移动数据元素的平均次数为:
E_{dl} = \sum\limits_{i=0}^{n-1} q_{i}(n-i) = \frac{1}{n} \sum\limits_{i=0}^{n-1} (n-i) = \frac{n-1}{2}

根据上面的分析可知,在顺序表中插入和删除一个数据元素的平均时间复杂度为O(n)
顺序表的其他操作与数据元素的个数n无关,所以顺序表的查询元素和获取元素的时间复杂度为O(1)
顺序表的主要优点是:算法简单,内存单元利用率较高。主要缺点是:需要预先确定数据元素的最大个数。

相关文章

  • 数据结构之线性表

    1、线性表-顺序表线性表-顺序表

  • 数据结构03-线性表之顺序表

    第三章 线性表之顺序表 第三章 线性表之顺序表一、什么是线性表?1> 概念2> 线性表的基本操作二、线性表的顺序存...

  • 顺序表和链表的区别

    参考:线性表和链表的区别 注:参考文中的‘线性表’准确的说应该是’顺序表‘,链表与顺序表都是线性表。 顺序表:顺序...

  • 数据结构-双向链表

    (一)什么是链表? 链表是线性表的一种,所谓的线性表包含顺序线性表和链表,顺序线性表是用数组实现的,在内存中有顺序...

  • 数据结构之线性表的链式存储结构

    之前写了线性表的顺序存储结构和有序线性表的顺序存储结构,今天接着写线性表的链式存储结构 数据结构之线性表的顺序存储...

  • 记录十一 线性表的链式存储结构

    前言 在前面记录八 线性表的顺序存储结构和记录九 线性表的顺序存储结构扩展(动态顺序表)中我们了解到线性表的顺序存...

  • 线性表及应用

    线性表 “线性表(List):零个或多个数据元素的有限序列。” 线性表的顺序存储结构 线性表的顺序存储结构,指的是...

  • 线性链表

    线性链表 线性表的顺序存储结构:顺序表线性表的链式存储结构:线性链表 线性表的链式存储所占存储空间大于顺序存储。 ...

  • 数据结构的标准形式(C、Python版本):1.顺序表

    一:C语言版本 顺序表基本操作 顺序表的定义/*****InitSize 线性表长度MaxSize 线性表允许的...

  • 数据结构与算法(二) -- 线性表

    线性表 线性表的顺序表示和实现 线性表的顺序表示是指用一组地址连续的储存单元依次储存线性表的数据元素。 我们通常将...

网友评论

    本文标题:线性表(一)——顺序表

    本文链接:https://www.haomeiwen.com/subject/rshrzctx.html