单链表ADT模板应用算法设计：长整数加法运算（坑定跑不起来，仅作自我学习参考）（老师版代码分析与学习）

文章目录

Input_Int_Division分析与总结 Two_LongNum_Compare分析与总结 单链表的逆置分析与总结 Int_String分析与总结 最终的总函数分析与总结

Input_Int_Division

template<class ElemType> void Input_Int_Division2(LinkList<ElemType> &A,string &str,int &length) { LinkNode<ElemType> *head; head = A.GetHead(); //len is the length of the string without the signal //temp is used to store the integer which is converted from the string //s is the number of the nodes of the linklist int len = str.length(); int s,temp; //confirm the signal of the long integer if(str.substr(0,1) == "-") { head->data = -1; str = str.substr(1,len); len = len - 1; } else head->data = 1; //get the length of the linklist if(len % 4 == 0) s = len /4; else s = len / 4 + 1; length = s; //divide string into pieces and create the linklist if(len <= 4) { temp = atoi(str.c_str()); A.InsFirst(temp); } else { for(int i = 1;i <= s;i ++) { if(4 * i <= len) { temp = atoi(str.substr(len - 4*i,4).c_str()); A.InsFirst(temp); } else { temp = atoi((str.substr(0,len-4*(i - 1))).c_str()); A.InsFirst(temp); } } } }

分析与总结

这部分没有想到，我完全是从正向去考虑的，想着如何去逆置字符串，从而实现将字符串从低位开始向高位平均分为四个字符一节，仅仅只有最高位可以不满一节。不逆转字符串讲条件设置为逆向开始遍历也是完全也可以实现的！不错！

Two_LongNum_Compare

template<class ElemType> int Two_LongNum_Compare2(LinkList<ElemType> &A,LinkList<ElemType> &B ,const int &len_A,const int &len_B) { //construct two pointers to traverse the whole linklist LinkNode<ElemType> *p_A,*p_B; //compare the linklist if(len_A > len_B) return 1; else if(len_A < len_B) return 2; else { p_A = A.GetHead()->next; p_B = B.GetHead()->next; while(p_A) { if(p_A->data > p_B->data) return 1; else if(p_A->data < p_B->data) return 2; else { p_A = p_A->next; p_B = p_B->next; } } } return 0; }

分析与总结

总的来说，这个思路都是大差不差的，但是代码写的比我要简洁多了。我比他多了一个不必要的变量基本思路： 先比较两者的总长度等长的情况下，在逐个比较各个结点的值的大小

单链表的逆置

template<class ElemType> void LinkList<ElemType>::ListReverse() { LinkNode<ElemType> *p_pre = head; LinkNode<ElemType> *p_cur = head->next; LinkNode<ElemType> *p_next = NULL; if(head->next == NULL) return; while(p_cur) { p_next = p_cur->p_next; if(p_pre == p_head) { p_cur->p_next = NULL; } else { p_cur->next = p_pre; } p_next->next = p_cur; p_cur = p_next; } head->next = p_pre; }

分析与总结

基本思路：三个指针，分别表示一个指针的所有的前驱和后继关系，通过中间的指针遍历所链表，通过前驱和后继其逻辑关系进行修改我之前在写什么，真的是汗颜，我的方法真是有繁琐，又浪费时间！逆序单向链表的两种方法 三个指针，改变next的方向单纯的交换前后结点的值

Int_String

string Int_String(int result,int &num) { string str = ""; char *Result = new char[4]; //convert the integer to the string itoa(result,Result,10); if(result == 0) str = "0000"; else { if(result < 10 && result > 0) str = "000"; if(result < 100 && result > 9) str = "00"; if(result < 1000 && result > 99) str = "0"; str.append(Result); } if(num > 0) str.append(","); else num ++; return str; }

分析与总结

这里涉及到两个问题： 输出时不足四位数的补零操作输出时的格式控制，何时疏忽逗号 更加汗颜，对于这个函数完全理解错了，甚是惭愧！我将输出的格式控制完全放在了链表的遍历函数上。

最终的总函数

template<class ElemType> void Long_Int_Add2(LinkList<ElemType> &A,LinkList<ElemType> &B ,string &result,const int &len_A,const int &len_B) { LinkNode<ElemType> *head_A = A.GetHead(); int neg_A = head_A->data; LinkNode<ElemType> *head_B = B.GetHead(); int neg_B = head_B->data; int Num_Compare = Two_LongNum_Compare2(A,B,len_A,len_B); //A is equal to B if(neg_A != neg_B && Num_Compare = 0) { cout<<"0"; } //the same signals //different signals } template<class ElemType> void get_ADD(LinkList<ElemType> &A,LinkList<ElemType> &B ,string &result,const int &len_A,const int &len_B) { LinkNode<ElemType> *p_A,*p_B; //两个长整数链表的结点指针，初始值为头结点 int i; //最低位标记 int A_data,B_data; //两个长整数链表的结点的存储的长整数 ElemType neg_A,neg_B; int temp_result = 0,temp_result1 = 0,flag; //中间计算结果 int temp = 0; //进位或者错位 char *Result = new char[4]; //中间计算结果，字符串转换用 int flag_A,flag_B; //链表A和链表B结束的标志，0表示结束，1是未结束 int neg_flag = 0; //最终结果负数标记，0为正数，1为负数 int Num_Compare; //两个长整数的绝对值比较 int num = 0; //是否输出计算结果 if(neg_A != neg_B && Num_Compare == 0) { cout<<endl<<"0"; return; } else { //判定链表是否已经结束了 while(flag_A == 0 || flag_B == 0) { //读取数据 if(flag_A == 0) { A_data = p_A->data; //A 比B小，A作为减数,并且A和B的符号是相反的 if(Num_Compare == 2 && neg_A != neg_B) { A_data = A_data* (-1); } } else A_data = 0; // if(flag_B == 0) { B_data = p_A->data; //A 比B小，A作为减数,并且A和B的符号是相反的 if(Num_Compare == 2 && neg_B != neg_A) { B_data =B_data* (-1); } } else B_data = 0; // temp_result = A_data + B_data + temp; temp = 0; //计算之后将temptemp置为零，等待下一次计算 //判定是否已经到达末尾 if(p_A->next == NULL) flag_A = 1; if(p_B->next == NULL) flag_B = 1; //对每一个结点计算的数字进行处理,处理来获得下一个进位 if(temp_result >= 1000 && (flag_A == 0 || flag_B == 0)) { temp = 1; temp_result = temp_result - 10000; } if(temp_result < 0 && (flag_A == 0 || flag_B == 0)) { temp = -1; temp_result = temp_result + 10000; } //如果没有到达末尾，就继续便利 if(flag_A == 0) p_A = p_A->next; if(flag_B == 0) p_B = p_B->next; } } if(flag_A == 0 || flag_B == 0) { //将最终计算的结点保存到对应的字符串中 result.insert(0,Int_String(temp_result,num)); //num为是否输出计算结果 } else { //已经到达数据的末尾了 if(temp_result == 0 && result != "") { result.insert(0,","); } else { result.insert(0,","); if(temp_result >= 10000) { temp_result = temp_result - 10000; int num1 = 0; string tt = Int_String(temp_result,num1); tt += result; result = tt; result.insert(0,"1"); } else { itoa(temp_result,Result,10); result.insert(0,Result); } } } }

分析与总结

只看懂一部分，可以尝试着将正数和负数的运算综合到一块，只需要提前对减数进行预处理就行！