數據結構-線性表順序存儲結構

數據結構-線性表順序存儲結構

線性表

 線性表是一種典型的線性結構。其基本特點是線性表中的數據元素是有序且是有限的。在這種結構中：

① 存在一個唯一的被稱為“第一個”的數據元素；
② 存在一個唯一的被稱為“最後一個”的數據元素；
③ 除第一個元素外，每個元素均有唯一一個直接前驅；
④ 除最後一個元素外，每個元素均有唯一一個直接後繼。

   線性表(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;    
}

時間主要耗費在數據元素的比較和移動操作上。