概念

上次學習了數(shù)據(jù)結(jié)構(gòu)的基本概念， 并用了一個簡單的例子來進行了說明裁替。這一次主要學習的是線性結(jié)構(gòu)的概念及其使用项玛。對于線性概念，在學習之前的概念就是鏈表弱判，可能鏈表還有堆棧就代表線性結(jié)構(gòu)襟沮，在學習了之后才明白線性結(jié)構(gòu)是一種解決問題是抽象數(shù)據(jù)類型，可以不準確地理解為一種模板（類似于物理里斜面模板這種模板），是一種解決問題的方式开伏。而其解決的問題主要針對于問題中的數(shù)據(jù)在經(jīng)過劃分之后是可以在一維情況下討論的（并不是代表問題本身的數(shù)據(jù)只是一維的）膀跌。
其實現(xiàn)的具體方法主要有順序結(jié)構(gòu)和鏈式結(jié)構(gòu)。順序結(jié)構(gòu)很容易理解固灵，也就是在物理上和邏輯上都是連續(xù)排列的捅伤，例如在過去解決問題時使用的數(shù)組就是順序結(jié)構(gòu)，所以雖然一開始感覺這些概念很陌生巫玻，其實后續(xù)的學習只是進行了系統(tǒng)的講解丛忆，在之前的解題時已經(jīng)不自知的使用了。而鏈式結(jié)構(gòu)就只是在邏輯上連續(xù)仍秤，在物理上是分開的熄诡。可以這樣理解诗力，數(shù)組這種順序結(jié)構(gòu)就好比買了一條商業(yè)街粮彤，然后你的分店（也就是數(shù)據(jù)）是按照這個商業(yè)街的方向排列的，一號就在第一個姜骡，二號就在一號的旁邊导坟，以此類推。而鏈式結(jié)構(gòu)則是先開一家總店圈澈，然后再在全國各地開分店惫周，不過每一家店都告訴你下一號店的地址在哪，方便你去訪問康栈〉莸荩考慮到邏輯的簡便性和代碼的復雜度，肯定是一次性把店面開好啥么，也就是順序結(jié)構(gòu)更方便登舞，但是鏈式的好處就是可以根據(jù)需要來進行數(shù)據(jù)的添加。具體實現(xiàn)方式的選擇還是看具體題目悬荣，如果題目中明確給出了數(shù)據(jù)的個數(shù)菠秒，并且使用數(shù)組不會出現(xiàn)內(nèi)存溢出的情況，就使用數(shù)組氯迂，否則使用鏈表践叠。
說了實現(xiàn)方式，具體的線性結(jié)構(gòu)可以根據(jù)其數(shù)據(jù)進出方式分為隊列和堆棧嚼蚀，如果要存儲的數(shù)據(jù)類型是自定義的話則可以使用線性表來進行存儲禁灼。數(shù)據(jù)是FIFO的話就需要使用隊列，F(xiàn)ILO的話則是使用堆棧轿曙。具體實現(xiàn)方式在此不細說弄捕。

例題

題目鏈接：https://pintia.cn/problem-sets/1077214780527620096/problems/1103507412634030081

題目描述

一元多項式的乘法與加法運算 （20 point(s))
設計函數(shù)分別求兩個一元多項式的乘積與和僻孝。

輸入格式:

輸入分2行，每行分別先給出多項式非零項的個數(shù)守谓，再以指數(shù)遞降方式輸入一個多項式非零項系數(shù)和指數(shù)（絕對值均為不超過1000的整數(shù)）穿铆。數(shù)字間以空格分隔。

輸出格式:

輸出分2行分飞，分別以指數(shù)遞降方式輸出乘積多項式以及和多項式非零項的系數(shù)和指數(shù)悴务。數(shù)字間以空格分隔睹限，但結(jié)尾不能有多余空格譬猫。零多項式應輸出0 0。

輸入樣例:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
輸出樣例:

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

本題是跟著MOOC上的教程來一步一步推進的羡疗，但是需要真正獨立寫完才能算掌握染服。

分析

首先看數(shù)據(jù)的類型，是一個多項式叨恨，題目中要求用其系數(shù)和指數(shù)來進行表示柳刮，所以我們可以使用鏈表來進行存儲。首先對每個結(jié)點進行定義痒钝，每個結(jié)點包含了系數(shù)c和指數(shù)e秉颗，以及指向下一個結(jié)點的指針next。

typedef struct PolyNode *PolyNum;
struct PolyNode{
    int c;
    int e;
    PolyNum next;//這里的next是一個PolyNode類型的指針送矩，這里沒有初始化蚕甥，則需要注意使用時的初始化
};

主函數(shù)的框架很簡單

int mian()
{
    PolyNum P1, P2, PS, PM;
    P1 = readp();
    P2 = readp();
    PS = Add(P1, P2);
    PM = Mul(P1, P2);
    printp(PM);
    printp(PS);
    return 0;
}

然后是各個函數(shù)模塊之間的設計，其中讀入栋荸、相加以及相乘在總體上思路相同菇怀，都是新建一個鏈表，然后依次向里添加結(jié)點晌块，不過后兩者需要一定的判斷條件爱沟，而輸出模塊就是簡單的對鏈表的遍歷。這里需要注意的就是每一次遍歷后一定要讓尾指針指向當前結(jié)點的下一個結(jié)點（相當于循環(huán)中的i++）匆背。加法的設計比較簡單呼伸，首先對公共部分進行判斷，然后再將剩下的添加即可钝尸。這里說一下乘法的思路：首先先讓第一個多項式的第一項蜂大，乘上第二個多項式的每一項，得到一個鏈表蝶怔，然后再進行一個二重循環(huán)奶浦，將相乘的每一項向鏈表中進行添加，這里就需要一個尾指針來對鏈表進行遍歷來實現(xiàn)指數(shù)遞減的操作踢星。

完整代碼

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

typedef struct PolyNode *PolyNum;
struct PolyNode{
    int c;
    int e;
    PolyNum next;
};

void attach(int c, int e, PolyNum *tail){
    PolyNum P_new;
    P_new = (PolyNum)malloc(sizeof(struct PolyNode));
    P_new->c = c;
    P_new->e = e;
    P_new->next = NULL;
    (*tail)->next = P_new;
    *tail = P_new;
}

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

void PrintP(PolyNum P_out){
    int flag = 0;
    if(P_out == NULL){//多項式為0
        printf("0 0\n");
        return;
    }
    else{
        while(P_out){
            if(P_out->c != 0){
                if(flag == 0){
                    flag = 1;
                }
                else{
                    printf(" ");
                }
                printf("%d %d", P_out->c, P_out->e);
            }
            P_out = P_out->next;
        }
    }
    printf("\n");
    return;
}

PolyNum Add(PolyNum P1, PolyNum P2){
    PolyNum PS, tail, t;
    PS = (PolyNum)malloc(sizeof(struct PolyNode));
    PS->next = NULL;
    tail = PS;
    while(P1&&P2){
        if(P1->e == P2->e){
            if(P1->c + P2->c != 0){
                attach(P1->c + P2->c, P1->e, &tail);
            }
            P1 = P1->next;
            P2 = P2->next;
        }
        else if(P1->e > P2->e){
            attach(P1->c, P1->e, &tail);
            P1 = P1->next;
        }
        else{
            attach(P2->c, P2->e, &tail);
            P2 = P2->next;
        }
    }
    while(P1){
        attach(P1->c, P1->e, &tail);
        P1 = P1->next;
    }
    while(P2){
        attach(P2->c, P2->e, &tail);
        P2 = P2->next;
    }
    t = PS;
    PS = PS->next;
    free(t);
    return PS;
}

PolyNum Mul(PolyNum P1, PolyNum P2){
    PolyNum PM, t, tail, t1, t2, de;
    int c, e;
    t1 = P1;
    t2 = P2;
    PM = (PolyNum)malloc(sizeof(struct PolyNode));
    PM->next = NULL;
    tail = PM;
    if(!t1 || !t2){
        return NULL;
    }
    while(t2){
        c = t1->c * t2->c;
        e = t1->e + t2->e;
        attach(c, e, &tail);
        t2 = t2->next;
    }
    t1 = t1->next;
    while(t1){
        t2 = P2;
        while(t2){
            tail = PM;
            c = t1->c * t2->c;
            e = t1->e + t2->e;
            while(tail->next && tail->next->e > e){
                tail = tail->next;
            }
            if(tail->next && tail->next->e == e){
                if((tail->next->c + c) != 0){
                    tail->next->c += c;  
                }
                else{
                    de = tail->next;
                    tail->next = de->next;
                    free(de);
                }
            }
            else{
                t = tail->next;
                attach(c, e, &tail);
                tail->next = t;
            }
            t2 = t2->next;
        }
        t1 = t1->next;
    }
    t = PM;
    PM = PM->next;
    free(t);
    return PM;
}

int main()
{
    PolyNum P1, P2, PS, PM;
    P1 = readp();
    P2 = readp();
    PS = Add(P1, P2);
    PM = Mul(P1, P2);
    PrintP(PM);
    PrintP(PS);
    return 0;
}

這里的申請結(jié)點空間也可以使用P = new PolyNode語句澳叉，比malloc簡潔很多。

運行結(jié)果

之后有比較好的相關題目也會把鏈接粘貼到這。