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

杨伟彬
杨伟彬   编辑于 2018-12-07 14:20
阅读量: 278

线性表的顺序存储

        线性表是最常用且最简单的一种线性结构。

线性结构的特点:

(1)   存在唯一的一个被称作“第一个”的数据元素。

(2)   存在唯一的一个被称作“最后一个”的数据元素。

(3)   除第一个之外,集合中的每个数据元素均只有一个前驱。

(4)   除最后一个之外,集合中每个数据元素均只有一个后继。

线性表的顺序存储指的是:用一组地址连续的存储单元依次存储线性表的数据元素。其特点是,表中相邻的元素ai和ai+1在计算机中存储的物理位置也相邻,若知道线性表的起始位置则可以随机存取。

        线性表的顺序存储又称为顺序表。

        根据其随机存取的特点所以选用高级程序设计语言中的数组来描述数据结构中的顺序存储结构。

线性表的顺序存储结构:

#define LIST_INIT_SIZE  100 //存储空间初始分配量 
#define LISTINCREMENT  10  //存储空间分配增量
 
typedef struct
{
   ElemType *elem;  // 存储空间基地址  根据基地址来访问其他元素
   int length;  // 元素表当前长度 
   int size;  //当前分配的存储容量 
}SqList; 

顺序存储结构中的基本操作。

(1)   插入操作:在线性表的第i个元素之前插入一个元素。

        算法思想:  首先确认插入位置i是否合法。(1<=i<=L.length+1,若在最后一个位置插入元素,则不需要移动其他元素)。插入操作会使得长度为n的线性表变为n+1,所以在插入操作之前需要确定线性表的存储空间是否已满,若满则需要增加分配空间。由基地址可以找到要插入的第i个元素的地址,使用循环将第i个元素后的元素依次分别向后移动一个位置。在第i个位置插入元素。线性表表长增1。

伪码如下:

 

Status ListInsert_Sq(SqList &L,int i,ElemType e)
{  
 	ElemType *newbase,*q,*p;
 	if(i<1||i>L.length+1)   /*   i值不合法    */
 		return ERROR;
  	if(L.length>=L.listsize)   /*   当前存储空间已满,增加分配   */
	{  		
        newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
 		if(!newbase)
 			exit(OVERFLOW);   /*   存储分配失败   */
  		L.elem=newbase;
  		/*新基址*/
  		L.listsize+=LISTINCREMENT;   /*   增加存储容量   */
 	}
 	q=L.elem+i-1;          /*   q为插入位置   */
    /*   插入位置及之后的元素右移  */
  	for(p=L.elem+L.length-1;p>=q;--p)    *(p+1)=*p; *q=e;        /*   插入e   */
  	++L.length;    /*   表长增1   */
  	return OK;
  } 

最好情况:在表尾插入(即i=n+1),元素后移语句将不执行,时间复杂度为O(1)。

最坏情况:在表头插入(即i=1),元素后移语句将执行n次,时间复杂度为O(n)。

平均情况:时间复杂度为O(n)。

(2)   删除操作:删除线性表的第i个元素。

        算法思想:首先确认要删除的第i个元素是否存在(1<=i<=L.length)。根据基地址找到要删除的元素位置。使用将该位置后边的元素依次向前移动一个位置。线性表表长减一。

伪码表示如下:

 

 Status ListDelete_Sq(SqList &L,int i,ElemType &e)
  {  	
  	ElemType *p,*q;
  	if(i<1||i>L.length)        /*    i值不合法    */
  		return ERROR;
  	p=L.elem+i-1;     /*    p为被删除元素的位置   */
  	e=*p;     /*     被删除元素的值赋给e     */
  	q=L.elem+L.length-1;   /*    表尾元素的位置    */
  	for(++p;p<=q;++p)     /*    被删除元素之后的元素左移   */
  		*(p-1)=*p;
  	L.length--;         /*    表长减1    */
  	return OK;
  } 

最好情况:删除表尾元素(即i=n),无需移动元素,时间复杂度为O(1)

最坏情况:删除表头元素(即i=1),需要移动除第一个元素外的所有元素,时间复杂度为O(n)

平均情况:时间复杂度为O(n)。

(3)   按值查找(顺序查找):

        在顺序表L中查找第一个元素值等于e的元素,并返回其位序。

算法思想:令e和L中的数据元素逐个比较,若L中存在和e相同的元素则返回元素的位序。

 

int  LocalElem_Sq(SqList L,ElemType e)
{  	
   int i;
   for(i=0;i<L.length;i++)
   {
	if(L.data[i]==e)
	    return i+1; /*   下标为i的元素值等于e,返回其位序为i+1   */
   }
   return 0;   /*   退出循环说明查找失败   */
} 

最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为O(1)。

最坏情况:查找的元素在表尾(或不存在时),需要比较n次,时间复杂度为O(n)

平均情况:时间复杂度为O(n)。

        线性表顺序存储结构的优缺点:

        线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1)。

        优点:可以快速地存取表中任意位置的元素。

        缺点:插入或删除元素时不方便;存储空间利用率低,预先分配内存可能造成存储空间浪费。

        如图1所示,为了在线性表的第4和第5个元素之间插入一个值为25的元素时,则需将第5个至第8个数据元素依次向后移动一个位置。如图2所示,为了删除第4个数据元素,必须将第5个至第8个元素都一次向前移动一个位置,并且会产生空间浪费。

 

图 1线性表插入前后的状况

 

图 2线性表删除前后的状况

 

 

收藏 转发 评论