數據結構：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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類