一元多项式运算数据结构课设.zip

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<ctype.h>//使用isdigit函数 #define INITCAPACITY 10//顺序表初始容量 //定义系数与幂的结构体 typedef struct Number { int cft;//系数 int pwr;//幂 }N; typedef N SQD;//将N命名为SQD //顺序表结构体 typedef struct SequenceList { SQD*p;//指向存储空间的指针 int capacity;//容量 int sz;//计数器 }S; void InitList(S*pf)//初始化顺序表 { pf->capacity = INITCAPACITY; pf->p = (SQD*)calloc(pf->capacity,sizeof(SQD)); pf->sz = 0; } void checkcapacity(S*pf)//检查容量是否足够 { if (pf->capacity == pf->sz)//存满时扩容 { pf->p = (SQD*)realloc(pf->p, sizeof(SQD)*pf->capacity * 2); pf->capacity *= 2; } } void Add(S*pf, SQD n)//向顺序表添加数据 { checkcapacity(pf); pf->p[pf->sz] = n; pf->sz++; } //////////////////////////////////////////////////////////////////////////////////// typedef N LLD;//将N命名为LLD //链表结构体 typedef struct LinkList { LLD data; struct LinkList*next; }L; L*Addnode(L*p, LLD val)//链表节点尾插 { L*node = (L*)malloc(sizeof(L)); node->data = val; node->next = NULL; if (!p) p= node; else { L*cur = p; while (cur->next) { cur = cur->next; } cur->next = node; cur = node; } return p; } int Listsize(L*p)//获取链表节点个数 { L*cur = p; int count=0; while (cur) { count++; cur = cur->next; } return count; } //////////////////////////////////////////////////////////////////////////////////// void menu_L1()//一级菜单，选择存储结构 { printf("********************************************\n"); printf("********* 数据结构课程设计 *********\n"); printf("********* 1.顺序表存储 *********\n"); printf("********* 2.链表存储 *********\n"); printf("********* 0.退出程序 *********\n"); printf("********************************************\n"); } void menu_L2()//二级菜单，选择运算方式 { printf("*********************************************\n"); printf("******** 1.M(x)=Am(x)+Bm(x) *********\n"); printf("******** 2.M(x)=Am(x)-Bm(x) *********\n"); printf("******** 3.M(x)=Am(x)*Bm(x) *********\n"); printf("******** 4.返回上级菜单 *********\n"); printf("*********************************************\n"); } void menu_L3()//三级菜单，选择排序方式并打印 { printf("*********************************************\n"); printf("******** 1.升幂输出结果 *********\n"); printf("******** 2.降幂输出结果 *********\n"); printf("*********************************************\n"); } void setdata_S(S*s)//提取输入的有效数据，存入顺序表中 { InitList(s);//初始化顺序表 char ch;//采用字符接收 int flag = 1;//第一个数字必然是系数，那么下一个就是幂数，在下一个又是系数 //因此用一个标识数判断是系数还是幂数，存入对应数据中。 N n; printf("请输入多项式:\n"); scanf("%d", &n.cft);//第一个必然是数，直接存入 n.pwr = 0; Add(s, n); while ((ch = getchar()) != '\n') { if (isdigit(ch))//是数字减‘字符0’使值转化为int类型上的数字 { ch -= '0'; if (flag == 1) n.cft = ch; else n.pwr = ch; if(flag==-1) Add(s, n); flag *= -1;//更新标识数 } } } int cmp_up(const void*e1, const void*e2)//快速排序比较函数 { return ((N*)e1)->pwr - ((N*)e2)->pwr; } int cmp_down(const void*e1, const void*e2) { return ((N*)e2)->pwr - ((N*)e1)->pwr; } void print_S(S*pf) { int i; for (i = 0; i < pf->sz; i++) { if (pf->p[i].pwr)//如果幂数不为0 { if(i)//如果i不为0，即不是第一个数 printf("+%dx%d", pf->p[i].cft, pf->p[i].pwr);//打印带+号 else printf("%dx%d", pf->p[i].cft, pf->p[i].pwr); } else//幂数为0.不打印幂数 { if(i) printf("+%d", pf->p[i].cft); else printf("%d", pf->p[i].cft); } } printf("\n"); } void Sort_S(S*sa, S*sb, S*sm)//顺序表排序选择 { system("cls");//清屏 menu_L3(); printf("请选择:\n"); int c3; scanf("%d", &c3); switch (c3)//选择排序方式 { case 1: qsort(sm->p, sm->sz, sizeof(N), cmp_up);//库函数快排 print_S(sa); print_S(sb); print_S(sm);//打印之前的数据，和结果 break; case 2: qsort(sm->p, sm->sz, sizeof(N), cmp_down); print_S(sa); print_S(sb); print_S(sm); break; default: printf("输入无效\n"); break; } system("pause"); } L* setdata_L(L*l)//将数据存入链表 { char ch; int flag = 1; N n; printf("请输入多项式\n"); scanf("%d", &n.cft); n.pwr = 0; l=Addnode(l, n);//链表添加节点要更新链表头指针 while ((ch = getchar()) != '\n') { if (isdigit(ch)) { ch -= '0'; if (flag == 1) n.cft = ch; else n.pwr = ch; if(flag==-1) l=Addnode(l, n); flag *= -1; } } return l; } void print_L(L*pf)// { L*cur = pf; int flag = 0;//判断第一个是否打印 while (cur) { if (cur->data.pwr) { if (flag) printf("+%dx%d", cur->data.cft, cur->data.pwr); else printf("%dx%d", cur->data.cft, cur->data.pwr); flag = 1; cur = cur->next; } else { if (flag) printf("+%d", cur->data.cft); else printf("%d", cur->data.cft); flag = 1; cur = cur->next; } } printf("\n"); } void sort_up_bubble(L*pf)//冒泡排升序 { L*i, *j; for (i = pf; i; i = i->next) { for (j = pf; j; j = j->next) { if (j->data.pwr >i->data.pwr) { N ret = j->data; j->data = i->data; i->data = ret; } } } } void sort_down_select(L*pf)//选择排降序 { L*i, *j; for (i = pf; i; i = i->next) { L*max = i; for (j = i->next; j; j = j->next) { if (max->data.pwr < j->data.pwr) max = j; } if (max != i) { N ret = max->data; max->data = i->data; i->data = ret; } } } void Sort_L(L*lm,L*la,L*lb)//链表排序选择 { system("cls"); menu_L3(); printf("请选择:\n"); int c3; scanf("%d", &c3); switch (c3) { case 1: sort_up_bubble(lm); print_L(la); print_L(lb); print_L(lm); break; case 2: sort_down_select(lm); print_L(la); print_L(lb); print_L(lm); break; default: printf("输入无效\n"); break; } system("pause"); } int main() { do { a1: menu_L1();//a1为goto标签，用于菜单返回 printf("请选择:"); int c1; scanf("%d", &c1); switch (c1)//一级菜单选择 { case 0: printf("答辩完毕\n"); exit(0); break; case 1: system("cls"); S sa, sb, sm; N n; setdata_S(&sa);//存入A的数据 setdata_S(&sb);//存入B的数据 int min = sa.sz < sb.sz ? sa.sz : sb.sz, max = sa.sz > sb.sz ? sa.sz : sb.sz;//选出数据个数最大值和最小值 do { system("cls"); menu_L2(); InitList(&sm);//每次计算先初始化M printf("请选择:"); int c2, i=0, j, z, flag = 1;//flag判断是否找到幂数相同的数据 scanf("%d", &c2); switch (c2) { case 1: while (i < min)//先将共同幂数数据相加 { n.cft = sa.p[i].cft + sb.p[i].cft;//系数相加 n.pwr = sa.p[i].pwr;//幂数不变 if(n.cft)//系数不为0才能添加 Add(&sm, n); i++; } while (i < max)//不同幂数 { if (sa.sz < sb.sz)//如果B的多 { if(sb.p[i].cft)//系数不为0 Add(&sm, sb.p[i]);//直接添加 } else { if (sa.p[i].cft) Add(&sm, sa.p[i]); } i++; } Sort_S(&sa, &sb, &sm);//排序 break; case 2: while (i < min) { n.cft = sa.p[i].cft - sb.p[i].cft; n.pwr = sa.p[i].pwr; if(n.cft) Add(&sm, n); i++; } while (i < max) { if (sa.sz < sb.sz) { n.cft = -sb.p[i].cft; n.pwr = sb.p[i].pwr; if(n.cft) Add(&sm, n); } else { if(sa.p[i].cft) Add(&sm, sa.p[i]); } i++; } Sort_S(&sa, &sb, &sm); break; case 3: for (i = 0; i < sa.sz; i++)//两层循环互乘 { for (j =