数据结构与算法及其航空航天应用（C语言版）（项目式微课版）最新章节_赵学武著

2.3　线性表的顺序存储及运算

2.3.1　顺序表

线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素，即逻辑上相邻的数据元素，其物理地址也相邻，可实现数据元素的随机存取。

以顺序存储方式表示的线性表简称为顺序表。已知顺序表L=( a ₁ , a ₂ ,…, a _i ₋₁ , a _i , a _i ₊₁ , … , a _n )，若第一个数据元素在内存的存储地址为Loc( a ₁ )，且每个数据元素占l字节，则第 i 个数据元素在内存的存储地址为Loc( a ₁ )+( i −1)×l，如图2.1所示。

图2.1 线性表的顺序存储

顺序表在使用C语言或C++实现相关操作时，根据实现方式不同，可进一步细分为静态顺序表和动态顺序表。其中静态顺序表使用“一维数组”实现，而动态顺序表使用“指针+一维数组”实现。

静态顺序表的结构体类型如下所示。

#define LIST_INIT_SIZE 100
struct StaticList                   //静态顺序表（数组）
{
      int elem[LIST_INIT_SIZE];     //线性表数据元素
      int length;                   //线性表的实际表长
      int listsize;                 //线性表分配大小(最大长度)
};

动态顺序表的结构体类型如下所示。

typedef int ElemType;              //为数据类型int起一个别名ElemType
typedef struct                     //动态顺序表（指针+数组）
{
      ElemType *elem;              //动态分配存储空间基址
      int length;                  //顺序表当前长度，即已存入的元素个数
      int listSize;                //当前存储空间容量
}SqList;

2.3.2　顺序表的基本运算

以下以动态顺序表为例，进行动态顺序表的基本操作介绍。

动态顺序表的基本运算包括初始化顺序表、插入元素、删除元素、查询元素、修改元素、访问顺序表、合并有序顺序表等。

1．初始化动态顺序表

根据动态顺序表的结构体类型进行初始化操作，将结构体类型的三个成员分别进行初始化，即完成了动态顺序表的初始化，形成一个空表。

动态顺序表的初始化算法如下所示。

int InitList_Sq(SqList &L)
{//初始化，构造一个空的线性表
     L.elem=new ElemType[LIST_INIT_SIZE];  //申请空间
     if(L.elem==0)                         //申请空间失败(空地址可用0或NULL表示)
    {
          printf(" failure! \n ");
          return 0;
     }
     else                                  //申请空间成功
     {    
           L.length=0;
           L.listSize=LIST_INIT_SIZE;
           return 1;
     }
}

2．遍历访问动态顺序表

遍历访问动态顺序表的操作，即输出动态顺序表的各个数据元素，既可以按照正序方式输出，也可以按照逆序方式输出。

遍历访问动态顺序表的算法如下所示。

void printSq(SqList L)
{//遍历访问动态顺序表（正序）
     ElemType *p;           //定义指针变量p
     for(p=&(L.elem[0]);p<=&(L.elem[L.length-1]);p++)
     {
           cout<<*p<<"  ";  //输出各个数据元素
     }
     cout<<endl;
}

3．动态顺序表插入数据元素

在顺序表中插入一个数据元素的步骤如下。

● 若在第 i （1≤ i ≤ n +1，表长为 n ）个数据元素之前插入一个数据元素，需从第 n 个数据元素（最后一个数据元素）至第 i 个数据元素（共 n − i +1个数据元素），依次后移一个位置；

● 第 i 个位置被空出，插入新数据元素；

● 线性表长度增加1。

（1）在表尾插入数据元素，不产生数据元素的移动。

在顺序表表尾插入数据元素的算法如下。

int ListEndInsert_Sq(SqList &L, ElemType e)
{//在顺序表的表尾插入数据元素e
     if(L.length==L.listsize)    //异常处理，溢出
      {
           printf(" overflow!\n ");
           return 0;
      }
      *(L.elem+L.length)=e;     //在表尾插入数据元素e
      L.length++;               //表长递增1
      return 1;
}

（2）在表头插入数据元素，将产生数据元素的移动。

在顺序表表头插入数据元素的算法如下。

int ListStartInsert_Sq(SqList &L, ElemType e)
{//在顺序表的表头插入数据元素e
     ElemType *p, *q;           //定义指针变量p和q
     if(L.length==L.listsize)   //异常处理，顺序表溢出
      {
           printf(" overflow!\n ");
           return 0;
      }
     /*在表头插入新的数据元素*/
     q=&(L.elem[0]);
      for(p=&(L.elem[L.length-1]); p>=q; p--)  
      {     
          *(p+1)=*p;            //向后移动数据元素
     }
      *q=e;                     //在表头插入数据元素e
      L.length++;               //表长递增1
      return 1;
}

（3）在表中插入数据元素，一般是指在表中第 i 个数据元素位置（或下标为 i 的位置）插入数据元素，也将会产生数据元素的移动。

在顺序表表中插入数据元素的算法如下。

int ListMidInsert_Sq(SqList &L, int i, ElemType e)
{//在顺序表的表中插入数据元素e
     ElemType *p,*q;             //定义指针变量p和q
      if(L.length==L.listsize)   //异常处理，空间不足
      {
          printf(" overflow!\n ");
          return -1;
      }
     if (i<=0 || i>L.length+1)   //异常处理，插入位置不合法
     {
          printf(" position error!\n ");
          return 0;
     }
     /*在第i个位置插入新的数据元素*/
     q=&(L.elem[i-1]);           //取第i个元素的地址
     for(p=&(L.elem[L.length-1]); p>=q; --p)
      {
           *(p+1)=*p;            //向后移动数据元素
      }
      *q=e;               //插入数据元素e
      L.length++;         //表长递增1
      return 1;
}

4．动态顺序表删除数据元素

在顺序表中删除一个数据元素的步骤如下。

● 若要删除第 i （1≤ i ≤ n ，表长为 n ）个数据元素，需从第 i +1个数据元素开始，直至第 n 个数据元素（共 n − i 个元素），依次前移一个位置；

● 线性表长度减少1。

（1）在表尾删除数据元素，不产生数据元素的移动。

在顺序表表尾删除数据元素的算法如下。

int DelEndList_Sq(SqList &L)
{//删除表尾数据元素
     if(L.length==0)    //异常处理，空表
     {
            printf(" UNDERFLOW!\n ");
            return -1;
     else
     {
          L.length--;   //表长递减1
          return 1;
     }
}

（2）在表头删除数据元素，将产生数据元素的移动。

在顺序表表头删除数据元素的算法如下。

int DelHeadList_Sq(SqList &L)
{//删除表头数据元素
     ElemType *p;
     if (L.length==0)        //异常处理，空表
     {
           printf(" UNDERFLOW!\n ");
           return -1;
     }
     else                    //删除表头元素
     {
            for(p=&(L.elem[1]);p<=&(L.elem[L.length-1]);p++)
                *(p-1)=*p;   //向前移动数据元素
            L.length--;      //表长递减1
            return 1;
     }
}

（3）在表中删除数据元素，一般是指在表中第 i 个数据元素位置（或下标为 i 的位置）删除数据元素，也将会产生数据元素的移动。

在顺序表表中删除数据元素的算法如下。

int DelMidList_Sq(SqList &L, int i)
{//删除第i个数据元素
     ElemType *p;
     if (L.length==0)                //异常处理，空表
     {
           printf(" UNDERFLOW!\n "); //溢出
           return -1;
     }
     else if (i<=0 || i>L.length)    //异常处理，删除位置不合法
     {
           printf(" position error!\n ");
           return 0;
     }
     else                            //删除第i个数据元素
     {
           for (p=&(L.elem[i]);p<=&(L.elem[L.length-1]);p++)
                *(p-1)=*p;           //向前移动数据元素
           L.length--;               //表长递减1
           return 1;
     }
}

5．动态顺序表查找数据元素

按照从前到后的顺序或者从后到前的顺序查找某个数据元素是否在顺序表中存在，如果存在返回其对应的位置 i +1（ i 为元素下标），否则返回0。

在动态顺序表中查找数据元素的算法如下。

int FindList_Sq(SqList L, ElemType e)
{//在顺序表L中查找数据元素e是否存在
     int i=0;
     ElemType *p;
     for (p=&(L.elem[0]);p<=&(L.elem[L.length-1]);p++)
     {
          if(*p==e)   //找到了
               return (i+1);
          i++;        //继续查找
     }
     return 0;        //未找到
}

6．动态顺序表修改数据元素

首先在顺序表中查找待修改数据元素是否在该表中存在，如果存在则进行修改并返回1，否则不进行修改并返回0。

在动态顺序表中查找数据元素的算法如下。

int ModifyList_Sq(SqList L, ElemType orig, ElemType targ)
{//在顺序表L中修改数据元素
     int i=0;
     ElemType *p;
     for (p=&(L.elem[0]); p<=&(L.elem[L.length-1]); p++)
     {
           if(*p==orig)      //找到了，进行修改
           {
                *p=targ;
                return 1;    //修改成功
           }
           i++;              //继续查找
     }
     return 0;               //修改失败
}

7．合并有序动态顺序表

两个有序顺序表的合并与两个一元多项式的运算有相似之处，类似于集合的合并运算。在合并时，进行两个有序顺序表对应元素的比较，按照相应的规则进行合并运算。

已知两个动态顺序表LA、LB，表中的数据元素按值非递减有序（升序）排列，现要求将LA和LB合并为一个新的动态顺序表LC，且LC中的数据元素仍按值非递减有序（升序）排列，如图2.2所示。要求LA、LB和LC中的数据元素不能重复出现。

图2.2　合并两个有序顺序表

合并有序动态顺序表的算法如下。

void MergeList_Sq(SqList LA, SqList LB, SqList &LC)
{//合并有序动态顺序表，将LA、LB合并为LC
      int i,j,k;   //i、j、k分别指向顺序表LA、LB、LC的数据元素
      i=j=k=0;
     /*初始化线性表LC*/
      LC.length=LA.length+LB.length;
      LC.listSize=LA.listSize+LB.listSize;
      LC.elem=new ElemType[LC.listSize];
     /*LA和LB的初次合并*/
      while(i<=LA.length-1 && j<=LB.length-1)
      {//当LA、LB同时不为空时，进行以下操作
           ElemType pa=LA.elem[i];  //取LA的第i+1个元素
           ElemType pb=LB.elem[j];  //取LB的第j+1个元素
           if (pa<pb)               //如果pa<pb，取LA中的数据元素
           {
                  LC.elem[k]=pa;    //将pa插入LC的尾部
                  k++;i++;          //LC、LA的下标同时后移
           }
           else if (pa>pb)          //如果pa>pb，取LB中的数据元素
           {
                   LC.elem[k]=pb;   //将pb插入LC的尾部
                   k++;j++;         //LC、LB的下标同时后移
           }
           else                     //如果pa=pb，重复的数据元素只取其一
           {
                   LC.elem[k]=pa;   //将pa插入LC的尾部
                   k++;i++;j++;     //LC、LA和LB的下标同时后移
           }
      }
     /*将LA中剩余数据元素合并到LC的尾部*/
      while(i<=LA.length-1)
      {//如果LA中还有元素，则所有元素全部插入LC尾部
            ElemType pa=LA.elem[i];
            LC.elem[k]=pa;
            k++;i++;
      }
     /*将LB中剩余数据元素合并到LC的尾部*/
      while(j<=LB.length-1)
      {//如果LB中还有元素，则所有元素全部插入LC尾部     
            ElemType pb=LB.elem[j];
            LC.elem[k]=pb;
            k++;j++;
      }
}

2.3 线性表的顺序存储及运算

2.3.1 顺序表

2.3.2 顺序表的基本运算