数据结构之线性表的顺序表示和实现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<L.lengh;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.插入位置在最前面