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

【数据结构|线性表的存储结构(顺序存储结构)】线性表是最基本、最简单、也是最常用的一种数据结构。线性表有顺序存储结构与链式存储结构两种表示方式,本章主要介绍线性表的顺序存储结构的表示方式。
线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。其原理大致如下图所示:
数据结构|线性表的存储结构(顺序存储结构)
文章图片

在此线性表中,可以定义创建线性表,插入、删除元素等操作。其原理如下图:
数据结构|线性表的存储结构(顺序存储结构)
文章图片

以下是实现的具体代码:
定义结构体

#include #include #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; //空表长度为0 L.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; //插入e L.length++; //表长+1 return 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--; //表长-1 return OK; }

笔者的经验:
看代码可能会枯燥难懂,动手画图思路就会清晰很多啦  ̄▽ ̄

    推荐阅读