背景
大一下学期 C 程序设计专题（C大程）的第二个专题，关于链表的操作，比较水的一次 Project ，当时正好生病了，便也没做的太认真，一开始是打算采用 GUI 或者 TeX 或者 HTML + CSS 实现多项式的显示的，以及幂为多项式的运算的，然而最后 DDL 在五一期间，赶完通识课的论文后就没有精力了（尤其是还生病了），当时的坑就放弃了。将具体链表操作的实现（毕竟比较简单）交给了队友 MagicPants ，然后我就实现了简单的 IO 操作和文件的模块化划分（这次变成我是可有可无的角色了(⊙﹏⊙)）。不过当时正好看了《 C 专家编程》，便尝试了一下可变参量列表。
报告及源码
一、问题说明(By LLonely)
采用链表结构，运用迭代等算法，设计相应的函数，计算出两个以链表结构储存的多项式的乘积。该问题涉及到多项式的输入、链表的相关操作、多项式的运算及输出等过程。
二、算法设计与说明（By MagicPants）
首先输入两个多项式（即新建两个链表）。分别为list1、list2.复制一个list1，得到list1’,再取list2中的第一项分别与list1’的每一项相乘，得到result1。随后再复制一个list1，得到list1’再取list2中的第二项乘以list1‘的每一项，得到result2.
以此类推（运用迭代的算法分别用list2的每一项与list1相乘得到result1、result2…）。最后可以得到Result = result1 + result2 +result3+ …，Result即为两多项式的积。
以上过程主要涉及到链表的操作及迭代运算。
三、数据结构设计与说明（By MagicPants）
对于多项式的乘法，首先要考虑多项式的存储。我们采用链表的结构存储多项式。每一个节点都存了多项式的一项。用该链表的头指针代表该多项式。
且该链表结构的定义存放在definitions.h头文件中。代码如下所示：
|
1 2 3 4 5 6 7 |
struct function { int cons; int power; struct function *next; }; typedef struct function polynomial; |
四、系统设计难点与解决方案
core.c 开发及测试过程（By MagicPants）：
- sum求和函数中两多项式相加。情况复杂需要细致的分类讨论。
- sum求和函数中系数变为0的情况
- 输入多项式时需考虑可能输入幂相同的项，此时需要考虑合并同类项。而再写一个合并一个多项式同类项的函数的话，难写而且麻烦。而我队友 LLonely 的一个想法很好的解决了这个问题。即在输入多项式时调用sum函数，将输入的每一项用sum函数加到前面的多项式中，而sum函数会帮我们解决合并同类项的问题。让我启发很大。
- 多项式乘法如何操作的问题。我们采用逐项相乘再相加的方法。即用第二个多项式的每一项分别乘以第一个多项式。再将这些多项式相加，得到结果。
io.c main.c及头文件开发及测试过程（By LLonely）：
- 头文件重复引用问题。在模块式开发时，将变量、函数定义储存在头文件中，必然需要在多个文件中都引用该头文件。为了避免编译、链接过程中的重复引用与定义，在参考标准头文件写法及相关文献后，我们采用宏进行了限制。如下所示：
12345#ifndef _DEFINITIONS_H#define _DEFINITIONS_H 1内容#endif // _DEFINITIONS_H//（考虑到平台移植性，未采用#pragma once宏） - 多项式的一次性输入。采用了char类型的buf数组缓存输入，然后以运算符为分隔符逐项构建多项式。缺陷是必须依照范例输入，否则录入数据不可靠。
- 输出函数的模块化封装。一个单一函数无法满足全部需求。为了满足函数的模块化需求，采用了可变参数列表的方式设计了可分运行模式的输出函数。
五、人员分工说明（By LLonely）
本小组仍然采用Git进行版本库控制。
链表操作以及多项式运算相关函数由MagicPants开发，作为核心模块（core.c）。
输入输出函数及主程序框架文件由LLonely开发，作为IO模块（io.c）和主程序模块（main.c）。
六、程序源码
definitions.h
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/* Filename: definitions.h * ############################################ * Version: alpha | v20150501 */ #ifndef _DEFINITIONS_H #define _DEFINITIONS_H 1 struct function{ int cons; int power; struct function *next; }; typedef struct function polynomial; #define SUM_MODE 1 #define PRODUCTION_MODE 2 #define PRINT_ONLY 3 #ifndef _FUNCTIONS_H #include "functions.h" #endif #endif // _DEFINITIONS_H |
functions.h
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
/* Filename: functions.h * ############################################ * Version: alpha | v20150501 */ #ifndef _FUNCTIONS_H #define _FUNCTIONS_H 1 #include<stdarg.h> // Core-Functions polynomial *copy(polynomial *list1); polynomial *multi(polynomial *list1,polynomial *pa); polynomial *sum(polynomial *result,polynomial *part); polynomial *sort(polynomial *list); //IO-Functions polynomial *input(void); void print_poly(polynomial *list); void output(int mode,...); #endif // _FUNCTIONS_H |
main.c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
/* Filename: main.c * ############################################ * Author: LLonely * ID: Deleted * Email: i#llonely.com * Website: llonely.com * -------------------------------------------- * Version: alpha | v20150501 */ #include "definitions.h" #include "core.c" #include "io.c" #include<stdio.h> #include<windows.h> int main() { HANDLE hConsoleOut; polynomial *list1=NULL,*list2=NULL,*result=NULL,*temp,*part; hConsoleOut=GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hConsoleOut,FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE|FOREGROUND_INTENSITY); printf("╔══════════════════════════╗\n" "║%-52s║\n" "╠══════════════════════════╣\n" "║%-52s║\n" "╟──────────────────────────╢\n" "║%-52s║\n" "╠══════════════════════════╣\n" "║%-52s║\n" "╚══════════════════════════╝\n", "多项式乘法运算器", "开发者: MagicPants 内容: core.c", "开发者: LLonely 内容: main.c io.c", "版本: v20150501"); printf("输入格式范例: 3x^5+9x^3-2x^-1+0x^5-9x^0\n\n请输入第一个多项式: "); list1=input(); sort(list1); printf("\n请输入第二个多项式: "); list2=input(); sort(list2); printf("\n运算结果: \n"); if(list1==NULL||list2==NULL) printf("0\n"); else { for(part=list2;part!=NULL;part=part->next) { temp=multi(list1,part); result=sum(result,temp); } sort(result); output(PRODUCTION_MODE,list1,list2,result); } system("pause"); return 0; } |
io.c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 |
/* Filename: io.c * ############################################ * Author: LLonely * ID: Deleted * Email: i#llonely.com * Website: llonely.com * -------------------------------------------- * Version: beta | v20150502 */ #include "definitions.h" #include<stdio.h> #include<stdlib.h> polynomial *input(void) { char buf[BUFSIZ+1],*p_buf,*p_buf_temp,c_temp; polynomial *temp=NULL,*head=NULL; int coefficient,exponent; gets(buf); p_buf=buf; while(*p_buf) { if(*p_buf=='X') *p_buf='x'; p_buf++; } p_buf=buf; while(*p_buf!='\0') { p_buf_temp=p_buf+1; while(*p_buf_temp!='+'&&*p_buf_temp!='-'&&*p_buf_temp!='\0'||(*p_buf_temp=='-'&&*(p_buf_temp-1)=='^')) p_buf_temp++; c_temp=*p_buf_temp; *p_buf_temp='\0'; sscanf(p_buf,"%dx^%d",&coefficient,&exponent); temp=(polynomial *)malloc(sizeof(polynomial)); temp->cons=coefficient; temp->power=exponent; temp->next=NULL; if(head==NULL) { head=temp; } else { head=sum(head,temp); } p_buf=p_buf_temp; *p_buf=c_temp; } return head; } void output(int mode,...) { va_list argp; polynomial *list_1,*list_2,*result; va_start(argp,mode); switch(mode) { case PRINT_ONLY: result=va_arg(argp,polynomial *); print_poly(result); printf("\n"); break; case SUM_MODE: list_1=va_arg(argp,polynomial *); list_2=va_arg(argp,polynomial *); result=va_arg(argp,polynomial *); printf(" ("); print_poly(list_1); printf(") + ("); print_poly(list_2); printf(") = "); print_poly(result); printf("\n"); break; case PRODUCTION_MODE: list_1=va_arg(argp,polynomial *); list_2=va_arg(argp,polynomial *); result=va_arg(argp,polynomial *); printf(" ("); print_poly(list_1); printf(") * ("); print_poly(list_2); printf(") = "); print_poly(result); printf("\n"); break; } va_end(argp); return ; } void print_poly(polynomial *list) { if(list==NULL) printf("0"); else if(list->cons==0) { if(list->next==NULL) printf("0"); else { list=list->next; if(list->cons==1||list->cons==-1) { if(list->power==0) { printf("%d",list->cons>0?list->cons:-list->cons); } else if(list->power==1) { printf("x",list->cons>0?list->cons:-list->cons); } else { printf("x^%d",list->power); } } else { if(list->power==0) { printf("%d",list->cons>0?list->cons:-list->cons); } else if(list->power==1) { printf("%dx",list->cons>0?list->cons:-list->cons); } else { printf("%dx^%d",list->cons>0?list->cons:-list->cons,list->power); } } } } else { if(list->cons==1||list->cons==-1) { if(list->power==0) { printf("%d",list->cons>0?list->cons:-list->cons); } else if(list->power==1) { printf("x",list->cons>0?list->cons:-list->cons); } else { printf("x^%d",list->power); } } else { if(list->power==0) { printf("%d",list->cons>0?list->cons:-list->cons); } else if(list->power==1) { printf("%dx",list->cons>0?list->cons:-list->cons); } else { printf("%dx^%d",list->cons>0?list->cons:-list->cons,list->power); } } } list=list->next; while(list!=NULL) { if(list->cons==0) { list=list->next; continue; } if(list->cons==1||list->cons==-1) { if(list->power==0) { printf(" %c %d",list->cons>0?'+':'-',list->cons>0?list->cons:-list->cons); } else if(list->power==1) { printf(" %c x",list->cons>0?'+':'-'); } else { printf(" %c x^%d",list->cons>0?'+':'-',list->power); } } else { if(list->power==0) { printf(" %c %d",list->cons>0?'+':'-',list->cons>0?list->cons:-list->cons); } else if(list->power==1) { printf(" %c %dx",list->cons>0?'+':'-',list->cons>0?list->cons:-list->cons); } else { printf(" %c %dx^%d",list->cons>0?'+':'-',list->cons>0?list->cons:-list->cons,list->power); } } list=list->next; } return ; } |
core.c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
/* Filename: core.c * ############################################ * Author: MagicPants * ID: Deleted * Email: Deleted * -------------------------------------------- * Version: alpha | v20150422 */ #include "definitions.h" #include<stdio.h> #include<stdlib.h> static int size = sizeof(struct function); static struct function *Input(); static void Print(struct function *list); struct function *Input() { struct function *head,*tail,*p; int cons,power; head = tail =NULL; printf("Input!\n"); scanf("%d%d",&cons,&power); while(cons!=0){ p=(struct function*)malloc(size); p->cons = cons; p->power = power; p->next = NULL; if(head==NULL) head=tail=p; else{ head=sum(head,p); } scanf("%d%d",&cons,&power); } return head; } struct function *copy(struct function *list1) { struct function *p,*q,*head,*tail; for(head=tail=NULL,p=list1;p!=NULL;p=p->next ){ q=(struct function*)malloc(size); q->cons =p->cons ; q->power =p->power ; q->next =NULL; if(head==NULL) head=tail=q; else{ tail->next = q; tail = q; } } return head; } struct function *multi(struct function *list1,struct function *pa) { struct function *q,*head; head = copy(list1); for(q=head;q!=NULL;q=q->next ){ q->cons *= pa->cons ; q->power += pa->power ; } return head; } void Print(struct function *list) { struct function *p; if(list == NULL) printf(" 0\n"); else{ for(p=list;p->next !=NULL;p=p->next ) printf(" %d*x^%d +",p->cons ,p->power ); printf(" %d*x^%d\n",p->cons ,p->power ); } printf("result = list1 * list2\n"); return; } struct function *sum(struct function*result,struct function *list) { struct function *p1,*p2,*q,*mark,*temp; if(result==NULL) return list; else if(list==NULL) return result; for(q=list;q!=NULL;q=mark){ mark = q->next ; if(q->power > result->power ){ q->next = result; result = q; } else if(q->power == result->power){ result->cons += q->cons ; if(result->cons == 0){ temp = result->next ; free(result); result = temp; } free(q); } else{ p1=result,p2=result->next ; while((p2!=NULL)&&(q->power < p2->power )){ p1 = p2; p2 = p2->next ; } if(p2 == NULL){ p1->next = q; q->next = NULL; } else if(q->power > p2->power){ q->next = p2; p1->next =q; } else if(q->power == p2->power ){ p2->cons += q->cons ; if(p2->cons == 0){ p1->next = p2->next ; free(p2); } free(q); } } } return result; } struct function *sort(struct function*list) { struct function *p1,*p2,*p; int i,flag,cons,power; for(p=list,flag=0;p!=NULL;p=p->next,flag++); for(i=0;i<flag-1;i++){ for(p1=list,p2=list->next;p2!=NULL;p1=p2,p2=p2->next ){ if(p1->power < p2->power){ cons=p1->cons ; power=p1->power ; p1->cons=p2->cons ; p1->power =p2->power ; p2->cons =cons; p2->power =power; } } } return list; } |