題目

在c++中使用指標的概念在之後程式設計的路上是非常重要的，為了讓各位更加了解指標的概念，本次練習請嘗試將兩個串列以指標的形式宣告，並將其合併後排序。

注意：需動態宣告指標陣列，並使用指標作為函式的輸入

例：
input自此始，但不包括此行
6
1 8 4 10 26 100
5
1000 27 85 44 36
input至此止，但不包括此comment
output自此始，但不包括此行
1 4 8 10 26 27 36 44 85 100 1000

補充說明：
注意輸出最後須用endl換行

注意：函式庫只能使用iostream、string、vector。

完整程式碼

#include<iostream>
using namespace std;

void merge(int* array1,int* array2,int num1,int num2){
    int len = num1+num2;
    //建merge後的陣列
    int result[len];
    for(int i=0;i<num1;i++){
        result[i]=*(array1+i);
    }
    for(int i=0;i<num2;i++){
        result[i+num1]=*(array2+i);
    }

    //merge陣列排序 - bubble sort
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            int n1=result[j];
            int n2=result[j+1];
            if(n1>n2){
                result[j]=n2;
                result[j+1]=n1;
            }
        }
    }

    //print result
    for(int i=0;i<num1+num2;i++){
        printf("%d ",result[i]);
    }
    cout << endl;
}

int main(){

    //建立指標array1
    int num1;
    cin >> num1;
    int arr1[num1];
    int* array1[num1];
    for(int i=0;i<num1;i++){
        cin >> arr1[i];
        array1[i]=&(arr1[i]);
    }

    //建立指標array2
    int num2;
    cin >> num2;
    int arr2[num2];
    int* array2[num2];
    for(int i=0;i<num2;i++){
        cin >> arr2[i];
        array2[i]=&(arr2[i]);
    }

    //用function讓兩個array排序後合併
    merge(array1[0],array2[0],num1,num2);
}

解題過程&觀念

1.建立指標陣列

//建立指標array1
    int num1;
    cin >> num1;
    int arr1[num1];
    int* array1[num1];
    for(int i=0;i<num1;i++){
        cin >> arr1[i];
        array1[i]=&(arr1[i]);
    }

我們要將創立一個儲存int資料型態指標的陣列

int* array1[num1]

但直接創立array1裡面的預設元素值(地址)是不連續的
e.g array1[0]=8290 array1[1]=7642 array1[2]=3286 ...
之後傳遞陣列地址到函數是傳遞array1[0]
傳遞到函式後很難藉由array1[0]+i= array1[i]去推斷剩下元素的地址

而一般陣列如int arr1[num1]的元素address為連續的
e.g &(arr1[0])=8290 &(arr1[1])=8291 &(arr1[2])=8292 ...
因此我們使用arr1先存入input值
再讓array1去存arr1的元素地址,如此一來array1的存的地址為連續的
且地址裡面已經存有值

for(int i=0;i<num1;i++){
        cin >> arr1[i];
        array1[i]=&(arr1[i]);
    }

2.傳遞指標陣列當作函式參數

merge(array1[0],array2[0],num1,num2);

由於array1,array2的值已經是連續的地址元素
我們只要傳[0]和陣列長度就可以推出陣列中的所有元素值

3.函式內容

因為array1,array2為地址標示剛剛array1[0] array2[0]存的地址
因此我們只要使用 *(array1+i)就可以得到arr1[i]的儲存值
array2也同理
-->這就是我們希望地址位置可以連續的原因
只要(陣列起始位置)+i就可以得到全部元素值

void merge(int* array1,int* array2,int num1,int num2){
    int len = num1+num2;
    //建merge後的陣列
    int result[len];
    for(int i=0;i<num1;i++){
        result[i]=*(array1+i);
    }
    for(int i=0;i<num2;i++){
        result[i+num1]=*(array2+i);
    }

    //merge陣列排序 - bubble sort
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            int n1=result[j];
            int n2=result[j+1];
            if(n1>n2){
                result[j]=n2;
                result[j+1]=n1;
            }
        }
    }

    //print result
    for(int i=0;i<num1+num2;i++){
        printf("%d ",result[i]);
    }
    cout << endl;
}

首先創立新的array , 其前半段為array1內容,剩下的為array2的內容

int len = num1+num2;
    //建merge後的陣列
    int result[len];
    for(int i=0;i<num1;i++){
        result[i]=*(array1+i);
    }
    for(int i=0;i<num2;i++){
        result[i+num1]=*(array2+i);
    }

這樣我們就地到了一個有array1 & array2元素值的新陣列
等等要進行小-->大的排序

觀念大魔王: bubble sort
演算法讀法:一定要先懂觀念,再看程式碼!!

//merge陣列排序 - bubble sort
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            int n1=result[j];
            int n2=result[j+1];
            if(n1>n2){
                result[j]=n2;
                result[j+1]=n1;
            }
        }
    }

有一段影片解釋的很好:
https://www.youtube.com/watch?v=Cq7SMsQBEUw

其核心思想:
假設array有n個元素
(1)從[0]-->[n-1]排序
由[0][1]比較,比較大的存[1],小的存[0]
[1][2]比較,比較大的存[2],小的存[1]
[2][3]比較,比較大的存[3],小的存[2]
...
[n-2][n-1]比較,比較大的存[n-1],小的存[n-2]
[n-1]就會存入整的array裡最大的元素值

(2)從[0]-->[n-2]排序
由[0][1]比較,比較大的存[1],小的存[0]
[1][2]比較,比較大的存[2],小的存[1]
[2][3]比較,比較大的存[3],小的存[2]
...
[n-3][n-2]比較,比較大的存[n-2],小的存[n-3]
[n-2]就會存入整的array裡第二大的元素值

...
(n-1)從[0]-->[1]排序
由[0][1]比較,比較大的存[1],小的存[0]
[1]就會存入整的array裡第二小的元素值
[0]就會存入最小的元素值

而第一個for loop i = (1)~(n-2)

for(int i=0;i<len-1;i++){
        ...
    }

第二個for loop j = [j][j+1]的比較

for(int j=0;j<len-1-i;j++){
            int n1=result[j];
            int n2=result[j+1];
            if(n1>n2){
                result[j]=n2;
                result[j+1]=n1;
            }
        }

整個做完之後就成功由小-->大排序