数据结构之线性表的顺序表示和实现1

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;

//一些数据结构中常用的常量

1.线性表的初始化

Status InitList_Sq(SqList &L)//构造一个新的顺序表
{
L.elem=new ElemType[MAXSIZE];//为顺序表分配空间
if(!L.elem)exit(OVERFLOW);//存储分配失败
L.length=0;//空表长度为0
return OK;
}

销毁线性表L

void DestoryList(SqList &L)
{
if(L.elem) delete L.elem;//释放储存空间

}

清空线性表L

void ClearList(SqList &L)
{
L.length=0;//将线性表的长度置为0
}

求线性表L的长度

int GetLength(SqList L)
{
return (L.length);
}

判断线性表L是否为空

int IsEmpty(SqList &L)
{
if(L.lengh==0)
return 1;
else
return 0;
}

顺序表的取值(根据位置i获取相应位置数据元素的内容)

int GetElem(SqList L,int i,ElemType &e)
{
if(i<1||i>L.length)//判断i值似乎否合理，如果不合理则返回ERROR
return ERROR;
e=L.elem[i-1];//第i-1的单元储存着第i个数据
return OK;
//算法复杂度为O(1);
}

//随机存取是指顺序表 想取任何一个位置的元素都可以通过下标获得它

这是链式存储结构不具有的好处

顺序表的按值查找

在线性表L中查找与指定值e相同的数据元素的位置

从表的一端开始，逐个进行记录的关键字和给定值的比较。

找到返回该元素的位置序号，没找到返回0

int LocateELem(SqList L,ElemType e)
{
//在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
for(i=0;i)
if (L.elem[i]==e)
return i+1;
return 0;
}

 关于它的时间复杂度，取决于查找的值，即 如果我查的值是第一个，那么只需要查询一次，但是如果我要差第n个值则需要查找n次 （n+1）/2为平均查找查长度

顺序表的插入

插入不同位置的算法不同 分为 插入位置在最后 插入位置在中间 插入位置在最前面

Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
if(i<1||i>L.length+1)//i值不合法
return ERROR;
if(L.length==MAXSIZE)//当前储存空间已满
return ERROR;
for(j=L.length-1;j>=i;j--)
L.elem[j+1]=L.elem[j];//插入元素及之后的元素后移
L.elem[i-1]=e;
L.length++;
return OK;
}

关于它的平均移动次数 n\2

时间复杂度 O(n);

1.插入位置在最后

2.插入位置在中间

3.插入位置在最前面