顺序表的操作例题——已知一个顺序表L, 其中的元素递增有序排列，设计一个算法，插入一个元素x (x为int 后保持该顺序表仍然递增有序排列(假设插入操作总能成功)。_设计一个算法,判断顺序表l中所有元素是否是递增有序的。

一、【题目描述】：

已知一个顺序表L, 其中的元素递增有序排列，设计一个算法，插入一个元素x (x为int
后保持该顺序表仍然递增有序排列(假设插入操作总能成功)。

二、【题目分析】:

由题干可知，解决本题需完成两个操作:
1)找出可以让顺序表保持有序的插入位置。
2)将步骤1)中找出的位置上以及其后的元素往后移动一个位置，然后将x放至腾出的位置上。

三、【问题解答】

①因为顺序表L中的元素是递增排列的，所以可以从小到大逐个扫描表中元素，当找到第一
个比x大的元素时，将x插在这个元素之前即可。

int findE(Sqlist L,int x){
int i;
for(i=0;i<L.length;++i){
	if(x<L.data[i]){
		return i;
		}
	}
	return i;
}
1
2
3
4
5
6
7
8
9

②找到插入位置之后，将插入位置及其以后的元素向后移动一个元素的位置即可。先移动最右边的元素。

void insertE(Sqlist &L,int x){
int p,i;
p=findE(L,x);
for(i=L.length-1;i>=p;--i)
L.data[i+1]=L.data[i];
L.data[p]=x;
L.length++;
}
1
2
3
4
5
6
7
8