Function

6-1 单链表逆转 (20 分)

本题要求实现一个函数，将给定的单链表逆转。（暂停更新）

//汉语实现版
List Reverse( List L ){//利用临时结点t另外新建一个链表实现逆转
  List P = NULL, t; //初始化，临时结点t，空结点P
  while(L){ //当链表不空时
    t = L; //第一项赋给t；第二项赋给t；第三项赋给t...
    L = L->Next; //移动到第二项；移动到第三项；移动到第四项... 用t遍历L
    t->Next = P; //结点t的Next设为P = NULL；结点t的Next设为P = 第一项；结点t的Next设为P = 第二项...结点t的Next设为P = 次最终项
    P = t; //结点t赋给P即第一项赋给P；结点t赋给P即第二项赋给P；结点t赋给P即第三项赋给P...结点t赋给P即最终项赋给P
  }
  return P;//返回最终项为头部的逆转链表
}

//言简意赅版
List Reverse( List L ){//利用临时结点t另外新建一个链表实现逆转
  List P = NULL, t; //初始化，临时结点t，空结点P
  while(L){ //当链表不空时
    t = L; 
    L = L->Next; //用t遍历L
    t->Next = P; //实现倒着连接
    P = t; //结点t赋给结点P
  }
  return P;
}

思路如图所示：

Programming

7-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个随机整数；

#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循环，比较当前子列和与预设最大子列和。

7-2 一元多项式的乘法与加法运算 (20 分)

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

输入格式:

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

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 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调整输出格式。

7-？

#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;
}

7-3 树的同构 (25 分)

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

#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)。
判断是否“同构”时，需要多方考虑。也要经常调用递归。

7-51 两个有序链表序列的合并 (20 分)

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

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

typedef struct Node *List;
struct Node{
    int a; //系数
    List link;
};

void Attach(int a, List *pRear){
    List P;
    P = (List)malloc(sizeof(struct Node));
    P->a = a;
    P->link = NULL;
    (*pRear)->link = P; //连接新建项
    *pRear = P; //将新建项当作临时尾部
}

List Read(){
  List S, Rear, t;
  int a;
  S = (List)malloc(sizeof(struct Node));
  S->link = NULL;
  Rear = S;
  while (1){
    scanf("%d", &a);
    if (a == -1) break; //当a == -1时结束循环
    Attach(a, &Rear);
  }
  t = S; S = S->link; free(t);//释放头部空结点
  return S;
}

// while (a != -1){  //错，因为a = -1时已经Attach了
//   scanf("%d", &a);
//   Attach(a, &Rear);
// }

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

List Merge(List S1, List S2){
    List front, rear, t;
    rear = (List)malloc(sizeof(struct Node));
    front = rear;
    while (S1&&S2){
        switch (compare(S1->a, S2->a)){
        case 1:
            Attach(S2->a, &rear);
            S2 = S2->link;    
            break;
        case -1:
            Attach(S1->a, &rear);
            S1 = S1->link;    
            break;        
        case 0:
            Attach(S1->a, &rear);
            Attach(S2->a, &rear);
            S1 = S1->link;
            S2 = S2->link;    
            break;
        }
    }
    for(; S1; S1 = S1->link) Attach(S1->a, &rear);
    for(; S2; S2 = S2->link) Attach(S2->a, &rear);
    rear->link = NULL;
    t = front; front = front->link; free(t); //释放头部空结点
    return front;
}

void Print(List S){
  int flag = 0;
  if (!S){printf("NULL"); return;}
  while (S){
    if (!flag) //调整输出格式，使第一项输出头部无空格
      flag = 1;
    else
      printf(" ");//使第二项输出头部、第三项输出头部...有空格
    printf("%d",S->a);
    S = S->link;
  }
  printf("\n");
}

int main(){
    List S1, S2, S3;
    S1 = Read();
    S2 = Read();
    S3 = Merge(S1, S2);
    Print(S3);
    return 0;
}

思路：输入格式最后一个是-1且无效把我折磨了好久。Merge函数中要注意两链表等价时都要输出，比较完之后还要看两链表有没有剩余的数字。

Memory Dot

PTA-数据结构与算法基础题目集（中文）