欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++11 标准特性:指向数组首元素和尾后元素的指针(附归并排序代码)

程序员文章站 2022-03-21 16:33:42
...

数组是以指针形式传递给函数的,所以函数一开始并不知道数组的确切尺寸,所以应该提供一些额外的信息。C++中常用方法有两种:1. 显示地传递一个表示数组大小的形参,这也是C语言和C++11标准之前常用的; 2. 在C++11标准中,可以传递指向数组首元素和尾后元素的指针,下面的代码我用了这种方法。这类似于容器类型的迭代器,但因为数组不是类类型,所以这两个函数不是成员函数,使用方法为:

int * beg = std::beging(array_name);

int * end = std::end(array_name);

这两个函数在iterator头文件中。这两个函数使得指针的使用更简单,更安全,避免下标越界或者访问非法指针造成segmentation error,前提是正确计算指针的位置。

特别注意,尾后指针不可以解引用和递增操作。

 

实现数组的归并排序(Merge Sort)

#include <iostream>
#include <iterator>
 
void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
 
void print_array(const int *beg, const int *end)
{
    while(beg != end)
    {
        std::cout << *beg++ << " ";
    }
    std::cout << "\n";
}
 
void merge(const int *beg, const int *end, int *result_ptr)
{
    int left_length = (end - beg) / 2;//左部分区间的数据元素的个数
    const int *left_ptr = beg;
    const int *right_ptr = beg + left_length;
    while(left_ptr != beg + left_length && right_ptr != end)
    {
        //对分别已经排好序的左区间和右区间进行合并
        if(*left_ptr <= *right_ptr)
            *result_ptr++ = *left_ptr++;
        else
            *result_ptr++ = *right_ptr++;
    }
    while(left_ptr != beg + left_length)
        *result_ptr++ = *left_ptr++;
    while(right_ptr != end)
        *result_ptr++ = *right_ptr++;
}
 
void merge_sort(int * beg, int * end, int *result_ptr)
{
    if((end - beg) == 1 || beg == end)//如果只有1或0个元素,则不用排序
        return;
    
    else if (end - beg == 2)
    {
        if (*beg > *(end-1))
        {
            swap(*beg, *(end-1));
        }
    }
    
    else
    {
        //继续划分子区间,分别对左右子区间进行排序
        merge_sort(beg, (end-beg)/2+beg, result_ptr);
        merge_sort((end-beg)/2+beg, end, result_ptr);
        //开始归并已经排好序的start到end之间的数据
        merge(beg, end, result_ptr);
        //把排序后的区间数据复制到原始数据中去
        while(beg != end)
            *beg++ = *result_ptr++;
    }
}
 
 
int main(void)
{
    int array[9] = {9,7,5,8,2,4,1,3,6};
    int result[9];
 
    int * beg = std::begin(array);
    int * end = std::end(array);
    int * result_ptr = std::begin(result);
 
    std::cout << "before sorting" << std::endl;
    print_array(beg, end);
 
    merge_sort(beg, end, result_ptr);
 
    beg = std::begin(result);
    end = std::end(result);
    std::cout << "after sorting" << std::endl;
    print_array(beg, end);
 
    return 0;
}

C++11 标准特性:指向数组首元素和尾后元素的指针(附归并排序代码)

相关标签: C 11