数组循环左移算法实验报告

课程设计题目：用 Reverse 实现时间复杂度为 O(n) 数组循环左移算法

一、问题描述

设计一个时间复杂度为 O(n) 的算法，实现将数组 A[n] 中所有元素循环左移 k 个位置。

详见王红梅等编著的《数据结构（C++版）（第2版）》P53页习题5(1)。

二、基本要求

  1. 实现将数组 A[n] 中所有元素循环左移 k 个位置。

  2. 时间复杂度为 O(n) 。

三、概要设计

1. 算法的设计

算法思路参考王红梅等编著的《数据结构（C++版）（第2版）》P16页思想火花，出自BW Kernighan和PJ Plauger于1981年发表的著作Software tools in Pascal。

  1. 设计reverse(first, last)函数，用于实现反转从first到last（不含）之间的元素；

  2. 通过3次reverse实现将数组 A[n] 中所有元素循环左移 k 个位置：

    reverse(a, a + k)

    reverse(a + k, a + n)

    reverse(a, a + n)

四、详细设计

1. 设计每个函数

void Reverse(int *first, int *last)
{
    last--;
    for (int temp; first < last; first++, last--)
        temp = *first, *first = *last, *last = temp;
}

2. 设计主函数

int main()
{
    reverse(a, a + k);
    reverse(a + k, a + n);
    reverse(a, a + n);
}

五、运行与测试

1. 测试环境

运行环境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

编译器：gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

编译命令：-g

运行终端：cmd

2. 在调试程序的过程中遇到的问题与解决方案

暂未发现异常。

3. 设计的测试数据与测试结果

测试3次。输入k，然后生成一个随机数组并输出，数组所有元素循环左移 k 个位置后再输出。

4. 程序清单及运行结果

4.1 A[n] 为整型数组

程序清单如下。

// ex1_2.cpp

/*
 * 1. 编写程序：课本p53页习题5(1),先做整数，然后改用模板函数做并测试。
 * 课本p53页习题5(1)：设计一个时间复杂度为 O(n) 的算法，实现将数组 A[n] 中所有元素循环左移 k 个位置。
 * 模板
 */

#include <iostream>
#include <ctime>
using namespace std;

template <typename T>
void Reverse(T *first, T *last)
{
    last--;
    for (T temp; first < last; first++, last--)
        temp = *first, *first = *last, *last = temp;
}

int main()
{
    srand(time(NULL));

    int n = 10, k;
    cout << "Please input k(0 < k < 10): ";
    cin >> k;

    int A[n];
    for (int i = 0; i < n; i++)
        cout << (A[i] = rand()) << " ";
    cout << endl;

    Reverse(A, A + k);
    Reverse(A + k, A + n);
    Reverse(A, A + n);

    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << endl;

    double B[n];
    for (int i = 0; i < n; i++)
        cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
    cout << endl;

    Reverse(B, B + k);
    Reverse(B + k, B + n);
    Reverse(B, B + n);

    for (int i = 0; i < n; i++)
        cout << B[i] << " ";
    cout << endl;

    return 0;
}

第1次测试（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
Please input k(0 < k < 10): 3
31255 22925 30731 23452 21176 11048 16126 26806 17875 16867
23452 21176 11048 16126 26806 17875 16867 31255 22925 30731

第2次测试（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
Please input k(0 < k < 10): 4
31297 31583 821 8595 24193 29328 23820 21519 3149 2478
24193 29328 23820 21519 3149 2478 31297 31583 821 8595

第3次测试（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1
Please input k(0 < k < 10): 5
31310 9040 6742 6545 32684 12267 3502 9810 3660 10654
12267 3502 9810 3660 10654 31310 9040 6742 6545 32684

4.2 模板

#include <iostream>
#include <ctime>
using namespace std;

template <typename T>
void Reverse(T *first, T *last)
{
    last--;
    for (T temp; first < last; first++, last--)
        temp = *first, *first = *last, *last = temp;
}

int main()
{
    srand(time(NULL));

    int n = 10, k;
    cout << "Please input k(0 < k < 10): ";
    cin >> k;

    int A[n];
    for (int i = 0; i < n; i++)
        cout << (A[i] = rand()) << " ";
    cout << endl;

    Reverse(A, A + k);
    Reverse(A + k, A + n);
    Reverse(A, A + n);

    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << endl;

    double B[n];
    for (int i = 0; i < n; i++)
        cout << (B[i] = (double)rand() / (rand() + 1)) << " ";
    cout << endl;

    Reverse(B, B + k);
    Reverse(B + k, B + n);
    Reverse(B, B + n);

    for (int i = 0; i < n; i++)
        cout << B[i] << " ";
    cout << endl;

    return 0;
}

第1次测试（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
Please input k(0 < k < 10): 3
31607 4105 26750 850 21038 9151 24591 5572 31655 8236
850 21038 9151 24591 5572 31655 8236 31607 4105 26750
0.551057 2.53344 0.209033 6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277
6.9253 0.0571197 1.1675 53.6444 0.791821 0.250341 1.0277 0.551057 2.53344 0.209033

第2次测试（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
Please input k(0 < k < 10): 4
31624 25079 17767 22863 7075 28785 7385 23704 15909 10263
7075 28785 7385 23704 15909 10263 31624 25079 17767 22863
0.511611 0.172095 1.52812 1.01504 0.720147 9.04 10.3216 0.00956241 2.05172 0.394671
0.720147 9.04 10.3216 0.00956241 2.05172 0.394671 0.511611 0.172095 1.52812 1.01504

第3次测试（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex1_2
Please input k(0 < k < 10): 5
31653 23511 14704 10057 1602 31357 2629 30126 673 20467
31357 2629 30126 673 20467 31653 23511 14704 10057 1602
0.4426 0.60074 5.66135 0.316398 0.906047 2.21183 135.865 0.0243682 0.37898 0.211203
2.21183 135.865 0.0243682 0.37898 0.211203 0.4426 0.60074 5.66135 0.316398 0.906047

六、总结与心得

算法之美，妙不可言！

七、参考资料

  1. 王红梅, 胡明, 王涛. 数据结构 (C++ 版)[M]. 清华大学出版社, 2005.

  2. Kernighan B W, Plauger P J. Software tools in Pascal[J]. 1981.

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容