线性表的存储结构（顺序存储结构）

本文主要是介绍线性表的存储结构（顺序存储结构），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性表是最基本、最简单、也是最常用的一种数据结构。线性表有顺序存储结构与链式存储结构两种表示方式，本章主要介绍线性表的顺序存储结构的表示方式。
线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。其原理大致如下图所示：
这里写图片描述
在此线性表中，可以定义创建线性表，插入、删除元素等操作。其原理如下图：

以下是实现的具体代码：

定义结构体

#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100  //线性表初始存储空间大小
#define LISTINCREMENT 10    //新增存储空间大小
typedef int ElemType;
typedef int Status;typedef struct{ElemType *elem; //存储空间基地址int length; //存储长度int listsize; //当前存储容量
}SqList;

初始化线性表

Status InitList_Sq(SqList &L){L.elem = (ElemType*)malloc((LIST_INIT_SIZE)* sizeof (ElemType)); //分配初始存储空间if (!L.elem) return ERROR;L.length = 0;   //空表长度为0L.listsize = LIST_INIT_SIZE;  //设置初始容量return OK;
}

插入元素（在第i-1个元素和i的元素之间插入值）

Status ListInsert_Sq(SqList &L,int i,ElemType e){ElemType *newbase, *p, *q;if(i < 1||i > L.length + 1) return ERROR;  //判断删除位置是否正确if(L.length >= L.listsize){newbase = (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)* sizeof (ElemType)); //存储空间不足，申请增加空间L.elem = newbase;  //新基地址L.listsize += LISTINCREMENT; //容量增加}p = &L.elem[i-1];for(q = &L.elem[L.length-1];q >= p; q--){  *(q+1) = *q;        //插入位置之后的元素后移}*p = e;  //插入eL.length++; //表长+1return OK;
}

删除元素

Status ListDelete_Sq(SqList &L,int i,ElemType e)
{if(i < 1 || i > L.length)return ERROR;ElemType *p,*q;p = &L.elem[i-1];  //获取删除位置的地址e = *p;   //获取地址对应值p++;   //把地址往后移q = &L.elem[L.length-1];  //获取表尾地址for(p ;p <= q; ++p)*(p-1) = *p;   //被删除元素后的元素往前移L.length--;  //表长-1return OK;
}