DHU26 有序鏈表ADT模板簡單應(yīng)用算法設(shè)計：一元多項式的加/減法運算

問題描述 :
目的：使用C++模板設(shè)計單鏈表的抽象數(shù)據(jù)類型（ADT）国葬。并在此基礎(chǔ)上贤徒，稍加改動，針對一元多項式建立相應(yīng)的稀疏多項式ADT汇四，使用單鏈表ADT的基本操作接奈，設(shè)計并實現(xiàn)稀疏一元多項式的加法計算的算法設(shè)計。

內(nèi)容：（1）請參照單鏈表的ADT模板通孽，設(shè)計稀疏一元多項式的抽象數(shù)據(jù)類型序宦。（由于該環(huán)境目前僅支持單文件的編譯，故將所有內(nèi)容都集中在一個源文件內(nèi)背苦。在實際的設(shè)計中互捌，推薦將抽象類及對應(yīng)的派生類分別放在單獨的頭文件中。參考網(wǎng)盤中的單鏈表ADT原型文件行剂，自行設(shè)計稀疏一元多項式的ADT秕噪。）

（2）ADT的簡單應(yīng)用：使用該ADT設(shè)計并實現(xiàn)稀疏一元多項式的加法計算的算法設(shè)計。

應(yīng)用1：假設(shè)2個稀疏一元多項式分別由帶頭結(jié)點的有序單鏈表A和B存儲（指數(shù)項遞增有序）『裨祝現(xiàn)要求設(shè)計一個算法腌巾，實現(xiàn)稀疏一元多項式的加減法計算。要求使用A和B的原存儲空間铲觉，且計算后B不再單獨存在澈蝙。輸入中的單鏈表的長度不得在計算算法中利用，僅作為建表使用撵幽。

注意：加/減法計算后灯荧，如某一項的結(jié)果系數(shù)為0，則該項要從多項式鏈表中刪除盐杂。

參考函數(shù)原型：

template<class ElemType1逗载，class ElemType2>

void Add_Poly( poly_LinkList<ElemType> &A, poly_LinkList<ElemType> &B, int add_sub );



有序鏈表模板類原型（用于一元多項式計算）參考如下：

/* 單鏈表的結(jié)點定義 */（用于一元多項式計算）

template<class ElemType1, class ElemType2>
struct LinkNode
{
    ElemType1 factor; //系數(shù)
    ElemType2 indice;  //指數(shù)
    LinkNode<ElemType1, ElemType2> *next;
    LinkNode(LinkNode<ElemType1, ElemType2> *ptr = NULL){next = ptr;} //構(gòu)造函數(shù)1，用于構(gòu)造頭結(jié)點
    LinkNode(const ElemType1 &item1, const ElemType1 &item2, LinkNode<ElemType1, ElemType2> *ptr = NULL) //構(gòu)造函數(shù)2况褪，用于構(gòu)造其他結(jié)點  
    //函數(shù)參數(shù)表中的形參允許有默認值，但是帶默認值的參數(shù)需要放后面
    {
        next = ptr;
        factor = item1;
        indice = item2;
    }
    ElemType1 getFactor(){ return factor;}  //取得結(jié)點中的系數(shù)
    ElemType2 getIndice(){ return indice;}  //取得結(jié)點中的指數(shù)
    void SetLink( LinkNode<ElemType1, ElemType2> *link ){ next = link; }  //修改結(jié)點的next域
    void SetFactor( ElemType1 value ){ factor = value; }   //修改結(jié)點的系數(shù)
    void SetIndice( ElemType2 value ){ indice = value; }   //修改結(jié)點的指數(shù)
};

//帶頭結(jié)點的單鏈表（用于一元多項式計算）
template<class ElemType1, class ElemType2>
class poly_LinkList{
   private:
      LinkNode<ElemType1, ElemType2> *head;   // 頭結(jié)點
      LinkNode<ElemType1, ElemType2> *tail;   // 尾結(jié)點
   public:
      //無參數(shù)的構(gòu)造函數(shù)
      poly_LinkList(){head = new LinkNode<ElemType1, ElemType2>;}
      //帶參數(shù)的構(gòu)造函數(shù)
      poly_LinkList(const ElemType1 &item1, const ElemType2 &item2 ){head = new LinkNode<ElemType1, ElemType2>(item1, item2);}
      //拷貝構(gòu)造函數(shù)
      poly_LinkList(poly_LinkList<ElemType1, ElemType2> &List);
      //析構(gòu)函數(shù)
      ~poly_LinkList(){ListDestroy();}
      //銷毀鏈表
      void ListDestroy();
      //清空鏈表
      void ListClear();
      //返回鏈表的長度
      int ListLength() const;
      //判斷鏈表是否為空表
      bool ListEmpty() const;
      //在首節(jié)點之前插入一個結(jié)點
      bool InsFirst( ElemType1 fact, ElemType2 indi );
      //獲取鏈表頭結(jié)點
      LinkNode<ElemType1,ElemType2>* GetHead() { return head;}
      //設(shè)置鏈表頭結(jié)點
      void SetHead(LinkNode<ElemType1,ElemType2> *p){ head = p;}     
      //獲取鏈表尾結(jié)點
      LinkNode<ElemType1,ElemType2>* GetTail() { return tail;}
      //返回鏈表的第i個元素的系數(shù)值
      ElemType1 GetElem_factor(int pos);
      //返回鏈表的第i個元素的指數(shù)值
      ElemType2 GetElem_indice(int pos);
      //在鏈表的第pos個位置之前插入e元素
      bool ListInsert_prior(int pos, ElemType1 fact, ElemType2 indi);
      //在鏈表的第pos個位置之后插入e元素
      bool ListInsert_next(int pos, ElemType1 fact, ElemType2 indi);
      //表頭插入法動態(tài)生成鏈表
      void CreateList_Head(int n, ElemType1 *fact, ElemType2 *indi);     
      //表尾插入法動態(tài)生成鏈表
      void CreateList_Tail(int n, ElemType1 *fact, ElemType2 *indi);    
      //刪除鏈表的第pos個位置的元素
      ElemType2 ListDelete(int pos);
      //按序號查找更耻，從鏈表的第一個結(jié)點開始测垛，判斷當前結(jié)點是否是第i個，
      //若是秧均，則返回該結(jié)點的數(shù)據(jù)域的值食侮；否則繼續(xù)后一個号涯，直至表結(jié)束。沒有第i個結(jié)點時返回空锯七。
      bool FindElem( int k, ElemType1 &fact, ElemType2 &indi);
      //bool compare(ElemType a, ElemType *b);
      //按值查找链快，即定位。從鏈表的第一個結(jié)點開始眉尸，判斷當前結(jié)點值是否等于e域蜗。
      //若是，則返回該結(jié)點的序號噪猾；否則繼續(xù)后一個霉祸，直至表結(jié)束。找不到時返回0袱蜡。
      int SearchElem( const ElemType2 &e) const;
      //返回鏈表給定數(shù)據(jù)元素的后繼數(shù)據(jù)元素的值
      bool NextElem(LinkNode<ElemType1, ElemType2> *p, ElemType1 &fact, ElemType2 &indi);
      //遍歷鏈表
      bool ListTraverse() const;
};

輸入說明 :

第一行：加/減法選擇（0：加法 1：減法）

第二行：一元多項式A的項數(shù)

第三行：一元多項式A的各項的系數(shù)（系數(shù)之間以空格分隔）

第四行：一元多項式A的各項的指數(shù)（指數(shù)之間以空格分隔）

第五行：一元多項式B的項數(shù)

第六行：一元多項式B的各項的系數(shù)（系數(shù)之間以空格分隔）

第七行：一元多項式B的各項的指數(shù)（指數(shù)之間以空格分隔）

輸出說明 :

第一行：多項式A的第一項的系數(shù)丝蹭、指數(shù)（以空格分隔）

第一行：多項式A的第二項的系數(shù)、指數(shù)（以空格分隔）

...

第n行：多項式A的第n項的系數(shù)坪蚁、指數(shù)（以空格分隔）（假設(shè)多項式A的項數(shù)為n）

第一行：多項式B的第一項的系數(shù)奔穿、指數(shù)（以空格分隔）

第一行：多項式B的第二項的系數(shù)、指數(shù)（以空格分隔）

...

第m行：多項式B的第m項的系數(shù)敏晤、指數(shù)（以空格分隔）（假設(shè)多項式B的項數(shù)為m）

第一行：加/減法計算后贱田，結(jié)果多項式A的第一項的系數(shù)、指數(shù)（以空格分隔）

第一行：加/減法計算后茵典，結(jié)果多項式A的第二項的系數(shù)湘换、指數(shù)（以空格分隔）

...

第p行：加/減法計算后，結(jié)果多項式A的第n項的系數(shù)统阿、指數(shù)（以空格分隔）（假設(shè)結(jié)果多項式的項數(shù)為p）

（輸入與輸出之間以空行分隔彩倚，多項式之間以空行分割）

輸入范例 :

1
6
7 3 -22 9 5 -8
0 1 7 8 17 100
3
8 22 -9
1 7 8
輸出范例 :

7 0
3 1
-22 7
9 8
5 17
-8 100

8 1
22 7
-9 8

7 0
-5 1
-44 7
18 8
5 17
-8 100

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

/* 單鏈表的結(jié)點定義 */

template<class ElemType1, class ElemType2>
struct LinkNode
{
    ElemType1 factor; //系數(shù)
    ElemType2 indice;  //指數(shù)
    LinkNode<ElemType1, ElemType2>* next;
    LinkNode(LinkNode<ElemType1, ElemType2>* ptr = NULL) { next = ptr; } //構(gòu)造函數(shù)1，用于構(gòu)造頭結(jié)點
    LinkNode( ElemType1& item1,  ElemType1& item2, LinkNode<ElemType1, ElemType2>* ptr = NULL) //構(gòu)造函數(shù)2扶平，用于構(gòu)造其他結(jié)點  
    //函數(shù)參數(shù)表中的形參允許有默認值帆离，但是帶默認值的參數(shù)需要放后面
    {
        next = ptr;
        factor = item1;
        indice = item2;
    }
    ElemType1 getFactor() { return factor; }  //取得結(jié)點中的系數(shù)
    ElemType2 getIndice() { return indice; }  //取得結(jié)點中的指數(shù)
    void SetLink(LinkNode<ElemType1, ElemType2>* link) { next = link; }  //修改結(jié)點的next域
    void SetFactor(ElemType1 value) { factor = value; }   //修改結(jié)點的系數(shù)
    void SetIndice(ElemType2 value) { indice = value; }   //修改結(jié)點的指數(shù)
};

//帶頭結(jié)點的單鏈表（用于一元多項式計算）
template<class ElemType1, class ElemType2>
class poly_LinkList {
private:
    LinkNode<ElemType1, ElemType2>* head = NULL;   // 頭結(jié)點
    LinkNode<ElemType1, ElemType2>* tail = NULL;   // 尾結(jié)點
public:
    //無參數(shù)的構(gòu)造函數(shù)
    poly_LinkList() { head = new LinkNode<ElemType1, ElemType2>; }
    //帶參數(shù)的構(gòu)造函數(shù)
    poly_LinkList( ElemType1& item1,  ElemType2& item2) { head = new LinkNode<ElemType1, ElemType2>(item1, item2); }
    //拷貝構(gòu)造函數(shù)
    poly_LinkList(poly_LinkList<ElemType1, ElemType2>& List);
    //析構(gòu)函數(shù)
    ~poly_LinkList() { ListDestroy(); }
    //銷毀鏈表
    void ListDestroy()
    {
        LinkNode<ElemType1, ElemType2>* p = head;
        while (p != NULL)
        {
            head = p;
            p = p->next;
            delete head;
        }
    }
    //清空鏈表
    void ListClear();
    //返回鏈表的長度
    int ListLength() ;
    //判斷鏈表是否為空表
    bool ListEmpty() ;
    //在首節(jié)點之前插入一個結(jié)點
    bool InsFirst(ElemType1 fact, ElemType2 indi);
    //獲取鏈表頭結(jié)點
    LinkNode<ElemType1, ElemType2>* GetHead() { return head; }
    //設(shè)置鏈表頭結(jié)點
    void SetHead(LinkNode<ElemType1, ElemType2>* p) { head = p; }
    //獲取鏈表尾結(jié)點
    LinkNode<ElemType1, ElemType2>* GetTail() { return tail; }
    //返回鏈表的第i個元素的系數(shù)值
    ElemType1 GetElem_factor(int pos);
    //返回鏈表的第i個元素的指數(shù)值
    ElemType2 GetElem_indice(int pos);
    //在鏈表的第pos個位置之前插入e元素
    bool ListInsert_prior(int pos, ElemType1 fact, ElemType2 indi);
    //在鏈表的第pos個位置之后插入e元素
    bool ListInsert_next(int pos, ElemType1 fact, ElemType2 indi);
    //表頭插入法動態(tài)生成鏈表
    void CreateList_Head(int n, ElemType1* fact, ElemType2* indi);
    //表尾插入法動態(tài)生成鏈表
    void CreateList_Tail(int n, ElemType1* fact, ElemType2* indi)
    {
        LinkNode<ElemType1, ElemType2>* p = head;
        for (int i = 0;i < n;i++)
        {
            tail = new LinkNode<ElemType1, ElemType2>;
            tail->factor = fact[i];
            tail->indice = indi[i];
            p->next = tail;
            p = p->next;
        }
    }
    //刪除鏈表的第pos個位置的元素
    ElemType2 ListDelete(int pos);
    //按序號查找，從鏈表的第一個結(jié)點開始结澄，判斷當前結(jié)點是否是第i個哥谷，
    //若是，則返回該結(jié)點的數(shù)據(jù)域的值麻献；否則繼續(xù)后一個们妥，直至表結(jié)束。沒有第i個結(jié)點時返回空勉吻。
    bool FindElem(int k, ElemType1& fact, ElemType2& indi);
    //bool compare(ElemType a, ElemType *b);
    //按值查找监婶，即定位。從鏈表的第一個結(jié)點開始，判斷當前結(jié)點值是否等于e惑惶。
    //若是煮盼，則返回該結(jié)點的序號；否則繼續(xù)后一個带污，直至表結(jié)束僵控。找不到時返回0。
    int SearchElem( ElemType2& e) ;
    //返回鏈表給定數(shù)據(jù)元素的后繼數(shù)據(jù)元素的值
    bool NextElem(LinkNode<ElemType1, ElemType2>* p, ElemType1& fact, ElemType2& indi);
    //遍歷鏈表
    bool ListTraverse()
    {
        LinkNode<ElemType1, ElemType2>* p = head->next;
        if (p == NULL)return false;
        while (p)
        {
            cout << p->factor << " " << p->indice << endl;
            p = p->next;
        }
        return true;
    }
};

template<class ElemType1,class ElemType2>
void Add_Poly(poly_LinkList<ElemType1,ElemType2>& A, poly_LinkList<ElemType1, ElemType2> & B, int add_sub)
{
    if (add_sub == 0)add_sub = 1;
    else add_sub = -1;
    LinkNode<ElemType1, ElemType2>* pre1 = A.GetHead(), * pre2 = B.GetHead();
    LinkNode<ElemType1, ElemType2>* p = A.GetHead()->next, * q = B.GetHead()->next;
    while (q != NULL)
    {
        if (q->getIndice() == p->getIndice())
        {
            p->SetFactor(p->getFactor() + add_sub * q->getFactor());
            delete pre2;
            pre2 = q;
            q = q->next;
        }
        else if (q->getIndice() < p->getIndice()) 
        {
            delete pre2;
            pre2 = q;
            q = q->next;
            pre1->next = pre2;
            pre2->SetFactor(pre2->getFactor() * add_sub);
            pre2->next = p;
            pre1 = pre2;
        }
        else 
        {
            pre1 = p;
            p = p->next;
        }
    }
    for (pre1 = A.GetHead(), p = pre1->next;p != NULL;)
    {
        if (p->getFactor() == 0)
        {
            pre1->next = p->next;
            delete p;
            p = pre1->next;
            continue;
        }
        pre1 = p, p = p->next;
    }
    B.SetHead(NULL);
}

template<class ElemType1, class ElemType2>
void input(int& n, ElemType1* fact, ElemType2* indi)
{
    cin >> n;
    for (int i = 0;i < n;i++)
        cin >> fact[i];
    for (int i = 0;i < n;i++)
        cin >> indi[i];
}

int main()
{
    typedef int ElemType1;
    typedef int ElemType2;
    int add_sub;
    int n = 0;
    ElemType1 fact[1000];
    ElemType2 indi[1000];
    cin >> add_sub;
    poly_LinkList<ElemType1, ElemType2>A, B;
    input(n, fact, indi);
    A.CreateList_Tail(n, fact, indi);
    input(n, fact, indi);
    B.CreateList_Tail(n, fact, indi);

    A.ListTraverse();
    cout << endl;
    B.ListTraverse();
    cout << endl;
    Add_Poly(A, B, add_sub);
    A.ListTraverse();
    return 0;
}