线性表练习题

初始设置

#define OK 1
#define ERROR 0

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

// 链表结构设计
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

// 初始化
Status ListInit(LinkList *L, ElemType array[], int count)
{
    LinkList tail = (LinkList)malloc(sizeof(Node));
    if (!tail) return ERROR;
    *L = tail;
    for (int i = 0; i < count; i++) {
        tail->next = (LinkList)malloc(sizeof(Node));
        if (!tail->next) return ERROR;
        tail->next->data = array[i];
        tail = tail->next;
    }
    tail->next = NULL;
    return OK;
}

// 遍历 
void PrintList(LinkList L)
{
    LinkList tail = L->next;
    while (tail) {
        printf("%3d", tail->data);
        tail = tail->next;
    }
    printf("\n");
}

1. 题目1

将2个递增的有序链表合并为⼀个链表的有序链表。

要求：

• 结果链表仍然使⽤两个链表的存储空间，不另外占⽤其他的存储空间。
• 表中不不允许有重复的数据。

解答

因为不能占用新的空间，即空间复杂度是。

我们只需要使用某一个链表头作为输出结果的表头，这里我使用L1。

想象条根链表，通过一根针串起来。L1和L2的遍历指针，谁小就移动谁，相等时同时移动。比如下图示意3<4，p1移动到5。

需要注意的是，L2中重复的节点需要释放，否则会内存泄露。

示意图

时间复杂度：

空间复杂度：

Status MergeTwoLists(LinkList *L1, LinkList *L2, LinkList *L3)
{
    // 另一个表为空表
    if (L1 == NULL || !(*L1)->next) {
        *L3 = *L2;
        return OK;
    } else if (L2 == NULL || !(*L2)->next) {
        *L3 = *L1;
        return OK;
    }
    // 初始化
    LinkList p1, p2, pre, tmp;
    p1 = (*L1)->next;
    p2 = (*L2)->next;
    *L3 = pre = *L1; // 确定表头为L1
    while (p1 && p2) {
        if (p1->data < p2->data) { // <
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
        } else if (p1->data > p2->data) { // >
            pre->next = p2;
            pre = p2;
            p2 = p2->next;
        } else { // ==
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
            tmp = p2; // 准备释放相同的数
            p2 = p2->next;
            free(tmp);
        }
    }
    pre->next = p1 ? p1 : p2;
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1, L2, L3;
    ElemType a[6] = {1, 3, 5, 6, 7, 9};
    ElemType b[6] = {2, 4, 5, 6, 8, 10};
    ListInit(&L1, a, 6);
    ListInit(&L2, b, 6);
    MergeTwoLists(&L1, &L2, &L3);
    PrintList(L3);
    return 0;
}
// 输出
  1  2  3  4  5  6  7  8  9 10

2. 题目2

已知两个链表A和B分别表示两个集合，其元素递增排列。设计⼀个算法，用于求出A与B的交集，并存储在A链表中。
例如 : La = {2,4,6,8}; Lb = {4,6,8,10}; 输出La = {4,6,8}。

解答

思路和题目1类似，要求结果存放于L1，那么我们就选L1作为输出结果的表头。

同样是双指针遍历，谁小就移动谁，相等时同时移动。但这一次需要释放L1中不用的节点。

先释放比L2中小的部分，取交集之后，如果p1还没有到头，说明还有更大的元素，需要释放这部分。最后尾节点置空。

时间复杂度：

空间复杂度：

Status intersection(LinkList *L1, LinkList *L2, LinkList *L3)
{
    if (L1 == NULL || L2 == NULL) return ERROR;
    // 初始化
    LinkList p1, p2, pre, tmp;
    p1 = (*L1)->next;
    p2 = (*L2)->next;
    *L3 = pre = *L1; // 确定表头为L1
    while (p1 && p2) {
        if (p1->data < p2->data) { // <
            tmp = p1; // 释放小于部分
            p1 = p1->next;
            free(tmp);
        } else if (p1->data > p2->data) { // >
            p2 = p2->next;
        } else { // ==
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    while (p1) { // 释放大于部分
        tmp = p1;
        p1 = p1->next;
        free(tmp);
    }
    pre->next = NULL;
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1, L2, L3;
    ElemType a[4] = {2, 4, 6, 8};
    ElemType b[4] = {4, 6, 8, 10};
    ListInit(&L1, a, 4);
    ListInit(&L2, b, 4);
    intersection(&L1, &L2, &L3);
    PrintList(L3);
    return 0;
}
// 输出
  4  6  8

3. 题目3

设计⼀个算法，将链表中所有节点的链接方向"原地旋转"。

• 仅利用原表的存储空间，即要求算法空间复杂度为O(1)。
• 例如：L={0,2,4,6,8,10}，逆转后：L = {10,8,6,4,2,0}。

解答

单链表的逆序。需要前一个节点和后一个节点的指针，方便指针逆向，和继续遍历。

时间复杂度：

空间复杂度：

Status reverse(LinkList *L1)
{
    if (*L1 == NULL) return ERROR;
    LinkList pre = NULL, cur = *L1, next = (*L1)->next;
    while (next) {
        cur = next;
        next = next->next;
        cur->next = pre;
        pre = cur;
    }
    (*L1)->next = cur;
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1;
    ElemType a[6] = {0, 2, 4, 6, 8, 10};
    ListInit(&L1, a, 6);
    reverse(&L1);
    PrintList(L1);
    return 0;
}
//输出
 10  8  6  4  2  0

4. 题目4

设计⼀个算法，删除递增有序链表中值大于等于mink且⼩于等于maxk(mink、maxk是给定的两个参数，值可以和表中的元素相同，也可以不同)的所有元素。

解答

单向链表节点的删除。不知道是否还有更好的方法。

时间复杂度：

空间复杂度：

Status delete(LinkList *L1, ElemType mink, ElemType maxk)
{
    if (*L1 == NULL) return ERROR;
    LinkList pre = *L1, cur = (*L1)->next, tmp;
    while (cur) {
        if (mink <= cur->data && cur->data <= maxk) {
            tmp = cur;
            pre->next = cur->next;
            cur = cur->next;
            free(tmp);
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1;
    ElemType a[6] = {0, 2, 4, 6, 8, 10};
    ListInit(&L1, a, 6);
    delete(&L1, 1, 7);
    PrintList(L1);
    return 0;
}
// 输出
  0  8 10

5. 题目5

设将n(n>1)个整数存放到⼀维数组R中，试设计⼀个在时间和空间两⽅面都尽可能高效的算法。将R中保存的序列循环左移p个位置(0<p<n)个位置，即将R中的数据由(x0,x1,......,xn-1)变换为 (xp,xp+1,...,xn-1,x0,x1,...,xp-1)。

例如：pre[10] = {0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3; pre[10] = {3,4,5,6,7,8,9,0,1,2}

解答

这里直接思路是：

1. 每次取头数字
2. 后面的元素前移1格
3. 把最后一个改为头数字

这个时间复杂度是
。

我们注意到先逆序{9,8,7,6,5,4,3,2,1,0}，然后把3-9和0-2再分别逆序就可以了。

时间复杂度：

空间复杂度：

void Reverse(ElemType a[], int left, int right)
{
    if (left > right) return;
    int mid = (left + right) / 2;
    ElemType tmp;
    for (int i = 0; i <= mid - left; i++){
        tmp = a[left + i];
        a[left + i] = a[right - i];
        a[right - i] = tmp;
    }
}

void MoveLeft(ElemType a[], int n, int p)
{
    Reverse(a, 0, n-1);
    Reverse(a, 0, n-1-p);
    Reverse(a, n-p, n-1);
}

int main(int argc, const char * argv[]) {
    int n = 10, p = 3;
    ElemType *array = (ElemType *)malloc(sizeof(ElemType) * n);
    for (int i = 0; i < n; i++) {
        array[i] = i;
    }
    MoveLeft(array, n, p);
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    free(array);
    return 0;
}
// 输出
3 4 5 6 7 8 9 0 1 2

6. 题目6

已知⼀个整数序列列A = (a0,a1,a2,...an-1)，其中0<=ai<=n, 0<=i<=n。 若存在ap1= ap2 = ...=apm = x，且m>n/2, 0<=pk<n,1<=k<=m，则称x为A的主元素。

例如，A=(0,5,5,3,5,7,5,5)，则5是主元素; 若B=(0,5,5,3,5,1,5,7)，则B中没有主元素。

假设A中的n个元素保存在⼀个一维数组中，请设计⼀个尽可能⾼效的算法，找出数组元素中的主元素，若存在主元素则输出该元素，否则输出-1。

解答

注意到主元素满足数量大于总数的一半。那么主元素数量减去其他元素数量肯定是大于0的。

也可以理解为，主元素和其他元素依次抵消，剩下的肯定是主元素。

利用这个思路，从第一个元素开始作为主元素，下一个元素若和它相等，计数加一，否则减一。当计数为0的时候，将主元素替换为下一个元素。

时间复杂度：

空间复杂度：

#define NOT_FOUND -1
int FindMainElement(ElemType *a, int count)
{
    if (a == NULL || count == 0) return NOT_FOUND;
    // 统计出现较多的数
    int statistics = 1;
    ElemType mainElem = a[0];
    for (int i = 1; i < count; i++) {
        if (a[i] == mainElem) {
            ++statistics;
        } else {
            --statistics;
        }
        if (statistics == 0) {
            statistics = 1;
            mainElem = a[i];
        }
    }
    // 出现较多，但不一定满足主元素数量>n/2的条件
    if (statistics > 0) {
        statistics = 0;
        for (int i = 1; i < count; i++)
            if (a[i] == mainElem) ++statistics;
        if (statistics > count / 2)
            return mainElem;
    }
    return NOT_FOUND;
}

int main(int argc, const char * argv[]) {   
    ElemType a[8] = {0,5,5,3,5,7,5,5};
    int mainElem = FindMainElement(a, 8);
    if (mainElem > 0) {
        printf("The main element is %d.\n", mainElem);
    } else {
        printf("The main element is not found.\n");
    }
    return 0;
}
// 输出
The main element is 5.

7. 题目7

⽤单链表保存m个整数，结点的结构为(data, link)， 且|data|<=n(n为正整数)。现在要去设计一个时间复杂度尽可能高效的算法。对于链表中的data绝对值相等的结点，仅保留第⼀次出现的结点，删除其余绝对值相等的结点。

例如，链表A = {21,-15,15,-7,15}，删除后的链表A={21,-15,-7}。

解答

这个只要求时间复杂度尽可能高效，潜台词就是说，我们可以拿空间换时间。

我们用一个char表来记录某个元素是否出现过，如果出现过为1，否则为0。再次出现时，删除对应节点。

又由于条件，那么表的大小为。

时间复杂度：

空间复杂度：

Status RemoveAbsRepeat(LinkList *L, int n)
{
    char *flag = (char *)calloc(n + 1, sizeof(char));
    if (flag == NULL) return ERROR;
    LinkList pre, cur, tmp;
    pre = *L;
    cur = pre->next;
    while (cur) {
        int value = cur->data > 0 ? cur->data : cur->data * -1;
        if (flag[value - 1]) {
            tmp = cur;
            cur = cur->next;
            pre->next = cur;
            free(tmp);
        } else {
            flag[value - 1] = 1;
            pre = cur;
            cur = cur->next;
        }
    }
    free(flag);
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1;
    ElemType a[6] = {0, 15, 3, -3, -15, 2};
    ListInit(&L1, a, 6);
    RemoveAbsRepeat(&L1, 16);
    PrintList(L1);
    return 0;
}
// 输出
  0 15  3  2