静态实现顺序表

#include <stdio.h>
#define MaxSize 10    //定义最大长度
typedef struct{
  int data[MaxSize];  //静态数组存放数据元素
  int length; //顺序表的当前长度
}SqList;  //顺序表的类型定义

//基本操作——初始化一个顺序表
void InitList(SqList &L){
  for(int i=0; i<MaxSize; i++)
    L.data[i]=0;    //初始化元素值
  L.length=0;  //顺序表初始化长度0
}
int main(){
  SqList L; //声明一个顺序表
  InitList(L); //初始化顺序表
  //后续操作
  return 0；
}

顺序表的实现——动态分配

#define InitSize 10 //顺序表的初始化长度
typedef struct{
  ElemType *data; //指示动态分配数组的指针
  int MaxSize; //顺序表的最大容量
  int length; //顺序表的当前长度
}SeqList;    //顺序表的类型定义

Key:动态申请和释放内存空间
L.data=(Elem Type *)malloc(sizeof(ElemType)*InitSize);

#define InitSize 10 //顺序表的初始化长度
typedef struct{
  int *data; //指示动态分配数组的指针
  int MaxSize; //顺序表的最大容量
  int length; //顺序表的当前长度
}SeqList;    //顺序表的类型定义

void InitList(SeqList &L){
  //用malloc函数申请一片连续的存储空间
  L.data=(int *) malloc (InitSize*sizeof(int));
  L.length=0;
  L.MaxSize=InitSize;
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
  int *p=L.data;
  L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
  for(int i=0; i<L.length; i++){
    L.data[i]=p[i];  //复制数据至新区域
  }
   L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len
  free(p);  //释放原来的内存空间
}

顺序表特点：随机访问 存储密度高 拓展容量不方便 插入、删除元素不方便

顺序表的插入与删除

#define MaxSize 10    //定义最大长度
typedef struct{
  int data[MaxSize];  //静态数组存放数据元素
  int length; //顺序表的当前长度
}SqList;  //顺序表的类型定义

bool ListInsert(SqList &L, int i, int e){
  if(i<1||i>L.length+1)  //判断i的范围是否有效
    return false;
  if(L.length>=MaxSize)  //当前存储空间已满，不能插入
    return false;
  for(int j=L.length; j>=i;j--)  //将第i个元素及之后的元素后移
    L.data[j] = L.data[j-1];
  L.data[i-1]=e; //在位置i处放入e
  L.length++;  //长度加一
  return true;
}

int main(){
  SqList L; //声明一个顺序表
  InitList(L);  //初始化顺序表
  //……操作
  ListInsert(L,3,3);
  return 0;
 }

时间复杂度：i=n+1,循环0次，时间复杂度O（1）
i=1,循环n次，时间复杂度O(n)
平均O(n)

顺序表的基本操作——删除

bool ListDelete(SqList &L, int i, int &e){
  if(i<1||i>L.length)  //判断i的范围是否有效
    return false;
  e=L.data[i-1]; //将被删除元素赋值给e
  for(int j=i;j<L.length;j++) //将i个位置后的元素前移
    L.data[j-1]=L.data[j];
  L.length--;
  return true;
}
int main(){
  SqList L;
  InitList(L);
  int e=-1;
  if(ListDelete(L,3,e))
    printf("已经删除第三个元素，删除元素值为=%d\n", e);
  else
    printf("位序不合法，删除失败\n");
  return 0;
}

顺序表按位查找

#define MaxSize 10 //定义最大长度
typedef struct{
  ElemType data[MaxSize];
  int length;
}SqList;  //静态方式实现

ElemType GetElem(SqList L, int i){
  return L.data[i-1];
}

define InitSize 10
typedef struct{
  Elemtype *data;   //指示动态分配数组的指针
  int MaxSize;
  int length;
}SeqList;  //动态方式实现

ElemType GetElem(SeqList L, int i){
  return L.data[i-1];
}

按值查找

#define InitSize 10
typedef struct{
  Elemtype *data;   //指示动态分配数组的指针
  int MaxSize;
  int length;
}SeqList;  //动态方式实现

int LocateElem(SqList L, ElemType e){
  for(int i=0; i<L.length;i++)
    if(L.data[i]==e)
      return i+1;
  return 0;
}