课程设计说明书设计题目： 数据结构课程设计 专 业： 班级： 设 计 人： 课 程 设 计 任 务 书一、 课程设计题目：设计一个一元稀疏多项式计算器 二、 设计原始资料：《数据结构C语言版》教材及习题集 三、 设计应解决下列各主要问题： 1、输入并建立一元稀疏多项式 2、输出多项式，输出形式为整数序列n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列； 3、多项式a和b相加，建立多项式a+b； 4、多项式a和b相减，建立多项式a-b。
四、 设计说明书应附有下列图纸： 五、命题发出日期： 设计应完成日期： 设计指导教师（签章）： 系主任（签章）： 指导教师对课程的评语 指导教师（签章）： 年 月 日一、 需求分析1. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。
2. 程序执行的命令包括：1) 创建一元多项式1；2) 创建一元多项式2；3) 输出一元多项式4) 计算多项式1和多项式2的和；5) 计算多项式1和多项式2的差注意：输出形式为整数序列n,c1,e1,c2,e2,…,cn,en，其中n是多项式的项数，ci和ei分别是第I项的系数和指数，序列指指数降序排列 3.测试数据1) ；2) ；3)4)二、 概要设计为实现上述程序功能，应以带头结点的单链表存储多项式1. 多项式的抽象数据类型为：ADT Polynmial{ 数据对象：D={ai|ai∈TermSet，i=1,2,3，…，m，TermSet中的每一个元素包含一个表示系数的实数和表示指数的整数}数据关系：R1={ai-1，ai∈D，且ai-1中的指数next=NULL; for(i=0; icoef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;}void DestroyPolyn(Polyn p){//销毁多项式p q1=p->next; q2=q1->next; while(q1->next) { free(q1); q1=q2; q2=q2->next; }}void Insert(Polyn p,Polyn h){ if(p->coef==0) free(p);//系数为0的话释放结点 else { q1=h; q2=h->next; while(q2&&p->expnexpn) { //查找插入位置 q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn) { //将指数相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef) { //系数为0的话释放结点 q1->next=q2->next; free(q2); } } else { //指数为新时将结点插入 p->next=q2; q1->next=p; } }}void PrintPolyn(Polyn P){ Polyn q=P->next; int flag=0;//项数计数器 while(q) { flag++; q=q->next; } q=P->next; if(!q) { //若多项式为空，输出0 putchar('0'); printf("\n"); return; } printf("%d ",flag); while(q) { if(q->coef!=1&&q->coef!=-1) { printf("%g %d ",q->coef,q->expn); } else { if(q->coef==1) { printf("%g %d ",q->coef,q->expn); } if(q->coef==-1) { printf("%g %d ",q->coef,q->expn); } } q=q->next; } printf("\n");}int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn) return 1; else if(!a||a->expnexpn) return -1; else return 0; } else if(!a&&b) return -1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空}Polyn AddPolyn(Polyn pa,Polyn pb) //求解并建立多项式a+b，返回其头指针{ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb) { qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;}Polyn SubtractPolyn(Polyn pa,Polyn pb) //求解并建立多项式a-b，返回其头指针{ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) { //将pb的系数取反 p->coef*=-1; p=p->next; } pd=AddPolyn(pa,h); for(p=h->next; p; p=p->next) //恢复pb的系数 p->coef*=-1; return pd;}3.主函数及其他函数的伪代码算法Int main(){ CreatPolyn(a); CreatPolyn(b); 交互界面菜单； Switch（choose）{ Case a： printf(a); Case b: printf(b); Case c: printf(a+b); Case d: printf(a-b); Case e: exit;}}四、 测试结果1.人机交互界面 2.测试结果显示 五、 总结反思经过这段为期不久的课程设计，使我对于数据结构有了更深层次的理解,对于链表这种数据结构的认识也更加深刻了。
在这个过程中我曾因为实践经验缺乏，错误过多失落过；也曾经仿真成功而热情高涨我也感觉用心细心地做好一件事情的重要性，在这次课程设计中，体会到了做设计的严谨，更加加深了我对课程设计的兴趣在此次课程设计过程中，遇到不懂的问题我会及时向老师，同学请教或者是在网上查询相关的资料，以更好地完成该项课题设计在实践结束后，深深地体会到实践对于工科专业的重要性在学习数据结构的过程中总是觉得有些东西模棱两可，感觉到不能深一步的理解，也因为代码的冗长而缺乏耐心去完成每一个通过这次课程设计，原本关于链表的模棱两可的东西逐渐变得清晰起来，以后一定加强动手实践的能力，多动手，多思考！。