PTA-Data Structures and Algorithms (English)函数题

Deque CreateDeque()
{
    // 创建双向链表
    Deque deque = (Deque)malloc(sizeof(struct DequeRecord));
    if(deque == NULL) return NULL;
  
    // 创建Deque中的节点，头节点
    PtrToNode head_node = (PtrToNode)malloc(sizeof(struct Node));
    if(head_node == NULL) 
    {
        free(deque);
        return NULL;
    }
    head_node->Next = NULL;
    head_node->Last = NULL;
    deque->Front = head_node;
    deque->Rear = head_node;

    return deque;
}

// 入队，成功返回1，失败返回0
int Push(ElementType X, Deque D )
{
    // 创建要插入的节点
    PtrToNode push_node = (PtrToNode)malloc(sizeof(struct Node));
    if(push_node == NULL) return 0;

    // 将X保存到节点中，并将节点插入到头节点之后
    push_node->Element = X;
    push_node->Next = D->Front->Next;
    push_node->Last = D->Front;

    // 非空链表插入处理
    // 将原本首元节点(如果存在)的前向指针指向当前节点
    if(push_node->Next != NULL)
    {
        push_node->Next->Last = push_node;
    }
    // 空链表插入处理
    else
    {
        D->Rear = push_node;
    }

    // 修改D的首元节点指针指向
    D->Front->Next = push_node;

    return 1;
}

// 出队，成功返回出队元素，并从队列中移除该元素，失败返回ERROR
ElementType Pop( Deque D )
{
    // 空队处理
    if(D->Front == D->Rear) return ERROR;

    // 非空队处理
    // 保存队头元素
    PtrToNode pop_node = D->Front->Next;
    ElementType element = pop_node->Element;
  
    D->Front->Next = pop_node->Next;
    // 从队列中删除该元素，删除后是否为空队，两种处理情况
    // 队列不止一个节点
    if(pop_node->Next != NULL)
    {
        pop_node->Next->Last = D->Front;
    }
    // 队列仅有一个节点
    else
    {
        // Front永远指向头节点，Rear指向头节点
        D->Rear = D->Front;
    }
    // 释放该节点
    free(pop_node);
    return element;
}

// 将X插入到D的末尾
int Inject( ElementType X, Deque D )
{
    // 创建要插入的节点
    PtrToNode inject_node = (PtrToNode)malloc(sizeof(struct Node));
    if(inject_node == NULL) return 0;
    inject_node->Element = X;
    // 因为头节点的存在，所以不论是空队还是非空队，都只需要将节点连接在Rear节点之后即可
    inject_node->Next = NULL;
    inject_node->Last = D->Rear;
    D->Rear->Next = inject_node;
    D->Rear = inject_node;

    return 1;
}

// 移出末尾节点
ElementType Eject( Deque D )
{
    // 空队处理
    if(D->Front == D->Rear) return ERROR;

    // 非空队处理
    PtrToNode eject_node = D->Rear;
    ElementType element = eject_node->Element;
    D->Rear = eject_node->Last;
    eject_node->Last->Next = NULL;
    free(eject_node);
    return element;
}

// 队头出队入队后 需要考虑 空队 和 非空队 是因为空队时需要修改Rear，非空队时不需要修改Rear
// 而队尾出队入队后 一定只需要处理Rear，Front永远指向头节点，不用处理

// 创建共享栈，两栈共享同一数组空间 
Stack CreateStack(int MaxElements)
{
    // 申请栈控制结构的内存 
    Stack stack = (Stack)malloc(sizeof(struct StackRecord));
  
    // 申请栈数组的内存空间（两个栈共享） 
    stack->Array = (ElementType *)malloc(sizeof(ElementType) * MaxElements);
  
    // 记录数组总容量 
    stack->Capacity = MaxElements;  
  
    // 栈1初始化：从数组头部开始，空栈时top指针为-1 
    stack->Top1 = -1;  
  
    // 栈2初始化：从数组尾部开始，空栈时top指针为数组末尾后一位置 
    stack->Top2 = MaxElements;   
  
    return stack;
}

// 判断指定栈是否为空 
int IsEmpty(Stack S, int Stacknum)
{
    if (Stacknum == 1)
        // 栈1为空的条件：top指针处于初始-1位置 
        return S->Top1 == -1;  
  
    if (Stacknum == 2)
        // 栈2为空的条件：top指针处于初始Capacity位置 
        return S->Top2 == S->Capacity; 
  
    // 处理异常栈编号（根据题意实际不会执行到这里） 
    return ERROR;  
}

// 判断共享数组是否已满 
int IsFull(Stack S)
{
    // 当栈1的下个插入位置(top+1)与栈2的下个插入位置(top-1)相遇时数组满 
    return S->Top1 + 1 == S->Top2; 
}

// 元素入栈操作 
int Push(ElementType X, Stack S, int Stacknum)
{
    if (Stacknum != 1 && Stacknum != 2) return 0;
    if(IsFull(S)) return 0;  // 前置检查数组是否已满
  
    switch (Stacknum)
    {
        case 1:
            // 栈1：先移动top指针再写入（前置++保证先移动到新位置） 
            S->Array[++S->Top1] = X;  
            break;
        case 2:
            // 栈2：先移动top指针再写入（前置--保证先移动到新位置） 
            S->Array[--S->Top2] = X;  
            break;
        default: 
            return ERROR;  // 处理异常栈编号
    }
    return 1;  // 入栈成功
}

// 获取栈顶元素并出栈 
ElementType Top_Pop(Stack S, int Stacknum)
{
    if (Stacknum != 1 && Stacknum != 2) return ERROR;
    if(IsEmpty(S,Stacknum)) return ERROR;  // 前置检查栈空
  
    switch (Stacknum)
    {
        case 1:
            // 栈1：先取当前元素，再移动top指针（后置--） 
            return S->Array[S->Top1--];  
        case 2:
            // 栈2：先取当前元素，再移动top指针（后置++） 
            return S->Array[S->Top2++];  
        default: 
            return ERROR;  // 处理异常栈编号
    }
}

// 两个多项式求和，指数相同，系数相加
// 给的例子是从高次到低次
Polynomial Add( Polynomial a, Polynomial b )
{
    // 不写这个也对，因为后续没有修改a和b链表，如果后续修改a和b链表，会同时影响main中的s，所以不写其实更好
    // if(a->Next == NULL) return b;
    // if(b->Next == NULL) return a;
    // 例子是高次到低次，先假设都是这样的
    PtrToNode a_temp = a->Next;
    PtrToNode b_temp = b->Next;
    Polynomial result = (Polynomial)malloc(sizeof(struct Node));
    result->Next = NULL;
    PtrToNode r_tail = result;

    // 都不为空的时候进行加法运算
    while (a_temp && b_temp)
    {
        if(a_temp->Exponent == b_temp->Exponent)
        {
            PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
            newNode->Coefficient = a_temp->Coefficient + b_temp->Coefficient;

            if(newNode->Coefficient != 0)
            {
                newNode->Exponent = a_temp->Exponent;
                newNode->Next = NULL;
                r_tail->Next = newNode;
                r_tail = newNode;
            }
            a_temp = a_temp->Next;
            b_temp = b_temp->Next;
        }
        else if(a_temp->Exponent > b_temp->Exponent)
        {
            PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
            newNode->Coefficient = a_temp->Coefficient;
            newNode->Exponent = a_temp->Exponent;
            newNode->Next = NULL;
            r_tail->Next = newNode;
            r_tail = newNode;

            a_temp = a_temp->Next;
        }
        else if(b_temp->Exponent > a_temp->Exponent)
        {
            PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
            newNode->Coefficient = b_temp->Coefficient;
            newNode->Exponent = b_temp->Exponent;
            newNode->Next = NULL;
            r_tail->Next = newNode;
            r_tail = newNode;

            b_temp = b_temp->Next;
        }
    }
    // 剩余a的情况下，复制a到result
    while(a_temp) 
    {
        PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
        newNode->Coefficient = a_temp->Coefficient;
        newNode->Exponent = a_temp->Exponent;
        newNode->Next = NULL;
        r_tail->Next = newNode;
        r_tail = newNode;

        a_temp = a_temp->Next;
    }
    // 剩余b的情况下，复制b到result
    while(b_temp) 
    {
        PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
        newNode->Coefficient = b_temp->Coefficient;
        newNode->Exponent = b_temp->Exponent;
        newNode->Next = NULL;
        r_tail->Next = newNode;
        r_tail = newNode;

        b_temp = b_temp->Next;
    }

    return result;
  
}

// 观察题目以及代码得知，为原地反转链表，而不是新建链表头插保存反转
List Reverse(List L)
{
    if (L == NULL || L->Next == NULL) return L; // 处理空链表情况

    Position current = L->Next; // 当前节点，从第一个节点开始
    Position last = NULL;  // 上一个节点
    Position next = NULL;  // 下一个节点

    while (current != NULL) 
    {
        next = current->Next;   // 先保存下一个节点
        current->Next = last;   // 反转指针
        last = current; // 上一个指针前移
        current = next; // 当前指针前移
    }
    // 当current为空时，last为最后一个节点
    L->Next = last;
    return L;
}

#include <string.h> // 包含字符串处理函数

ElementType EvalPostfix(char *expr)
{
    /* 栈结构定义 */
    ElementType stack[Max_Expr]; // 用于存储操作数的栈
    int top = -1;               // 栈顶指针，初始化为-1表示空栈

    /* 使用strtok分割表达式字符串 */
    char *token = strtok(expr, " "); // 首次调用：以空格为分隔符分割字符串
    ElementType a, b, result;

    while (token != NULL) {
        /* 操作符处理分支 */
        if (strlen(token) == 1 && strchr("+-*/", token[0])) {
            // 有效性检查：栈中至少需要两个操作数
            if (top < 1) return Infinity;

            // 弹出操作数（注意顺序：先弹出的是第二个操作数）
            b = stack[top--]; // 弹出栈顶元素作为右操作数
            a = stack[top--]; // 弹出次栈顶元素作为左操作数

            // 执行运算
            ElementType res;
            switch (token[0]) {
                case '+': 
                    res = a + b; 
                    break;  // 必须添加break防止case穿透
                case '-': 
                    res = a - b; 
                    break;
                case '*': 
                    res = a * b; 
                    break;
                case '/': 
                    if (b == 0) return Infinity; // 除零错误处理
                    res = a / b; 
                    break;
                default: 
                    return Infinity; // 无效操作符（理论上不会执行到这里）
            }

            // 运算结果入栈
            stack[++top] = res;
        } 
        /* 操作数处理分支 */
        else { 
            char *end; // 用于检测转换终止位置的指针
            ElementType num = strtod(token, &end); // 字符串转浮点数
  
            // 检查转换有效性：end必须指向字符串末尾
            if (*end != '\0') {
                return Infinity; // 包含非法字符（如12a3.5）
            }
  
            // 数字入栈
            stack[++top] = num;
        }

        // 继续获取下一个token（注意参数变为NULL）
        token = strtok(NULL, " ");
    }

    /* 最终结果检查 */
    // 正确情况下栈中应只剩1个元素（计算结果）
    return (top == 0) ? stack[0] : Infinity;
}

// 层序遍历
void Level_order ( Tree T, void (*visit)(Tree ThisNode) )
{
    if (T == NULL) return; // 处理空树情况

    // 使用数组模拟队列，题目中节点数量并不多
    Tree queue[MaxTree];
    int front = 0;  // 头指针
    int rear = 0;   // 尾指针

    queue[rear++] = T;  // 根节点入队，尾指针后移

    while(front < rear)
    {
        Tree current = queue[front++]; // 取出队头节点，并出队
        visit(current); // 访问队头节点
        if(current->Left)
        {
            queue[rear++] = current->Left;  // 左孩子入队
        }
        if(current->Right)
        {
            queue[rear++] = current->Right; // 右孩子入队
        }
    }
}

int Isomorphic(Tree T1, Tree T2)
{
    // 如果两棵树都为空，则同构
    if (T1 == NULL && T2 == NULL)
        return 1;
    // 如果其中一棵为空而另一棵不为空，则不同构
    if ((T1 == NULL && T2 != NULL) || (T1 != NULL && T2 == NULL))
        return 0;
    // 当前节点的元素必须相同
    if (T1->Element != T2->Element)
        return 0;
    // 递归判断两种情况：不交换左右子树或交换左右子树
    return (Isomorphic(T1->Left, T2->Left) && Isomorphic(T1->Right, T2->Right)) ||
           (Isomorphic(T1->Left, T2->Right) && Isomorphic(T1->Right, T2->Left));
}

// 向上渗透
void PercolateUp(int p, PriorityQueue H) {
    // 暂存刚插入的元素
    ElementType temp = H->Elements[p];
    // 从刚插入节点开始向上寻找父节点，从下往上遍历
    while (p > 1) {
        int parent = p / 2;
        // 如果刚插入的元素小于当前位置的父节点，父节点元素下移，指针上移
        if (temp < H->Elements[parent]) {
            H->Elements[p] = H->Elements[parent];
            p = parent;
        } else {// 如果出现刚插入的节点大于父节点，则不能向上调整
            break;
        }
    }
    // 当退出循环后，p在刚插入节点应该在的位置，将暂存元素保存到根节点
    H->Elements[p] = temp;
}
void PercolateDown(int p, PriorityQueue H) {
    // 暂存删除的元素
    ElementType temp = H->Elements[p];
    int child;
    // 没有溢出，从上往下遍历
    while (p * 2 <= H->Size) {
        // 寻找子节点位置
        child = p * 2;
        // 没溢出且找到左右节点较小的那个
        if (child != H->Size && H->Elements[child + 1] < H->Elements[child]) {
            child++;
        }
        // 如果子节点小于要删除的节点，子节点上移
        if (H->Elements[child] < temp) {
            H->Elements[p] = H->Elements[child];
            p = child;
        } else {
            break;
        }
    }
    // 此时找到最下方的位置，将暂存的要删除的元素保存到最下方
    H->Elements[p] = temp;
}

// low指针管理false，mid指针用于遍历，high指针用于管理true
// 将false放前边，true放后边，剩下的maybe就在中间了。
// 所以从头开始遍历，遇到false放前边，low指针右移，同时mid指针右移
// 因为是与前边交换，指针是从前边遍历过来的，只能是false和maybe互换，如果前边有true，已经换到了后边
// 如果遇到true，与high指针互换，high指针左移，但mid指针不动，因为high指的可能是maybe或者false
// 所以重新检查mid位置的元素是什么，继续遍历，
// 直到mid到high的位置遍历最后一个，如果这个是false，需要将它移动到前边，mid大于high之后遍历完毕
void MySort(ElementType A[], int N) {
    int low = 0, mid = 0, high = N - 1;
    while (mid <= high) {
        if (A[mid] == false) {        // false的枚举值为1
            // 交换到false区域
            ElementType temp = A[low];
            A[low] = A[mid];
            A[mid] = temp;
            low++;
            mid++;
        } else if (A[mid] == maybe) { // maybe的枚举值为2
            // 留在中间区域
            mid++;
        } else {                       // true的枚举值为0
            // 交换到true区域
            ElementType temp = A[mid];
            A[mid] = A[high];
            A[high] = temp;
            high--;
        }
    }
}

static void DFS(Vertex u, Graph G, int *visited, Vertex *stack, int *top) {
    visited[u] = 1;
    PtrToVNode node = G->Array[u];
    while (node != NULL) {
        Vertex v = node->Vert;
        if (!visited[v]) {
            DFS(v, G, visited, stack, top);
        }
        node = node->Next;
    }
    stack[++(*top)] = u;
}

static void DFS2(Graph G, Vertex u, int *visited, void (*visit)(Vertex)) {
    visited[u] = 1;
    visit(u);
    PtrToVNode node = G->Array[u];
    while (node != NULL) {
        Vertex v = node->Vert;
        if (!visited[v]) {
            DFS2(G, v, visited, visit);
        }
        node = node->Next;
    }
}

void StronglyConnectedComponents(Graph G, void (*visit)(Vertex V)) {
    Vertex stack[MaxVertices];
    int top = -1;
    int visited[MaxVertices] = {0};

    // 第一次DFS遍历原图，得到逆后序栈
    for (int u = 0; u < G->NumOfVertices; u++) {
        if (!visited[u]) {
            DFS(u, G, visited, stack, &top);
        }
    }

    // 构造转置图
    Graph transposeG = (Graph)malloc(sizeof(struct GNode));
    transposeG->NumOfVertices = G->NumOfVertices;
    transposeG->NumOfEdges = G->NumOfEdges;
    transposeG->Array = (PtrToVNode *)malloc(transposeG->NumOfVertices * sizeof(PtrToVNode));

    for (int i = 0; i < transposeG->NumOfVertices; i++) {
        transposeG->Array[i] = NULL;
    }

    for (int u = 0; u < G->NumOfVertices; u++) {
        PtrToVNode node = G->Array[u];
        while (node != NULL) {
            Vertex v = node->Vert;
            PtrToVNode newNode = (PtrToVNode)malloc(sizeof(struct VNode));
            newNode->Vert = u;
            newNode->Next = transposeG->Array[v];
            transposeG->Array[v] = newNode;
            node = node->Next;
        }
    }

    // 第二次DFS遍历转置图，按栈的顺序处理
    int visited2[MaxVertices] = {0};
    for (int i = top; i >= 0; i--) {
        Vertex u = stack[i];
        if (!visited2[u]) {
            DFS2(transposeG, u, visited2, visit);
            printf("\n");
        }
    }

    // 释放转置图内存
    for (int i = 0; i < transposeG->NumOfVertices; i++) {
        PtrToVNode node = transposeG->Array[i];
        while (node != NULL) {
            PtrToVNode tmp = node;
            node = node->Next;
            free(tmp);
        }
    }
    free(transposeG->Array);
    free(transposeG);
}