數據結構：DHUOJ 單鏈表ADT模板應用演算法設計：長整數加法運算（使用單鏈表存儲計算結果）

来源:https://www.cnblogs.com/zhuzhucheng/archive/2022/03/31/16071098.html
-Advertisement-
Play Games

1.標題 //標題一共六個級別 # 一級標題 ## 二級標題 ### 三級標題 #### 四級標題 ##### 五級標題 ###### 六級標題 #一級標題 ##二級標題 ###三級標題 ####四級標題 #####五級標題 六級標題 2.字體 **粗體** *斜體* ***粗體加斜體*** ~~刪 ...


單鏈表ADT模板應用演算法設計：長整數加法運算（使用單鏈表存儲計算結果）

時間限制: 1S類別: DS：線性表->線性表應用

題目描述：

 

 

 

 

 

 

 

 

輸入範例：

-534564675768465476586798709880985345646757684654765867987098809853456467576846547658679870988098534564675768465476586798709880985345646757684654765867987098809853456467576846547658679870988098534564675768465476586798709880985345646757684654765867987098809853456467576846547658679870988098534564675768465476586798709880985345646757684654765867987098809853456467576846547658679870988098
435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679435643754856985679


輸出範例 :

-5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098
4356,4375,4856,9856,7943,5643,7548,5698,5679,4356,4375,4856,9856,7943,5643,7548,5698,5679,4356,4375,4856,9856,7943,5643,7548,5698,5679,4356,4375,4856,9856,7943,5643,7548,5698,5679,4356,4375,4856,9856,7943,5643,7548,5698,5679,4356,4375,4856,9856,7943,5643,7548,5698,5679,4356,4375,4856,9856,7943,5643,7548,5698,5679

-5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,6467,5768,4654,7658,6798,7098,8098,5345,2111,1392,9797,7801,8855,1455,0549,9647,0788,1412,0279,2801,6941,9155,2454,7797,0769,0089,0298,3283,1941,7242,0154,9701,8919,0069,8975,3302,2423,2241,8241,7402,0823,8219,8956,1979,2442,2723,3241,5488,8524,0124,7106,1960,1119,2742,3723,0488,6610,7824,9011,0110,1100,1419,3742,0970,1610,5911,6711,2014,9250,1400,2419

 

這裡利用了幾個關鍵函數：鏈表的逆置 比較兩個鏈表的絕對值大小 鏈表的相加 輸出鏈表

 

我的題解：

//DHUOJ 單鏈表ADT模板應用演算法設計：長整數加法運算（使用單鏈表存儲計算結果）
#include<iostream>
#include<cstring>using namespace std;
template<class ElemType>
struct Node
{
    ElemType data;
    Node<ElemType>* next;
    //構造函數1 用於node構造頭結點
    Node(Node<ElemType>* ptr = NULL)
    {
        next = ptr;
    }
    //構造函數2 用於構造其他結點
    Node(const ElemType& item, Node<ElemType>* ptr = NULL)
    {
        next = ptr;
        data = item;
    }

public:
    ElemType getdata()
    {
        return data;
    }
    Node<ElemType>* getnext()
    {
        return next;
    }
    void set_next(Node<ElemType>* p)
    {
        this->next = p;
    }
    void set_date(ElemType num)
    {
        this->data = num;
    }
};
template<class ElemType>
class  LinkList {
private:
    Node<ElemType>* head;//頭指針
    Node<ElemType>* tail;//尾指針

public:
    //無參構造函數
    LinkList()
    {
        head = new Node<ElemType>;
        head->next = NULL;
        tail = head->next;//頭尾指針指向同一個記憶體
    }
    //有參構造
    LinkList(const ElemType& item)
    {
        head = new Node<ElemType>;
        tail = new Node<ElemType>;
        head->next = tail = new Node<ElemType>(item);//有參構造node
    }
    void display()
    {
        
       //避免出現以下情況 所以我們先判斷是不是就一個單0
      if(head->getnext()->getdata()==0&&head->getnext()->getnext()==NULL)
         {
               cout<<"0";
                return ;
       }
         if (head->getdata() == -1)
            cout << "-";//如果是0就不能輸出負號 
           //其實這樣寫也有問題 如果-0000 0005的就無法判斷 所以我們上面解決了單0的情況
        Node<ElemType>* q = head->next;
        bool zeroflag = 0;
        bool firstflag = 0;
        //0要先特判 避免出現0 0000 0000的情況 也不行 會出現0 0000 0005 的情況無法輸出
            while (q->next)
            {    
                if (q->getdata() == 0 && !zeroflag)
                {
                    q = q->next;
                    continue;
                }
                else if(q->getdata()!=0&&!zeroflag)
                {
                    zeroflag = 1;

                }
                if (!firstflag)
                {
                    cout << abs(q->data) << ",";
                    firstflag = 1;
                }
                else
                    printf("%04d,", abs(q->data));
                q = q->next;
            
            }
        if (q == head->next)//只有一位特判
            cout << abs(q->data);
        else
        {
            if (!firstflag)
            {
                cout << abs(q->data);

            }
            else
            {
                if (!zeroflag)
                {
                    cout << abs(q->data);

                }
                else
                {
                    printf("%04d", abs(q->data));
                }
                
            }
                
        }
            
        cout << endl;
    }
    int size()
    {
        if (head->next == NULL)
            return 0;
        int len = 0;
        Node<ElemType>* q;
        q = head->next;
        while (q)
        {
            len++;
            q = q->next;
        }
        return len;
    }
    void push_back(ElemType x)
    {
        Node<ElemType>* q = new Node<ElemType>;//新建結點
        q->data = x;
        q->next = NULL;
        if (size() == 0)
        {
            head->next = q;

        }
        else
        {
            tail->next = q;

        }
        tail = q;

    }
    Node<ElemType>* get_front(Node<ElemType>* p)
    {//獲取一個指針的上一個，頭指針和非法指針會報錯.
        Node<ElemType>* q;
        q = head->next;
        while (q->next != NULL)
        {
            if (q->next == p)
                return q;
            q = q->next;
        }
    }
    Node<ElemType>* get_next(Node<ElemType>* p)
    {
        return p->next;
    }
    Node<ElemType>* get_address(int i)//獲取指定下標的地址
    {
        Node<ElemType>* q;
        q = head->next;
        while (i--)
            q = q->next;
        return q;
    }
    ElemType at(int i)
    {
        Node<ElemType>* q = get_address(i);
        return q->data;
    }
    bool del_p(Node<ElemType>* p)//傳入一個指針 刪除
    {
        if (size() == 0)
            return false;
        if (tail->next == NULL)//如果只有一個元素
        {
            if (p == tail)//如果這個指針是那個唯一的指針
            {
                delete tail;
                tail = NULL;
                return true;
            }
            else
                return false;//如果不是

        }
        if (p == tail)//如果刪除的是尾指針 
        {
            Node<ElemType>* q = get_front(p);
            q->next = NULL;
            tail = q;
            delete p;
            return true;
        }
        //其他的
        Node<ElemType>* q = get_front(p);
        q->next = p->next;
        delete p;
        return true;

    }
    bool del(int i)//刪除指定位置的元素
    {
        return del_p(get_address(i));
    }
    Node<ElemType>* get_head()
    {
        return head;
    }
    Node<ElemType>* get_tail()
    {
        return tail;
    }
    void set_head(Node<ElemType>* p)
    {

        head = p;
    }
    void set_tail(Node<ElemType>* p)
    {
        tail = p;
    }
    void ListReverse()
    {
        Node<ElemType>* a, * b, * temp;
        a = head->getnext();
        ElemType datas = head->getdata();
        temp = NULL;
        b = NULL;
        bool flag = 0;//設置尾指針的標誌
        while (a)
        {
            b = a;
            a = a->getnext();
            b->set_next(temp);
            if (!flag)
            {
                tail = b;
                flag = 1;
            }
            temp = b;
        }
        Node<ElemType>* newhead = new Node<ElemType>;
        newhead->set_next(b);
        newhead->set_date(datas);
        head = newhead;

    }
};


//從長整數的低位開始拆分（4位為一組，即不超過9999的非負整數），依次存放在單鏈表的每個結點的數據域中；
//頭結點的數據域存放正負數標誌（正數或0：1，負數：-1）。
template<class ElemType>
void Input_Int_Division(LinkList<ElemType>& L, string& str, int& length)
{
    Node<ElemType>* head = L.get_head();
    bool zhengfu_flag = 0;//記錄正負的flag
    int l = str.length();
    if (str[0] == '-')//先特判正負數    
    {

        zhengfu_flag = 1;
        head->set_date(-1);

    }
    else
    {
        head->set_date(1);
    }
    int i = 0;
    if (zhengfu_flag)
        i = 1;
    int t0 = l % 4;
    if (t0 == 0)
        t0 = 4;
    int t = 0;//記錄位數
    int num = 0;//存四位數
    bool changeflag = 0;//判斷標誌 判斷是否有進行第一次
    for (; i < t0; ++i)
    {
        num = num * 10 + (str[i] - '0');
        changeflag = 1;
    }
    if (changeflag)
    {
        length++;//記錄長度
        L.push_back(num);
        num = 0;
    }

    for (; i < str.length(); ++i)
    {

        num = num * 10 + (str[i] - '0');
        t++;
        if (t == 4)
        {
            length++;//記錄長度
            L.push_back(num);
            t = 0;
            num = 0;
        }
    }
    //L.display();
}
//兩個長整數的 絕對值 大小比較
//（x>y 返回值為1；x<y 返回值為2；x=y 返回值為0；）
template<class ElemType>
int Two_LongNum_Compare(LinkList<ElemType>& A, LinkList<ElemType>& B, const int& len_A, const int& len_B)
{
    Node<ElemType>* head1 = A.get_head();
    Node<ElemType>* head2 = B.get_head();

    //正數的情況 先看長度 
    if (len_A > len_B)
    {
        return 1;
    }
    else if (len_A < len_B)
    {
        return 2;
    }
    else if (len_A == len_B)
    {
        Node<ElemType>* a, * b;
        a = head1->getnext();
        b = head2->getnext();
        while (a)
        {
            if (a->getdata() > b->getdata())
                return 1;
            else if (a->getdata() < b->getdata())
                return 2;
            else
                a = a->getnext(), b = b->getnext();
        }
        return 0;
    }


}
template<class ElemType>
void swaps(LinkList<ElemType>& a, LinkList<ElemType>& b)
{
    LinkList<ElemType>temp = a;
    a = b;
    b = temp;
}
template<class ElemType>
void Listadds(LinkList<ElemType>& a, LinkList<ElemType>& b, int& la, int& lb)
{
    Node<ElemType>* x, * y;

    int ans = 0;
    if (la < lb)
    {
        //swap一下兩個
        swaps(a, b);
        int temp = la;
        la = lb;
        lb = temp;
    }
    x = a.get_head()->getnext();
    y = b.get_head()->getnext();//兩個指針的創建必須放在 交換判斷之後
    int m = a.get_head()->getdata();//m n 存儲符號
    int n = b.get_head()->getdata();//存儲符號也必須放在交換判斷之後

    //第一步 判斷結果的最高位//!必須再加法前進行 ！！因為a會隨著加法而改變 引用傳遞
    bool flag = 0;//標記元素
    int comp = Two_LongNum_Compare(a, b, la, lb);


    while (y)//先把每一位結點的數值加起來
    {
        ans = x->getdata() * m + y->getdata() * n;
        x->set_date(ans);
        x = x->getnext();
        y = y->getnext();
    }
    //把長的位都化成同號的 不然接下來進位會出問題
    while (x)
    {
        x->set_date(x->getdata() * m);
        x = x->getnext();
    }
    //再做進位處理
    
    if (comp == 1)
    {
        flag = 1;
    }
    //第二步 開始逐位遍歷
    x = a.get_head()->getnext();
    int zheng_fu = 0;//判斷正負的符號
    if (flag)
        zheng_fu = a.get_head()->getdata();
    else
        zheng_fu = b.get_head()->getdata();
    if (zheng_fu > 0)//分正負兩種情況 先看是正的    
    {
        a.get_head()->set_date(1);//定最高位符號
        while (x->getnext())//最後一個結點先不遍歷 最後單獨討論
        {
            if (x->getdata() > 9999)
            {
                x->set_date(x->getdata() - 10000);
                x->getnext()->set_date(x->getnext()->getdata() + 1);
                //下一位就加一
            }
            else if (x->getdata() < 0)
            {
                x->set_date(x->getdata() + 10000);
                x->getnext()->set_date(x->getnext()->getdata() - 1);
            }
            x = x->getnext();
        }
        //討論最後一位 是否要進位
        if (x->getdata() > 9999)
        {
            x->set_date(x->getdata() - 10000);
            a.push_back(1);
        }
    }
    else //討論負數的情況
    {
        a.get_head()->set_date(-1);//定最高位符號
        while (x->getnext())//最後一個結點先不遍歷 最後單獨討論
        {
            if (x->getdata() < -9999)
            {
                x->set_date(x->getdata() + 10000);
                x->getnext()->set_date(x->getnext()->getdata() - 1);
                //下一位就加一
            }
            else if (x->getdata() > 0)
            {
                x->set_date(x->getdata() - 10000);
                x->getnext()->set_date(x->getnext()->getdata() + 1);
            }
            x = x->getnext();
        }
        //討論最後一位 是否要進位
        if (x->getdata() < -9999)
        {
            x->set_date(x->getdata() + 10000);
            a.push_back(1);
        }
    }
}

int main()
{
    LinkList<int>head1, head2;
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    int la = str1.length();
    int lb = str2.length();
    if (str1[0] == '-')
        la -= 1;
    if (str2[0] == '-')
        lb -= 1;
    int length1 = 0;
    int length2 = 0;
    Input_Int_Division(head1, str1, length1);
    Input_Int_Division(head2, str2, length2);
    head1.display();
    head2.display();
    cout << endl;
    head1.ListReverse();
    head2.ListReverse();
    Listadds(head1, head2, la, lb);
    head1.ListReverse();
    head1.display();
    //swaps(head1, head2);
    //head1.display();
    //head2.display();
    //cout << endl;
    //int comp = Two_LongNum_Compare(head1, head2, length1, length2);
    //cout << comp;
    //cout << length<<endl;
    //head.ListReverse();
    //head.display();

    return 0;

}

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • css中實現元素隱藏的幾種方法
    一、display:none; display翻譯成中文是顯示、展覽的意思；將display的屬性改為none可以實現元素的隱藏，元素和盒子模型也不生成，被隱藏的元素不占位置，看不見摸不著，它會導致瀏覽器的重排和重繪。 二、visibility:hidden; visibility翻譯成中文是能見、 ...
  • 讓你輕鬆看懂defer和async
    defer和async產生的原因 HTML 網頁中，瀏覽器通過<script>標簽載入 JavaScript 腳本。 <!-- 頁面內嵌的腳本 --> <script type="application/javascript"> // module code </script> <!-- 外部腳本 ...
  • 如何逃離框架孤井？
    框架看起來就像是宗教（或者說是政治）：每一個框架都假裝自己為開發者提供瞭解決方案，但每一個又都不一樣。它們每一個都聲稱可以為應用程式提供最好的前景，但關於哪一個真正名副其實的爭論又不絕於耳。每一個框架都要求你遵循特定的規則，它們之間可能有相似之處，但要從一個框架轉換到另一個框架總是很難。所以沒有什麼... ...
  • ES6中對象新增的方法
    屬性的簡潔表示法 ES6 允許在大括弧裡面直接寫入變數和函數，作為對象的屬性和方法。這樣的書寫更加簡潔。 const foo = 'bar'; const baz = { foo }; console.log(baz); // { foo: 'bar' } function f(name, age) ...
  • JS—關於排序（一）冒泡、選擇、歸併
    一、冒泡排序 原理：相鄰兩元素之間兩兩比較，比較出大值進行賦值互換，再依次與相鄰的元素比較，層層遞進。#互換元素位置，相互賦值。 時間複雜度：最好O(n)，最差O(n^2) 1、比較相鄰的兩個元素，如果前一個比後一個大，則交換位置。2、比較完第一輪的時候，最後一個元素是最大的元素。3、這時候最後一個 ...
  • python面向對象之魔術方法(特定時機自動觸發) 魔術屬性
    魔術方法(特定時機自動觸發) __init__ 構造方法 觸發時機：實例化對象,初始化的時候觸發 功能：為對象添加成員 參數：參數不固定,至少一個self參數 返回值：無 # (1) 基本語法 class MyClass(): def __init__(self): print("構造方法被觸發 . ...
  • 結構型：四. 代理模式
    代理模式是什麼 代理模式是一種結構型設計模式， 讓你能提供真實服務對象的替代品給客戶端使用。 代理接收客戶端的請求併進行一些處理 （訪問控制和緩存等）， 然後再將請求傳遞給服務對象。 為什麼用代理模式 在某些情況下客戶類不想或者不能訪問目標對象，這時候就可以使用代理類訪問。 代理模式怎麼實現 pac ...
  • import 導入模塊或包
    import 導入模塊或包 文件就是一個模塊,文件夾就是一個包文件夾裡面可以有很多文件,就相當於包中有好多的模塊. import 模塊或者包(包是文件夾,模塊是文件)模塊不會被重覆導入，引入一次終生受益 '''調用的時候: 模塊.變數 模塊.函數 模塊.類''' (1) 模塊.變數 print(my ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類