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

线性表(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)