【大话数据结构C语言】4 线性表的顺序存储结构

系列文章参考资料为《大话数据结构》，源码为个人私有，未经允许不得转载 技术交流群或资料添加微信号：CoderAllen，回复关键字即可

定义：

在物理空间的存储示意图为下面这个样子：

看上图可以知道顺序存储结构其实就是数组

顺序存储结构的三个特性 1.存储空间的起始位置：数组data存储的位置就是存储空间的存储位置 2.线性表的最大存储容量：数组长度MaxSize 3.线性表的当前长度：length

看下其结构代码：

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

地址计算方法： 由于自然数是从1开始，而C语言的数组是从0下标开始的，于是线性表的第i个元素存储在数据i-1的位置，如下图所示

由于其这样的物理结构，所以线性表的存入取出时间复杂度为O(1)

顺序存储结构的插入与删除

获得元素操作：GetElem 即将线性表中的第i个元素返回

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || iL.length)
            return ERROR;
    *e=L.data[i-1];

    return OK;
}

插入操作：ListInsert 即在线性表中的第i个位置插入新元素

算法思路：

实现代码：

/* 初始条件：顺序线性表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 (iL->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
        return ERROR;

    if (ilength)        /* 若插入数据位置不在表尾 */
    {
        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;
}

删除操作：ListDelete

算法思路：

实现代码：

/* 初始条件：顺序线性表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 (iL->length)         /* 删除位置不正确 */
        return ERROR;
    *e=L->data[i-1];
    if (ilength)                /* 如果删除不是最后位置 */
    {
        for(k=i;klength;k++)/* 将删除位置后继元素前移 */
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

--------------------------------------------------------END----------------------------------------------------------- 电子书及源码点击下载