线性表插入算法

wzs6668 · 发表于 2016-7-13 16:07

EDA365欢迎您！

您需要登录才可以下载或查看，没有帐号？注册

x

在这种存储结构中，容易实现线性表的某些操作，如随机存取第i个数据元素等。只是要特别注意的是，C语言中数组的下标从“0”开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.elem[i-1]。下面重点讨论线性表的插入和删除两种操作在顺序存储表示时的实现方法。
线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表
（a1,…,ai-1,ai,…,an）
变成长度为n+1的线性表
（a1,…,ai-1,b，ai,…,an）
数据元素ai-1和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动元素才能反映这个逻辑变化的关系。
一个线性表在进行插入操作的前、后，其数据元素在存储空间中的位置变化。为了才线性表的第4和第5个元素之间插入一个值为25的数据元素，则需将第5个至第8个数据元素依次往后移动一个位置。
一般情况下，在第i（1≤i≤n）个元素之前插入一个元素时，需将第n至第i个元素向后移动一个位置。
StatusListInsert_Sq(SqList &L,int i,ElemType){
//在顺序线性表L中第i个位置之前插入新的元素e，
//i的合法值为1≤i≤ListLength——Sq（L）+1
if（i<1||i>L.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]);             //q为插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
                              //插入位置及之后的元素右移
*q=e；       //插入e
++L.Length;    //表长增1
return OK;
} //ListInsert_Sq