我正在尝试做一个简单的练习,我想从用户输入中填充一个整数数组,并保持输入顺序,这样就不需要在用户完成后对数组进行排序。
假设数组的状态是这样的:{ 3, 5, 7, 8, 9,-,-,-,-,- } ( - 表示空)
现在在这种状态下,例如,如果你输入 6,arr[1] 之后的所有元素都应该向前移动一个位置,以便 6 可以放在 arr[2] 中。
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
bool ok = true;
int x // the input
, n = 0 // to keep track of numbers already in the array
, i, j // to iterate in loops
, arr[10];
cout << "Enter 10 numbers: n";
while (cin >> x) {
if (n == 0) { arr[n] = x; n++; } // for the first entry.
else if (x < arr[0]) { // is x lower than the first element in the array?
for (i = n; i > 0; i--)
arr[i] = arr[i - 1];
arr[0] = x; n++;
}
else if (x > arr[n - 1]) { // is x greater than the top of already addded
// elements to the array?
arr[n] = x; n++;
}
else { // when x is in between of elements. Also I think the problem is here.
for (i = 0; i < n && ok; i++)
if (x > arr[i] && x < arr[i + 1]) {
for (j = n; j > i + 1; j--)
arr[j] = arr[j - 1];
ok = false;
}
arr[i + 1] = x; n++;
}
if (n == 10) break; // if you reached to end of the array, break while.
}
for (i = 0; i < 10; i++)
cout << arr[i] << " ";
cin.get();
cin.get();
}
这段代码有很多问题,但是当我尝试输入:1、10、2、3、4、5、6、7、8、9 时,程序不会将 10 移动到数组的末尾,它输出:1、10、2、3、4、5、6、7、8、9。
这里的问题是,for-loop的增量步骤总是在上一个执行条件为真时执行。
for (i = 0; i < n && ok; i++) // i is incremented
if (x > arr[i] && x < arr[i + 1]) {
for (j = n; j > i + 1; j--)
arr[j] = arr[j - 1];
ok = false;
}
arr[i + 1] = x; n++;
因此,在插入"2"之后,for循环的条件为真:
for (i = 0; i < n && ok; i++)
之后,执行 for 循环的主体并递增 i。现在再次检查条件并评估为 false,但 i 是 1 而不是预期值 0。
所以在表演之后
arr[i + 1] = x; n++;
您的数组如下所示:[1] [10] [2]
您可以将std::vector
与std::upper_bound
结合使用,而不是原始数组,并为每个用户输入使用以下构造:
template<typename T>
typename std::vector<T>::iterator insertInOrder(std::vector<T> &v, T const &val){
auto it = std::upper_bound(v.begin(), v.end(), val);
v.insert(it, val);
return it;
}
现场演示
这是你的功课,你不允许使用带有vector::insert()
的向量,也不允许使用其他适当的标准容器或算法。
我建议通过使用一个单一的一般应用来简化算法:尝试找到数组中 x 速度较慢的第一个元素。 如果找到,请在正确的位置插入 x,否则,将其添加到末尾:
while (cin >> x) {
for (i=0, ok=false; i<n; i++ ) { // iterate for the general case
if (x < arr[i]) { // find first wher x is lower
for (j = n; j>i; j--) // move remaining elements
arr[j] = arr[j - 1];
arr[i] = x;
n++;
ok = true; // we've found the place and inserted x
break;
}
}
if (!ok) { // if we didn't insert until now, we have to add it at the end
if (n<arrsize)
arr[n++] = x;
else cerr << "Array full "<<endl;
}
}
这里是现场演示(arrsize 是一个定义为 10 的常量)。
你可以试试:
for (i = 0; i < n && ok; i++)
if (x > arr[i] && x < arr[i + 1]) {
for (j = n; j > i + 1; j--)
arr[j] = arr[j - 1];
// All elements moved - get out of the for-loop
break;
}
arr[i + 1] = x; n++;
然而,这条线
if (x > arr[i] && x < arr[i + 1]) {
也会给你带来问题。
如果您的阵列保持
2, 3, 4
下一个输入是 3,if 语句永远不会变为真,程序将失败。
数组对这种事情很不利。考虑使用链表,创建一个包含值和指向下一个节点的指针的 Node 类:
class Node{
int number;
Node *nextNode;
}
以及 List 类处理主题的更多代码,您会发现在 betwin 拖曳其他节点中插入节点要容易得多,而不是将数组移动一千次。
更好的信息 -> http://www.cprogramming.com/tutorial/lesson15.html
也许这会有所帮助,所以
#include <iostream>
#include <algorithm>
using namespace std;
void inputInOrder(int *arr, int num){
// Start from the end of array.
// If newly added element is smaller then the element before it swap them.
for(int i(num); i > 0; i--)
if(arr[i] < arr[i-1])
std::swap(arr[i], arr[i-1]);
else break;
}
int main()
{
int n;
cout << "Number of elements: ";
cin >> n;
int *arr = new int[n];
int input(0);
for(int i(0); i < n; ++i){
cout << "Insert element: ";
cin >> input;
arr[i] = input; // you add a new element to the end of array
// call a function that will move newly added element to the right place
inputInOrder(arr, i);
}
for(int i(0); i < n; ++i)
cout << arr[i] << " ";
delete[] arr;
return 0;
}