数据结构课程设计模板结构设计.doc

数据结构课程设计模板结构设计 课程设计概述 共完成4个题目： 1.一元稀疏多项式计算器 2.成绩分析问题 3.背包问题 4.八皇后问题 编程语言：VC6.0 运行环境：Windows8.0 二．一元稀疏多项式计算器 问题描述： 1.1 输入并建立多项式； 1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 1.3多项式a和b相加，建立多项式a+b； 1.4多项式a和b相减，建立多项式a-b。 1.5多项式a和b相乘，建立乘积多项式ab。 需求分析： 2.1 定义线性表的动态分配顺序存储结构； 2.2 建立多项式存储结构，定义指针*next 2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式 2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为：c1x^e1+c2x^e2+…+cnx^en 设计思路： 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为 序数coef 指数exp指针域next 运用尾插法建立两条单链表，以单链表和poly分别表示两个一元多项式和，的求和运算等同于单链表的插入问题（将单链表poly中的结点插入到单链表poly中），因此“和多项式”中的结点无须另生成。 为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则： ① 若p-expq-expn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。 ② 若p-exp=q-expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。 ③ 若p-expq-expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7); （2）、(2x+5x^8-3.1x^11)-(7-5x^8+11x^9)=-3.1x^11-11x^9+10x^8+12x-7; (3)(2x+5x^8-3.1x^11)*(7-5x^8+11x^9)=34.1x^20+15.5x^19+55x^17-25x^16-21.7x^11+22x^10-10x^9+35x^8+14x 概要设计 1.元素类型、结点类型和指针类型： typedef struct Polynomial{ float coef; //系数 int expn; //指数 struct Polynomial *next; }*Polyn,Polynomial; 2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点: Polyn CreatePolyn(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head-next=NULL; for(i=0;im;i++) { p=(Polyn)malloc(sizeof(struct Polynomial)); printf(请输入第%d项的系数与指数:,i+1); scanf(%f %d,p-coef,p-expn); Insert(p,head); } return head; } 3、主函数和其他函数： void main() { int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; } 数据结构： 带头结点单链表抽象数据类型的结点结构定义如下： typedef struct Polynode //多项式结点 { int coef; //系数 int exp;