如何在保持顺序的同时填充一个整数数组？

Question

我想做一个简单的练习，我想从用户输入中填充一个整数数组，并保持输入顺序，这样就不需要在用户完成后对数组进行排序。

假设数组的状态是这样的：{ 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.

Answer 1

您可以将 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;
}

Live Demo

Answer 2

我想这是你的作业，你不能将向量与 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; 
    }
}

这里的live demo（arrsize是一个定义为10的const）。

Answer 3

这里的问题是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-loop 的条件为真：

for (i = 0; i < n && ok; i++)

之后 for-loop 的主体被执行并且 i 递增。现在再次检查条件并评估为 false，但 i 仍然是 1 而不是预期值 0。

所以执行后

    arr[i + 1] = x; n++;

你的数组看起来像： [1] [10] [2]

Answer 4

你可以试试：

        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-statement 永远不会变为真，程序将失败。

Answer 5

数组对这种事情来说很糟糕.. 考虑使用链表，您创建了一个节点 class，其中包含一个值和指向下一个节点的指针：

class Node{
    int number;
    Node *nextNode;
}

还有更多代码用于列表 class 来处理主题，你会发现在两个其他节点之间插入一个节点要容易得多，而不是移动数组一千次。

更好的信息 -> http://www.cprogramming.com/tutorial/lesson15.html

Answer 6

也许这会有所帮助，所以

#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;
}

如何在保持顺序的同时填充一个整数数组？

How to fill an array of ints while keeping its order?

c++

arrays

sorting

console-application