使用单链表实现多项式计算示例

代码如下:

#include <stdio.h>
#include <stdlib.h>

//比较函数返回值
#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;
}