线性的顺序表示和实现.txt

数据结构是计算机学科的一门核心课程。数据结构课程的 任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存 储结构以及实现各种操作的算法等问题。掌握如何组织数据、 如何存储数据和如何处理数据的基

线性的顺序表示和实现


    线性表的抽象数据类型表示了线性表的数据元素、数据元
素间的路基关系以及线性表的操作集合。任何需要计算机进行
管理和处理的数据元素都必须首先按某种方式存储在计算机中。
线性表的抽象数据类型有两种存储方式：一种是顺序存储结构；
另一种是链式存储结构。一旦确定了线性表的存储结构，线性
表操作集合中的所有操作就可以具体实现。本节将讨论现行表
的顺序存储和顺序存储结构下的操作实现。
    顺序存储结构的线性表称作顺序表。

    1  顺序表的存储结构

    当采用如C语言这样的高级程序设计语言描述数据结构问
题时，实现顺序存储结构的方法是使用数组。数组把线性表的
数据元素存储在一块连续地址空间的内存单元中，这样线性表
中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素
间的逻辑上的前驱，后继逻辑关系就表现在数据元素的存储单
元的物理位置关系上。
    数组有静态数组合动态数组两种。静态数组存储空间的申
请和释放由系统自动完成，动态数组存储空间的申请和释放由
用户通过调用系统函数来完成。不论是静态数组还是动态数组，
其功能都是向系统申请一块地址连续的有限空间，只是使用的
方法不同而已。顺序表一般采用静态数组方法实现其数据元素
的存储。
  
    2  顺序表的操作实现
    
    在顺序存储结构下，线性表抽象数据类型的操作集合中各
个操作的具体实现方法如下：
    1. 初始化 ListInitiate(L)
     VOID ListInitiate(SeqList*L)    /*初始化顺序表L*/ 
     {
       L->size=0;   /*返回顺序表L的当前数据元素个数*/
     }
说明：由于函数中要改变参数L的size域的值，所以参数L应设
计为输出型参数，即设计为SeqList的指针类型。

    2. 求当前数据元素个数ListLength(L)
     int ListLength(SeqList L) /*返回顺序表L的当前数据元素个数*/
     {
       return L.size;
     }

    3.  插入数据元素ListInsert(L,i,x)
     int ListInsert(SeqList*L,int i,Data Type x)
     /*在顺序表L的数据元素ai(0<=i<=size)前插入数据元素值x*/
     /*插入成功返回1，插入失败返回0*/
     {
       int j;
       if(L->size>=MaxSize)
       {
         printf("顺序表已满无法插入！\n");
         return0;
       }

       else if(i<0||i>L->size)
       {
         printf("参数i不合法！\n");
         return0;
       }

       else
       {
         /*为插入做准备*/
         for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];

       
         L->list[i]=x;      /*插入*/
         L-〉size++;        /*元素个数加1*/
         return1;
       }
     }
说明：因顺序表的当前数据元素个数size初始时为0，有一个
数据元素时为1（即数据元素个数size比数组下标（即参数i
的值）大1），所以插入位置参数i应满足0<=i<=size,当参
数i不在此区间时，即可判定参数出错。顺序表的存储空间是
有限的，若当前已经存满了顺序表的MaxSize个存储空间，则
不能继续插入。

  4.  删除数据元素ListDelete(L,i,x)
    int ListDelete(SeqList *L,int i,DataType *x) 
    /*删除顺序表L中位置i(0<=i<=size-1)的数据元素值并存放到x中*/
    /*删除成功返回1，删除失败返回0*/
    {
       int j;
       if(L->size<=0)
       {
         printf("顺序表已空无数据元素可删！\n");
         return0;
       }
       else if(i<0||i>L->size-1)
       {
          printf("参数i不合法");
          return0;
       }
       else
       {
         *=L->list[i];    /*保存删除的元素到参数x中*/

         /*依次前移*/
         for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];
 
         L->size--;      /*数据元素个数减1*/
         return1;
        }
     }
说明：若顺序表中当前没有一个数据元素，则无法进行删除，应
判函数调用出错。删除位置参数i应满足0《=i<=size-1,当参数i
不在此区间时，即可判定参数错。

   5.  取数据元素ListGet(L,i,x)
     int ListGet(SeqList L,int i ,DataType *x)
     /*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/
   {
      if(i<0||i>L.size-1)
      {
        printf("参数i不合法！\n");
      }
      else
      {
         * x=L.list[i];
        return1;
      }
    }
说明：取数据元素操作和删除数据元素操作类同，差别仅是取数
据元素操作只需要取数据元素list[i]到参数x中。