使用單鏈表實現多項式計算示例

2020-01-26 15:34:03

字體：大中小

來源：轉載

供稿：網友

復制代碼代碼如下:

#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);