【数据结构】储存多项式的链表（输出计算）

一个多项式形如
f ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 f(x)=a_{n}x^n+a_{n-1}x^{n-1}+cdots+a_1x+a_0 f(x)=an​xn+an−1​xn−1+⋯+a1​x+a0​
定义数据结构Term为:

struct Term{
	double coeff;  	//系数
	int power;  	//幂次
}

要求：

试编写一个程序，该程序接收用户输入的系数和幂次对后，将其保存到链表中。输入系数和幂次对时，不要求一定按幂次由高到低的顺序输入，但最后输入的系数和幂次对中的幂次必定为 0 0 0;然后，按幂次对由高到低打印出用户输入的多项式，其中每个项形如 a i x i a_ix^i ai​xi最后，程序反复提示用户输入 x x x的值，并计算出该多项式的值，直到输入 x x x的值为0时程序执行结束。 思路

首先建立一个Term结构体，一个节点类，一个链表类，用来存放数据。对链表中的（Term元素）按幂的大小进行排序。输出/计算链表中的数据。

#include 
#include 
using namespace std;
struct Term
{
    double coeff;           //系数
    int power;              //幂次
};

template 
class Node{					//节点类
public:	
    T data;
    Node * next;
    Node * pre;
    Node(const T& item){
        data=item;
        next=NULL;
        pre=NULL;
    }
    ~Node(){

    }
};

// 1->2->3->4
// 4->3->2->1
template 
class linkList{					//链表类
private:
    Node * head;
    Node * pre;
    int size;
public:
    linkList();
    ~linkList(){}
    void insert(const T& item);      //插入链表元素
    void display();                  //打印链表元素
    void SortByPower();              //排序链表元素
    Node * GetHighest();          //获得最大链表元素
    void show();                     //打印方程函数
    void DelNode(Node * del);     //删除节点  没用到诶,白写了
    double calc(int x);				 //计算多项式
};

template 
linkList::linkList(){
    head=NULL;
    pre=NULL;
    size=0;
}

template 
void linkList::insert(const T& item){
    Node * tmp= new Node(item);
    if (head==NULL)
    {
        head=tmp;
        size++;
    }
    else
    {
        tmp->next=head->next;               //一开始这里忘了要有这句，因为是中间添加节点
        tmp->pre=head;
        head->next=tmp;
        head=tmp;
        size++;
    }
}

template 
void linkList::display(){
    Node * ptr= head;
    for (int i=0; idata.power <<"->";
        ptr=ptr->pre;       //这里一开始错了,写成了head=head->pre
    }
    cout<
void linkList::DelNode(Node * Del){
    if(Del->pre==NULL){                        
        //del 1 2
        if(Del->next==NULL){     //对待删除节点没有后置节点进行讨论
            head==NULL;
        }
        else{
            Del->next->pre=NULL;   //对待删除节点有没有前置节点进行讨论
            size--;
        }    
    }

    else
    {
        Del->next->pre=Del->pre;        //忽略了Del是第一个节点，没有pre的情况
        Del->pre->next=Del->next;
        size--;
        
    }
    
}


template 
Node * linkList::GetHighest(){
    Node * high=head;              //假设最大节点是head
    Node * tmp=head->pre;                         
    for (int i = 0; i < size-1; i++)   //n个节点找最大，只要比较n-1次,n次会报错
    {
        if(head->pre==NULL)
        {
            high=head;
            }   
        if (tmp->data.power > high->data.power)         
        //虽然是模板不知道具体节点的结构但是可以这样使用元素
        {
            high=tmp;        //保存最高次幂的节点
        }
        tmp=tmp->pre;         //一开始漏了这句
    }
    return  high;
}

template 
void linkList::show(){
    int time=size;
    int sum=0;                                          
    cout<<"f(x)=";
    Node * high=GetHighest();          //又把这个放在循环里了
    for (int i = 0; i < time; i++)
    {
        if (high->data.power!=0)
        {
            cout<data.coeff<<"x^"<data.power<<"+";
        }
        else
        {
            cout<data.coeff<<"x^"<data.power;
        }
        high=high->next;
    }
}

template 
void linkList::SortByPower(){
    Node * min=head;                                             //开始把这个写在循环里面了
    for (int i =0 ; i < size; i++)
    {
        Node * t=min->pre;
        while (t!=NULL)
        {
            if (t->data.powerdata.power)
            {
                swap(t->data,min->data);
            }
            t=t->pre;
            
        }
        min=min->pre;
        //1 2 3 4 head
    }
}


template 
double linkList::calc(int x){
    double sum=0;
    Node * max=GetHighest();
    for (int i = 0; i < size; i++)
    {
      
        sum+=max->data.coeff*(pow(x,max->data.power));
        max=max->next;                                          //又把它放到外面了
    }

    return sum;
}

int main(){
    linkList List;
    int p;                          //幂
    double c;                   //系数
    
    while (true)
    {
        cout<<"power?"<>p;
        cout<<"coeff?"<>c;
        Term term;
        term.coeff=c;
        term.power=p;
        if (term.power>0)
        {
            List.insert(term);
        }
        else if(term.power==0){
            List.insert(term);
            break;
        }

    }
    
    List.display();                 //成功测试添加元素
    // List.show();                 //成功打印出函数式子
    
    List.SortByPower();
    List.display();
    List.show();
    


    int x;
    do
    {   
        cout<>x;
        cout<<"结果是:"< 
后记 
重点是对链表元素按某个属性的排序算法（虽然思想本质上和普通的排序没有区别，实际上代码还是不一样的）有很多在遍历链表的时候把节点后移一个放到循环外边了调试真是个好东西