數(shù)組循環(huán)左移算法實(shí)驗(yàn)報(bào)告

課程設(shè)計(jì)題目：用 Reverse 實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 數(shù)組循環(huán)左移算法

一、問(wèn)題描述

設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為 O(n) 的算法，實(shí)現(xiàn)將數(shù)組 A[n] 中所有元素循環(huán)左移 k 個(gè)位置。

詳見(jiàn)王紅梅等編著的《數(shù)據(jù)結(jié)構(gòu)（C++版）（第2版）》P53頁(yè)習(xí)題5(1)。

二、基本要求

  1. 實(shí)現(xiàn)將數(shù)組 A[n] 中所有元素循環(huán)左移 k 個(gè)位置。

  2. 時(shí)間復(fù)雜度為 O(n) 。

三、概要設(shè)計(jì)

1. 算法的設(shè)計(jì)

算法思路參考王紅梅等編著的《數(shù)據(jù)結(jié)構(gòu)（C++版）（第2版）》P16頁(yè)思想火花，出自BW Kernighan和PJ Plauger于1981年發(fā)表的著作Software tools in Pascal。

  1. 設(shè)計(jì)reverse(first, last)函數(shù)，用于實(shí)現(xiàn)反轉(zhuǎn)從first到last（不含）之間的元素；

  2. 通過(guò)3次reverse實(shí)現(xiàn)將數(shù)組 A[n] 中所有元素循環(huán)左移 k 個(gè)位置：

    reverse(a, a + k)

    reverse(a + k, a + n)

    reverse(a, a + n)

四、詳細(xì)設(shè)計(jì)

1. 設(shè)計(jì)每個(gè)函數(shù)

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

2. 設(shè)計(jì)主函數(shù)

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

五、運(yùn)行與測(cè)試

1. 測(cè)試環(huán)境

運(yùn)行環(huán)境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

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

編譯命令：-g

運(yùn)行終端：cmd

2. 在調(diào)試程序的過(guò)程中遇到的問(wèn)題與解決方案

暫未發(fā)現(xiàn)異常。

3. 設(shè)計(jì)的測(cè)試數(shù)據(jù)與測(cè)試結(jié)果

測(cè)試3次。輸入k，然后生成一個(gè)隨機(jī)數(shù)組并輸出，數(shù)組所有元素循環(huán)左移 k 個(gè)位置后再輸出。

4. 程序清單及運(yùn)行結(jié)果

4.1 A[n] 為整型數(shù)組

程序清單如下。

// ex1_2.cpp

/*
 * 1. 編寫程序：課本p53頁(yè)習(xí)題5(1),先做整數(shù)，然后改用模板函數(shù)做并測(cè)試。
 * 課本p53頁(yè)習(xí)題5(1)：設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為 O(n) 的算法，實(shí)現(xiàn)將數(shù)組 A[n] 中所有元素循環(huán)左移 k 個(gè)位置。
 * 模板
 */

#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次測(cè)試（符合預(yù)期）

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次測(cè)試（符合預(yù)期）

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次測(cè)試（符合預(yù)期）

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次測(cè)試（符合預(yù)期）

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次測(cè)試（符合預(yù)期）

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次測(cè)試（符合預(yù)期）

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

六、總結(jié)與心得

算法之美，妙不可言！

七、參考資料

  1. 王紅梅, 胡明, 王濤. 數(shù)據(jù)結(jié)構(gòu) (C++ 版)[M]. 清華大學(xué)出版社, 2005.

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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容