C++数据结构合并顺序表

Question

只能用指针还要求时间空间复杂度，是应该用链表储存吗？那个第二条要求也没看明白。可以写一下完整代码吗，谢谢。

Answer 1

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

#define DEFAULT_CAPICITY 3
#define CAPICITY_STEP 3

typedef struct _SeqList
{
    char *data;
    size_t size;
    size_t capicity;
} SeqList;

SeqList *createSeqList()
{
    SeqList *list = (SeqList *)malloc(sizeof(SeqList));
    list->data = (char *)malloc(sizeof(char) * DEFAULT_CAPICITY);
    list->size = 0;
    list->capicity = DEFAULT_CAPICITY;
    return list;
}

void destroySeqList(SeqList *list)
{
    free(list->data);
    free(list);
}

void reallocSeqList(SeqList *list, size_t size)
{
    assert(size > list->capicity);
    list->data = (char *)realloc(list->data, size);
    list->capicity = size;
}

void insertSeqList(SeqList *list, size_t pos, char value)
{
    assert(pos <= list->size);
    if (list->size == list->capicity)
        reallocSeqList(list, list->capicity + CAPICITY_STEP);
    for (size_t i = list->size; i > pos; i--)
        list->data[i] = list->data[i - 1];
    list->data[pos] = value;
    list->size++;
}

void mergeSeqList(SeqList *m1, const SeqList *m2)
{
    size_t size = m1->size + m2->size;
    if (size > m1->capicity)
        reallocSeqList(m1, size);
    char *p = m1->data + m1->size - 1;
    char *q = m2->data + m2->size - 1;
    char *r = m1->data + m1->capicity - 1;
    while (p >= m1->data && q >= m2->data)
    {
        if (*p > *q)
            *r-- = *p--;
        else
            *r-- = *q--;
    }
    while (p >= m1->data)
        *r-- = *p--;
    while (q >= m2->data)
        *r-- = *q--;
    m1->size += m2->size;
}

void printSeqList(const SeqList *list)
{
    for (size_t i = 0; i < list->size; i++)
        printf("%c,", list->data[i]);
    printf("\n");
}

int main()
{
    SeqList *m1 = createSeqList();
    SeqList *m2 = createSeqList();
    char ch;
    int n, m;
    scanf("%d,", &n);
    for (size_t i = 0; i < n; i++)
    {
        scanf("%c,", &ch);
        insertSeqList(m1, i, ch);
    }
    scanf("%d,", &m);
    for (size_t i = 0; i < m; i++)
    {
        scanf("%c,", &ch);
        insertSeqList(m2, i, ch);
    }
    mergeSeqList(m1, m2);
    printSeqList(m1);
    destroySeqList(m1);
    destroySeqList(m2);
    return 0;
}

$ g++ -Wall main.c
$ ./a.out
6,a,b,c,d,e,f,5,A,a,e,g,z,
A,a,a,b,c,d,e,e,f,g,z,
$ ./a.out
3,a,c,d,0,
a,c,d,