資料結構：遞增排列的數組 union all 算法 2.1

遞增排列的數組 union all

假設有2個線性表，遞增排列的數組，如

char a[20]="abbcopqtuwz";

char b[20]="bcfgjmtv";

我們需要實作一個union all，将兩個字元串中的字元合并到

一個新的線性表c中，其中也是按照遞增排列的。

那麼按照我們要求輸出應該為

abbbccfgjmopqttuvwz

那麼算法如下：

點選(此處)折疊或打開

#include<stdio.h>

#include <string.h>

int main(void)

{

        char a[20]="abbcopqtuwz";

        char b[20]="bcfgjmtv";

        char c[30];

        memset(c,0,30);

        int n=0;

        int m=0;

        int h=0;

        int a_len=strlen(a);

        int b_len=strlen(b);

        while(n<a_len && m<b_len)

        {

                if(a[n]< b[m])

                {

                        c[h]=a[n];

                        n++;

                }

                else if(a[n]==b[m])

                else

                        c[h]=b[m];

                        m++;

                h++;

        }

        if(a[n] != 0)

                while(n<a_len)

                        h++;

        if(b[m] != 0 )

                while(m<b_len)

        printf("%s\n",c);

}

運作程式輸出為：abbbccfgjmopqttuvwz

可以看到和預期一模一樣。

分析這個算法的漸進時間複雜度，實際上我們發現他隻是一個單循環，很明顯我們原操作隻是c[h]=a[n];這樣的複制

是以時間複雜度為：

T(n)=O(n)

但是這樣的算法明顯依賴于兩個數組排序好了的情況