数据结构-线性表顺序存储

学了这么久，也该写点笔记了：）

定义

由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表,(n=0)的时候称为空表。
一个数据元素可以是简单的一个数据，一个符号，也可以是复杂的若干个数据项的组合

顺序表

线性表的顺序存储结构又被称为顺序表。
顺序存储表示：用一组地址连续的存储单元一次存储线性表的数据元素的方式，具有顺序存储的特点(数据间的逻辑关系和物理关系是一致的)

实例

#include <stdio.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 100//最大长度
#define LISTINCREMENT 10 //额外增量
//定义顺序表
typedef struct {
ElemType * elem;//存储空间基址
int length;//当前长度
int listsize //当前分配的存储容量
} SqList;
//初始化操作
Statys InitList_Sq(Sqlist& L)
{
L.elem=(ElemType*)malloc(List_INIT_SIZE*sizeof(ElemType));//分配存储空间
if(!L.elem) exit(OVERFLOW);//存储分配失败
L.length=0;//空表长度为0；
L.listsieze=LIST_INIT_SIZE;//初始容量；
return ok;
}
//插入操作
ListInsert_Sq(SqList &L,int i,ElemType e)
{
if(i<1||i>L.ength+1) return ERROER;//超过范围，退出
//重新分配
if(L.length>=L.listsize){
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(PVERFLOW);//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
q=&(L.elem[i-1]);//q为插入位置
for(p=&(L.elem[L.length-1];p>=q;--p)
*(p+1)=*p;
*q=e;
L.length++;
return ok;
}

ListDelete_Sq(SqList &L,int i,ElemType &e)
{
if(i<1||i>L.ength) return ERROR ;//i不合法
p=&(L.elem[i-1]);//p为被删元素的位置
e=*p;被删元素的值赋给e;
q=L.elem+L.length-1;//表尾元素的位置
for(++p;p<=q;++p)
*(p-1)=*p;//被删元素之后的元素左移；

L.length--;

}

复杂度分析

线性表的顺序操作，分析其插入操作，显然，每次操作都会把后面的n-i+1个元素进行位移，
从数字直觉来看，时间复杂度期望是n/2;
几何直觉上来看，是个三角形，平均下来也确实是n/2;
删除操作是(n-1)/2

别问，这就是直觉！
总的来说，时间复杂度就是O(n)