数据结构第一次上机实习

C++ 上机 数据结构
数据结构上机实习
发布日期:   2021-01-19
文章字数:   1.6k
阅读时长:   7 分
阅读次数:  

实习题目：一元稀疏多项式运算器

一、 上机实习题目与要求

问题描述

设计一个一元稀疏多项式简单计算器。

基本要求

（1）输入并建立两个多项式；

（2）多项式a与b相加，建立和多项式c；

（3）多项式a与b相减，建立差多项式d；

（3）输出多项式a,b,c,d。输出格式：比如多项式a为： A(x)=c1x^e1+ c2x^e2+…+ cmx^em，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜… ＜em。

二、数据结构设计

选择带头结点的单链表存储稀疏多项式。

原因是稀疏多项式相邻两项的系数差距可能比较大，若使用数组会由较大存储空间的浪费，若系数过大甚至还会有项数溢出的现象；系数还可能为小数，数组没有办法为每一个系数预先分配好空间；多项式的运算中存在项数的增减，有频繁的插入和删除操作，若存在数组中会有大量数据的移动。选择带头结点的单链表来存储稀疏多项式，不存在存储空间的浪费与溢出的情况，对大部分项数都能灵活应对，在进行加减运算时可以直接利用利用原多项式的存储空间。

三、源代码

stdfx.h

#ifndef STDFAX_H_INCLUDE
#define STDFAX_H_INCLUDE
#include <iostream>

using namespace std;
#endif // !SYDFAX_H_INCLUDE

multinomial.h

#ifndef MULTINOMIAL_H_INCLUDED
#define MULTINOMIAL_H_INCLUDED
#include "stdfx.h"

struct Node                    //多项式结点
{
    float coef;                //多项式的系数
    int exp;                //多项式的指数
    Node* next;                //链表指针
    Node() { coef = 0, exp = 0, next = NULL; }
    Node(float c, int e, Node* link = NULL)        //构造函数
    {
        coef = c; exp = e;next = link;
    }
    Node* InsertAfter(float c, int e)            //在链表插入元素
    {
        next = new Node(c, e, next);            
        return next;
    }
};

class Poly
{
private:
    Node* first;            //指向多项式的头节点
    Node* getHead() const { return first; }        //获取多项式的表头指针
    friend Poly operator+(Poly&, Poly&);
    friend Poly operator-(Poly&, Poly&);

public:
    //多项式构造函数,只有头节点的链表
    Poly() { first = new Node(0,-1); }    

    //拷贝构造函数
    Poly(Poly& R)
    {
        first = new Node(0, -1);
        Node* desptr = first, * srcptr = R.getHead()->next;
        while (srcptr != NULL)
        {
            //将数据逐个拷贝
            desptr->InsertAfter(srcptr->coef, srcptr->exp);
            srcptr = srcptr->next;
            desptr = desptr->next;
        }
    }

    //析构函数
    ~Poly(){}

    //通过用户输入建立多项式
    void Creat()
    {
        int n;
        Node* value = first;
        cout << "请输入多项式的项数：";
        cin >> n;
        if (n <= 0)
        {
            cout << "项数应该大于0";
            return;
        }
        for (int i = 0; i < n; i++)
        {
            //将每一项依次存入链表中
            value->next = new Node;
            value = value->next;
            value->next = NULL;
            cout << "请输入该项的系数与指数：";
            cin >> value->coef >> value->exp;
        }
    }

    //获取多项式的长度
    int Getlength()
    {
        Node* current = first;
        int count = 0;
        if(current == NULL)
        {
            //多项式为空时返回0
            cout << "该多项式为空！" << endl;
            return 0;
        }
        while (current->next != NULL)
        {
            //每有一个元素，计数增加1
            count++;
            current = current->next;
        }
        return count;
    }

    //将多项式降序排序与合并同类项
    void Sort()
    {
        Node* current = first->next;
        Node* follow = first->next;
        Node* t = first->next;

        //冒泡排序
        while (true)       
        {
            current = t;
            follow = current->next;
            while (follow!=NULL)
            {
                //如果当前项指数小于后一项，继续往下走
                if (current->exp < follow->exp) 
                {
                    if (follow->next != NULL)
                        follow = follow->next;
                    else
                        break;
                }
                //系数相同时合并同类项
                else if (current->exp == follow->exp)    
                {
                    //用一个临时结点存放两项的和
                    current->coef += follow->coef;
                    Node* temp = first;
                    while (temp->next != follow)
                        temp = temp->next;
                    if (follow->next != NULL)
                    {
                        follow = temp;
                        temp = temp->next;
                        follow->next = temp->next;
                        delete temp;
                        follow = follow->next;
                    }
                    else
                    {
                        follow = temp;
                        temp = temp->next;
                        delete temp;
                        follow->next = NULL;
                        break;
                    }
                }
                else
                {
                    //交换两节点指数和系数的位置
                    Node* temp = new Node;
                    temp->coef = current->coef;
                    temp->exp = current->exp;
                    current->coef = follow->coef;
                    current->exp = follow->exp;
                    follow->coef = temp->coef;
                    follow->exp = temp->exp;
                    if (follow->next != NULL)
                        follow = follow->next;
                    else
                        break;
                }
            }
            if (t->next!=NULL)
            {
                t = t->next;
            }
            else
                break;
        }
    }

    //多项式的输出
    void Print()    
    {
        Sort();
        bool h = true;
        Node *current = first->next;
        if (current == NULL)
        {
            //多项式为空时无输出
            cout << "该多项式为空！" << endl;
        }
        else
        {
            while (current != NULL)
            {
                if (h == false && current->coef > 0)
                {
                    cout << "+";
                }
                h = false;
                if (current->exp == 0)
                {
                    cout << " " << current->coef << " ";
                }
                else if (current->exp == 1 && current->coef != 1)
                {
                    cout << " " << current->coef <<"x" << " ";
                }
                else if (current->coef == 1 && current->exp != 0)
                { 
                    if (current->exp == 1) 
                    { cout << " " << "x" << " "; }
                    else
                    { cout << " " << "x^" << current->exp << " " ; }
                }
                else{ cout << " " << current->coef << "x^" << current->exp <<" "; }
                current = current->next;
            }
        }
        cout << endl;
    }
};

//对运算符+的重载，实现运算符的加法运算
Poly operator+(Poly& A, Poly& B)
{
    A.Sort();
    B.Sort();
    Node* pa, * pb, * pc, * p;
    float temp;
    //两个多项式相加的结果为多项式C
    Poly C;
    pc = C.first;
    //pa与pb分别指A与B的第一个结点，相加后的元素指针后移
    pa = A.getHead()->next;
    pb = B.getHead()->next;
    while (pa != NULL && pb != NULL)
    {
        //都不为空时先进行比较
        if (pa->exp == pb->exp)
        {
            //相等时两系数相加,指针均后移
            temp = pa->coef + pb->coef;
            if (fabs(temp) != 0)
            {
                //相加后系数不为0时，将元素加入C链
                pc = pc->InsertAfter(temp, pa->exp);
            }
            pa = pa->next;
            pb = pb->next;
        }
        else if (pa->exp < pb->exp)
        {    
            //如果pa指数较小，将pa指向的元素链入C链
            pc = pc->InsertAfter(pa->coef, pa->exp);
            pa = pa->next;
        }
        else
        {
            pc = pc->InsertAfter(pb->coef, pb->exp);
            pb = pb->next;
        }
    }
    //处理剩余链
    if (pa != NULL) { p = pa; }
    else { p = pb; }
    while (p != NULL)
    {
        pc = pc->InsertAfter(p->coef, p->exp);
        p = p->next;
    }
    return C;
}

Poly operator-(Poly& A, Poly& B)
{
    A.Sort();
    B.Sort();
    Node* pa, * pb, * pc;
    float temp;
    //两个多项式相减的结果为多项式C
    Poly C;
    pc = C.first;
    //pa与pb分别指A与B的第一个结点，相减后的元素指针后移
    pa = A.getHead()->next;
    pb = B.getHead()->next;
    while (pa != NULL && pb != NULL)
    {
        //都不为空时先进行比较
        if (pa->exp == pb->exp)
        {
            //相等时两系数相减,指针均后移
            temp = pa->coef - pb->coef;
            if (fabs(temp) != 0)
            {
                //相减后系数不为0时，将元素加入C链
                pc = pc->InsertAfter(temp, pa->exp);
            }
            pa = pa->next;
            pb = pb->next;
        }
        else if (pa->exp < pb->exp)
        {
            //如果pa指数较小，将pa指向的元素链入C链
            pc = pc->InsertAfter(pa->coef, pa->exp);
            pa = pa->next;
        }

        else
        {
            pb->coef = pb->coef;
            pc = pc->InsertAfter(pb->coef, pb->exp);
            pb = pb->next;
        }
    }
    //处理剩余链
    if (pa != NULL)
    { 
        while (pa != NULL)
        {
            pc = pc->InsertAfter(pa->coef, pa->exp);
            pa = pa->next;
        }
    }
    else 
    { 
        while (pb != NULL)
        {
            pb->coef = -pb->coef;
            pc = pc->InsertAfter(pb->coef, pb->exp);
            pb = pb->next;
        }
    }
    return C;
}

#endif // !MULTINOMIAL_H_INCLUDED

main.cpp

#include "multinomial.h"
#include "stdfx.h"

int main()
{
    Poly A;
    A.Creat();
    cout << "A链为：";
    A.Print();
    Poly B;
    B.Creat();
    cout << "B链为：";
    B.Print();
    Poly C;
    C = A + B;
    cout << "相加后的C链为：";
    C.Print();
    C = A - B;
    cout << "相减后的C链为：";
    C.Print();
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/01/19/shu-ju-jie-gou-di-yi-ci-shang-ji/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 上机 数据结构
赏
评论
 上一篇
数据结构第二次上机实习 数据结构第二次上机实习
实习题目：表达式的后缀表示一、 上机实习题目与要求问题描述表达式的后缀表示： 表达式中包含运算对象、运算符和圆括号等，习惯上使用中缀表示（指运算符夹在两运算符对象中间）形式。计算表达式的值，涉及到运算符的优先级别，如先乘除后加减。括在一对
2021-01-21 数据结构上机实习
C++ 上机 数据结构
下一篇 
C++编程训练9 C++编程训练9
滴滴打车是目前出行的一种选择，打车时根据选择车型不同，实际行驶路程进行计费。武汉市的滴滴打车目前提供了 4 种车型，分别为快车、出租车、专车和豪华车。不同车型的 起步价以及起步价内的行驶路程不同，同时，每公里的计费标准也不相同；例如武汉市
2020-08-21 C++编程训练
C++ 上机实习
  目录