算法2.9--有序序列的合并算法(Merge)

将两个有序队列合并为一个，这个并不复杂，只要一一比较即可，W(N)=N-1

#include
#include
#include

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s (Both should be less than 100)>\n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{
        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
        int i;
        for(i = 0; i < length; i ++)
                printf("%d      ", list[i]);

        printf("\n");
}

void insert_sort(int * list, int length)
{
        int i, j, temp;

        for(i = 1; i < length; i ++)
        {
                temp = list[i];
                j = i - 1;
                while((list[j] > temp)&&(j >= 0))
                {
                        list[j+1] = list[j];
                        j --;
                }
                list[j+1] = temp;
        }
}

/*Algorithm*/
void merge(int * srclist, int length, int length1, int length_src)
{
        int * ord_list = (int *)malloc(length * sizeof(int));
        int i = 0, j = length1, k = 0;
        int t;
        while((i < length1) && (j < length_src))
        {
                if(srclist[i] < srclist[j])
                {
                        ord_list[k] = srclist[i];
                        i ++;
                        k ++;
                }
                else
                {
                        ord_list[k] = srclist[j];
                        j ++;
                        k ++;
                }
        }

        if(i >= length1)
        {
                for(t = j; t < length_src; t ++)
                {
                        ord_list[k] = srclist[t];
                        k ++;
                }
        }
        else
        {
                for(t = i; t < length1; t ++)
                {
                        ord_list[k] = srclist[t];
                        k ++;
                }
        }
//      for(t = 0; t < length_src; t ++);
//              srclist[t] = ord_list[t];
        printf("Merged List:\n");
        show_list(ord_list, length_src);
        free(ord_list);

}

int main(int argc, char * argv[])
{
        int length1, length2, length;
        int * list1 = NULL, * list2 = NULL, * src_list = NULL;
        int i;

        /*Deal with the arguments*/
        if(argc != 3)
        {
                usage(argv[0]);
                exit(127);
        }

        length1 = atoi(argv[1]);
        length2 = atoi(argv[2]);

        if(!length1 || !length2 || length1 > MAX_LENGTH || length2 > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        srandom((unsigned int)time(NULL));
        list1 = generate_list(length1);
        list2 = generate_list(length2);

        if(list1 == NULL)
        {
                if(list2 != NULL)
                        free(list2);
                exit(110);
        }
        else if(list2 == NULL)
        {
                free(list1);
                exit(110);
        }

        insert_sort(list1, length1);
        insert_sort(list2, length2);

        src_list = (int * )malloc((length1 + length2) * sizeof(int));
        for(i = 0; i < length1; i ++)
                src_list[i] = list1[i];
        for(i = 0; i < length2; i ++)
                src_list[length1 + i] = list2[i];

        length = length1 + length2;
        printf("Source List 1:\n");
        show_list(list1, length1);
        printf("Source List 2:\n");
        show_list(list2, length2);

        free(list1);
        free(list2);

        printf("Source List, lenght of 1st list is %d, length of 2nd list is %d\n", length1, length2);
        show_list(src_list, length1+length2);
        merge(src_list, length, length1, length1+length2);
        free(src_list);

        return 1;
}