线性搜索函数实现的动态数组

Question

需要实现一个功能

int* linearSearch(int* array, int num);

这会得到一个固定大小的整数数组，其中包含一个数字，return 一个数组，其中包含搜索到的数字出现的索引。例如 array={3,4,5,3,6,8,7,8,3,5} & num=5 将 return occArray={2,9}。我用 C++ 实现了它，主要功能是检查输出

#include <iostream>
using namespace std;
int* linearSearch(int* array, int num);

int main()
{
    int array[] = {3,4,5,3,6,8,7,8,3,5}, num=5;
    int* occArray = linearSearch(array, num);
    int i = sizeof(occArray)/sizeof(occArray[0]);
    while (i>0) {
        std::cout<<occArray[i]<<" ";
        i--;
    }
}

int* linearSearch(int* array, int num)
{
    int *occArray= new int[];
    for (int i = 0,j = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        if (array[i] == num) {
            occArray[j] = i;
            j++;
        }
    }
    return occArray;
}

我认为逻辑很好，但我在为 occArray 创建动态单元格时遇到语法问题也欢迎使用 std::vector 进行更简洁的植入

谢谢

Answer 1

起初我在问题的评论中加入了std::vector建议（将其作为const参考传递以避免不必要的复制！），这解决了你所有的问题：

std::vector<size_t> linearSearch(std::vector<int> const& array, int value)
{
    std::vector<size_t> occurrences;
    // to prevent unnecessary re-allocations, which are expensive,
    // one should reserve sufficient space in advance
    occurrences.reserve(array.size());
    // if you expect only few occurrences you might reserve a bit less,
    // maybe half or quarter of array's size, then in general you use
    // less memory but in few cases you still re-allocate

    for(auto i = array.begin(); i != array.end(); ++i)
    {
        if(*i == value)
        {
            // as using iterators, need to calculate the distance:
            occurrences.push_back(i - array.begin());
        }
    }
    return occurences;
}

或者，您可以使用从 0 到 array.size() 的 size_t i 变量进行迭代，比较 array[i] == value 和 push_back(i); – 这是等效的，所以 select 无论你喜欢更好...

如果您出于某种原因无法使用 std::vector，您需要注意以下几个问题：

您确实可以通过 sizeof(array)/sizeof(*array) 获得数组的长度 – 但只有当您可以直接访问该数组时才有效。在大多数其他情况下（包括将它们传递给函数）数组会衰减为指针并且它们不会保留任何大小信息，因此这个技巧将不再有效，在典型的现代 64- int* 的位硬件为 8/4 = 2——无论数组最初有多长。

所以你需要在附加参数中传递数组的大小，例如：

size_t* linearSearch
(
    int* array,
    size_t number, // of elements in the array
    int value      // to search for
);

同样，您需要通过某种方式 return 搜索值的出现次数。有几个选项：

把num变成一个引用（size_t& num），然后你可以在函数内部修改它，并且变化在外部可见。但是，函数 get 的使用有点不方便，因为您需要显式定义一个变量：

size_t num = sizeof(array)/sizeof(*array);
auto occurrences = linearSearch(array, num, 7);

向数组附加一个标记值，它可能是数组大小或可能更好的最大值 size_t – 具有 C 字符串的所有缺点（主要是必须迭代结果检测出现次数的数组）。
将出现次数添加到数组中 - 有点丑陋，而且您将不同类型的信息混合到同一个数组中。
Return 结果指针和大小在您的自定义结构中或例如一个std::pair<size_t, size_t*>。您甚至可以在调用函数时在结构化绑定表达式中使用它：

auto [num, occurences] = linearSearch(array, sizeof(array)/sizeof(*array), 7);
//                                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// here the trick yet works provided the array is declared above the call, too,
// as is in your example

选项 4 是我个人的推荐。

旁注：我将 size_t 切换为 return 值，因为数组中的负索引无论如何都是无意义的（除非您打算将它们用作标记值，例如 -1 表示事件结束在选项 2 中）。

线性搜索函数实现的动态数组

Dynamic array of Linear search funcion implementation

c++

stdvector

dynamic-arrays

linear-search