[数据结构与算法]数据结构考前复习（2）

2.2线性表的顺序表示和实现（2）

顺序表的插入和删除操作

预定义内容省略。。。

1.顺序表插入操作

注：关于realloc函数的使用参考?

realloc() 用法详解 - xuefenhu - 博客园

在顺序线性表L中第i个位置之前插入新的元素e?

Status ListInsert_Sq(SqList &L,int i,Elemtype e)
{
	//i的合法值：1<=i<=ListLength_Sq(L)+1
	//判断是否合法
	if(i<1||i>ListLength_Sq(L)+1) 
	{
		return ERROR;//i值不合法 
	}
	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;//增加存储容量 
	}

?若L是Sq类型的顺序表，则表中第i个数据元素是L.elem[i-1]?
?开始插入?

	q=&(L.elem[i-1]);//q为插入位置
	//在第i个元素之前插入一个元素时，需将第n至第i个元素向后移一个位置 
	for(p=&(L.elem[L.length-1]);p>=q;--p)//插入位置及之后的元素右移
	{
		*(p+1) =*p;
	}
 	*q=e;//插入e
	++L.length; 
	return OK;
}

2.顺序表删除操作

删除操作无需增加分配

在顺序线性表L中 删除第i个元素，并用e返回其值?

Status ListDelete_Sq(SqList &L,int i,Elemtype &e)
{
	//i的合法值：1<=i<=ListLength_Sq(L)
	//判断是否合法
	if(i<1||i>ListLength_Sq(L)) 
	{
		return ERROR;//i值不合法 
	}

开始删除

	p=&(L.elem[i-1]);//p为删除位置
	//删除第i个元素时，需将第i+1至第n个元素向前移一个位置 
	e=*p;//把被删除元素的值赋给e
	q=L.elem+L.length-1;//表尾元素的位置 
	for(++p;p<=q;++p)//被删除元素之后的元素左移
	{
		*(p-1) =*p;
	}
	--L.length; //表长-1 
	return OK;
}