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

复制代码 代码如下:
#include
#include

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

linklist *creat_lnklst()
{
 linklist *head = (linklist *)malloc(sizeof(linklist));
 head->next = NULL;
 return head;
}

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;
}

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;
}

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;
}

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("%sn", "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;
}

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;
}