C语言编程问题描述】 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合，现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列。试对顺序表编写求C的算法, C为重新创建的线性表。【样例输入】 7 1 2 3 5 7 9 11 4 2 4 5 9 【样例输出】 2 5 9

以下是C语言的实现代码，时间复杂度为O(m+n)，其中m和n分别为A和B的长度：

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

#define MAX_SIZE 100

void intersection(int A[], int m, int B[], int n, int C[], int *len)
{
    int i = 0, j = 0, k = 0;

    while (i < m && j < n) {
        if (A[i] < B[j]) {
            i++;
        } else if (A[i] > B[j]) {
            j++;
        } else {
            C[k++] = A[i++];
            j++;
        }
    }

    *len = k;
}

int main()
{
    int A[MAX_SIZE], B[MAX_SIZE], C[MAX_SIZE];
    int m, n, len, i;

    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &A[i]);
    }

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &B[i]);
    }

    intersection(A, m, B, n, C, &len);

    for (i = 0; i < len; i++) {
        printf("%d ", C[i]);
    }
    printf("\n");

    return 0;
}

算法思路：

1. 用三个指针i、j、k分别指向A、B、C中的元素。
2. 从头开始遍历A和B，若A[i] < B[j]，则i++；若A[i] > B[j]，则j++；否则将A[i]存入C[k]中，并同时i++和j++，最后k++。
3. 返回C的长度k。