有序顺序表的插入

下面看问题场景

---

 如图是一个有序表,有序表是用数组承载的,然后我想把 元素 8插入到有序表 ,

怎么实现呢?

下面开始用人脑模拟?

要把 8 插入到有序表 ,先从有序表的第一个元素和8进行比较 ,依次看到了7 ,下一个元素9大于8,停止遍历,

我们就把 8 插入到7和 9 之间,但是没有空位了,所以先把15往后移动一格 ,9也向后移动一格,然后把空位腾出来, 把8 插入到有序表标号为3 的位置.

这样一个有序表的插入就完成了.

下面构造有序表插入的成员方法:

传入 有序表 , 传入要插入的元素

void ListInsert(SqList *&L, ElemType e){

int i =0 ;       //从有序表的0号元素开始遍历

int  j;           //从有序表的末位元素开始往后腾位置,直到把要插入的元素的位置腾出来

开启循环,遍历,先找到一个区间, 插入元素比前一个元素大,比后一个元素小, 后一个元素需要向后移动.

while( i < L->length  &&  L->data[i] < e)

{

        i++;                //当 标号为 i 的元素 ,大于等于插入元素的时候,就会跳出循环,我们此时的 i 的标号是新元素插入的位置,下面我们需要为插入元素腾位置

}

for(j = ListLength(L); j>i; j--)

{

        L->data[j] = L ->data[j-1];

}

---

这可能不容易理解,我们要把末尾元素 往后移动一位,直到把标号为 i 的位置腾出来给新插入的元素,  所以要先把末尾元素往后移动,

末尾元素的位序是 ,表元素个数减去 1 ,               L-> data[j-1]

然后移动到 ,位序加一的位置                                 L->data[j]  

---

那何时移动到呢? 最后一个元素就是 位序为 i 的元素, 往后移动一位 ,

也就是

L->data[ i+1 ]  = L->data [ i ] ;

所以当  j-1 = i 的时候,即 j = i +1 执行完这一步, 就要退出了

因为 j每次都是 j-- ,所以 , j != i  ,顶多执行到 j 比 i 大一这一步就结束了,

所以循环结束的条件 , 是 j != i ,或者 j> i 都可以,   j 一旦等于 i  ,就跳出循环,不参加运算,

 接下来 , 位置也腾出来了,把 新插入的元素给 i 就行了

列表长度自然加一

L -> data[i] = e;
L -> length++;

}

这样我们就完成了插入操作,下面是完整代码:

void ListInsert(SqList *&L, ElemType e)
{
	int i= 0,j;
	while(i<L->length && L->data[i]<e)
	{
		i++;
	}
	for(j = ListLength(L); j>i ; j--)
	{
		L->data[j] = L->data[j-1];
	}
	L ->data[i] = e;
	L ->length++;
}