关于数据结构线性表的插入操作（基础问题）

Question

Status ListInsert(SqList &L,int i,ElemType e)
{
ElemType newbase,*q,*p;
if(iL.length+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;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
请问设置中间指针变量newbase的作用是什么？

Answer 1

newbase主要是用来避免意外情况的。如果当前的存储空间已经满了，仍然想插入元素的话，就必须增加空间，新增加一些节点。

那么就遇到问题，因为线性表是连续的，如果要增加一定数量的空间，但是那么多数量的空间不连续，那怎么办？

用realloc函数来动态增加空间，如果空间不连续没关系，realloc会去寻找新的，连续的空间，以提供你来新建节点。

那么原来内存中已经有的，就会被复制到新的连续的空间里面去，这个新的空间的基地址就是newbase。

总之，newbase，和realloc函数，为空间已经满，但还要插入元素情况，提供全新的，连续的空间。