当前位置:   article > 正文

数据结构--线性表顺序存储_数据结构线性表的应用(顺序存储)

数据结构线性表的应用(顺序存储)

1 线性表定义

由零个或多个数据元素组成的有限序列。

数学定义

若将线性表记为(a1,…,ai-1,ai,ai+1,…an),则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。

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

2 抽象数据类型 ADT

一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。

ADT 抽象数据类型名
Data
数据元素之间逻辑关系的定义
Operation
操作
endADT

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

3 线性表的相关操作

InitList(*L): 初始化操作,建立一个空的线性表L。

ListEmpty(L): 判断线性表是否为空表,若线性表为空,返回true,否则返回false。

ClearList(*L): 将线性表清空。

GetElem(L,i,*e): 将线性表L中的第i个位置元素值返回给e。

LocateElem(L,e): 在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。

ListInsert(*L,i,e): 在线性表L中第i个位置插入新元素e。

ListDelete(*L,i,*e): 删除线性表L中第i个位置元素,并用e返回其值。

ListLength(L): 返回线性表L的元素个数。

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

4、顺序存储结构

把一定的内存空间给占了,然后把相同数据类型的数据元素依次放在这块空地中。

#define MAXSIZE 20    
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;    // 线性表当前长度
} SqList;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

地址计算方法

线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是:

LOC(ai+1) = LOC(ai) + c
  • 1

对于第i个数据元素ai的存储位置可以由a1推算得出:

LOC(ai) = LOC(a1) + (i-1)*c
  • 1

GetElem(L,i,*e)

typedef int Status;

// Status 是函数的类型,其值是函数结果状态代码,如OK
// 初始条件:顺序线性表L已存在,1 <= i <= ListLength(L)
// 操作结果:用e返回L中第i个数据元素的值
Status GetElem(SqList L, int i, ElemType *e)
{
    if( L.length==0 || i<1 || i>L.length )
    {
        return ERROR;
    }
    *e = L.data[i-1];

    return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

ListInsert(*L,i,e)

// 初始条件:顺序线性表L已存在,1<= i <= ListLength(L)
// 操作结果:在L中第i个位置之前插入新的数据元素e,L长度+1

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;

    if( L->length == MAXSIZE )  // 顺序线性表已经满了
    {
        return ERROR;
    }
    if( i<1 || i>L->length+1)   // 当i不在范围内
    {
        return ERROR;
    }
    if( i <= L->length )   // 若插入数据位置不在表尾
    {
        // 将要插入位置后数据元素向后移动一位
        for( k=L->length-1; k >= i-1; k-- )
        {
            L->data[k+1] = L->data[k];
        }
    }

    L->data[i-1] = e;  // 将新元素插入
    L->length++;

    return OK;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

ListDelete(*L,i,*e)

/* 初始条件:顺序线性表L已存在,1<=i<=ListLength(L) */
/* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度-1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;

    // 判断是否是空表
    if( L->length == 0 )
    {
        return ERROR;
    }
    // 判断删除元素位置是否不合法
    if( i<1 || i>L->length )
    {
        return ERROR;
    }

    // 数组从0开始,i位置对应索引-1,记住
    *e = L->data[i-1];

    if( i < L->length )
    {
        // 循环,向前移动1位
        for( k=i; k < L->length; k++ )
        {
            L->data[k-1] = L->data[k];
        }
    }

    // 删除一次成功,表长减1
    L->length--;

    return OK;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

插入和删除操作刚好要求在最后一个位置操作,因为不需要移动任何元素,所以此时的时间复杂度为O(1)。
如果要插入和删除的位置是第一个元素,那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)。

优缺点

线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1)。

而在插入或删除时,时间复杂度都是O(n)。

它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用。

优点:
◆无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
◆可以快速地存取表中任意位置的元素。
缺点
◆插入和删除操作需要移动大量元素。
◆当线性表长度变化较大时,难以确定存储空间的容量。
◆容易造成存储空间的“碎片”。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/801615
推荐阅读
相关标签
  

闽ICP备14008679号