//拙作不免有些bug，如果您发现了,请指正
#include
#include
#include
#include
/* 多项式运算 加减乘运算
* 输入说明如下：输入的每项 axb ，a为系数,b为次数,且a,b,均不超过三位数,包括负号不超过4位,也不要为了好看加入空格,加入之后程序可能崩溃！
* 若次数b为负数,在输入的时候,应加上阔号,输入的时候应尽可能按高次项,低次项的顺序输入
* 以#号结束,例如 5x2+6x+5-x(-1)#
*
*
*/
#define M 50
#define M1 550
typedef struct {
float coe; //系数
int index; //次数
} Node; //节点结构类型
void initNode(Node * node)
{ //初始化节点
node->coe = 0.0;
node->index = 0;
}
typedef struct {
Node data[M]; //节点数组
int last; //最后节点的下标
} Seqlist; //存放项的结构类型
void initSeqlist(Seqlist * seqlist)
{
int i;
i = 0;
for (; i < M; i++)
initNode(&seqlist->data[i]);
seqlist->last = -1;
}
int dxInput(Seqlist * seqlista)
{ //接受多项式输入,并存入数组中
char str[M1];
int i, j, v;
int z, f, w;
fgets(str, M1, stdin);
//puts(str);
i = 0;
if (!(str[i] >= '0' && str[i] <= '9') && (str[i] != '-')
&& (str[i] != 'x')) {
puts("输入非法字符！");
return 0;
}
j = 0; //多项式的第j+1项
v = 0;
z = f = 0; //对于多项式中的每项,负值的标识 f负
w = 0;
for (i = 0; str[i] != '#'; i++) {
if (str[i] == '-') //检测第一个字符
{
f = 1;
}
if (str[i] == '+')
z = 1;
if (str[i] == 'x') {
if (w != 1) {
if (f == 1) {
seqlista->data[j].coe = -1;
} else
seqlista->data[j].coe = 1;
}
i++;
if (str[i] == 'x') {
puts("输入有误！2");
return 0;
}
goto n1;
}
if (str[i] >= '0' && str[i] <= '9') {
for (; str[i] >= '0' && str[i] <= '9'; i++)
v = v * 10 + str[i] - '0';
if (f == 1)
seqlista->data[j].coe = (-1) * v;
else
seqlista->data[j].coe = v;
w = 1;
if (str[i] == '+' || str[i] == '-'
|| str[i] == '#') {
seqlista->data[j].index = 0;
v = 0;
z = f = 0;
j++;
w = 0;
i--;
continue;
}
i--;
}
if (str[++i] == '+' || str[i] == '-') //容错
{
if (f || z) {
puts("输入有误！1");
return 0;
}
}
--i;
continue;
//判断每项的第一个字符,并标记,若正z=1，若负f=1,
n1:v = 0; //往下处理次数,上面处理的是每项的系数
if (str[i] == '+' || str[i] == '-' || str[i] == '#') {
seqlista->data[j].index = 1;
i--;
j++;
f = z = 0;
w = 0;
continue;
}
if (str[i] == '(') {
i += 2;
for (; str[i] >= '0' && str[i] <= '9'; i++)
v = v * 10 + str[i] - '0';
seqlista->data[j].index = (-1) * v;
//i--;
j++;
v = 0; //
w = 0;
f = 0;
z = 0;
continue;
}
for (; str[i] >= '0' && str[i] <= '9'; i++)
v = v * 10 + str[i] - '0';
seqlista->data[j].index = v;
v = 0;
z = f = 0;
i--;
j++;
w = 0;
}
seqlista->last = --j;
return 1;
}
int testXushu(Seqlist * a)
{ //测多项式中的项是否为从高次到低次输入,若是返回1,否则返回0
int i = 1;
for (; i <= a->last; i++)
if (a->data[i].index > a->data[i - 1].index)
return 0;
return 1;
}
void quickSort(Node a[], int left, int right) //快速排序法
{
int middle = (left + right) / 2;
int i, j, t1, t2, midvalue;
i = left;
j = right;
midvalue = a[middle].index;
while (i <= j) {
while (a[i].index > midvalue && i < right)
i++;
while (a[j].index < midvalue && j > left)
j--;
if (i <= j) {
t1 = a[i].coe;
t2 = a[i].index;
a[i].coe = a[j].coe;
a[i].index = a[j].index;
a[j].coe = t1;
a[j].index = t2;
i++;
j--;
}
if (i > j && i < right)
quickSort(a, i, right);
if (i > j && j > left)
quickSort(a, left, j);
}
}
void kuaiPaiDuoXiang(Seqlist * adr)
{
quickSort(adr->data, 0, adr->last);
}
void deleteFromDm(Seqlist * S, int n) //从多项式存储结构中删除一项,接受被删项的(下标!!!)
{
int i = n + 1;
for (; i <= S->last; i++) {
S->data[i - 1] = S->data[i];
}
S->last--;
}
void addToDm(Seqlist * S, int n, Node * data) //在多项式存储结构中添加一项,接受添加的位置的(下标!!!)
{
int i;
for (i = S->last; i >= n; i--) {
S->data[i + 1] = S->data[i];
}
S->data[n].coe = data->coe;
S->data[n].index = data->index;
S->last++;
}
int testCiXu(Seqlist * adr) //测试有无同次项,有返回1,无返回零
{
int i, j;
for (i = 0; i < adr->last; i++)
for (j = i + 1; j <= adr->last; j++) {
if (adr->data[j].index == adr->data[i].index)
return 1;
}
return 0;
}
void deleteLingXiang(Seqlist * adr) //删除零项
{
for (int i = 0; i <= adr->last; i++) //删掉系数为零的项
{
if (fabs(adr->data[i].coe) <= 0.000001)
deleteFromDm(adr, i);
}
}
void heBingTongCiXiang(Seqlist * adr) //合并同次项
{
int i, j;
for (i = 0; i < adr->last; i++)
for (j = i + 1; j <= adr->last; j++) {
if (adr->data[j].index == adr->data[i].index) {
adr->data[i].coe += adr->data[j].coe;
deleteFromDm(adr, j);
j--;
}
}
deleteLingXiang(adr);
}
int paiXuDuoXiang(Seqlist * a) //将存储结构中的每项重新排列,如果输入的多项式次数从高到低排列,那么就不排,否则重新排列,使用快速排序法
{
deleteLingXiang(a);
if (!testXushu(a)) { //printf("多项式排序中……\n");//可当掉
kuaiPaiDuoXiang(a);
return 1;
}
if (testCiXu(a)) {
//printf("yes!同次数项\n");//可当掉
heBingTongCiXiang(a);
return 1;
}
return 0;
}
void print(Seqlist * adr)
{
for (int i = 0; i <= adr->last; i++)
printf("%f,%d\n", adr->data[i].coe, adr->data[i].index);
if (adr->last < 0) //处理和为零的情况
printf("0\n");
}
void print2(Seqlist * adr)
{
float f;
int t, v;
v = adr->last;
if (adr->last < 0) //处理和为零的情况
{
printf("0\n");
return;
}
for (int i = 0; i <= v; i++) {
f = adr->data[i].coe;
t = adr->data[i].index;
if (f > 0.0) {
if (i != 0)
printf("+");
if (fabs(f - 1.0) < 0.000002) {
if (t == 0)
printf("%.0f", f);
} else
printf("%.0f", f);
} else {
if (fabs(f + 1.0) < 0.000002) {
printf("-");
if (t == 0)
printf("\b%.0f", f);
} else
printf("%.0f", f);
}
if (t > 0) {
printf("x");
if (t > 1)
printf("%d", t);
}
if (t < 0) {
printf("x(");
printf("%d", t);
printf(")");
}
}
printf("\n");
}
void add2DuoXiangShi(Seqlist * a, Seqlist * b) //将两个多项式做加法
{
int i, j;
i = j = 0; //两个存储结构的指向
//Seqlist c;
paiXuDuoXiang(a);
paiXuDuoXiang(b);
if (a->last == -1) {
for (; i <= b->last; i++) {
addToDm(a, i, &b->data[i]);
}
return;
}
for (i = 0; i <= a->last; i++) //第一个存储结构
{
for (; j <= b->last; j++) //第二个存储结构
{
if (a->data[i].index < b->data[j].index) {
addToDm(a, i, &b->data[j]);
i++;
continue;
}
if (a->data[i].index == b->data[j].index) {
a->data[i].coe += b->data[j].coe;
if (fabs(a->data[i].coe) <= 0.000001) {
deleteFromDm(a, i);
i--;
}
j++;
if (i == a->last) {
i--;
break;
}
break;
}
if (a->data[i].index > b->data[j].index) {
if (i < a->last)
break;
else {
for (; j <= b->last; j++)
addToDm(a, i + 1,
&b->data[j]);
}
}
}
}
if (testCiXu(a)) {
//printf("yes!同次数项\n");
heBingTongCiXiang(a);
}
}
void changeZheng2Fu(Seqlist * a)
{
int i = 0;
for (; i <= a->last; i++)
a->data[i].coe *= -1;
}
void chengDuoXiang(Seqlist * a, Seqlist * b, Seqlist * ji) //多项式乘积函数
{
int i, j;
Seqlist d;
Node e;
//initSeqlist(&c);
//print2(a);
//print2(b);
//exit(0);
i = 0;
j = 0;
for (; i <= a->last; i++) {
initSeqlist(&d);
for (j = 0; j <= b->last; j++) {
e.coe = a->data[i].coe * b->data[j].coe;
e.index = a->data[i].index + b->data[j].index;
addToDm(&d, j, &e);
//printf("%f,%d",e.coe,e.index);
}
add2DuoXiangShi(ji, &d);
//print2(ji);
}
}
void divideDuoXiang(Seqlist * a, Seqlist * b, Seqlist * ji)
{
paiXuDuoXiang(a);
paiXuDuoXiang(b);
if (a->last == -1 && b->last != -1) {
printf("0\n");
return;
}
if (a->last != -1 && b->last == -1) {
printf("除数不能为零！\n");
return;
}
if (a->data[0].index < b->data[0].index) {
printf("商：0;\n余数：");
print2(b);
return;
}
}
void dealInput2(int i)
{
Seqlist a, b, c; //
initSeqlist(&a);
initSeqlist(&b);
initSeqlist(&c);
printf("请输入第一个多项式！,以#号结束！\n");
dxInput(&a);
//print(&a);
//if(paiXuDuoXiang(&a));
//print(&a);
printf("请输入第二个多项式！,以#号结束！\n");
dxInput(&b);
//print(&b);
//if(paiXuDuoXiang(&b));
//print(&b);
if (i == 1) {
printf("两个多项式的和为：");
add2DuoXiangShi(&a, &b);
print2(&a);
}
if (i == 2) {
printf("两个多项式的差为：");
changeZheng2Fu(&b);
add2DuoXiangShi(&a, &b);
print2(&a);
}
//print(&a);
if (i == 3) {
printf("两个多项式的积为：");
chengDuoXiang(&a, &b, &c);
print2(&c);
}
//print(&a);
/*
printf("两个多项式的商为：");
*/
}
void menu(void)
{
printf("**********************************************\n");
printf("****************多项式运算**********************\n");
printf("***1:多项式加\n");
printf("***2:多项式减\n");
printf("***3:多项式乘\n");
printf("***4:退出\n");
printf("**********************************************\n");
printf("请输入选项！");
}
int main(int argc, char *arg[])
{
char c;
puts("");
puts(" 多项式运算 加减乘运算");
puts("输入说明如下：输入的每项 axb ，a为系数,b为次数,且a,b,均不超过三位数,包括负号不超过4位,也不要为了好看加入空格,加入之后程序可能崩溃！");
puts("若次数b为负数,在输入的时候,应加上阔号,输入的时候应尽可能按高次项,低次项的顺序输入");
puts("以#号结束,例如 5x2+6x+5-x(-1)#");
while (1) {
menu();
c = getchar();
getchar();
//getchar();
switch (c) {
case '1':
dealInput2(1);
break;
case '2':
dealInput2(2);
break;
case '3':
dealInput2(3);
break;
case '4':
exit(0);
}
}
return 1;
}
阅读(1640) | 评论(0) | 转发(0) |
