据说今天要交这个变态的作业，所以，我赶了一夜写了这么个小程序，可是今天拿到了学校老师却说今天不上课，害的我困的差点撞车。
唉，多少也是写完了一点东西，传上来大家看看吧。
输入一个一元多项式，例如：-23x^9+54x^8+22x^9等等，把指数相同的项目合并，并且按照指数大小排列输出字符串。差不多了吧。
老师要求使用线性表来操作，我也就按要求做了。源代码含有四个文件，datastruct.h是数据结构的定义；ListOper.h是线性表操作函数的声明；ListOper.cpp是线性表操作函数的定义；main.cpp是主单元含有主函数和字符串分析函数。
datastruct.h
typedef struct list
{
int c; //多项式的项数
int e; //多项式的指数
struct list *next; //下一结点
};
typedef struct list *LinkList;
typedef struct list Node;
下面是线性表的操作相关函数声明，对应文件ListOper.h:
//File: ListOper.h
#ifndef DATASTRUCT
#define DATASTRUCT
#include "datastruct.h"
#endif
//some functions declaretioin
bool CreateList(LinkList &L);
Node *CreateNode(int e, int c);
void FreeList(LinkList &L);
void SortList(LinkList &L);
void DeleteNextNode(Node *d);
void SweepNextNode(Node *s);
void OutPutList(LinkList &L);
相关函数的实现，对应文件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;
}
pos=pos->next;
}
cout << endl;
}
主单元文件main.cpp:
#include <iostream>
#include <stdlib.h>
#include <ctype.h>
#include "ListOper.h"
using namespace std;
LinkList AnayString(char aString[], int aLength);
int main(int argc, char *argv[]) //-------------------------------
{
LinkList L;
char InStr[1024];
int len;
cout << "一元稀疏多项式计算器" << endl;
cout << "Copyright@1999-2004, Gashero Liu." << endl;
cout << "作者：刘晓明" << endl << endl;
cout << "请输入一个1024个字符以内的稀疏多项式：";
cin >> InStr;
len=strlen(InStr);
L=AnayString(InStr,len);
SortList(L);
OutPutList(L);
FreeList(L);
system("PAUSE");
return 0;
}
LinkList AnayString(char aString[], int aLength) //---------------
//TODO: 字符串分析函数
{
LinkList L=NULL;
Node *pos=NULL;
Node *last;
Node *head;
CreateList(L);
head=L;
last=head;
int c=0;
int e=0;
char temp[1];
char tp;
bool plus=true;
char status='n'; //状态指示符,我省略了系数为负的情况
/*
n: 非运算状态
c: 正在计算系数
e: 正在计算指数
p: 指数为0
f: 完成了一个项目的输入
*/
for(int i=0;i<aLength;i++)
{
temp[0]=aString[i];
tp=temp[0];
switch(status)
{
case 'n':
{
c=0;e=0;
status='c';
if(tp=='-')
{
plus=false;
continue;
}
if(isdigit(tp))
{
c=atoi(temp);
continue;
}
if(tp=='x')//多项式以x开头
{
c=1;
status='e';
continue;
}
}
case 'c':
{
if(isdigit(aString[i]))
{
if(plus)
{
c=c*10+atoi(temp);
}
else
{
c=c*10-atoi(temp);
}
continue;
}
if(tp=='x')
{
if(c==0)
{
c=1;
}
status='e';
e=0;
continue;
}
//此处考虑了常数项出现在其他位置的可能
if(tp=='+')
{
plus=true;
status='p';
continue;
}
if(tp=='-')
{
plus=false;
status='p';
continue;
}
/*if(temp[0]=='^')
{
status='e';
e=0;
continue;
}*/ //此种情况不可能出现
continue;
} //正在解析系数
case 'e':
{
if(tp=='^')
{
continue;
}
if(isdigit(tp))
{
e=e*10+atoi(temp);
continue;
}
if(tp=='+')
{
plus=true;
status='f';
continue;
}
if(tp=='-')
{
plus=false;
status='f';
continue;
}
} //正在解析系数
case 'p':
{
e=0;
status='f';
continue;
}
case 'f':
{
pos=CreateNode(e,c);
last->next=pos;
last=pos;
c=0;e=0;
status='c';
i--;
continue;
}
}
}
pos=CreateNode(e,c);
last->next=pos;
return L;
}
我就写了这么一点代码，而且其中应该还会有bug，推荐大家看一下只是为了学习除虫技术么，嘿嘿嘿嘿。
第一次在博客上发文章试试看，写的不好大家包含哈。
