Java教程

第二章线性表——顺序存储结构(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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!