数据结构:DHUOJ 单链表ADT模板应用算法设计:长整数加法运算(使用单链表存储计算结果)
单链表ADT模板应用算法设计:长整数加法运算(使用单链表存储计算结果)
成都一家集口碑和实力的网站建设服务商,拥有专业的企业建站团队和靠谱的建站技术,十余年企业及个人网站建设经验 ,为成都超过千家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设,高端网站设计,同时也为不同行业的客户提供成都网站建设、做网站的服务,包括成都电商型网站制作建设,装修行业网站制作建设,传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选创新互联公司。
时间限制:1S类别:DS:线性表->线性表应用
题目描述:
输入范例:
-
输出范例 :
-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#include using namespace std; template<class ElemType> struct Node { ElemType data; Node * next; //构造函数1 用于node构造头结点 Node(Node * ptr = NULL) { next= ptr; } //构造函数2 用于构造其他结点 Node(const ElemType& item, Node * ptr = NULL) { next= ptr; data= item; } public: ElemType getdata() { return data; } Node * getnext() { return next; } void set_next(Node * p) { this->next = p; } void set_date(ElemType num) { this->data = num; } }; template<class ElemType> class LinkList { private: Node * head;//头指针 Node * tail;//尾指针 public: //无参构造函数 LinkList() { head= new Node ; head->next = NULL; tail= head->next;//头尾指针指向同一个内存 } //有参构造 LinkList(const ElemType& item) { head= new Node ; tail= new Node ; head->next = tail = new Node (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 * 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 * q; q= head->next; while (q) { len++; q= q->next; } return len; } void push_back(ElemType x) { Node * q = new Node ;//新建结点 q->data = x; q->next = NULL; if (size() == 0) { head->next = q; } else { tail->next = q; } tail= q; } Node * get_front(Node * p) {//获取一个指针的上一个,头指针和非法指针会报错. Node * q; q= head->next; while (q->next != NULL) { if (q->next == p) return q; q= q->next; } } Node * get_next(Node * p) { return p->next; } Node * get_address(int i)//获取指定下标的地址 { Node * q; q= head->next; while (i--) q= q->next; return q; } ElemType at(int i) { Node * q = get_address(i); return q->data; } bool del_p(Node * 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 * q = get_front(p); q->next = NULL; tail= q; delete p; return true; } //其他的 Node * q = get_front(p); q->next = p->next; delete p; return true; } bool del(int i)//删除指定位置的元素 { return del_p(get_address(i)); } Node * get_head() { return head; } Node * get_tail() { return tail; } void set_head(Node * p) { head= p; } void set_tail(Node * p) { tail= p; } void ListReverse() { Node * 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 * newhead = new Node ; newhead->set_next(b); newhead->set_date(datas); head= newhead; } }; //从长整数的低位开始拆分(4位为一组,即不超过9999的非负整数),依次存放在单链表的每个结点的数据域中; //头结点的数据域存放正负数标志(正数或0:1,负数:-1)。 template<class ElemType> void Input_Int_Division(LinkList & L, string& str, int& length) { Node * 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 template<class ElemType> int Two_LongNum_Compare(LinkList & A, LinkList & B, const int& len_A, const int& len_B) { Node * head1 = A.get_head(); Node * 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 * 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 & a, LinkList & b) { LinkList temp = a; a= b; b= temp; } template<class ElemType> void Listadds(LinkList & a, LinkList & b, int& la, int& lb) { Node * 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() - ); x->getnext()->set_date(x->getnext()->getdata() + 1); //下一位就加一 } else if (x->getdata() < 0) { x->set_date(x->getdata() + ); x->getnext()->set_date(x->getnext()->getdata() - 1); } x= x->getnext(); } //讨论最后一位 是否要进位 if (x->getdata() > 9999) { x->set_date(x->getdata() - ); a.push_back(1); } } else //讨论负数的情况 { a.get_head()->set_date(-1);//定最高位符号 while (x->getnext())//最后一个结点先不遍历 最后单独讨论 { if (x->getdata() < -9999) { x->set_date(x->getdata() + ); x->getnext()->set_date(x->getnext()->getdata() - 1); //下一位就加一 } else if (x->getdata() > 0) { x->set_date(x->getdata() - ); x->getnext()->set_date(x->getnext()->getdata() + 1); } x= x->getnext(); } //讨论最后一位 是否要进位 if (x->getdata() < -9999) { x->set_date(x->getdata() + ); 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< //head.ListReverse(); //head.display(); return 0; }
分享名称:数据结构:DHUOJ 单链表ADT模板应用算法设计:长整数加法运算(使用单链表存储计算结果)
转载来源:http://pwwzsj.com/article/dsoihsc.html