對于稀疏多項(xiàng)式，采用數(shù)組存儲(chǔ)效率低下，因此考慮采用鏈表結(jié)構(gòu)，節(jié)點(diǎn)包括系數(shù)，指數(shù)，next指針三個(gè)域。多項(xiàng)式的運(yùn)算中，主要要考慮的是同類項(xiàng)合并的問題，這實(shí)際是一個(gè)數(shù)組元素去重的問題（合并冪相同的節(jié)點(diǎn)），因此可以采用先排序（快排平均O(Nlog(N))），后遍歷（O(N)）的方式完成。總時(shí)間O(nlog(n))。

#include <stdio.h> #include <stdlib.h>typedef struct node {int coef;int exponent;struct node* next; }node;typedef struct List {node* next; }List;//打印多項(xiàng)式 void print_poly(List* poly) {node* p = poly->next;while (p != NULL){printf("%d*x^%d + ", p->coef,p->exponent);p = p->next;}printf("\n"); }//創(chuàng)建空表 List* make_empty() {List* list = (List*)malloc(sizeof(List));list->next = NULL;return list; }//在鏈表p節(jié)點(diǎn)后插入一個(gè)節(jié)點(diǎn) void insert_node(List* list, node* p,int coef,int exponent) {if (list == NULL)return;node* p_new = (node*)malloc(sizeof(node));p_new->coef = coef;p_new->exponent = exponent;if (p == NULL)//在頭部插入{p_new->next = list->next;list->next = p_new; }else{p_new->next = p->next;p->next = p_new;} }//獲取鏈表長度 int length(List* list) {int len = 0;node* pCur = list->next;while (pCur != NULL){++len;}return len; }//獲取尾部節(jié)點(diǎn) node* last_node(List* list) {node* p_node = list->next;while (p_node->next != NULL){p_node = p_node->next;}return p_node; } //交換兩節(jié)點(diǎn)內(nèi)容 void swap_node(node* n1,node* n2) {int tmp_coef = n1->coef;int tmp_exponent = n1->exponent;n1->coef = n2->coef;n1->exponent = n2->exponent;n2->coef = tmp_coef;n2->exponent = tmp_exponent; } //快速排序的分割，隨機(jī)選取一個(gè)基準(zhǔn)，把小于它的放到前面，大于的放到后面 node* partition(node* start, node* end) {//取第一個(gè)數(shù)作為基準(zhǔn)數(shù)，這其實(shí)有問題，當(dāng)為有序數(shù)組時(shí)速度很慢，應(yīng)當(dāng)選(start+end)/2位置的數(shù)，保證一定的隨機(jī)性node* p = start;node* q = p->next; //q比p初始快一步node* reference = start; //基準(zhǔn)//從start開始向后進(jìn)行一次遍歷（單鏈表無法從后向前）while (/*q != NULL &&*/ q != end->next){if (q->exponent < reference->exponent){p = p->next; //p永遠(yuǎn)指向的是當(dāng)前已遍歷過且比基準(zhǔn)數(shù)小的最后一個(gè)數(shù)swap_node(p, q);}q = q->next;}swap_node(p, reference); //最后將位于頭部的基準(zhǔn)與p交換，完成當(dāng)前段的分割return p; }void quick_sort(node* start,node* end) {if (start == end || start == NULL || end == NULL) //這個(gè)停止條件要注意必須保證start和end非空{(diào)return;}node* mid = partition(start, end);quick_sort(start, mid);quick_sort(mid->next, end); } //鏈表多項(xiàng)式的排序，同時(shí)合并指數(shù)相同的項(xiàng) void sort_list(List* list) {if ((list->next == NULL) || (list->next->next == NULL)){return;}node* start = list->next;node* end = last_node(list);quick_sort(start, end); }//多項(xiàng)式乘法返回一個(gè)新多項(xiàng)式鏈表 List* mult_polynomial(List* list_in1, List* list_in2) {//先準(zhǔn)備好新的多項(xiàng)式鏈表的大小List* prod = make_empty();node* p_node_in1 = list_in1->next;node* p_node_in2 = list_in2->next;int prod_exponent = 0;int prod_coef = 0;while (p_node_in1 != NULL){p_node_in2 = list_in2->next; //這里記住要及時(shí)返回while (p_node_in2 != NULL){prod_coef = p_node_in1->coef * p_node_in2->coef;prod_exponent = p_node_in1->exponent + p_node_in2->exponent;insert_node(prod, NULL, prod_coef, prod_exponent); //每次都在頭部插入p_node_in2 = p_node_in2->next;}p_node_in1 = p_node_in1->next;}//鏈表排序sort_list(prod);//合并同類項(xiàng)node* pCur = prod->next;node* pDelete = NULL;int i = 0;while (pCur->next != NULL){if (pCur->exponent == pCur->next->exponent){pCur->coef += pCur->next->coef;//刪除多余節(jié)點(diǎn)pDelete = pCur->next;pCur->next = pDelete->next;free(pDelete);pDelete = NULL;continue; //這個(gè)很關(guān)鍵，因?yàn)檫@里的if中修改了節(jié)點(diǎn)的next的指向，因此pCur就不能進(jìn)行步進(jìn)，而應(yīng)當(dāng)停留原地}pCur = pCur->next;}return prod; }int main() {List* poly1 = (List*)malloc(sizeof(List));List* poly2 = (List*)malloc(sizeof(List));node* x1 = (node*)malloc(sizeof(node));x1->coef = 3; x1->exponent = 7; //3x^3node* x2 = (node*)malloc(sizeof(node));x2->coef = 5; x2->exponent = 12; //5x^1node* x3 = (node*)malloc(sizeof(node));x3->coef = 2; x3->exponent = 15; //2x^6node* x4 = (node*)malloc(sizeof(node));x4->coef = 9; x4->exponent = 6; //9x^6x1->next = x2;x2->next = x3;x3->next = x4;x4->next = NULL;poly1->next = x1;node* y1 = (node*)malloc(sizeof(node));y1->coef = 4; y1->exponent = 7; //4x^2node* y2 = (node*)malloc(sizeof(node));y2->coef = 1; y2->exponent = 6; //1x^5node* y3 = (node*)malloc(sizeof(node));y3->coef = 3; y3->exponent = 12; //3x^4node* y4 = (node*)malloc(sizeof(node));y4->coef = 7; y4->exponent = 5; //7x^5y1->next = y2; y2->next = y3; y3->next = y4;y4->next = NULL;poly2->next = y1;sort_list(poly1);sort_list(poly2);print_poly(poly1);print_poly(poly2);List* prod = mult_polynomial(poly1, poly2);print_poly(prod);return 0; }

總結(jié)

以上是生活随笔為你收集整理的1.多项式乘法实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。