线性表－顺序表示及实现

线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。
（1）地址连续的存储单元：指在物理内存中，存储单元是物理上相邻的。
（2）依次存储线性表的数据元素：指逻辑关系上，线性表中的数据元素是相邻的。

e.g.
我们定义一个数组a[5]，在物理内存中的表示如图所示；在逻辑关系上就是，a[0]与a[1]，a[1]与a[2]是相邻的，即它们的位序相邻。

a[0]

a[1]

a[2]

a[3]

a[4]

优点：线性表的顺序存储结构是一种随机存取的存储结构。
缺点：在作插入或删除操作时，需要移动大量元素。

线性表的顺序实现：
线性表的动态顺序分配存储结构：

#define TRUE      1            //操作成功
#define FALSE     0            //操作失败
#define INIT_SIZE 100          //分配的存储空间的初始值
#define ADD_SIZE  10           //分配的存储空间的增量

/*定义一个结构体，来表示线性表*/
typedef struct
{
   MYTYPE   *elem;             //线性表的基地址
   int      length;            //当前的长度
   int      listsize;          //当前分配的存储空间大小，不够可以再分配
}List;
       
/*创建一个线性表*/
int creatList(List &L)
{
   int Ok;

   //构造一个空的线性表L
   L.elem = (MYTYPE *)malloc(INIT_SIZE * sizeof(MYTYPE));
   if(L.elem == NULL)
    ｛
         Ok = FALSE;            //存储分配失败
         exit();
    }
   L.length = 0;               //空表长度为0
   L.listsize = INIT_SIZE;     //分配的存储容量的初始值

   return Ok;
}//creatList

/*在线性表中插入一个数据元素*/
int inserttList(L *, int i, MYTYPE a)
{
   MYTYPE ＊new; 
   int Ok;
   MYTYPE *p, *q;
 
   //在线性表List中第i个之前插入新的元素
  
   //判断i值是否为合法值(i从第一个元素算起)
   if(i > L.length + 1)
    ｛
        printf("i 超出可以插入的范围！\n");
        return FALSE;
    ｝

   //判断线性表List是否为满
   if(L.length >= L.listsize)
    {
        //线性表已满，增加分配
        new = (MYTYPE *)realloc(L.elem, (L.listsize + ADD_SIZE) * sizeof(MYTYPE));
        if(new == NULL)
            Ok = FALSE;
        L.elem = new;                              //地址变为新的基址
        L.listsize += ADD_SIZE;                    //长度变为增加元素后的         
    }
       
   //插入元素（先右移插入位置及其后的元素，再插入新元素）
   p = &(L.elem[i - 1]);                      //p为要插入的位置，下标要减1
   //元素右移，现从后面的元素开始，一个一个向后移动
   for(q = &L.elem[L.length - 1]; q >= p; --p)
         *(p + 1) = *p;   
   //插入元素a
   *p = e;
   //长度加1
   L.length++;

   return Ok;
}//insertList

/*在线性表中删除一个元素*/
int deleteList(L *, int i, MYTYPE a)
{
    //判断i值是否合法（i从第一个元素算起）
    if(i > L.length + 1)
    ｛
        printf("i 超出可以插入的范围！\n");
        return FALSE;
    ｝
   
    //删除元素（若有需要，先保存要被删除的元素的值，再左移要删除元素之后的元素）
    p = &(L.elem[i - 1])；                      //p为要删除的位置，下标要减1
    q = L.elem + L.length - 1;                 //先确定表尾元素，再左移元素
    //元素左移，从左向右的先后顺序依次移动
    for(++p; p <= q; ++p)
        *(p - 1) = *p;
    //长度减1
    L.length--;
 
    return Ok;
}//deleteList


注：以上很多内容是参考清华大学出版社的《数据结构（c语言版）》，由严蔚敏老师和吴伟民老师编著的