《计算机算法设计与分析》电子工业出版社·第4版 算法分析题 3-1

a3-1.c

#include <stdlib.h>
#include <stdio.h>

struct IntArray {
    int *array;
    int length;
};

void IntArray_init(struct IntArray *a, const int max_length) {
    a->array = malloc(max_length * sizeof(int));
    a->length = 0;
}

void IntArray_copy(struct IntArray *a, const struct IntArray b) {
    int i;
    for (i = 0; i < b.length; i++) {
        a->array[i] = b.array[i];
    }
    a->length = b.length;
}

void IntArray_append(struct IntArray *a, const int n) {
    a->array[a->length] = n;
    a->length++;
}


int main(int argc, char **argv) {
    const int ARRAY[10] = {2, 3, 1, 6, 8, 4, 5, 7, 9};
    const int LENGTH = 9;
    const int LENGTH_2 = LENGTH * LENGTH;
    int i, j, k;

    struct IntArray *seq = malloc(LENGTH_2 * sizeof(struct IntArray));
    int seq_length = 0;
    for (i = 0; i < LENGTH_2; i++) {
        IntArray_init(seq + i, LENGTH);
    }

    int *list = malloc(LENGTH_2 * sizeof(int));
    int list_length = 0;
    int max_length;
    for (k = 0; k < LENGTH; k++) {
        // Find the longest sequence of ARRAY[0, ... , k-1] which 
        // can be appended ARRAY[k] legally.
        max_length = -1;
        list_length = 0;
        for (i = 0; i < seq_length; i++) {
            if (seq[i].array[ seq[i].length - 1 ] < ARRAY[k]) {
                // printf("i: %d, ml: %d\n", i, max_length);
                if (seq[i].length > max_length) {
                    max_length = seq[i].length;
                    list[0] = i;
                    list_length = 1;
                }
                else if (seq[i].length == max_length) {
                    list[list_length] = i;
                    list_length++;
                }
                // Pass if (seq[i].length < max_length);
            }
        }

        // Append ARRAY[k] to selected sequence.
        if (list_length == 0) {
            IntArray_append(&seq[seq_length], ARRAY[k]);
            seq_length++;
        } else \
        for (i = 0; i < list_length; i++) {
            IntArray_copy(&seq[seq_length], seq[list[i]]);
            IntArray_append(&seq[seq_length], ARRAY[k]);
            seq_length++;
        }

        // Debug
        /*
        printf("k: %d\n", k);
        for (i = 0; i < seq_length; i++) {
            for (j = 0; j < seq[i].length; j++) {
                printf("%d ", seq[i].array[j]);
            }
            printf("\n");
        }
        printf("========\n");
        */
    }
    
    // Find the longest one in all subsequence.
    max_length = -1;
    for (i = 0; i < seq_length; i++) {
        if (seq[i].length > max_length) {
            max_length = seq[i].length;
            list[0] = i;
            list_length = 1;
        }
        else if (seq[i].length == max_length) {
            list[list_length] = i;
            list_length++;
        }
    }
    for (i = 0; i < list_length; i++) {
        for (j = 0; j < seq[list[i]].length; j++) {
            printf("%d ", seq[list[i]].array[j]);
        }
        printf("\n");
    }

    return 0;
}