算法刷题笔记三之线性结构篇

1.两个有序链表序列的合并

Problem
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。详细描述

Analysys

1. 分三步：构造两个链表；合并链表；遍历打印。
2. 合并链表可以新建一条新链表，根据归并排序中得merge思想，每次选择小接到新链表得尾部，然后将另一条链表剩下部分(已经有序)直接接到新链表尾部。
3. 空表特殊情况处理。

Code

#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;
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    return 0;
}

// 初始化链表 
List Read(){

    List L = (List)malloc(sizeof(struct Node));
    L->Next = NULL;
    PtrToNode rear = L;
    ElementType data;

    while(true) {
        scanf("%d", &data);
        if(data != -1) {
            PtrToNode p = (PtrToNode)malloc(sizeof(struct Node));
            p->Data = data;
            p->Next = NULL;
            rear->Next = p;
            rear = p;       
        } else {
            break;
        }
    }
    
    return L->Next;
}

// 归并链表
List Merge( List L1, List L2 ){
    
    if(L1 == NULL && L2 == NULL) {
        return NULL;
    }
    
    List p1 = L1;
    List p2 = L2;
    
    List LM = (List)malloc(sizeof(struct Node));
    LM->Next = NULL;
    List rear = LM;
    while(p1 && p2) {
        if(p1->Data < p2->Data) {
            rear->Next = p1;
            rear = p1;
            p1 = p1->Next;
        } else {
            rear->Next = p2;
            rear = p2;
            p2 = p2->Next;
        }
    }
    
    rear->Next = p1 ? p1 : p2;  
    return LM->Next;
} 

void Print( List L ){
    List p = L;
    
    if(p == NULL) {
        printf("NULL");
        return ;
    }
    while(p) {
        printf("%d", p->Data);
        p = p->Next;
        if(p!=NULL) printf(" ");
    }
}

2.一元多项式的乘法与加法运算

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

Analysys

1. 链表保存多项式的系数和系数，设计出程序框架,根据各部分分别实现函数。
2. 加法：新建第三条链表，根据两个链表对应每一项指数大小关系，不等时添加大的一项，相等时判断系数和是否为0，不为0又该怎么移动。最后将链表剩余部分依次拷贝出来添加到第三条链表后面。
3. 乘法：两种思路，一种是将乘法转化加法即将P1当前项(ci,ei)乘P2多项式，再加到结果多项式中。我选用另一种方法——逐项插入，即将当前P1当前项与P2当前项相乘，找到插入位置插入多项式。
4. 乘法需要注意的细节：保证多项式指数递减顺序；指数相同与指数不同情况；指数相同系数和是否为0.

Code

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

// 定义数据结构
typedef struct PolyNode* Polynomial;
struct PolyNode {
    int ceof; // 系数 
    int expon; // 指数
    Polynomial next; 
} ;
// 函数声明部分;需要设计的函数 

void printPoly(Polynomial P) ;
Polynomial readPoly();
Polynomial mult(Polynomial P1, Polynomial P2);
Polynomial add(Polynomial P1, Polynomial P2);
// 函数实现部分 

void printPoly(Polynomial P){
    // 链表为空
    if(P == NULL) {
        printf("0 0\n");
        return;
    } 
    // 链表非空
    bool flag = false; 
    while(P){
        if(!flag) flag = true;
        else printf(" ");
        printf("%d %d", P->ceof, P->expon);
        P = P->next;
    } 
    printf("\n");
}

void attach(int c, int e, Polynomial* pRear){
    Polynomial P;
    
    P = (Polynomial)malloc(sizeof(PolyNode));
    P->ceof = c;
    P->expon = e;
    P->next = NULL;
    (*pRear)->next = P;
    (*pRear) = P;
}

Polynomial readPoly() {
    int n;
    scanf("%d", &n);
    
    Polynomial P,rear,t;
    P = (Polynomial)malloc(sizeof(PolyNode));
    P->next = NULL;
    rear = P;
    
    int c,e;
    while(n--) {
        scanf("%d %d", &c, &e);
        attach(c, e, &rear);
    }
    t = P; 
    P = P->next; 
    free(t);
    return P;
}

Polynomial add(Polynomial P1, Polynomial P2) {
    Polynomial PS,p1,p2,rear,t;
    
    p1 = P1;p2 = P2;
    PS = (Polynomial)malloc(sizeof(PolyNode));
    PS->next = NULL;
    rear = PS;
    
    while(p1 && p2) {
        if(p1->expon > p2->expon) {
            attach(p1->ceof, p1->expon, &rear);
            p1 = p1->next;
        } else if(p1->expon == p2->expon) {
            if(p1->ceof + p2->ceof != 0) {
                attach(p1->ceof + p2->ceof, p1->expon, &rear);
            }
            p1 = p1->next;
            p2 = p2->next;  
        } else {
            attach(p2->ceof, p2->expon, &rear);
            p2 = p2->next;
        }
    }
    
    while(p1) {
        attach(p1->ceof, p1->expon, &rear); 
        p1 = p1->next;
    }
    // for(; p1; p1 = p1->next) attach(p1->ceof, p1->expon, &rear);
    
    while(p2) {
        attach(p2->ceof, p2->expon, &rear); 
        p2 = p2->next;  
    }
    
    rear->next = NULL;
    t = PS;
    PS = PS->next;
    free(t);
        
    return PS;
}

Polynomial mult(Polynomial P1, Polynomial P2) {
    Polynomial p1,p2,PP,rear, t;
    int c,e;
    
    if(!P1 || !P2) return NULL;
    
    PP = (Polynomial)malloc(sizeof(PolyNode));
    PP->next = NULL;
    
    p1 = P1;
    p2 = P2;
    rear = PP;
    // p1乘p2
    while(p2) {
        attach(p1->ceof*p2->ceof,p1->expon+p2->expon,&rear);
        p2 = p2->next;
    } 
    
    p1 = p1->next; // 从第二项开始 
    // 逐项插入 
    while(p1) {
        // p2每次初始化为多项式2得头，rear为新链表的头，插入删除操作都在PP链表(有一个空的节点)中进行 
        p2 = P2;
        rear = PP;
        while(p2) {
            c = p1->ceof*p2->ceof;
            e = p1->expon+p2->expon;
            while(rear->next && rear->next->expon > e){ // 找到插入位置 
                rear = rear->next;
            }
            
            if(rear->next && rear->next->expon == e){ // 当前指数次数相同，合并 
                if(rear->next->ceof+c != 0){ // 和不为0  
                    rear->next->ceof += c;
                }else{ // 和为0 
                    t = rear->next;
                    rear->next = t->next;
                    free(t);
                }
            } else { // 当前指数不相同，后插 
                t = (Polynomial)malloc(sizeof(PolyNode));
                t->ceof = c;
                t->expon = e;
                
                t->next = rear->next;
                rear->next = t;
                rear = rear->next;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    
    p2 = PP;
    PP = PP->next;
    free(p2);
    return PP;
}

// 主函数入口
int main() {
    Polynomial P1,P2,PP,PS; 
    
    #ifndef ONLINE_JUDGE
    freopen("Polymial.txt", "r", stdin);
    #endif
    
    // 读入多项式1
    P1 = readPoly();
    // 读入多项式2
    P2 = readPoly();
    // 乘法运算并输出
    PP = mult(P1, P2);
    printPoly(PP);
    // 加法运算并输出 
    PS = add(P1, P2);
    printPoly(PS);
    
    return 0;
} 

3.Pop Sequence

Problem
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. 详细描述

Analysys

1. 假设当前元素出栈，则比它小的元素都要入栈，这些元素什么时候出栈我们不管。当栈顶元素等于序列当前元素时，出栈，不等证明该序列不是出栈序列.
2. 序列元素后移，重复此操作。

Code

#include <stdio.h>
#include <stack>
using namespace std;

#define MAXN 1001

int check(int seq[], int M, int N) {
    stack<int> stack1;
    stack1.push(0);
    int index = 1;
    int num = 1;
    
    while(index <= N){
        while(seq[index] > stack1.top() && stack1.size() <= M){
            stack1.push(num++);
        }

        if(seq[index] == stack1.top()){
            stack1.pop();
            index++;
        } else {
            return 0;
        }
    }
    return 1;
}

int main(){
    int M, N, K;
    int seq[MAXN];
    
    #ifndef ONLINE_JUDGE
    freopen("PopSequence.txt", "r", stdin);
    #endif
    
    scanf("%d %d %d", &M, &N, &K); 
    
    while(K--) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &seq[i]);
        }
        
        if(check(seq, M, N)) {
            printf("YES\n");    
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

声明：本站所有文章均为原创或翻译，遵循署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议，如需转载请确保您对该协议有足够了解，并附上作者名 (Tsukasa) 及原文地址