线性表的线性存储结构数据结构

顺序存储结构：指的是用一段地址按需的存储单元一次存储线性表的数据元素，因为各个元素的数据类型相同，可以使用编程语言（这里使用的是C语言）用数组来实现顺序存储结构

文章最后使用实例加强对顺序存储结构的理解。

顺序存储结构定义代码：

typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; }Sqlist;

这里需要注意的是线性表长度和数组长度的区别。
数组长度：是指存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表长度：是指线性表中数据元素的个数，随着线性表的插入或者删除而变化。

获取元素操作：

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 //获取元素 int 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; }

插入元素操作：

//插入操作 int ListInsert(Sqlist *L,int i,ElemType e) { int k; if(L->length==MAXSIZE) {return ERROR; } if(i<1||i>L->length+1) {return ERROR; } if(i<=L->length) { for(k=L->length; k>=i-1; k--) { L->data[k+1]=L->data[k]; } }L->data[i-1]=e; L->length++; return OK; }

删除元素操作：

int ListDelete(Sqlist *L,int i,ElemType *e) {int k; if(L->length==MAXSIZE) {return ERROR; } if(i<1||i>L->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; }

【线性表的线性存储结构】最后展示一个调试示例：

#include #define MAXSIZE 20 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; }Sqlist; //获取元素 int 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; }//插入操作 int ListInsert(Sqlist *L,int i,ElemType e) { int k; if(L->length==MAXSIZE) {return ERROR; } if(i<1||i>L->length+1) {return ERROR; } if(i<=L->length) { for(k=L->length; k>=i-1; k--) { L->data[k+1]=L->data[k]; } }L->data[i-1]=e; L->length++; return OK; } //删除操作 int ListDelete(Sqlist *L,int i,ElemType *e) {int k; if(L->length==MAXSIZE) {return ERROR; } if(i<1||i>L->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; }int main() { Sqlist list={{3,5,1,7,9,2,1},7}; printf("%d\n",list.length); ElemType *e,test=1; e=&test; printf("---------------------------查看所有元素-----------------------------------\n"); //查看所有元素 int k; for(k=1; k<=list.length; k++) { GetElem(list,k,e); printf("%d ",*e); } printf("\n-----------------------------测试获取元素---------------------------------\n"); //测试获取元素 if(GetElem(list,3,e)==OK) { printf("The Element=%d\n",*e); } printf("-----------------------------测试插入元素---------------------------------\n"); //测试插入元素 if(ListInsert(&list,4,6)==OK) { printf("insert successdully!\n"); } if(GetElem(list,4,e)==OK) { printf("insert,The Element=%d\n",*e); } printf("---------------------------测试删除元素-----------------------------------\n"); //测试删除元素 if(ListDelete(&list,4,e)==OK) { printf("delete successdully!\n"); printf("delete,The Element=%d\n",*e); } else { printf("delete fail..."); }printf("---------------------------查看所有元素-----------------------------------\n"); //查看所有元素 int i; for(i=1; i<=list.length; i++) { GetElem(list,i,e); printf("%d ",*e); }return 0; }

总结：
线性表的顺序存储结构的插入、删除、查询的时间复杂度为：
插入：O(n)
删除：O(n)
查询：O(1)

优点：可以快速地获取线性表中的任一未知的元素；
因为元素之间的未知是按照顺序存储的，减少了为表示元素之间的逻辑关系而额外增加存储空间。
缺点：当执行插入和删除操作是需要移动大量的元素；
不适合线性表长度随机变动的情况；
容易造成存储空间“碎片”,浪费空间。