listoper.cpp

一元稀疏表达式计算器 大学数据结构实验

//File: ListOper.cpp

#include <stdlib.h>
#include <iostream>
#ifndef DATASTRUCT
#define DATASTRUCT
#include "datastruct.h"
#endif
#include "ListOper.h"

using namespace std;

bool CreateList(LinkList &L)
{
    //TODO: 创建线性链表
    Node *head;
    head=(Node *)malloc(sizeof(Node));
    if(head==NULL)
    {
        cout << "内存分配错误" << endl;
        return false;
    }
    head->next=NULL;
    head->c=0;
    head->e=0;
    L=head;
    return true;
}

Node *CreateNode(int e, int c)
{
    //TODO: 创建结点
    Node * pos;
    pos=(Node *)malloc(sizeof(Node));
    if(pos==NULL)
    {
        cout << "内存分配错误" << endl;
        exit(1);
    }
    pos->e=e;
    pos->c=c;
    pos->next=NULL;
    return pos;
}
         
void FreeList(LinkList &L)
{
    //TODO: 释放整个线性表所占用的内存空间
    Node *pos;
    Node *next;
    pos=L;
    while(pos!=NULL)
    {
        next=pos->next;
        free(pos);
        pos=next;
    }
}

void SortList(LinkList &L)
{
    bool flag=true; //是否需要排序标志
    Node *head=L->next;
    Node *pos;
    Node *last;
    Node *temp;
    if(head->next==NULL)
    {
        return;
    }
    while(flag)
    {
        flag=true;
        last=head;
        pos=last->next;
        if(last==NULL||last->next==NULL)
        {
            break;
        }
        while(last!=NULL && last->next!=NULL)
        {
            flag=false;
            pos=last->next;
            if(last->e<pos->e)    //哈哈哈哈哈，HTML代码
            {
                SweepNextNode(last);
                flag=true;
            }
            if(last->e==pos->e)
            {
                last->c+=pos->c;
                DeleteNextNode(last);
                flag=true;
                /*last=last->next;
                pos=last->next;*/
            }
            last=last->next;
        }
    }
}

void DeleteNextNode(Node *d)
{
    Node *temp;
    temp=d->next;
    d->next=temp->next;
    free(temp);
}

void SweepNextNode(Node *s)
//一点偷懒的办法，只交换值，不修改指针
{
    int c,e;
    c=s->c;e=s->e;
    s->c=s->next->c;s->e=s->next->e;
    s->next->c=c;s->next->e=e;
}

void OutPutList(LinkList &L)
{
    Node *pos;
    pos=L->next;
    cout << "输出表达式：";
    while(pos!=NULL)
    {
        if(pos->c>0)
        {
            cout << "+";
        }
        if(pos->c!=1)
        {
            cout << pos->c;
        }
        if(pos->e!=0)
        {
            cout << "x^";
            cout << pos->e;
        }
        else
        {
            cout << "x";
        }    
        pos=pos->next;
    }
    cout << endl;
}