数据结构与算法

# 笔记
# 数据结构

数据结构——算法设计实践

7 mins.7.9k160

线性表

NO.1 链表交叉逆序

从1到n顺序排列的n个元素带头结点单链表L = {a1, a2, …, an}，列表定义为

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode;

请设计一个算法，将L重新排列为L’ = {a1, an, a2, an-1, a3, an-2, …}，即将L的前半部分和后半部分交替排列。

要求：

时间复杂度为O(n)。
空间复杂度为O(1)。

Solution:

将链表分为两部分，前半部分和后半部分，然后将后半部分逆序，再交替合并两个部分。逆序和合并的操作分别时间复杂度为O(n)和O(n)，总时间复杂度为O(n)，原地操作空间复杂度为O(1)。

void Function(LNode *L) {
    // 找到链表中间位置后，将后半部分逆序
    LNode *slow = L->next, *fast = slow;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    LNode *mid = slow->next;
    slow->next = NULL;
    LNode *pre = NULL, *next = NULL;
    while (mid) {
        next = mid->next;
        mid->next = pre;
        pre = mid;
        mid = next;
    }
    mid = pre;

    // 从mid和头结点开始交叉合并两个链表
    pre = L->next;
    while (mid) {
        LNode *q = mid->next;
        mid->next = pre->next;
        pre->next = mid;
        pre = pre->next->next;
        mid = q;
    }
}

NO.2 链表的公共后缀

给定两个单链表L1和L2，要求找出它们的公共后缀部分。即找出从某个结点开始，L1和L2的后续结点完全相同的部分。

要求：

时间复杂度为O(n)。

Solution:
找到链表的公共后缀按理说应该从后向前遍历，但所给单链表无法实现。
由于共同后缀的长度应一样，所以我们可以首先计算链表长度差距，将长链表后半部分与短链表等长的部分一起检查。

LNode* Funciton(LNode *L1, LNode *L2) {
    int m=1, n=1;
    LNode *p = L1, *q = L2;
    while (p->next) {
        m++;
        p = p->next;
    } 
    while (q->next) {
        n++;
        q = q->next;
    }

    if (m > n) {
        for (int i = 0; i < m - n; i++) p = p->next;
    } else {
        for (int i = 0; i < n - m; i++) q = q->next;
    }

    LNode ans;
    while (p) {
        while (p && p->data != q->data) {
        p = p->next;
        q = q->next;
        }
        ans = p;
        while (p && p->data == p->data) {
        p = p->next;
        q = q->next;
        }
    }

    return ans;
}

NO.3 合并循环链表

给定两个循环链表的头结点L1和L2,要求最快速度将它们合并，m和n分别为L1和L2的长度。

要求：

时间复杂度为O(m+n)。

Solution:
将两个循环链表的尾结点指向对方的头结点即可，但循环链表里不需要两个头结点，所以删除一个头结点。

void Function(LNode *L1, LNode *L2) {
    if (!L1 || !L2) return;

    LNode *tail1 = L1;
    while (tail1->next != L1) {
        tail1 = tail1->next;
    }
    tail1->next = L2->next;

    LNode *tail2 = L2;
    while (tail2->next != L2) {
        tail2 = tail2->next;
    }
    tail2->next = L1;

    free(L2);
}

NO.4 链表排序

给定一个单链表头结点L，要求将其按升序排序。

要求：

时间复杂度为O(nlogn)。
就地排序，空间复杂度为O(1)。

Solution:
使用归并排序的思想，将链表分为两部分，分别排序后再合并。由于链表的特性，归并排序可以在O(nlogn)时间内完成。

LNode* Merge(LNode *L1, LNode *L2) {
    LNode dummy;
    LNode *tail = &dummy;
    dummy.next = NULL;

    while (L1 && L2) {
        if (L1->data < L2->data) {
            tail->next = L1;
            L1 = L1->next;
        } else {
            tail->next = L2;
            L2 = L2->next;
        }
        tail = tail->next;
    }

    if (L1) tail->next = L1;
    if (L2) tail->next = L2;

    return dummy.next;
}

LNode* Sort(LNode *L) {
    if (!L || !L->next) return L;

    // 使用快慢指针找到中间结点
    LNode *slow = L, *fast = L;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 分割链表
    LNode *mid = slow->next;
    slow->next = NULL;

    // 递归排序两部分
    LNode *left = Sort(L);
    LNode *right = Sort(mid);

    // 合并已排序的两部分
    return Merge(left, right);
}

NO.5 链表的逆向建立（头插法）

从表尾到表头依次输入n个整数，要求逆向建立一个带头结点的单链表。

要求：

时间复杂度为O(n)。

Solution:
可以使用头插法逆向建立链表。每次读取一个新元素，就将其插入到链表的头部。

LNode* CreateList(int n) {
    LNode *head = (LNode*)malloc(sizeof(LNode));
    head->next = NULL;

    for (int i = 0; i < n; i++) {
        int value;
        scanf("%d", &value);
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = value;
        newNode->next = head->next;
        head->next = newNode;
    }

    return head;
}

NO.6 循环链表的逆置

给定一个循环链表的头结点L，要求将其逆置。

要求：

时间复杂度为O(n)。

Solution:
可以使用双指针法，遍历链表并将每个结点的next指针指向前一个结点，直到遍历完整个链表。

void ReverseCircularList(LNode *L) {
    if (!L || !L->next || L->next == L) return;

    LNode *prev = NULL, *current = L->next, *next = NULL;
    LNode *tail = L; // 用于记录原链表的尾结点

    do {
        next = current->next;
        current->next = prev ? prev : L; // 如果prev为NULL，说明是第一个结点
        prev = current;
        current = next;
    } while (current != L->next);

    // 更新头结点的next指针
    tail->next = prev;
}

栈和队列

NO.7 公共栈

假设有两个栈S1, S2, 采用顺序栈方式，并且共享一个存储区[0..maxsize-1]。为了尽量利用空间，减少溢出的可能，采用栈顶相向迎面增长的存储方式，请设计有关的出入栈操作

Solution:

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top1; // 栈1的栈顶
    int top2; // 栈2的栈顶
} TwoStack;

void initTwoStack(TwoStack *s) {
    s->top1 = -1; // 栈1的栈顶指针
    s->top2 = MAXSIZE; // 栈2的栈顶指针
}

int push1(TwoStack *s, int value) {
    if (s->top1 + 1 == s->top2) {
        return -1; // 栈满
    }
    s->data[++s->top1] = value;
    return 0; // 成功
}

int push2(TwoStack *s, int value) {
    if (s->top2 - 1 == s->top1) {
        return -1;
    }
    s->data[--s->top2] = value;
    return 0;
}

int pop1(TwoStack *s) {
    if (s->top1 == -1) {
        return -1; // 栈空
    }
    int e;
    e = s->data[s->top1--];
    return e;
}

int pop2(TwoStack *s) {
    if (s->top2 == MAXSIZE) {
        return -1; // 栈空
    }
    int e;
    e = s->data[s->top2++];
    return e;
}

NO.8 递归展开（hard）

Ackerman函数定义：
Ack(m, n) =

n + 1 (m == 0)
Ack(m-1, 1) (m != 0, n == 0)
Ack(m-1, Ack(m, n-1)) (m != 0, n != 0)

写出非递归的Ack算法

Solution:

void Ack(int m, int n) {
    Stack s;
    initStack(&s);
    push(&s, m);
    push(&s, n);
    
    while (!isEmpty(&s)) {
        n = pop(&s);
        m = pop(&s);

        if (m == 0) {
            pop(&s);
            push(&s, n+1);
        } else if (n == 0) {
            push(&s, m - 1);
            push(&s, 1);
        } else {
            push(&s, m - 1);
            push(&s, n);
            push(&s, m);
            push(&s, n - 1);
        }
    }

}

思路：将递归算法展开成非递归算法的思路就是

写出递归形式
理清“递归中每一步都干了什么”
把递归形式中的每一次调用都当成一个栈帧，可以准备一个结构体来存储当前状态
处理好每次调用的内部情况，维护一个变量（本算法中是n）做好状态转移。

NO.9 递归展开趁热打铁

F(m) =

1 (m == 0)
mF(m / 2) (m > 0)
写出非递归形式的F函数。

Solution:

/*
if m ==0 return 1;
else return m * F(m / 2)
*/

int F_Function(int m) {
    Stack s;
    init(&s);
    int ans = 1;
    if (m == 1) return ans;
    while (m != 1) {
        push(&s, m);
        m = m / 2;
    }

    while (s.top + 1) {
        ans *= pop(&s);
    }
    return ans;
}

NO.10 循环队列

如果允许循环队列的两端都可以插入和删除，给出循环队列的定义和“队尾删除”以及“队头插入”的实现。

Solution:

// 循环队列的定义
#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front;  // 指向队头元素前一位置
    int rear;   // 指向队尾元素
} Deque;

// 队尾插入
int enqueue_rear(Deque* dq, int value) {
    if (isFull(dq)) return 0;

    dq->data[dq->rear] = value;
    dq->rear = (dq->rear + 1) % MAXSIZE;
    return 1;
}

// 队头删除
int dequeue_front(Deque* dq, int* value) {
    if (isEmpty(dq)) return 0;

    *value = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAXSIZE;
    return 1;
}