数据结构-线性表顺序存储结构

数据结构-线性表顺序存储结构

线性表

 线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：

① 存在一个唯一的被称为“第一个”的数据元素；
② 存在一个唯一的被称为“最后一个”的数据元素；
③ 除第一个元素外，每个元素均有唯一一个直接前驱；
④ 除最后一个元素外，每个元素均有唯一一个直接后继。

   线性表(Linear List) ：是由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。该序列中的所有结点具有相同的数据类型。

线性表中的数据元素 ai 所代表的具体含义随具体应用的不同而不同。在线性表的定义中，只不过是一个抽象的表示符号，它可以是一个数字、一个字符串或一个记录。

线性表逻辑结构

◆ 线性表中的结点可以是单值元素(每个元素只有一个数据项) 。
例1: 26个英文字母组成的字母表：
(A，B，C、…、Z）
例2 ： 某校从1978年到1983年各种型号的计算机拥有量的变化情况，用线性表的形式给出：
(6，17，28，50，92，188）
例3 ： 一副扑克的点数
(2，3，4，…，J，Q，K，A)

线性表中的数据元素是各种各样的，但同一线性表必定具有相同的特性，即属同一数据对象。相邻数据元素之间存在序偶关系。将非空的线性表记作：
(a1，a2，…an)
a1 （无前驱）称为线性表的第一个(首)结点，
an （无后继）称为线性表的最后一个(尾)结点。
当n=0时，称为空表。
a1，a2，…ai-1都是ai(2 ≤ i ≤ n)的前驱，其中ai-1是ai的直接前驱;
ai+1，ai+2，…an都是ai(1≤i ≤ n-1)的后继，其中ai+1是ai的直接后继。

线性表的顺序存储结构

##

    顺序存储 ：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

顺序存储的线性表的特点：
◆ 线性表的逻辑顺序与物理顺序一致;
◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。
除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。

#define  OK   1
#define  ERROR   -1
#define  MAX_SIZE  100
typedef  int  Status ;
typedef  int  ElemType ; 
typedef  struct  sqlist
{   ElemType  *Elem_array ;
int    length;
} SqList ;

   顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。

 Status Init_SqList( SqList *L ) //新建一张名为L的空表
{  L->elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ;
if ( !L -> elem_array ) return  ERROR ; //如果返回空指针，则表示分配失败
else {   L->length= 0 ;    return OK ;  }  

 在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的第i(1≦i≦n+1)个位置上插入一个新结点e，使其成为线性表：
  L=(a1，…a i-1，e，ai，ai+1，…，an) 

Status Insert_SqList(Sqlist *L，int i ，ElemType e)
 {   int j ;
if  ( i<1||i>L->length+1)   return  ERROR ;
if  (L->length>=MAX_SIZE)
{    printf(“线性表溢出!\n”);  return  ERROR ;  }
for  ( j = L->length-1; j >=i-1; --j )
L->Elem_array[j+1]=L->Elem_array[j];
/*  i-1位置以后的所有结点后移  */
L->Elem_array[ i-1 ]=e;    /*  在第i个位置插入结点  */
L->length++ ;
return  OK ;  
}

   在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。

在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结点ai(1≦i≦n)，使其成为线性表：
       L= (a1，…ai-1，ai+1，…，an)

删除算法实现
ElemType  Delete_SqList(Sqlist *L，int i)
{  int  k ;   ElemType  x ;
if  (L->length==0)
{  printf(“线性表L为空!\n”); return ERROR;  } 
else if ( i<1||i>L->length ) 
{  printf(“要删除的数据元素不存在!\n”) ; 
return ERROR ; }
else  {  x=L->Elem_array[i-1] ;   /*保存第i个结点的值*/
for ( k=i ;  k<=L->length-1 ; k++) 
      L->Elem_array[k-1]=L->Elem_array[k];
             /*  i+1位置以后的所有结点前移  */
L->length--;  return (x);
}
} 

Status  Locate_Delete_SqList(Sqlist *L，ElemType x)
     /*  删除线性表L中值为x的第一个结点  */
{  int  i=0 , k ; 
while  (i<L->length)      /*查找值为x的第一个结点*/
{   if  (L->Elem_array[i]!=x )  i++ ; 
else   // 找到！  
   {  for ( k=i+1; k< L->length; k++)
           L->Elem_array[k-1]=L->Elem_array[k]; 
           L->length--;  break ; //跳出while循环
   }
}
if  (i>L->length)
{    printf(“要删除的数据元素不存在!\n”) ; 
return ERROR ;  }
return  OK;    
}

时间主要耗费在数据元素的比较和移动操作上。