顺序存储 :把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点:
◆ 线性表的逻辑顺序与物理顺序一致;
◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
设有非空的线性表:(a1,a2,…an) 。顺序存储如图2-1所示。
用结构类型来定义顺序表类型。
#define OK 1
#define ERROR -1
#define MAX_SIZE 100
typedef int Status ;
typedef int ElemType ;
typedef struct sqlist {
ElemType Elem_array[MAX_SIZE] ;
int length ;
} SqList ;
Status Init_SqList( SqList *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)个位置上插入一个新结点e,
使其成为线性表: L=(a1,…a i-1,e,ai,ai+1,…,an)
实现步骤
(1) 将线性表L中的第i个至第n个结点后移一个位置。
(2) 将结点e插入到结点ai-1之后。
(3) 线性表长度加1。
算法描述 Status Insert_SqList(Sqlist *L,int i ,ElemType e) { int j ; if ( i<0||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-1位置插入结点 */ L->length++ ; return OK ; }
在顺序表上做插入运算,平均要移动表上一半结点。当表长n较大时,算法的效率相当低。因此算法的平均时间复杂度为O(n)。
在线性表 L=(a1,…a i-1,ai, ai+1,…,an) 中删除结点ai(1≦i≦n),
使其成为线性表: L= (a1,…ai-1,ai+1,…,an)
实现步骤 (1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。 (2) 线性表长度减1。
算法描述
1 ElemType Delete_SqList(Sqlist *L,int i) 2 { int k ; ElemType x ; 3 if (L->length==0) 4 { printf(“线性表L为空!\n”); return ERROR; } 5 else if ( i<1||i>L->length ) 6 { printf(“要删除的数据元素不存在!\n”) ; 7 return ERROR ; } 8 else { x=L->Elem_array[i-1] ; /*保存结点的值*/ 9 for ( k=i ; k<L->length ; k++) 10 L->Elem_array[k-1]=L->Elem_array[k]; 11 /* i位置以后的所有结点前移 */ 12 L->length--; return (x); 13 } 14 }
在线性表 L= (a1,a2,…,an) 中删除值为x的第一个结点。
实现步骤
(1) 在线性表L查找值为x的第一个数据元素。
(2) 将从找到的位置至最后一个结点依次向前移动一个位置。
(3) 线性表长度减1。
1 Status Locate_Delete_SqList(Sqlist *L,ElemType x) 2 /* 删除线性表L中值为x的第一个结点 */ 3 { int i=0 , k ; 4 while (i<L->length) /*查找值为x的第一个结点*/ 5 { if (L->Elem_array[i]!=x ) i++ ; 6 else 7 { for ( k=i+1; k< L->length; k++) 8 L->Elem_array[k-1]=L->Elem_array[k]; 9 L->length--; break ; 10 } 11 } 12 if (i>L->length) 13 { printf(“要删除的数据元素不存在!\n”) ; 14 return ERROR ; 15 } 16 return OK; 17 }