//比较函数返回值
#define A_EQUAL_B 0
#define A_LARGE_B 1
#define A_LOWER_B -1
//错误返回之集合
#define SUCCESS 0
#define POINT_ARG_IS_NULL -1
#define LINKLIST_IS_NULL -2
#define NOT_FOUND -3
typedef struct
{
int cst_term;//常数项
int idx_term;//指数
}factor;
typedef factor data_t;
typedef struct linklist
{
data_t data;
struct linklist *next;
}linklist;
/*
*
* malloc头节点，头节点内的数据是无效的
*
*/
linklist *creat_lnklst()
{
linklist *head = (linklist *)malloc(sizeof(linklist));
head->next = NULL;
return head;
}
/*
* pll是插入节点的前一项
* data是数据
* 为新节点分配内存，之后插入
*
*/
int ins_head_lnklst(linklist *pll, const data_t *data)
{
linklist *newnode = NULL;
if(NULL == pll || NULL == data)
return POINT_ARG_IS_NULL;
newnode = (linklist *)malloc(sizeof(linklist));
newnode->data = *data;
newnode->next = pll->next;
pll->next = newnode;
return SUCCESS;
}
/*
*
* pll是要删除节点的前一个
* data存放删除的数据
* 检查pll是否是空
* 检查链表是否为空
* data是NULL就不用保存删除的数据
*
*/
int del_head_lnklst(linklist *pll, data_t *data)
{
linklist *tmp = NULL;
if(NULL == pll)
return POINT_ARG_IS_NULL;
if(pll->next == NULL)
return LINKLIST_IS_NULL;
tmp = pll->next;
if(NULL != data)
*data = tmp->data;
pll->next = tmp->next;
free(tmp);
return SUCCESS;
}
/*
*
* 内部支持data_t大小比较函数
* 如果data_t修改成其他类型则需要修改此方法
*
*/
static int cmp_data(const data_t *a, const data_t *b)
{
int res = 0;
if(a == NULL || b == NULL)
return POINT_ARG_IS_NULL;
res = a->idx_term - b->idx_term;
if(res == 0)
return A_EQUAL_B;
else if(res > 0)
return A_LARGE_B;
else
return A_LOWER_B;
}
/*
*
* 实现在链表中查找data匹配的前一项
* compare是实现虚拟数据类型比较函数
*
*/
linklist * locate_lnklst(linklist *pll, const data_t *data, int (*compare)(const data_t *, const data_t *))
{
if(NULL == pll || data == NULL)
return NULL;
if(NULL == compare)
compare = cmp_data;
while(pll->next)
{
if(A_EQUAL_B == compare(&(pll->next->data), data))
return pll;
pll = pll->next;
}
return NULL;
}
/*
*
* 打印链表数据
* 检查参数空指针
* 检查空链表
*
*/
int print_lnklst(linklist *pll)
{
if(NULL == pll)
return POINT_ARG_IS_NULL;
if((pll = pll->next) == NULL)
{
printf("%s\n", "no element in linklist.\n");
return LINKLIST_IS_NULL;
}
while(pll)
{
if(pll->next == NULL)
{
printf("%2d*X^%1d ", pll->data.cst_term, pll->data.idx_term);
}
else
{
printf("%2d*X^%1d +", pll->data.cst_term, pll->data.idx_term);
}
pll = pll->next;
}
printf("\n");
return SUCCESS;
}
/*
*
* 删除对应数据的节点
*
*/
int locate_del_lnklst(linklist *pll, const data_t *data)
{
linklist *prev = NULL;
if(NULL == pll || data == NULL)
return POINT_ARG_IS_NULL;
prev = locate_lnklst(pll, data, NULL);
if(NULL == prev)
return NOT_FOUND;
return del_head_lnklst(prev, NULL);
}
int add_linklist(linklist *a, linklist *b)
{
linklist *tmp;
if(NULL == a || NULL == b)
return POINT_ARG_IS_NULL;
if((b = b->next) == NULL)
{
return LINKLIST_IS_NULL;
}
while(b != NULL)
{
tmp = locate_lnklst(a, &b->data, NULL);
if(NULL == tmp)
ins_head_lnklst(a, &b->data);
else
tmp->next->data.cst_term += b->data.cst_term;
b = b->next;
}
return 0;
}
/*
*
* A = 1 + 2*X + 3*X^2
* B = 4 + 5*X + 6*X^2
* R = A + B
* = 5 + 7*X + 9*X^2
*
*/
int init_a_b(linklist *a, linklist *b)
{
factor tmp;
tmp.cst_term = 1;
tmp.idx_term = 0;
ins_head_lnklst(a, &tmp);
tmp.cst_term = 2;
tmp.idx_term = 1;
ins_head_lnklst(a, &tmp);
tmp.cst_term = 3;
tmp.idx_term = 2;
ins_head_lnklst(a, &tmp);
tmp.cst_term = 4;
tmp.idx_term = 0;
ins_head_lnklst(b, &tmp);
tmp.cst_term = 5;
tmp.idx_term = 1;
ins_head_lnklst(b, &tmp);
tmp.cst_term = 6;
tmp.idx_term = 2;
ins_head_lnklst(b, &tmp);
return 0;
}
int main(int argc, const char *argv[])
{
linklist *fml_a = creat_lnklst();
linklist *fml_b = creat_lnklst();
init_a_b(fml_a, fml_b);
printf("A =");
print_lnklst(fml_a);
printf("B =");
print_lnklst(fml_b);
add_linklist(fml_a, fml_b);
printf("A + B =");
print_lnklst(fml_a);
return 0;
}
