顺序表及其举例

1. 顺序表的定义
　　用把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法存储的线性表简称为顺序表。
　　顺序表是用向量实现的线性表，向量的下标可以看作结点的相对地址。因此顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。
2. 顺序表存储结构
    在计算机内，可以用不同的方法来存储数据信息，最常用的方法是顺序存储。顺序存储结构也称为向量存储。
    　假设每个元素占用的空间大小为L个字节，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a₁的存储地址（简称为基地址）是LOC（a₁），那么结点a_i的存储地址LOC（a_i）可通过下式计算：
            LOC（a_i）= LOC（a₁）+L*（i-1）   1≤i≤n
 注意：
    　在顺序表中，每个结点a_i的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址。是一种随机存取结构。

3. 顺序表的类定义

 typedef int ElemType;
                  //定义数据元素的类型，类型可根据实际情况而定，这里假设为int
         const int MAXSIZE=100;
                  //表空间的大小可根据实际需要而定，这里假设为100
         class Sqlist
         {   private:
                  ElemType elem[MAXSIZE];           //数组，用于存放表结点
                  int length;                                    //线性表的长度
              public:
                  Sqlist(void);                                  //构造函数
                  ~Sqlist(){};                                   //析构函数
                  void SetData();                             //初建一个简表函数 
                  void PrintOut();                             //输出线性表函数
                  void Insert(int i,ElemType e);         //插入函数
                  ElemType Delet(int i);                   //删除函数
          };

   用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。存放线性表结点的向量空间的大小MAXSIZE应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。

4. 顺序表的插入算法

（1） 插入运算的逻辑描述

线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表：

          （a1，…，ai-1，ai，…an）

变成长度为n+1的线性表：

          （a1，…，ai-1，x，ai，…an）

注意：

① 由于向量空间大小在声明时确定，当L-＞length≥ListSize时，表空间已满，不可再做插入操作

 ② 当插入位置i的值为i＞n或i＜1时为非法位置，不可做正常插入操作

（2） 顺序表插入操作过程

在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。

（3）具体算法描述

void Sqlist::Insert(int i,ElemType e)

{

 int j;

  i--;             //逻辑位置换算为C++数组下标值

  if ( i<0 || i>length )             //判断插入位置的正确性

  cout<<"i Error!"<

  else{  

for(j=length;j>1;j--)

elem[j]=elem[j-1];                   //移动元素

elem[i]=e;                          //插入元素

 length++;                          //表长加1

       }

}

（4）算法分析

① 问题的规模

    表的长度L-＞length（设值为n）是问题的规模。

② 移动结点的次数由表长n和插入位置i决定

算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。

 当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1)

 当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n)

③ 移动结点的平均次数Eis(n)

   其中：

    在表中第i个位置插入一个结点的移动次数为n-i+1

    pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n+1）上的插入结点的机会是均等的，则

             p1=p2=…=pn+1=1/(n+1)

    　因此，在等概率插入的情况下，

    即在顺序表上进行插入运算，平均要移动一半结点。

5.程序实例：

#include

#define Max  100

using namespace std;

typedef int datatype;

/*线性表结构*/

typedef struct SeqList{

    datatype data[Max];

    int last;

} SeqList;

/*初始化*/

SeqList * init_SeqList()

{

      SeqList *L;  int i;

      L=new SeqList;

      cout<<"请输入顺序表的长度"<

      cin>>L->last;

      L->last--;

      cout<<"请输入顺序表的内容"<

      for(i=0;i<=L->last;i++)

             cin>>L->data[i];

      return L;

}

/*读取*/

void Print(SeqList *L)

{

      int i;

      cout<<"顺序表内容为："<

      for(i=0;i<=L->last;i++)

             cout<data[i]<

}

/*从小到大排序*/

void Sort(SeqList *L)

{

      int i,j;

      datatype t;

      for(j=0;j<=L->last;j++)

    {

             for (i=0;ilast-j;i++)

    if (L->data[i]>L->data[i+1])

    {

             t=L->data[i];

    L->data[i]=L->data[i+1];

    L->data[i+1]=t;}

    }

}

/*插入*/

int Insert(SeqList *L,int i,datatype x){

    int j;

    if(L->last>Max-1){

             cout<<"表满"<

             return -1;

      }

    if(i<1||i>L->last+2){

             cout<<"插入位置错误!插入失败"<

             return 0;

      }

    for(j=L->last;j>=i-1;j--)

             L->data[j+1]=L->data[j];

      L->data[i-1]=x;

      L->last++;

      return 1;

}

/*删除*/

int Delete(SeqList *L,int i){

    int j;

    if(i<1||i>L->last+1){

             cout<<"不存在第i个元素"<

             return 0;

      }

    for(j=i;j<=L->last;j++)

             L->data[j-1]=L->data[j];

    L->last--;

    return 0;

}

/*按值查找*/

int Location(SeqList *L,datatype x){

    int i;

    i=0;

    while(i<=L->last&&L->data[i]!=x){

             i++;

             if(i>L->last){

                    return -1;

             }

      }

    return i+1;

}

/*线性表合并*/

void Merge(SeqList *A,SeqList *B,SeqList *C){

      int i,j,k;

      i=0;

      j=0;

      k=0;

//    C = new SeqList[A->last+B->last];

      //C = (SeqList*)malloc(sizeof(SeqList *)*200);

//    C=new SeqList;

      while(i<=A->last && j<=B->last)

             if(A->data[i]data[j])

                    C->data[k++]=A->data[i++];

             else

                    C->data[k++]=B->data[j++];

             while(i<=A->last)

                    C->data[k++]=A->data[i++];

             while(j<=B->last)

                    C->data[k++]=B->data[j++];

             C->last=k-1;

}

/*两个线性表的比较*/

int Compare(int A[],int B[],int m,int n){

    int i,j,AS[100],BS[100],ms,ns;

    i=0;

    ms=ns=0;

    while(i<=m && i<=n && A[i]==B[i])

             i++;

    for(j=i;j

             AS[j=i]=A[j];

             ms++;

      }

    for(j=i;j

             BS[j-i]=B[j];

             ns++;

      }

    if(ms==ns&&ms==0)

             return 0;

    else

             if(ms==0&&ns>0||ms>0&&ns>0&&AS[0]

                    return -1;

             else

                    return 1;

}

/*线性表转化成数组*/

int Change(SeqList *L){

      int i;

      int *a= new int[L->last];

      //int a[L->last];

      for(i=0; ilast; i++){

             a[i]=L->data[i];

      }

             return a[L->last];

 

}

 

/*主函数*/

int main()

{

      int into;

      int del;

      int result;

      int a[100];

      int b[100];

      datatype find;

      datatype num;

      SeqList *L;

      SeqList *L2;

      SeqList *L3;

      L3 = new SeqList;

      L=init_SeqList();

      cout<<"您输入的";

      Print(L);

    Sort(L);

      cout<<"从小到大排序后的";

      Print(L);

      cout<<"请输入您要插入的数："<

      cin>>num;

      cout<<"请输入您要插入的位置："<

      cin>>into;

      Insert(L,into,num);

      cout<<"插入后的";

      Print(L);

      cout<<"请输入您要删除的元素位置："<

      cin>>del;

      Delete(L,del);

      Print(L);

      cout<<"请输入您要查找的数"<

      cin>>find;

      cout<<"您查找的数在第"<位"<

 

      cout<<"输入第二个线性表："<

      L2=init_SeqList();

      cout<<"您输入的";

      Print(L2);

    Sort(L);

      Sort(L2);

      Merge(L,L2,L3);

      cout<<"两个从小到大线性表合并后的";

      Print(L3);

      cout<<"线性表转化成数组"<

      a[100]=Change(L);

      b[100]=Change(L2);

      int *x;

      int *y;

      x=&a[100];

      y=&b[100];

      cout<<"两个线性表的比较"<

      result=Compare(x,y,L->last,L2->last);

      if(result=1){

             cout<<"A线性表大于B线性表"<

      }else if(result=0){

             cout<<"A线性表等于B线性表"<

      }else if(result=-1){

             cout<<"A线性表小于B线性表"<

      }

      return 0;

}