• 周五. 3月 1st, 2024

    数据结构笔记(4) 线性表-顺序存储结构

    root

    3月 20, 2021 #数据结构

    线性表(List):零个或多个数据元素的有限序列。
    一、 线性表的抽象数据类型定义

    ADT 线性表(List)
    Data
        线性表的数据对象集合为{a1,a2,...an},每个元素的类型均为DataType.数据元素之间的关系是一对一关系。
    Operation
        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的元素个数。
    endADT

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

    #define MAXSIZE 20 //存储空间初始分配量
    typedef int ElemType; //ElemType类型根据实际情况而定,这里假设为int
    typedef struct {
            ElemType data[MAXSIZE];//数组存储数据元素,最大值为MAXSIZE
            int length; // 线性表当前长度
    }SqList;

    描述顺序存储结构需要三个属性:

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

    1. 获取元素操作

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    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;
    }

    2. 插入操作
    插入算法思路:

    • 如果插入位置不合理,抛出异常;
    • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
    • 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
    • 将要插入元素填入位置i处;
    • 表长加1
    /*初始条件: 顺序线性表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 (1<=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;
    }

    3. 删除操作
    删除算法思路:

    • 如果删除位置不合理,抛出异常
    • 取出删除元素;
    • 从删除元素位置开始遍历到最后一个元素位置, 分别将它们都向前移动一个位置
    • 表长减1
    /*初始条件:顺序线性表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;
        }
        *e = L->data[i-1];
        if (i<L->length) {
            for(k=i;k<L->length;k++) {
                L->data[k-1] = L->data[k];
            }
        }
        L->length--;
        return OK;
    }

    线性表 存,读数据时 时间复杂度为O(1)

    线性表 插入、删除时 时间复杂度为O(n)

    root