int CopyStack(SqStack S1,SqStack *S2,SqStack temp);/*本题要求函数*/

/**
* 复制栈S1到S2，并返回元素数量
* S1: 待复制的栈
* S2: 复制后的栈
* temp: 临时栈
*/
int CopyStack(SqStack S1, SqStack *S2, SqStack temp)
{
int count = 0; // 计数器，记录元素数量
ElemType e; // 临时变量，保存栈顶元素

// 初始化S2和temp
InitStack(S2);
InitStack(&temp);

// 将S1中的所有元素倒入temp中
while (!StackEmpty(S1))
{
Pop(&S1, &e);
Push(&temp, e);
count++;
}

// 将temp中的所有元素倒入S2中
while (!StackEmpty(temp))
{
Pop(&temp, &e);
Push(S2, e);
}

// 返回元素数量
return count;
}

相关问题

用C语言利用temp栈将一个非空栈s1的所有元素按原样复制到另一个栈s2当中去。

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

#define MAXSIZE 100

typedef struct Stack {
    int data[MAXSIZE];
    int top;
}Stack;

Stack* createStack() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->top = -1;
    return stack;
}

void push(Stack* stack, int value) {
    if(stack->top == MAXSIZE-1) {
        printf("Stack is full.\n");
        return;
    }
    stack->top++;
    stack->data[stack->top] = value;
}

int pop(Stack* stack) {
    if(stack->top == -1) {
        printf("Stack is empty.\n");
        return -1;
    }
    int value = stack->data[stack->top];
    stack->top--;
    return value;
}

void copyStack(Stack* s1, Stack* s2) {
    Stack* temp = createStack();
    while(s1->top != -1) {
        push(temp, pop(s1));
    }
    while(temp->top != -1) {
        int value = pop(temp);
        push(s1, value);
        push(s2, value);
    }
    free(temp);
}

void printStack(Stack* stack) {
    while(stack->top != -1) {
        printf("%d ", pop(stack));
    }
    printf("\n");
}

int main() {
    Stack* s1 = createStack();
    push(s1, 1);
    push(s1, 2);
    push(s1, 3);
    push(s1, 4);
    printf("s1: ");
    printStack(s1);

    Stack* s2 = createStack();
    copyStack(s1, s2);

    printf("s1: ");
    printStack(s1);
    printf("s2: ");
    printStack(s2);

    free(s1);
    free(s2);

    return 0;
}

输出结果：

s1: 4 3 2 1 
s1: 4 3 2 1 
s2: 4 3 2 1

1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列； 3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列； 4．求二叉树的深度/结点数目/叶结点数目； 5．将二叉树每个结点的左右子树交换位置； 6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）； 7. 计算二叉树最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）； 8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点。 9.用C语言

实现以上功能。

1. 构造二叉链表表示的二叉树

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 先序遍历构造二叉树
void createBiTree(BiTree *T) {
    int data;
    scanf("%d", &data);
    if (data == 0) {
        *T = NULL;
    } else {
        *T = (BiTree) malloc(sizeof(BiTNode));
        (*T)->data = data;
        createBiTree(&(*T)->lchild);
        createBiTree(&(*T)->rchild);
    }
}

2. 递归遍历二叉树

// 先序遍历
void preOrderTraverse(BiTree T) {
    if (T) {
        printf("%d ", T->data);
        preOrderTraverse(T->lchild);
        preOrderTraverse(T->rchild);
    }
}

// 中序遍历
void inOrderTraverse(BiTree T) {
    if (T) {
        inOrderTraverse(T->lchild);
        printf("%d ", T->data);
        inOrderTraverse(T->rchild);
    }
}

// 后序遍历
void postOrderTraverse(BiTree T) {
    if (T) {
        postOrderTraverse(T->lchild);
        postOrderTraverse(T->rchild);
        printf("%d ", T->data);
    }
}

// 层次遍历
void levelOrderTraverse(BiTree T) {
    if (!T) return;
    Queue Q;
    initQueue(&Q);
    enQueue(&Q, T);
    while (!isEmptyQueue(Q)) {
        BiTree p = deQueue(&Q);
        printf("%d ", p->data);
        if (p->lchild) enQueue(&Q, p->lchild);
        if (p->rchild) enQueue(&Q, p->rchild);
    }
}

3. 非递归遍历二叉树

// 先序遍历
void preOrderTraverseNonRecursion(BiTree T) {
    Stack S;
    initStack(&S);
    BiTree p = T;
    while (p || !isEmptyStack(S)) {
        if (p) {
            printf("%d ", p->data);
            push(&S, p);
            p = p->lchild;
        } else {
            p = pop(&S);
            p = p->rchild;
        }
    }
}

// 中序遍历
void inOrderTraverseNonRecursion(BiTree T) {
    Stack S;
    initStack(&S);
    BiTree p = T;
    while (p || !isEmptyStack(S)) {
        if (p) {
            push(&S, p);
            p = p->lchild;
        } else {
            p = pop(&S);
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
}

// 后序遍历
void postOrderTraverseNonRecursion(BiTree T) {
    Stack S;
    initStack(&S);
    BiTree p = T, r = NULL;
    while (p || !isEmptyStack(S)) {
        if (p) {
            push(&S, p);
            p = p->lchild;
        } else {
            BiTree peek_elem = getTop(S);
            if (peek_elem->rchild && r != peek_elem->rchild) {
                p = peek_elem->rchild;
            } else {
                printf("%d ", peek_elem->data);
                r = pop(&S);
            }
        }
    }
}

4. 求二叉树的深度/结点数目/叶结点数目

// 求二叉树深度
int getDepth(BiTree T) {
    if (!T) return 0;
    int left_depth = getDepth(T->lchild);
    int right_depth = getDepth(T->rchild);
    return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

// 求二叉树结点数
int getNodeNum(BiTree T) {
    if (!T) return 0;
    return getNodeNum(T->lchild) + getNodeNum(T->rchild) + 1;
}

// 求二叉树叶结点数
int getLeafNodeNum(BiTree T) {
    if (!T) return 0;
    if (!T->lchild && !T->rchild) return 1;
    return getLeafNodeNum(T->lchild) + getLeafNodeNum(T->rchild);
}

5. 将二叉树每个结点的左右子树交换位置

void swap(BiTree T) {
    if (!T) return;
    BiTree tmp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = tmp;
    swap(T->lchild);
    swap(T->rchild);
}

6. 设计双序遍历算法

void doubleOrderTraverse(BiTree T) {
    if (!T) return;
    printf("%d ", T->data);
    doubleOrderTraverse(T->lchild);
    printf("%d ", T->data);
    doubleOrderTraverse(T->rchild);
}

7. 计算二叉树最大宽度

int getWidth(BiTree T) {
    if (!T) return 0;
    Queue Q;
    initQueue(&Q);
    enQueue(&Q, T);
    int max_width = 1;
    while (!isEmptyQueue(Q)) {
        int level_len = getSize(Q);
        max_width = max(max_width, level_len);
        for (int i = 0; i < level_len; i++) {
            BiTree p = deQueue(&Q);
            if (p->lchild) enQueue(&Q, p->lchild);
            if (p->rchild) enQueue(&Q, p->rchild);
        }
    }
    return max_width;
}

8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点

void getLongestPath(BiTree T, int *max_depth, Stack *S, Stack *max_S) {
    if (!T) return;
    push(S, T);
    if (!T->lchild && !T->rchild) { // 到达叶结点
        if (S->size > *max_depth) {
            *max_depth = S->size;
            copyStack(S, max_S);
        }
    } else {
        getLongestPath(T->lchild, max_depth, S, max_S);
        getLongestPath(T->rchild, max_depth, S, max_S);
    }
    pop(S);
}

void printStack(Stack *S) {
    for (int i = 0; i < S->size; i++) {
        printf("%d ", S->data[i]->data);
    }
}

void printLongestPath(BiTree T) {
    int max_depth = 0;
    Stack S, max_S;
    initStack(&S);
    initStack(&max_S);
    getLongestPath(T, &max_depth, &S, &max_S);
    printStack(&max_S);
}