数据结构 第3讲 顺序表_if (i<1 || i>l->length+1 || l->length==maxsize) re

数据结构 第3讲 顺序表

顺序表是最简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。

顺序表可以分配一段连续的存储空间Maxsize，用elem记录基地址，用length记录实际的元素个数，即顺序表的长度，



结构体的定义：



结构体定义后，如果要定义个顺序表L，就可以写：

SqList L;

1. 顺序表初始化

初始化是指给顺序表分配一个预定义大小的空间，用基地址elem记录这段空间的首地址，里面什么都没用，元素个数为0。前面我们已经预定义好了一个最大空间数Maxsize，那么就用new分配这么大的空间，分配成功会返回空间的首地址。假设顺序表里面需要存储整型数，那么就可以这样初始化：

boolInitList(SqList &L) //构造一个空的顺序表L

{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

    //不加&内部改变，跳出函数后无效

    L.elem=new int[Maxsize];    //为顺序表分配Maxsize个空间

    if(!L.elem) return false;      //存储分配失败

    L.length=0;                          //空表长度为0

    return true;

}

1. 顺序表创建

顺序表创建是向顺序表中输入数据，输入数据的类型要与类型定义中的类型一致。假设顺序表里面需要存储整型数，那么就可以这样创建：

boolCreateList(SqList &L) //创建一个顺序表L

{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

    //不加&内部改变，跳出函数后无效

    int a,i=0；

   while(a!=-1)

   {

       cin>>a;

      if(L.length==Maxsize)

     {

          cout<<”顺序表已满！”

          return false;

     }

    L.elem[i++]=a;

      L.length++;

   }

    return true;

}

1. 顺序表取值

顺序表中的任何一个元素都可以立即找到，称为随机存取方式，例如我们我取第i个元素，只要i值是合理的（1≤i≤L.length），那么立即就可以找到该元素L.elem[i-1]：

bool GetElem(SqList L,int i,int &e)

{

    if (i<1||i>L.length) return false;

      //判断i值是否合理，若不合理，返回false

    e=L.elem[i-1]; //第i-1的单元存储着第i个数据

   return true;

}



1. 顺序表查找

在顺序表中查找一个元素e，需要从第一个元素开始顺序查找，依次比较每一个元素值，如果相等，则返回元素位置(第几个元素)，如果查找整个顺序表都没找到，则返回-1：

int LocateELem(SqList L,int e)

{

   for (i=0;i< L.length;i++)

       if (L.elem[i]==e) return i+1; //第几个元素，例如第5个元素，下标其实为4

  return -1;

}

时间复杂性分析：

最好情况：如果元素正好在第一个位置，一次比较成功；时间复杂度为O(1);

最坏情况：如果元素正好在最后一个位置，需要比较n次成功，时间复杂度为O(n);

平均情况：假设每个元素查找概率均等，在第一个位置需要比较1次，第二个位置需要比较2次，…，最后一个位置，需要比较n次，把n种情况加起来平均，平均时间复杂度也为O(n)：



1. 顺序表插入

在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始后移，…，直到把第i个元素也后移一位，然后把e放入第i个位置。



（1）判断插入位置i是否合法（1≤i≤L.length+1），可以在第n+1个元素之前插入。

（2）判断顺序表的存储空间是否已满。

（3）将第n至第i 位的元素依次向后移动一个位置，空出第i个位置。

（4）将要插入的新元素e放入第i个位置。

（5）表长加1，插入成功返回true。

bool ListInsert_Sq(SqList &L,int i ,int e)

{

   if(i<1 || i>L.length+1) return false;     //i值不合法

   if(L.length==Maxsize) return false; //存储空间已满

   for(j=L.length-1;j>=i-1;j–)

      L.elem[j+1]=L.elem[j]; //从最后一个元素开始后移，直到第i个元素后移

   L.elem[i-1]=e; //将新元素e放入第i个位置

   L.length++;             //表长增1

  return true;

}

时间复杂性分析：

假设每个位置插入的概率均等，可以在第一个位置之前插入，第二个位置之前插入，…，最后一个位置之前，第n+1个位置之前，一共有n+1种情况，每种情况移动元素的个数是n-i+1，把所有情况加起来平均，平均时间复杂度为O(n)：



1. 顺序表删除

在顺序表中删除第i个元素，需要把该元素暂存到变量e，然后从i+1个元素开始前移，…，直到把第n个元素也前移一位，然后把e放入第i个位置。



（1）判断插入位置i是否合法（1≤i≤L.length）。

（2）将欲删除的元素保留在e中。

（3）将第i+1至第n 位的元素依次向前移动一个位置。

（4）表长减1，删除成功返回true。

bool ListDelete_Sq(SqList &L,int i, int &e)

{

   if((i<1)||(i>L.length)) return false;     //i值不合法

  e=L.elem[i-1]; //将欲删除的元素保留在e中

  for (j=i;j<=L.length-1;j++)

　 　L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移

  L.length–;      //表长减1

  return true;

}

时间复杂性分析：

假设删除每个元素的概率均等，一共有n种情况，每种情况移动元素的个数是n-i，把所有情况加起来平均，平均时间复杂度为O(n)：



完整代码

include

using namespace std;

define  Maxsize 100  //最大空间

typedef struct{

  int *elem;

  int length;       // 顺序表的长度

}SqList;

bool InitList(SqList &L) //构造一个空的顺序表L

{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

//不加&内部改变，跳出函数后无效

    L.elem=new int[Maxsize];    //为顺序表分配Maxsize个空间

    if(!L.elem) return false;      //存储分配失败

    L.length=0;                          //空表长度为0

    return true;

}

bool CreateList(SqList &L) //创建一个顺序表L

{   //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效

//不加&内部改变，跳出函数后无效

    int a,i=0;

    cin>>a;

    while(a!=-1)

    {

     if(L.length==Maxsize)

     {

       cout<<”顺序表已满！”;

       return false;

     }

     L.elem[i++]=a;

     L.length++;

     cin>>a;

   }

   return true;

}

bool GetElem(SqList L,int i,int &e)

{

  if (i<1||i>L.length) returnfalse;

   //判断i值是否合理，若不合理，返回false

  e=L.elem[i-1];   //第i-1的单元存储着第i个数据

  return true;

}

int LocateELem(SqList L,int x)

{

  for (int i=0;i