首页 > 代码库 > 一元多项式的相加（单链表的应用）
一元多项式的相加（单链表的应用）
一元多项式的相加，基于单链表的结构上实现的。
单链表的结点结构定义为：
typedef struct _NODE
{
int coef;
int exp;
struct _NODE *next;
}NODE；
第一个变量指的是系数，第二个变量指的是指数，x^7系数为1，指数为7
第三个变量next指针，将结点连接起来。
比如a1 = x^5+x^4+x^2+3 a2 = x^7+x^4+x+8
a1+a2 = x^7+x^5+2x^4+x^2+x+11
list.h 里面包含了一些对单链表进行操作的方法的声明
#ifndef _LINK_LIST_H_ #define _LINK_LIST_H_ #define ERROR -1 typedef struct _NODE { int coef; int exp; struct _NODE *next; }NODE; NODE *alloc_node(int coef,int exp); NODE *init_link_list_ex(); bool insert_head(NODE *phead,int coef,int exp); //O(1)---- bool is_empty(NODE *phead); //O(1) bool show(NODE *phead);//O(N) int get_length(NODE *phead); //O(N)---- NODE *get_last(NODE *phead); bool insert_tail(NODE *phead,int coef,int exp); //O(N)---- NODE *get_sec_last(NODE *phead); bool delete_head(NODE *phead);//O(1)---- bool delete_tail(NODE *phead);//O(N)---- bool destory_link_list(NODE *phead); //O(N)---- #endif
list.c里面实现了对单链表操作方法的实现。
#include "LINK_LIST.h" #include <stdio.h> #include <stdlib.h> NODE *alloc_node(int coef,int exp) { NODE *tmp = (NODE *)malloc(sizeof(NODE) * 1); if (tmp == NULL) { return NULL; } tmp->coef = coef; tmp->exp = exp; tmp->next = NULL; return tmp; } NODE *init_link_list_ex() { NODE *phead = (NODE *)malloc(sizeof(NODE) * 1); phead->coef = 0; phead->exp = 0; phead->next = NULL; return phead; } bool insert_head(NODE *phead,int coef,int exp) { if (phead == NULL) { return false; } NODE *tmp = alloc_node(coef,exp); tmp->next = phead->next; phead->next = tmp; return true; } bool is_empty(NODE *phead) { if (phead == NULL) { return true;//ERROR } return phead->next == NULL; } bool show(NODE *phead) { if (phead == NULL) { return false; } if (is_empty(phead)) { return false; } NODE *p = phead->next; while(p != NULL) { if (p->coef > 0) { printf("+%dx^%d ",p->coef,p->exp); } else if( p->coef == 0) { printf("0+"); } else { printf("-%dx^%d ",p->coef,p->exp); } p = p->next; } printf("\n"); return true; } int get_length(NODE *phead) { if (phead == NULL) { return ERROR; } int count = 0; NODE *p = phead->next; while(p != NULL) { p = p->next; count++; } return count; } NODE *get_last(NODE *phead) { if (phead == NULL) { return NULL; } NODE *p = phead; while(p->next != NULL) { p = p->next; } return p; } bool insert_tail(NODE *phead,int coef,int exp) { if (phead == NULL) { return false; } get_last(phead)->next = alloc_node(coef,exp); return true; } NODE *get_sec_last(NODE *phead) { if (phead == NULL) { return NULL; } if (is_empty(phead)) { return NULL; } NODE *p = phead->next; NODE *s = phead; while(p->next != NULL) { s = p; p = p->next; } return s; } bool delete_head(NODE *phead) { if (phead == NULL) { return false; } if (is_empty(phead)) { return false; } NODE *p = phead->next; phead->next = p->next; free(p); return true; } bool delete_tail(NODE *phead) { if (phead == NULL) { return false; } if (is_empty(phead)) { return false; } NODE *p = get_sec_last(phead); free(p->next); p->next = NULL; return true; } bool clear_link_list(NODE *phead) { if (phead == NULL) { return false; } while(!is_empty(phead)) { delete_head(phead); } //free(phead); return true; } bool destory_link_list(NODE *phead) { clear_link_list(phead); free(phead); return true; }
另外，实现了方法NODE *create_poly()生成多项式 ,
add_poly相加函数，这里我实现的是a1 = a1+a2;
NODE *create_poly()//创建好的单链表有序 { NODE *phead = init_link_list_ex(); int coef = 0; int exp = 0; while(1) { printf("请输入系数,指数，形式如下：10,20 输入0,0结束表达式输入\n"); scanf("%d,%d",&coef, &exp); if (coef ==0 && exp ==0) { printf("输入结束\n"); show(phead); break; } NODE *tmp = alloc_node(coef, exp); NODE *p = phead; while(p->next != NULL) { if (p->next->exp > tmp->exp) { break; } p = p->next; } tmp->next = p->next; p->next = tmp; } return phead; }
NODE *add_poly(NODE *pa,NODE *pb) { NODE *p = pa->next; NODE *s = pb->next; NODE *m = pb->next; while(p != NULL && s != NULL) { if (p->exp < s->exp) { //p下去 p = p->next; } else if (p->exp > s->exp) { //s下去 m = s; p->next = m; p = m; s = s->next; } else//合并 { if (!(p->coef+s->coef)) { p = p->next; s = s->next; continue; } p->coef = p->coef + s->coef ; p = p->next; s = s->next; } } while(p != NULL) { p = p->next; } while(s != NULL) { m = s; p->next = m; p = m; s = s->next; } return pa; }
最后在主函数中调用：
int main() { NODE *pheadA = create_poly(); NODE *pheadB = create_poly(); show(pheadA); show(pheadB); pheadA =add_poly(pheadA,pheadB); show(pheadA); show(pheadB); destory_link_list(pheadA); destory_link_list(pheadB); return 0; }
值得注意，所以结点的开辟都是在堆（heap）上进行的，所以务必要对内存进行释放，防止内存泄漏。
一元多项式的相加（单链表的应用）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。