Function

01-复杂度3 二分查找 (20 分)

本题要求实现二分查找算法。

Position BinarySearch( List L, ElementType X ){
  int left = 1, right = L->Last, mid;
  while(left <= right){
    mid = (left + right) / 2;
    if (X < L->Data[mid]) right = mid - 1; //updata right
    else if (X > L->Data[mid]) left = mid + 1; //updata left
    else return mid; // if (X == Data[mid])
  } 
  return NotFound; //when left > right, it is malposed that meant not find 'X', so return NotFound
}

思路：
想一想这个说法是否正确？在二分查找的程序实现中，如果left和right的更新不是取mid+1和mid-1而是都取mid，程序也是正确的。

答案

这个说法是错误的。考虑查找值大于数组内最大值的情况，如果都取mid，循环到只有两元素时就会导致mid始终与左边界值相等，从而程序**无限循环**；考虑查找值小于数组内最小值的情况，由于可能存在数列中仅有一个元素的情况所以进入循环的条件必须要包含left==right，在此前提下，循环到最后左右边界与mid将会重合从而无限循环。

02-线性结构1 两个有序链表序列的合并 (15 分)

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

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

            temp = L2->Next;
            L2->Next = temp->Next;
            rear->Next = temp;
            rear = temp;
        }
    }
    if (L1->Next) {
        rear->Next = L1->Next;
        L1->Next = NULL;
    }
    if (L2->Next) {
        rear->Next = L2->Next;
        L2->Next = NULL;
    }
    return L;
}

思路：注意非递减的意思是，不严格递增。也就是说，当遇到两个相同的数字时，两个数字都要合并进去。

04-树7 二叉搜索树的操作集 (30 分)

完成日期：21.11.06

本题要求实现给定二叉搜索树的5种常用操作。

函数接口定义：

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；
函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；
函数FindMin返回二叉搜索树BST中最小元结点的指针；
函数FindMax返回二叉搜索树BST中最大元结点的指针。

裁判测试程序样例：

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

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3结尾无空行

输出样例：

Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9结尾无空行

AC code：

//Insert根据搜索二叉树左小右大的特点设置，以建立一个搜索二叉树
BinTree Insert( BinTree BST, ElementType X ) {

    //插入操作
    if (BST == NULL) { 
        BST = (BinTree) malloc(sizeof(struct TNode)); //开辟树结点空间
        BST->Data = X;
        BST->Left = NULL;
        BST->Right = NULL;
    }

    //找到插入结点
    else if (X > BST->Data)
        BST->Right = Insert(BST->Right, X);
    else if (X < BST->Data)
        BST->Left = Insert(BST->Left, X);
    return BST;
}

//Find根据搜索二叉树左小右大的特点设置，以查找目标元素
//返回值是树结点的地址'Position'
Position Find( BinTree BST, ElementType X ) {

    //返回目标元素所在二叉树，注意，返回的是树结点，不是元素数值
    if (BST == NULL)
        return NULL; //没找到返回NULL
    else if (X == BST->Data)
        return BST;
    
    //找到目标元素所在树结点
    else if (X > BST->Data)
        return Find (BST->Right, X);
    else if (X < BST->Data)
        return Find (BST->Left, X);
}

//FindMin根据搜索二叉树左小右大的特点设置，以查找最小元素
//返回值是树结点的地址'Position'
Position FindMin( BinTree BST ) {
    if (BST == NULL)
        return NULL; //树是空的，找不了返回NULL

    //树的最左端是最小元素
    while (BST->Left != NULL) 
        BST = BST->Left;
    return BST;
}

//FindMax根据搜索二叉树左小右大的特点设置，以查找最大元素
//返回值是树结点的地址'Position'
Position FindMax( BinTree BST ) {
    if (BST == NULL)
        return NULL;//树是空的，找不了返回NULL
    
    //树的最右端是最小元素
    while (BST->Right != NULL)
        BST = BST->Right;
    return BST;
}

//Delete根据搜索二叉树左小右大的特点设置，以删除目标元素所在树结点
BinTree Delete( BinTree BST, ElementType X ){
    BinTree temp; //temp暂时是个空的树结点

    //找不到，返回"Not Found\n"
    if (BST == NULL)
        printf("Not Found\n");

     //找得到
    else{
        //找到要删除的树结点
        if (X < BST->Data)
            BST->Left = Delete(BST->Left, X);
        else if (X > BST->Data)
            BST->Right = Delete(BST->Right, X);
        
        //执行删除
        else{
            //如果该结点的左、右子树都存在（不妨命名该结点为'TNodeA'）
            if (BST->Left && BST->Right){
                temp = FindMin(BST->Right); //将TNodeA的右子树最小结点赋给temp
                BST->Data = temp->Data; //将TNodeA的右子树最小结点的值给自己，完成删除TNodeA
                BST->Right = Delete(BST->Right, temp->Data);  //记得还要删掉TNodeA的右子树最小结点
            }

            //如果该结点的左、右子树只有一棵存在，或者两棵都不存在（不妨命名该结点为'TNodeB'）
            else{
                temp = BST; //将TNodeB本身赋给temp

                //如果TNodeB的左子树不存在，即TNodeB的右子树存在
                if (BST->Left == NULL) 
                    BST = BST->Right; //将TNodeB的右子树赋给自己，完成删除TNodeB
                
                //如果TNodeB的右子树不存在，即TNodeB的左子树存在
                else if (BST->Right == NULL)
                    BST = BST->Left;//将TNodeB的左子树赋给自己，完成删除TNodeB
                
                //记得还要通过temp释放原本的TNodeB（这也是TNodeB左、右两棵子树都不存在的情况）
                free(temp); 
            }
        }
    }
    return BST;
}

思路：

根据搜索二叉树左小右大的特点设置函数。
时常利用递归。
多考虑树节点为空的情况。

本地AC code：

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

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}

void PreorderTraversal( BinTree BT ) //先序遍历，重复递归即可
{
    if (BT == NULL)
        return; 
    printf(" %d", BT->Data);
    PreorderTraversal( BT->Left);
    PreorderTraversal( BT->Right);
}

void InorderTraversal( BinTree BT ) //中序遍历，重复递归即可
{
    if (BT == NULL)
        return;
    InorderTraversal( BT->Left );
    printf(" %d", BT->Data);
    InorderTraversal( BT->Right);
}

//Insert根据搜索二叉树左小右大的特点设置，以建立一个搜索二叉树
BinTree Insert( BinTree BST, ElementType X ) {

    //插入操作
    if (BST == NULL) { 
        BST = (BinTree) malloc(sizeof(struct TNode)); //开辟树结点空间
        BST->Data = X;
        BST->Left = NULL;
        BST->Right = NULL;
    }

    //找到插入结点
    else if (X > BST->Data)
        BST->Right = Insert(BST->Right, X);
    else if (X < BST->Data)
        BST->Left = Insert(BST->Left, X);
    return BST;
}

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

//Find根据搜索二叉树左小右大的特点设置，以查找目标元素
//返回值是树结点的地址'Position'
Position Find( BinTree BST, ElementType X ) {

    //返回目标元素所在二叉树，注意，返回的是树结点，不是元素数值
    if (BST == NULL)
        return NULL; //没找到返回NULL
    else if (X == BST->Data)
        return BST;
    
    //找到目标元素所在树结点
    else if (X > BST->Data)
        return Find (BST->Right, X);
    else if (X < BST->Data)
        return Find (BST->Left, X);
}

//FindMin根据搜索二叉树左小右大的特点设置，以查找最小元素
//返回值是树结点的地址'Position'
Position FindMin( BinTree BST ) {
    if (BST == NULL)
        return NULL; //树是空的，找不了返回NULL

    //树的最左端是最小元素
    while (BST->Left != NULL) 
        BST = BST->Left;
    return BST;
}

//FindMax根据搜索二叉树左小右大的特点设置，以查找最大元素
//返回值是树结点的地址'Position'
Position FindMax( BinTree BST ) {
    if (BST == NULL)
        return NULL;//树是空的，找不了返回NULL
    
    //树的最右端是最小元素
    while (BST->Right != NULL)
        BST = BST->Right;
    return BST;
}

//Delete根据搜索二叉树左小右大的特点设置，以删除目标元素所在树结点

BinTree Delete( BinTree BST, ElementType X ){
    BinTree temp; //temp暂时是个空的树结点

    //找不到，返回"Not Found\n"
    if (BST == NULL)
        printf("Not Found\n");

     //找得到
    else{
        //找到要删除的树结点
        if (X < BST->Data)
            BST->Left = Delete(BST->Left, X);
        else if (X > BST->Data)
            BST->Right = Delete(BST->Right, X);
        
        //执行删除
        else{
            //如果该结点的左、右子树都存在（不妨命名该结点为'TNodeA'）
            if (BST->Left && BST->Right){
                temp = FindMin(BST->Right); //将TNodeA的右子树最小结点赋给temp
                BST->Data = temp->Data; //将TNodeA的右子树最小结点的值给自己，完成删除TNodeA
                BST->Right = Delete(BST->Right, temp->Data);  //记得还要删掉TNodeA的右子树最小结点
            }

            //如果该结点的左、右子树只有一棵存在，或者两棵都不存在（不妨命名该结点为'TNodeB'）
            else{
                temp = BST; //将TNodeB本身赋给temp

                //如果TNodeB的左子树不存在，即TNodeB的右子树存在
                if (BST->Left == NULL) 
                    BST = BST->Right; //将TNodeB的右子树赋给自己，完成删除TNodeB
                
                //如果TNodeB的右子树不存在，即TNodeB的左子树存在
                else if (BST->Right == NULL)
                    BST = BST->Left;//将TNodeB的左子树赋给自己，完成删除TNodeB
                
                //记得还要通过temp释放原本的TNodeB（这也是TNodeB左、右两棵子树都不存在的情况）
                free(temp); 
            }
        }
    }
    return BST;
}

Programming

01-复杂度1 最大子列和问题 (20 分)

给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；
数据2：10^2个随机整数；
数据3：10^3个随机整数；
数据4：10^4个随机整数；
数据5：10^5个随机整数；

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

1
2
3

6
-2 11 -4 13 -5 -2
结尾无空行

输出样例:

1
2

20
结尾无空行

答案：

#include<stdio.h>

int MaxSubseqSum2(int a[], int N);

int main(){
    int N,i;
    scanf("%d",&N);
    int A[N];
    for(i=0 ;i<N ;i++)
        scanf("%d",&A[i]);              //scanf是存储于地址当中
    printf("%d",MaxSubseqSum2(A, N));   //输入指针地址 A
    return 0;
}

int MaxSubseqSum2(int a[], int n){      //此时数组即是首地址，也可以用*A表示
    int ThisSum, MaxSum = 0;
    int i,j;
    for(i = 0; i < n; i++){
        ThisSum = 0;
        for(j = i; j < n; j++){
           ThisSum += a[j];
            if(ThisSum > MaxSum)//比较当前子列和与预设最大子列和
            MaxSum = ThisSum;
        }
    }
    return MaxSum; //O(N^2)
}

思路：用数组实现，MaxSubseqSum2使用两个for循环，比较当前子列和与预设最大子列和。

01-复杂度2 Maximum Subsequence Sum (25 分)

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

1
2
3

10
-10 1 2 3 4 -5 -23 3 7 -21
结尾无空行

Sample Output:

1 2	10 1 4 结尾无空行

AC code:

/*double for loop algorithm*/
#include<stdio.h>

int* MaxSubseqSum2(int a[], int N);

int main(){
    int N,i;
    scanf("%d",&N);
    int A[N];
    for(i=0 ;i<N ;i++)
        scanf("%d",&A[i]);         
    printf("%d %d %d",*(MaxSubseqSum2(A, N)), *(MaxSubseqSum2(A, N) + 1), *(MaxSubseqSum2(A, N) + 2));   
    return 0;
}

int* MaxSubseqSum2(int a[], int n){  
  int first, last, ThisSum, MaxSum = 0;
  static int ret[3]; 
  int i,j;
  for(i = 0; i < n; i++){
    ThisSum = 0;
    for(j = i; j < n; j++){
      ThisSum += a[j];
      if(ThisSum > MaxSum){//比较当前子列和与预设最大子列和
        MaxSum = ThisSum;
        first = a[i];//设置最大子列和的第一个元素
        last = a[j];//设置最大子列和的最后一个元素
      }
    }
  }
  if(MaxSum == 0){ 
    first = a[0]; //序列全是负整数的情况
    last = a[n - 1];
    for(i = 0; i < n ;i++)//序列全是非正整数的情况，即至少有一个0和其它负数
      if(a[i] == 0){
        first = last = 0;
        break;
      }
    }
  ret[0] = MaxSum;
  ret[1] = first;
  ret[2] = last;
  return ret; //O(N^2)
}

Reference AC code:

/*online algorithm*/
/*这是其它博主根据在线算法写的，作为参考*/
#include <stdio.h>
#define MAXSIEZ 10000
int a[MAXSIEZ];
int n;
void online() {
    int temp_Left = 0, right = 0, left = 0;//temp_Left为临时左下标，left为最大子序列最左边下标，right为最右边下标
    int ThisSum = 0, MaxSum = -1;//首先ThisSum代表临时子列和，MaxSum为最大子列和
    for (int i = 0; i < n; i++) {
        ThisSum += a[i];
        if (ThisSum < 0) {
            ThisSum = 0;
            temp_Left = i+1;//更新临时下标
        }
        else if (ThisSum > MaxSum) {
            MaxSum = ThisSum;
            left =  temp_Left;//更新左下标
            right = i;//右下标
        }
    }
    if (MaxSum < 0) {
        printf("0 %d %d", a[0], a[n-1]);
    }
    else {
        printf("%d %d %d", MaxSum, a[left], a[right]);
    }
}//O(NlogN)
int main() {
    //freopen("data.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    online();
    return 0;
}

思路：要区分两种特殊情况。

至少有一个零，输出结果为 0 0 0
全都是负数，输出结果为 0 first_neg_number last_neg_number

02-线性结构2 一元多项式的乘法与加法运算 (20 分)

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

1
2
3

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
结尾无空行

输出样例:

1
2
3

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
结尾无空行

答案：

//链表实现
#include<stdio.h>
#include<stdlib.h>

struct PolyNode{
    int coef; //系数
    int expon; //指数
    struct PolyNode *link;
};
typedef struct PolyNode *Polynomial;

int compare(int a, int b){
    if (a > b) return 1;
    if (a == b) return 0;
    if (a < b) return -1;
} //Compare(a, b)函数，若a > b，返回1；若a < b，返回-1；若a == b，返回0

void Attach(int c, int e, Polynomial *pRear){
    Polynomial P;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->link = NULL;
    (*pRear)->link = P;
    *pRear = P;
}

Polynomial ReadPoly(){
    Polynomial P, Rear, t;
    int c, e, N;
    scanf("%d", &N);
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while (N--) {
        scanf("%d %d", &c, &e);
        Attach(c, e, &Rear);
    }
    t = P; P = P->link; free(t);
    return P;
}

Polynomial Add(Polynomial P1, Polynomial P2){
    Polynomial front, rear, t;
    int sum;
    rear = (Polynomial)malloc(sizeof(struct PolyNode));
    front = rear;
    while (P1&&P2){
        switch (compare(P1->expon, P2->expon)){ //判别多项式尾部rear插入哪一项
        case 1:
            Attach(P1->coef, P1->expon, &rear);
            P1 = P1->link;    
            break;
        case -1:
            Attach(P2->coef, P2->expon, &rear);
            P2 = P2->link;    
            break;        
        case 0:
            sum = P1->coef + P2->coef;
            if (sum) Attach(sum, P1->expon, &rear);
            P1 = P1->link;
            P2 = P2->link;    
            break;
        }
    }
    for(; P1; P1 = P1->link) Attach(P1->coef, P1->expon, &rear);
    for(; P2; P2 = P2->link) Attach(P2->coef, P2->expon, &rear);
    rear->link = NULL;
    t = front; front = front->link; free(t);
    return front;
}

Polynomial Mult(Polynomial P1, Polynomial P2){ //逐项插入的解法，先用t1第一项历遍t2作为P，再用t1第二项、t2第三项...逐个历遍t2，同时每历遍一次插入一次P
    Polynomial P, Rear, t1, t2, t;
    int c, e;
    if (!P1 || !P2) return NULL;
    t1 = P1; t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL; //设置首部空结点
    Rear = P;
    while (t2) { //先用P1的第一项乘以P2，得到P
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->link;
    }
    t1 = t1->link;
    while (t1){
        t2 = P2; Rear = P;
        while (t2){
            e = t1->expon + t2->expon;
            c = t1->coef * t2->coef;
            while (Rear->link && Rear->link->expon > e) //rear下一项不为空，移动rear，直到rear下一项指数不大于插入项指数
                Rear = Rear->link; //移动rear
            if (Rear->link && Rear->link->expon == e) {//rear下一项不为空，且rear下一项指数和插入项指数相等时
                if (Rear->link->coef + c) //系数相加不为0时
                    Rear->link->coef += c;
                else { //系数相加为0时
                    t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            }
            else {//rear下一项指数和插入项指数不相等时，新建结点插入
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->link = Rear->link;
                Rear->link = t;
                Rear = Rear->link;
            }
            t2 = t2->link; //历遍t2
        }
        t1 = t1->link;//逐个历遍t1第二项之后
    }
    t2 = P; P = P->link; free(t2);
    return P;
}

void PrintPoly(Polynomial P){
    int flag = 0;
    if (!P){printf("0 0\n"); return;}
    while (P){
        if (!flag) //调整输出格式，使第一项输出头部无空格
            flag = 1;
        else
            printf(" ");//使第二项输出头部、第三项输出头部...有空格
        printf("%d %d",P->coef, P->expon);
        P = P->link; //输出下一个结点，我找了它接近两个小时，写的时候漏了
    }
    printf("\n");
}

int main(){
    Polynomial P1, P2, PP, PS;
    P1 = ReadPoly(); //读取
    P2 = ReadPoly();
    
    PP = Mult(P1, P2); //乘法
    PS = Add(P1,P2); //加法
    
    PrintPoly(PP); //打印
    PrintPoly(PS);
    return 0;
}

注意：
1、P(front)作为头部空结点指针，最后P(front)要用t配合free函数释放。

2、rear = P(front) 一开始是空结点指针，但最后会作为尾部结点指针，所以最终rear->link == NULL

3、设置flag调整输出格式。

02-线性结构3 Reversing Linked List (25 分)

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

翻译：给定一个常数K和一个单链链表L，你应该把L上每个K元素的链结颠倒。例如，给定L为1→2→3→4→5→6，如果K=3，那么你必须输出3→2→1→6→5→4；如果K=4，你必须输出4→3→2→1→5→6。

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

翻译：每个输入文件包含一个测试用例。对于每种情况，第一行包含第一个节点的地址、节点总数的正N（<105）和要反转的子列表的长度的正K（<N）。节点的地址是一个5位非负整数，空值用-1表示。

Then N lines follow, each describes a node in the format:

1	Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
结尾无空行

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
结尾无空行

AC code:

#include<stdio.h>
#define MaxSize 100005

int main(){
	int Data[MaxSize];
	int Next[MaxSize]; 
	int List[MaxSize]; //List[]用来存放当前结点的地址，其索引是序号0 ~ 100005
	int FirstAdd, N, K, i ,j, t;
	scanf("%d %d %d", &FirstAdd, &N, &K);

	//在Data[]中存放数值，在Next[]中存放下一个结点地址
	for(i = 0; i < N; i++){
		int tmpAdd, tmpData, tmpNext;
		scanf("%d %d %d", &tmpAdd, &tmpData, &tmpNext);
		Data[tmpAdd] = tmpData; //Date[]用来存放数值，其索引是当前结点地址
		Next[tmpAdd] = tmpNext; //Next[]用来存放下个结点的地址，其索引是当前结点地址
	}

	//在List中存放当前结点的地址
	int count = 0;   //累计有效结点数
	while(FirstAdd != -1){   //当尾结点为 -1 时结束 
		List[count++] = FirstAdd; 
		FirstAdd = Next[FirstAdd];  //将下个结点的地址赋值给FistAddress
	}

	//按区间反转
	for(i = 0; i < count-count%K; i += K){  //每 K个结点一个区间 
	//每个区间内，首、尾结点互换，次首、次尾结点互换结点，以此类推
	//奇数区间到最后自己和自己互换，没有影响
		for(j = 0; j < K/2; j++){  
			t = List[i+j];
			List[i+j] = List[i+K-j-1];
			List[i+K-j-1] = t; 
		}
	}

	//输出
	for(i = 0; i < count-1; i++)
		printf("%05d %d %05d\n",List[i], Data[List[i]], List[i+1]);
	//-1按'%05%'的格式输出为-0001，不符合要求，所以我们单独输出最后一个结点
	printf("%05d %d -1\n", List[count-1], Data[List[count-1]]); 
	return 0;
}

思路：用三个数组的方式模拟链表，分别存放当前地址、数值、下一个地址。实际上用结构数组、链表的方法也可以，但三个数组易于理解。

样例图示：

参考链接1；参考链接2

02-线性结构4 Pop Sequence (25 分)

完成日期：21.11.07

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

翻译：

给定一个最多能保存M个数的堆栈。按1，2，3，…，N的顺序推N个数字，然后随机弹出。您应该知道给定的数字序列是否可能是堆栈的弹出序列。例如，如果M是5，N是7，我们可以从堆栈中获得1，2，3，4，5，6，7，但不能从3，2，1，7，5，6，4。

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行包含3个数字（都不超过1000）：M（堆栈的最大容量）、N（推送序列的长度）和K（要检查的pop序列的数量）。接下来是K行，每行包含N个数字的pop序列。一行中的所有数字都用空格隔开。

输出规格：

对于每个弹出序列，如果确实是堆栈的可能弹出序列，则在一行中打印 “YES”，如果不是，则打印”NO”。

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
结尾无空行

Sample Output:

YES
NO
NO
YES
NO
结尾无空行

AC code：

#include <stdio.h> 
#include <stdlib.h> 
#define maxCapacity 1000 //堆栈最大可设置的容量为1000
 
typedef struct SNode{
	int capacity; //栈的容量'M'
	int top; //栈顶位置
	int data[maxCapacity]; 
}*Stack;

Stack CreatStack(int M){ //初始化一个空栈 
	Stack s = (Stack)malloc(sizeof(struct SNode));
	s->top = -1; //初始栈顶位置设为-1
	s->capacity = M;
	return s;
}

int Push(Stack s, int x){ //入栈，成功返回1，若溢出（即超出栈的容量'M'）返回0 
	if(s->capacity == s->top + 1) //若栈顶位置 + 1等于capacity，说明已经溢出一格
		return 0;
	else{
		s->data[++s->top] = x;//堆栈的索引即栈顶的位置要不断 + 1（从0开始赋值）
		return 1;
	}
}

void Pop(Stack s){//出栈 
	s->top--;
}

int Top(Stack s){//返回栈顶元素
	if(s->top >= 0)
		return s->data[s->top];
	else
		return -1;
}

//题目所考察的最重要的函数，利用stack先进后出的特点，判断样例是否可能为出栈序列
int IsPopPossible(int test[], int M, int N){ 
	Stack s = CreatStack(M);
	int j = 0; //样例的索引

  //按正整数序列顺序Push，每Push一个元素都要先判断是否溢出，再判断该元素能否Pop及其之前已经push的元素能否Pop
	for(int i = 1; i <= N; i++){
		if(!Push(s, i)) //入栈的同时，判断是否溢出，溢出直接返回0
			return 0;
		while(Top(s) == test[j]){ //判断能否Pop（栈顶元素数值和样例的元素数值相等才能Pop）
			Pop(s);
			j++; //'while'循环移到样例的下一个元素（可能只Pop一个，也可能连续Pop多个）
		}
	}

  //如果出栈元素个数和样例元素个数相等，说明是出栈序列，否则不是
	if(j == N)
		return 1;
	else
		return 0;
}

int main(){
	int M, N, K;//栈的容量M，进栈序列长度N，被检查的出栈序列个数K 
	scanf("%d %d %d",&M ,&N ,&K);	
	int test[N]; //测试样例
  
  //循环读取每一条出栈序列的元素并判断
	for(int i = 0; i < K; i++){ 		
		for(int j = 0; j < N; j++) 
			scanf("%d", &test[j]);					
		if(IsPopPossible(test, M, N))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

思路：

pop randomly这句话要和堆栈先进后出的特点紧密联系。
按1，2，3….，N（正整数序列）依次入栈，每入栈一个元素都要先判断是否溢出，如果没溢出，再判断该元素能否出栈及其之前已经入栈的元素能否出栈。最后，如果样例所有元素都能出栈，则说明是出栈序列。

参考链接

03-树1 树的同构 (25 分)

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

现给定两棵树，请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
结尾无空行

输出样例1:

1
2

Yes
结尾无空行

输入样例2（对应图2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:

No

答案：

#include<stdio.h>

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1

struct TreeNode{
  ElementType Element;
  Tree Left;
  Tree Right;
} T1[MaxTree], T2[MaxTree];

Tree BuildTree ( struct TreeNode T[]);
int Isomorphic(Tree R1,Tree R2);

int main(){
  Tree R1, R2;
  R1 = BuildTree(T1);
  R2 = BuildTree(T2);
  if (Isomorphic(R1, R2)) 
    printf("Yes\n");
  else 
    printf("No\n");
 return 0;
}

Tree BuildTree( struct TreeNode T[] ){
  int N, i;
  int check[MaxTree];
  Tree Root = Null; //Root set Null, because line 34 and line 55, if N = 0, return Null
  ElementType cl, cr;
  scanf("%d", &N);
  if (N) {
    for (i=0; i<N; i++) check[i] = 0;
    for (i=0; i<N; i++) {
    scanf("\n%c %c %c", &T[i].Element, &cl, &cr);
    if (cl != '-') { // four ‘if’ are at the same level
      T[i].Left = cl - '0';
      check[T[i].Left] = 1;
   }
    if (cl == '-') 
      T[i].Left = Null;
    if (cr != '-') {
      T[i].Right = cr-'0';
      check[T[i].Right] = 1;
    }
    if (cr == '-') 
      T[i].Right = Null;
    }
    for (i=0; i<N; i++)
      if (!check[i]) break;
    Root = i;
  }
  return Root;
}

int Isomorphic ( Tree R1, Tree R2 ){
  if ( (R1==Null )&& (R2==Null) ) 
    return 1;/* both empty */
  if ( ((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null)) )
    return 0; /* one of them is empty */
  if ( T1[R1].Element != T2[R2].Element )
    return 0; /* roots Element are different */
  if ( ( T1[R1].Left == Null )&&( T2[R2].Left == Null ) )
    return Isomorphic( T1[R1].Right, T2[R2].Right );/* both have no left sontree */
  if ( ((T1[R1].Left!=Null)&&(T2[R2].Left!=Null)) && ((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)) )
  /* no need to swap the left and the right */
  /*If the left son of both trees is not empty and the Element is the same, recurse on the left son*/
  /* 如果两棵树左儿子都不为空并且元素还是一样的，对左儿子进行递归*/
    return ( Isomorphic( T1[R1].Left, T2[R2].Left ) && Isomorphic( T1[R1].Right, T2[R2].Right ) );
  else /* need to swap the left and the right */
  /*If two trees have different left sons (one is empty and neither is empty or neither is empty), 
  then determine whether the left (right) son of the first tree is isomorphic to the right (left) son of the second tree*/
  /* 如果两棵树左儿子（一个空一个不空或者都不空）并且元素不一样，
  那么判断第一棵树的左（右）儿子是否跟第二棵树的右（左）儿子同构 */
    return ( Isomorphic( T1[R1].Left, T2[R2].Right) && Isomorphic( T1[R1].Right, T2[R2].Left ) );
}

思路：

判断cl、cr是否为横杠-时，四个if语句是处于同一水平同时判断的。
初始化root为Null可以使得当N为空时，能够返回Null(-1)。
判断是否“同构”时，需要多方考虑。也要经常调用递归。

04-树4 是否同一棵二叉搜索树 (25 分)

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

输出样例:

Yes
No
No
结尾无空行

AC code：

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

typedef struct TreeNode *Tree;
struct TreeNode {
  int v;
  Tree Left, Right;
  int flag;
};

Tree MakeTree( int N );
Tree Insert( Tree T, int V );
Tree NewNode( int V );
int check ( Tree T, int V );
int Judge( Tree T, int N );
void ResetT ( Tree T );
void FreeTree ( Tree T );

int main(){ 
  int N, L, i;
  Tree T;
  scanf("%d", &N);
  while (N) { //N = 0时结束循环
		scanf("%d", &L);
		T = MakeTree(N);
		for (i = 0; i < L; i++) {
			if (Judge(T, N)) printf("Yes\n");
			else printf("No\n");
			ResetT(T); //清除T中的标记flag，用以判断下一课搜索二叉树
		}
		FreeTree(T);
		scanf("%d", &N);
  }
 return 0;
}

//制造树，先建个结点，再对其插入即可
Tree MakeTree( int N ){ 
  Tree T;
  int i, V;
  scanf("%d", &V);
  T = NewNode(V);
  for (i=1; i<N; i++) {
    scanf("%d", &V);
    T = Insert(T, V);
  }
  return T;
}

//插入时利用二叉搜索树左小右大的特点
Tree Insert( Tree T, int V ){
  if ( !T ) //如果要该树是空的，要创建值为 V新结点
		T = NewNode(V);
  else { 
    if ( V > T->v ) //如果该树的值小于插入值 V，递归到该树的右子树插入
      T->Right = Insert( T->Right, V );
    else //反之，递归到该树的左子树插入
      T->Left = Insert( T->Left, V );
  }
  return T;
}

//创建一个值为 V新结点
Tree NewNode( int V ){ 
  Tree T = (Tree)malloc(sizeof(struct TreeNode));
  T->v = V;
  T->Left = T->Right = NULL;
  T->flag = 0; //标志flag初始化为0
  return T;
}

//利用二叉搜索树左小右大的特点检查结点值是否相等
//此时的 T是对照二叉树
int check ( Tree T, int V ){

	//标志flag存在时（即flag置1时），说明要检查的值已经满足检查，无需再检查，跳过它，去检查它的左或右子树
  if ( T->flag ) {
    if ( V < T->v ) return check(T->Left, V);
    else if ( V > T->v ) return check(T->Right, V);
    else return 0;
  }

	//否则标志flag不存在时（即flag置0时），对其进行检查
	//如果相等，就将flag置为1，说明它已经满足检查，然后返回1
	//如果不相等，不满足检查，直接返回0
  else {
    if ( V == T->v ) { //检查即判断是否两者的值是否相等
      T->flag = 1;
      return 1;
    }
    else return 0;
  }
}

//判断对照和目标二叉搜索树是否一致
//此时的 T是对照二叉树
int Judge( Tree T, int N ){
  int i, V, flag = 0;

 	/* flag: 0代表目前还一致，1代表已经不一致*/
 	//此flag专用于Judge函数
  scanf("%d", &V);
  if ( V != T->v ) flag = 1; //先单独判断第一个结点值，如果不相等就无需判断后续的了，提高效率
  else T->flag = 1;
  for (i = 1; i < N; i++) {
    scanf("%d", &V);
    if ( (!flag) && (!check(T, V)) ) flag = 1; //逐个值进行检查
  }
  if (flag) return 0;
  else return 1;
}

void ResetT ( Tree T ) { /* 清除T中各结点的flag标记 */
  if (T->Left) ResetT(T->Left);
  if (T->Right) ResetT(T->Right);
  T->flag = 0;
}

void FreeTree ( Tree T ) { /* 释放T的空间 */
  if (T->Left) FreeTree(T->Left);
  if (T->Right) FreeTree(T->Right);
  free(T);
}

思路：

两个flag要区分开，Check的flag是要用来标记是否已经检查过，不要重复检查
Judge的flag是用来标记两棵树是否已经一致
除了对照树要当作树来建立，目标树当作序列对待即可，这也是Check设置flag的原因

b站参考链接

05-树7 堆中的路径 (25 分)

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

输入格式:

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:

对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3
结尾无空行

输出样例:

AC code：

#include <stdio.h>

#define MAXN 1001
#define MINH -10001

int H[MAXN], size; //用数组的方式构建最小堆

void Create (){ //建一个最小堆，也称为堆的初始化
 size = 0; //size初始化为0。size是一个全局变量，主函数main结束前，其值不会被释放
 H[0] = MINH; //因为岗哨要占据索引为0的位置，所以最小堆的数据起始为索引为1的位置，且最小堆的数据最小取到-10000
 /*设置“岗哨”*/
}

void Insert ( int X ){
  /* 将X插入H。这里省略检查堆是否已满的代码 */
  //因为这道题用不到，用了会出错
  
  int i;
  //注意size是全局变量
  //找到要插入的位置，从索引最小（即[1]）的位置开始找（++size改变带动i改变），向下过滤
  
  //为什么要i /= 2
  //插入值和父结点[i/2]比较，如小于父节点，要改变父节点，如果还小于父节点的父节点，要继续向上过滤
  for (i = ++size; H[i/2] > X; i /= 2) //因为size初始化为0，所以i = ++size = 1
    H[i] = H[i/2]; //改变父结点的值
  H[i] = X; //插入
}

 //这段代码是自我调试用的
  // int i = ++size;
  // int a = size; 
  // while (H[i/2] > X){
  //   H[i] = H[i/2];
  //   i /= 2;
  // }
  // H[i] = X;

int main(){
  int n, m, x, i, j;
  scanf("%d %d", &n, &m);
  Create(); /* 堆初始化 */
  for (i = 0; i < n; i++) { /*以逐个插入方式建堆 */
    scanf("%d", &x);
    Insert(x);
} 
  for (i = 0; i < m; i++) {
    scanf("%d", &j);
    printf("%d", H[j]);
    while (j > 1) { /*沿根方向输出各结点*/ //向上折半逐个输出父结点即可
      j /= 2;
      printf(" %d", H[j]);
    }
    printf("\n");
  }
  return 0;
}

思路：

debug了一小时多，才发现size是全局变量，其值在主函数解释前未被释放，一直保存着，是用来改变Insert中的i，以向下过滤找插入点。
i /= 2用以向上过滤，逐个改变父结点的值。

b站参考链接

05-树8 File Transfer (25 分)

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification:

Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

I c1 c2

where I stands for inputting a connection between c1 and c2; or

C c1 c2

where C stands for checking if it is possible to transfer files between c1 and c2; or

where S stands for stopping this case.

Output Specification:

For each C case, print in one line the word “yes” or “no” if it is possible or impossible to transfer files between c1 and c2, respectively. At the end of each case, print in one line “The network is connected.” if there is a path between any pair of computers; or “There are k components.” where k is the number of connected components in this network.

Sample Input 1:

Sample Output 1:

no
no
yes
There are 2 components.

Sample Input 2:

Sample Output 2:

no
no
yes
yes
The network is connected.

AC code：

#include<stdio.h>

#define MaxSize 100001

typedef int ElementType; /*默认元素可以用非负整数表示*/
typedef int SetName; /*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[MaxSize];

void Initialization( SetType S, int n );
void Input_connection( SetType S );
void Check_connection( SetType S );
void Check_network( SetType S, int n );
void Union( SetType S, SetName Root1, SetName Root2 );
SetName Find( SetType S, ElementType X );

void Initialization( SetType S, int n ){
  int i;
  for(i = 0; i < n; i++)
    S[i] = -1;
}

void Input_connection( SetType S ){
  ElementType u, v;
  SetName Root1, Root2;
  scanf("%d %d\n", &u, &v);
  Root1 = Find(S, u-1);
  Root2 = Find(S, v-1);
  if ( Root1 != Root2 )
    Union( S, Root1, Root2 );
}

void Check_connection( SetType S ){ 
  ElementType u, v;
  SetName Root1, Root2;
  scanf("%d %d\n", &u, &v);
  Root1 = Find(S, u-1);
  Root2 = Find(S, v-1);
  if ( Root1 == Root2 )
    printf("yes\n");
  else 
    printf("no\n");
}

void Check_network( SetType S, int n ){
  int i, counter = 0;
  for (i=0; i<n; i++) {
    if ( S[i] < 0 ) counter++;
  }
  if ( counter == 1 )
    printf("The network is connected.\n");
  else
    printf("There are %d components.\n", counter);
}

void Union( SetType S, SetName Root1, SetName Root2 ){
  if ( S[Root2] < S[Root1] ){
    S[Root2] += S[Root1];
    S[Root1] = Root2;
  }
  else {
    S[Root1] += S[Root2];
    S[Root2] = Root1;
  }
}

SetName Find( SetType S, ElementType X ){
  if ( S[X] < 0 ) /* 找到集合的根 */
    return X;
  else
    return S[X] = Find( S, S[X] );
}

int main(){ 
  SetType S;
  int n;
  char in;
  scanf("%d\n", &n);
  Initialization( S, n );
  do {
    scanf("%c", &in);
    switch (in) {
      case 'I': Input_connection( S ); break;
      case 'C': Check_connection( S ); break;
      case 'S': Check_network( S, n ); break;
    }
  } while ( in != 'S');
return 0;
}

思路：先丢个链接，陈越老师的思路。

b站参考链接

Memory Dot

中国大学MOOC-陈越、何钦铭-数据结构-2021秋

Function

01-复杂度3 二分查找 (20 分)

02-线性结构1 两个有序链表序列的合并 (15 分)

04-树7 二叉搜索树的操作集 (30 分)

Programming

01-复杂度1 最大子列和问题 (20 分)

01-复杂度2 Maximum Subsequence Sum (25 分)

02-线性结构2 一元多项式的乘法与加法运算 (20 分)

02-线性结构3 Reversing Linked List (25 分)

02-线性结构4 Pop Sequence (25 分)

03-树1 树的同构 (25 分)

04-树4 是否同一棵二叉搜索树 (25 分)

05-树7 堆中的路径 (25 分)

05-树8 File Transfer (25 分)