單鏈表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 =https://www.cnblogs.com/zhuzhucheng/p/ 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 =https://www.cnblogs.com/zhuzhucheng/p/ 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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452804.html
標籤：C++