1.链表实现

分为三个文件进行编写,分别为自定义头文件,实现的cpp文件与main主程序文件.

整个过程中在实现乘的函数MutiplePoly和展示的Display函数上遇到较大困难.

1)MutiplePoly:由于一开始便默认数据是按低阶到高阶的,在设计乘算法时强迫自己尽量不使用双循环来计算.关键在于找到相乘后同阶的所有项并相加,,故将两个链表各循环一遍存入两个数组中方便访问.在将两个多项式各个系数相乘的结果规律排列成矩阵后,发现相乘后的阶数规律排列.

如两个数组大小分别为4,3.则下标分别为0,1,2,3与0,1,2,相乘后系数相加得到如下矩阵:

0	1	2	3
1	2	3	4
2	3	4	5

矩阵中相同数字代表的项阶数相同,则按斜线划分成6层,大循环从0层开始遍历到顶层.则计算可分为两部分,一部分层数0~2,a[i]+b[j],i+j=当前层数,当j<0时跳出小循环.另一部分3~5,当i>3时跳出小循环.通过小循环将相同阶数的系数全部相加.

 

 

 

2)Display:展示多项式的实现过程主要在于细节的繁多,如首项若为正项则不加符号,若为0则不显示,非首项若为0则不显示,为正项要添加正号等等.也因为这样最后的实现体跳转较多,代码显得繁琐.

顺序表实现虽然用的是vector,但基本也符合顺序表的定义,实现过程与链表相差无几.故不多赘述.

最后附上完整链表实现代码:

头文件:

#ifndef __POLY_H__
#define __POLY_H__
#include <iostream>
#include <vector>
using namespace std;

// 存储系数的结构体,采用双链表结构
typedef struct data
{
    int coefficient;
    struct data *next;
    struct data *pre;
} Data;
typedef Data *PtrToNode;

// 存储链表首末位置的结构体
typedef struct upper
{
    PtrToNode head;
    PtrToNode end;
    int items;
} list;

//声明链表
typedef list *List;

void InitList(List &);                     //初始化链表
void Add(List &);                          //添加数据
void AddNode(List &);                      //添加节点
void GetInfo(List &);                      //输入数据
void Calculate(List &);                    //运用霍纳法则进行计算
void AddPoly(List &, List &, List &);      //将两个多项式相加
void SubtractPoly(List &, List &, List &); //将两个多项式相减
void MutiplePoly(List &, List &, List &);  //将两个多项式相乘
// void DividePoly(List &, List &, List &);
void Differential(List &);
void Clear(List &);                                             //清空列表
void Reset(List &, List &);                                     //重新输入两个多项式
void menu1();                                                   //展示菜单1
void menu2();                                                   //展示菜单2
void Display(List &);                                           //展示多项式
void ListToArray(List &, List &, vector<int> &, vector<int> &); //将链表数据转化为数组存储
void DeleteHead(List &);                                        //删除首节点
#endif

 

实现文件:

#include "poly.h"

//给多项式添加信息
void Add(List &l)
{
    int num;
    cout << "Enter the number of terms:" << endl;
    cin >> num;
    cout << "Enter the coefficients in ascending power:" << endl; //提醒用户以幂次的升序输入系数
    for (int i = 0; i < num; i++)
    {
        AddNode(l);
        GetInfo(l);
    }
}

// 初始化链表
void InitList(List &l)
{
    l = (List) new list;
    l->head = NULL;
    l->end = NULL;
    l->items = 0;
}

//多项式相加
void AddPoly(List &l1, List &l2, List &l3)
{
    PtrToNode cur1 = l1->head;
    PtrToNode cur2 = l2->head;
    while (cur1 != NULL || cur2 != NULL)
    {
        AddNode(l3);
        if (cur1 != NULL && cur2 != NULL)
        {
            l3->end->coefficient = cur1->coefficient + cur2->coefficient;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        else if (cur1 == NULL) //处理多项式项数不同的情况
        {
            l3->end->coefficient = cur2->coefficient;
            cur2 = cur2->next;
        }
        else
        {
            l3->end->coefficient = cur1->coefficient;
            cur1 = cur1->next;
        }
    }
    Display(l3);
}

// 多项式相减
void SubtractPoly(List &l1, List &l2, List &l3)
{
    PtrToNode cur1 = l1->head;
    PtrToNode cur2 = l2->head;
    while (cur1 != NULL || cur2 != NULL)
    {
        AddNode(l3);
        if (cur1 != NULL && cur2 != NULL)
        {
            l3->end->coefficient = cur1->coefficient - cur2->coefficient;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        else if (cur1 == NULL)
        {
            l3->end->coefficient = -cur2->coefficient;
            cur2 = cur2->next;
        }
        else
        {
            l3->end->coefficient = cur1->coefficient;
            cur1 = cur1->next;
        }
    }
    Display(l3);
}
void MutiplePoly(List &l1, List &l2, List &l3)
{
    vector<int> a1;
    vector<int> a2;
    ListToArray(l1, l2, a1, a2);

    //根据幂次相加后形成的规律矩阵查找每个幂次对应的项并相加,最后赋值
    int top = (l1->items + l2->items - 2);
    int floor = 0; //幂次为0开始
    int border = a2.size() - 1;
    int sum = 0; //存储每个幂次对应的系数
    while (floor <= top)
    {
        AddNode(l3);
        if (floor <= border)
            for (int i = 0, j = floor - i; j >= 0; i++, j--)
            {
                sum += a1[i] * a2[j];
                l3->end->coefficient = sum;
            }
        else
            for (int j = border, i = floor - j; i < a1.size() && j >= 0; i++, j--)
            {
                sum += a1[i] * a2[j];
                l3->end->coefficient = sum;
            }
        sum = 0;
        floor++;
    }
    Display(l3);
}

// 求一阶导
void Differential(List &l)
{
    DeleteHead(l);

    int time = 1;
    PtrToNode cur = l->head;
    while (cur != NULL)
    {
        cur->coefficient *= time;
        cur = cur->next;
        time++;
    }
    Display(l);
}

void Calculate(List &l)
{
    //获得x值
    int x;
    cout << "Enter the value of x:" << endl;
    cin >> x;

    PtrToNode cur = l->end; //按照霍纳法则从后往前遍历
    int poly = 0;
    while (cur != NULL)
    {
        poly = x * poly + cur->coefficient; //将多项式进行拆分成相乘形式
        cur = cur->pre;
    }
    cout << "The result is " << poly << endl;
}

//两个菜单
void menu1()
{
    cout << "Choose one to execute:" << endl;
    cout << "a)Add\nb)Subtract\nc)Mutiply" << endl;
}
void menu2()
{
    cout << "Choose one to execute:" << endl;
    cout << "a)Calculate\nb)Retype the two polynomials\nc)Differential\nq)quit" << endl;
}

//获得系数
void GetInfo(List &l)
{
    cin >> l->end->coefficient;
}

void AddNode(List &l)
{
    PtrToNode newNode = (PtrToNode) new Data;
    newNode->next = NULL;
    newNode->pre = l->end;
    if (l->head == NULL)
    {
        l->head = newNode;
        l->end = newNode;
    }
    else
    {
        l->end->next = newNode;
        l->end = newNode;
    }
    l->items++;
}

//清除结果
void Clear(List &l)
{
    PtrToNode cur = l->head;
    PtrToNode temp;
    while (cur != NULL)
    {
        temp = cur->next;
        free(cur);
        cur = temp;
    }
    l->head = NULL;
    l->end = NULL;
    l->items = 0;
}

//重设l1,l2
void Reset(List &l1, List &l2)
{
    Clear(l1);
    Clear(l2);
    Add(l1);
    Add(l2);
}

//将多项式以字符串形式展示
void Display(List &l)
{
    string polynomial;
    PtrToNode cur = l->head;
    if (l->items == 0)
        polynomial.append("0");
    else //遍历以确定系数是否全为0
    {
        int cnt = 0;
        while (cur != NULL)
        {
            if (cur->coefficient == 0)
                cnt++;
            cur = cur->next;
        }
        if (cnt == l->items)
        {
            polynomial.append("0");
            cout << polynomial << endl;
            return;
        }
    }

    //通过不断将系数与符号append到string中从而展示

    int time = 0; //记录幂的次数
    cur = l->head;
    while (cur != NULL)
    {
        if (cur == l->head)
        {
            if (cur->coefficient != 0)
                polynomial.append(to_string(cur->coefficient));
            cur = cur->next;
            time++;
            continue;
        }
        else
        {
            if (cur->coefficient > 0)
                polynomial.append("+");
            else if (cur->coefficient < 0)
                polynomial.append("-");
            else //系数为零则跳过不显示
            {
                cur = cur->next;
                time++;
                continue;
            }
            polynomial.append(to_string(abs(cur->coefficient)));
            polynomial.append("x^");
            polynomial.append(to_string(time));
            time++;
            cur = cur->next;
        }
    }
    cout << polynomial << endl;
}

// 将链表存储到数组当中方便访问
void ListToArray(List &l1, List &l2, vector<int> &a1, vector<int> &a2)
{
    PtrToNode p1 = l1->head;
    PtrToNode p2 = l2->head;

    //通过if,else语句让a1.a2分别固定存储长多项式于短多项式
    if (l1->items > l2->items)
    {
        while (p1 != NULL)
        {
            a1.push_back(p1->coefficient);
            p1 = p1->next;
        }

        while (p2 != NULL)
        {
            a2.push_back(p2->coefficient);
            p2 = p2->next;
        }
    }
    else
    {
        while (p1 != NULL)
        {
            a2.push_back(p1->coefficient);
            p1 = p1->next;
        }

        while (p2 != NULL)
        {
            a1.push_back(p2->coefficient);
            p2 = p2->next;
        }
    }
}

// 删除第一个节点
void DeleteHead(List &l)
{
    PtrToNode temp = l->head;
    if (l->items > 1) //项数大于1的情况
        l->head->next->pre = NULL;
    l->head = l->head->next;
    delete temp;
    l->items--;
}

 

 

 

 

 

 

主程序文件:

#include "poly.h"
int main(void)
{
    List l1;//第一个多项式
    List l2;//第二个多项式
    List l3;//操作之后的多项式
    char option;

    //初始化三个链表
    InitList(l1);
    InitList(l2);
    InitList(l3);

    //输入多项式
    Add(l1);
    Add(l2);
    do
    {
        menu1();
        cin >> option;
        switch (option)
        {
        case 'a':
            AddPoly(l1, l2, l3);
            break;
        case 'b':
            SubtractPoly(l1, l2, l3);
            break;
        case 'c':
            MutiplePoly(l1, l2, l3);
            break;
        case 'd':
            // DividePoly(l1, l2, l3);
            break;
        default:
            cout << "Invalid input" << endl;
            continue;
        }

        menu2();
        cin >> option;
        switch (option)
        {
        case 'a':
            Calculate(l3);
            break;
        case 'b':
            Reset(l1, l2);
            break;
        case 'c':
            Differential(l3);
            break;
        case 'q':
            break;
        default:
            cout << "Invalid input" << endl;
            break;
        }

        Clear(l3);
    } while (option != 'q');
}