线性表的相关算法操作（顺序表）、数据结构

• 线性表之顺序表的有关操作
• • 1.顺序表特点
  • 2.线性表的顺序存储表示
  • 3.线性表的初始化
  • 4.线性表的销毁
  • 4.清空线性表
  • 5.求线性表L的长度
  • 6.判断线性表是否为空
  • 7.顺序表的取值
  • 8.顺序表的查找
  • 9.顺序表的插入
  • 10.顺序表的删除

顺序表的特点
1.线性表的逻辑结构与存储结构一致
2.随机存储：访问线性表时，可以快速计算出任何一个数据元素的存储地址

顺序表的优缺点
优点：
    (1)存取密度大
    (2)可以随机存取任一元素
缺点
    (1)在插入或删除某一元素时，需要移动大量元素(时间效率极低)
    (2)浪费存储空间
    (3)静态存储形式，数据元素个数不能自由扩充

//表示1
#define MAXSIZE 100
typedef struct{
   ElemType elem[MAXSIZE];
   int length;
}Sqlist;

//表示2
typedef struct{
   ElemType * elem;
   int length;
}Sqlist;

Sqlist L;
L.elem=(ElemType*)malloc(sizeof(ElemType*)*MAXSIZE)

//线性表的初始化
Status InitList_Sq(SqList &L){
   L.elem = new ElemType[MAXSIZE];
   if(!L.elem)
      exit(OVERFLOW);//存储分配失效
   L.length = 0;//空表
   return OK;
}

//线性表的销毁
void DestroyList(SqList &L){
  if(L.elem)
    delete L.elem;//释放存储空间
}

//清空线性表
void ClearList(SqList &L){
  L.length = 0;//将线性表长度置为0；此时仍然占着空间，但空间中没有元素
}

//求线性表的长度
int GetLength(SqList &L){
  return L.length;
}

//判断线性表是否为空
int IsEmpty(SqList &L){
  if(L.length==0)
     return 1;
  else
     return 0;
}

//取值：根据位置i获取相对位置数据元素的内容
int GetElem(SqList L,int i,Elem &e){
  if(i<1||i>L.length)
     return ERROR;
  e = L.elem[i-1];//取元素。逻辑位序与物理位序相差1
  return OK;
]

//按值查找
//(1)在线性表L中查找与指定值e相同的数据元素的位置
//(2)从表的一端开始，逐个进行记录的关键字和给定值的比较，找到返回该元素的位置
int LocateElem(SqList L,ElemType e){
  for(i=0;i
    if(L.elem[i]==e)
       return i+1;//查找成功，返回逻辑序号
  }
  return 0;//查找失败
}

顺序表的插入
基本思想：
(1)判断插入的位置i是否合法
(2)判断顺序表的存储空间是否已满，若满则返回ERROR
(3)将第i个至第n位的元素依次向后移动一个位置，空出第i个位置
(4)将要插入的新元素e放入第i个位置
(5)表长加1，插入成功则返回OK

Status ListInsert_Sq(SqList &L,int i,ElemType e){
  if(i<1||i>L.length+1) 
     return ERROR;//位置i不合法
  if(L.length==MAXSIZE)
     return ERROR;//空间已满
  for(j=L.length-1;j>=i-1;j--){
     L.elem[j+1]=L.elem[j];//插入位置及其之后元素后移
  }
  L.elem[i-1]=e;
  L.length++;//表长加1
  return OK;
}
插入算法分析:
(1)插入在尾节点之后，无需移动节点(特别快)
(2)插入在首结点之前，元素全部向后移动(特别慢)
(3)在各种位置插入的平均移动次数，时间复杂度位O(n)=n/2

顺序表的删除
算法思想:
(1)判断删除位置i是否合法(i<=i<=n)
(2)将欲删除的元素保留在e中
(3)将第i+1到第n位的元素依次向前移动一个位置
(4)表长减1，删除成功

Status ListDelete_Sq(SqList &L,int i){
  if((i<1)||(i>L.length))
     return ERROR;//i值不合法
  for(j=i;j<=L.length-1;i++)
     L.elem[j-1]=L.elem[j];
  L.length--;//表长减1
  return OK;
}
//时间复杂度O(n)