Mki's Blog

数据结构(三):二叉树建立/遍历以及有序链表的合并

题目描述

题目要求

03-树2 List Leaves (25 分)
Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

输入格式:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

输出格式:

For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

输入样例:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例:

4 1 5
这题也不难。 (感谢三金学长带我学调试。。呜呜呜呜呜

#include<stdio.h>
#include<ctype.h>
#define _NO_CRT_STDIO_INLINE
struct Node {
    int root;
    int left;
    int right;
};
/*


*/

int main(void) {
    int num;
    struct Node nodes[10];
    scanf_s("%d\n", &num);
    for (int i = 0; i < num; i++) {
        nodes[i].root = 1;
        nodes[i].left = -1;
        nodes[i].right = -1;
    }

    for (int i = 0; i < num; ++i) {
        char ch1, ch2;
        scanf_s("%c\n", &ch1);
        scanf_s("%c", &ch2);
        getchar();

        if (isdigit(ch1)) {
            nodes[i].left = ch1 - '0';  //'0'是 48
            nodes[ch1 - '0'].root = 0;
        }
        if (isdigit(ch2)) {
            nodes[i].right = ch2 - '0';  //'0'是 48
            nodes[ch2 - '0'].root = 0;
        }
    }

    int root;
    for (int i = 0; i < num; ++i) {
        if (nodes[i].root == 1) {
            root = i;
            break;
        }
    }

    int leaves = 0;
    int queue[10];
    int head = 0, rear = 0;
    queue[rear++] = root;
    while (rear - head) {
        int node = queue[head++];
        if (nodes[node].left == -1 && nodes[node].right == -1) {
            if (leaves)
                printf(" ");
            printf("%d", node);
            ++leaves;
        }
        if (nodes[node].left != -1) {                //先left后right
            queue[rear++] = nodes[node].left;
        }
        if (nodes[node].right != -1) {
            queue[rear++] = nodes[node].right;
        }
    }
    //system("pause");
    getchar();
    getchar();
    getchar();
    return 0;
}

题目描述

题目要求

02-线性结构1 两个有序链表序列的合并 (15 分)
本题要求实现一个函数,将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义:

List Merge( List L1, List L2 );

其中List结构定义如下:

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L1和L2是给定的带头结点的单链表,其结点存储的数据是递增有序的;函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点,返回归并后的带头结点的链表头指针。

裁判测试程序样例:

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表;空链表将输出NULL */

List Merge( List L1, List L2 );

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例

3
1 3 5
5
2 4 6 8 10

输出样例

1 2 3 4 5 6 8 10
NULL
NULL

代码

傻乎乎的小题目,直接上代码。

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

typedef int ElementType;
typedef struct Node *PtrToNode;

struct Node {
    ElementType Data;
    PtrToNode Next;
};

typedef PtrToNode List;  //这里的List是个指针

List Read();
void Print(List L);
List Merge(List L1, List L2);

int main(void) {
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    getchar();
    getchar();
    return 0;
}

List Read() {
    int n;
    scanf_s("%d", &n);
    List L = (List)malloc(sizeof(PtrToNode));   //L是一个开始地址
    L->Next = NULL;
    if (n) {
        List r = L;
        for (int i = 0; i < n; i++) {
            List p = (List)malloc(sizeof(struct Node));
            scanf_s("%d", &(p->Data));
            r->Next = p;
            r = p;
        }
        r->Next = NULL;
    }
    return L;
}

void Print(List L) {
    List p = L->Next;
    if (p) {
        List r;
        r = L;
        while (r->Next) {
            r = r->Next;
            printf("%d", r->Data);
        }
    }
    else{
        printf("NULL");
    }
    printf("\n");
}

List Merge(List L1, List L2) {
    List pa, pb, pc, L;
    L = (List)malloc(sizeof(struct Node));
    pa = L1->Next;
    pb = L2->Next;
    pc = L;
    while (pa&&pb) {
        if (pa->Data <= pb->Data) {
            pc->Next = pa;
            pc = pa;
            pa = pa->Next;
        }
        else {
            pc->Next = pb;
            pc = pb;
            pb = pb->Next;
        }
    }

    pc->Next = pa ? pa : pb;
    L1->Next = NULL;
    L2->Next = NULL;
    return L;
}