数据结构题:设顺序表va中的数据元数递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
时间: 2023-11-03 16:06:22 浏览: 130
考研数据结构算法代码总结.pdf
5星 · 资源好评率100%
算法步骤:
1. 如果顺序表为空或者x的值大于等于顺序表中最后一个元素的值,则直接将x插入到顺序表最后一个位置。
2. 否则,先找到顺序表中第一个大于等于x的元素所在的位置,然后将x插入到该位置之前。
算法实现(C++):
```
void insertSorted(int va[], int& n, int x) {
if (n == 0 || x >= va[n-1]) { // 如果顺序表为空或者x的值大于等于顺序表中最后一个元素的值
va[n] = x; // 直接将x插入到顺序表最后一个位置
n++;
} else {
int i = 0;
while (i < n && va[i] < x) { // 找到顺序表中第一个大于等于x的元素所在的位置
i++;
}
for (int j = n; j > i; j--) { // 将va[i]到va[n-1]的元素都向后移动一个位置
va[j] = va[j-1];
}
va[i] = x; // 将x插入到该位置之前
n++;
}
}
```
其中,va是顺序表数组,n是顺序表中元素的个数,x是要插入的元素的值。
阅读全文