第二章线性表——顺序存储结构（2）

本文主要是介绍第二章线性表——顺序存储结构（2），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、定义

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

顺序存储的线性表的特点：

◆ 线性表的逻辑顺序与物理顺序一致;

◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

设有非空的线性表：(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 ;

二、顺序表的基本操作

1 顺序线性表初始化

 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 ;  }  
}

2 顺序线性表的插入

在线性表 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)。

3 顺序线性表的删除

在线性表 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 } 

4 顺序线性表的查找定位删除

在线性表 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 } 

这篇关于第二章线性表——顺序存储结构（2）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！