莫知其始
// 链表式的多项式相加#include <stdio.h>#include <stdlib.h>#include <math.h>// 多项式中的一项typedef struct Node{ /////////数据部分 float _ratio; // 系数 unsigned _index; // 指数 /////////链表结构部分 struct Node * _next;} Node;// 插入到多项式中, 并保持按指数降序排列.Node * SortInsert ( Node * poly, Node *new_node ){ if ( new_node != NULL ) { if ( poly != NULL ) { // 因为第一项没有prev,所以需要特殊处理 // 指数大于第一项,放在最前面 if ( new_node->_index > poly->_index ) { new_node->_next = poly; return new_node; } else if ( new_node->_index == poly->_index ) // 指数与第一项相同 { Node * cur = poly; cur->_ratio += new_node->_ratio; free ( new_node ); // 如果系数变为0, 把老节点也删除 if ( abs ( cur->_ratio ) < 0.0000001f ) // 浮点数不应该直接比较, 只能算误差 { poly = poly->_next; free ( cur ); } return poly; } else { // 找一个指数相同,或前面比自身大&&后面比自身小的位置, 例如: 2 要找到一个 2, 或者3->1 Node * prev = poly; // 记录匹配的前一个节点,用于在cur前面插入节点 Node * cur = prev->_next; // 节点是否匹配的测试节点 for ( ; cur != NULL; prev = cur, cur = cur->_next ) // 维护好prev, cur在遍历过程中的关系 { if ( cur->_index == new_node->_index ) // 找到前面例子中的2了, 加起来就好了 { cur->_ratio += new_node->_ratio; free ( new_node ); // 如果系数变为0, 把老节点也删除 if ( abs ( cur->_ratio ) < 0.0000001f ) // 浮点数不应该直接比较, 只能算误差 { prev->_next = cur->_next; free ( cur ); } return poly; // 找到就不找了, 所以是第一次 } if ( cur->_index < new_node->_index ) // 找到前面例子中的3->1中的1了 { new_node->_next = cur; // 类似于: 2->1; ...->3->1 prev->_next = new_node; // 类似于: ...->3->2(->1) return poly; } } // 到了这里说明任意节点指数都比新指数大, 同时prev也指向了最后一个元素. 所以直接插入到最后 new_node->_next = NULL; // 类似于: 2-> NULL prev->_next = new_node; // 类似于: ...->3->2->NULL return poly; } } return new_node; // 多项式无效,返回只有一个节点的多项式 } return poly; // 新节点无效,不插入 Node * prev = new_node; Node * cur = poly; if ( new_node == NULL ) return poly; new_node->_next = poly;}// 释放多项式void free_poly ( Node * poly ){ while ( poly != NULL ) { Node * tmp = poly; poly = poly->_next; free ( tmp ); }}// 输入多项式Node * input_poly() // 这里简单的处理输入, 不考虑输入过程可能产生的异常(比如输入了字母){ unsigned i = 0, n = 0; Node * poly = NULL; printf ( "请先输入多项式项数: " ); scanf ( "%u", &n ); for ( i = 1; i <= n; ++i ) { Node * item = ( Node * ) malloc ( sizeof ( Node ) ); if ( NULL == item ) { free_poly ( poly ); printf ( "内存不足\n" ); return NULL; } printf ( "请输入第%d项的系数和指数(例如: 1.2,2)", i ); scanf ( "%f,%d", &item->_ratio, &item->_index ); poly = SortInsert ( poly, item ); } return poly;}// 输出项void display_node ( Node * item ){ printf ( "%fX^%u", item->_ratio, item->_index );}// 输出多项式void display ( Node * poly ){ Node * tmp = NULL; if ( poly == NULL ) return ; display_node ( poly ); for ( tmp = poly->_next; tmp != NULL; tmp = tmp->_next ) { printf ( " + " ); display_node ( tmp ); } printf ( "\n" );}int main(){ Node * A = NULL; Node * B = NULL; // 输入A A = input_poly(); printf("您输入的多项式A为:"); display(A); // 输入B B = input_poly(); printf("您输入的多项式B为:"); display(B); // 相加 { // 注意到SortInsert中,在指数相等时会合并项, // 所以只需要把其中一个多项式中的所有项SortInsert到另外一个多项式中就完成了 // 该方法破坏了A和B!!!, 但是题目没有禁止 Node * tmp = NULL; while ( B != NULL ) // 只要多项式B还有项 { // 从头分离项 tmp = B; B = B->_next; // 插入到另外一个多项式中 SortInsert ( A, tmp ); } } // 输出 display ( A ); free_poly( A ); return 0;}/* 测试io:请先输入多项式项数: 4请输入第1项的系数和指数(例如: 1.2,2)400,4请输入第2项的系数和指数(例如: 1.2,2)100,1请输入第3项的系数和指数(例如: 1.2,2)200,2请输入第4项的系数和指数(例如: 1.2,2)300,3您输入的多项式A为:400.000000X^4 + 300.000000X^3 + 200.000000X^2 + 100.000000X^1请先输入多项式项数: 2请输入第1项的系数和指数(例如: 1.2,2)20,2请输入第2项的系数和指数(例如: 1.2,2)30,3您输入的多项式B为:30.000000X^3 + 20.000000X^2400.000000X^4 + 330.000000X^3 + 220.000000X^2 + 100.000000X^1*/// 写了一个多小时,累死了。 希望能帮到了。。