一元稀疏多项式计算器-数据结构课程设计.docx-资料库

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第1页.png

第1页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第2页.png

第2页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第3页.png

第3页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第4页.png

第4页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第5页.png

第5页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第6页.png

第6页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第7页.png

第7页 / 共17页

ab4fa874-54a9-44ad-9e76-3c295625706d.docx.pdf-第8页.png

第8页 / 共17页

1.5 一元稀疏多项式计算器实习报告一、需求分析 1．输入并建立多项式； 2．输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，……，cn，en，其中 n 是多项式的项数，ci 和 ei 分别是第 i项的系数和指数，序列按指数降序排列； 3．多项式 a 和 b 相加，建立多项式 a＋b； 4．多项式 a 和 b 相减，建立多项式 a—b； 5．多项式 a 和 b 相乘，建立多项式 a×b； 6．计算多项式在 x 处的值； 7．求多项式 P 的导函数 P'； 8.多项式的输出形式为类数学表达式； 9.做出计算器的仿真界面； 10. 测试数据：（1） (2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7) （2） (6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15 ) =(-7.8x^15-1.2x^9+12x^-3-x); （3）(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5); （4）(x+x^3)+(-x-x^3)=0 （5）(x+x^100)+(x^100+x^200)=(x+2x^100+x^200) （6）(x+x^2+x^3)+0=x+x^2+x^3 （7）互换上述测试数据中的前后两个多项式二、概要设计 1. 链表的抽象数据类型定义为： n≥0 } ADT LinkList{ 数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, 数据关系：R1＝{ |ai-1, ai∈D, i=2,...,n } 基本操作： InitList(&L) 操作结果：构造一个空的线性表 L。 DestroyList(&L) 初始条件：线性表 L 已存在。操作结果：销毁线性表 L。 ClearList(*L) 初始条件：线性表 L 已存在。操作结果：将线性表 L 重置为空表。 LocateElem(L, e, cmp()) 初始条件：线性表 L 已存在，compare()是元素判定函数。操作结果：返回 L 中第 1 个与 e 满足关系 cmp()的元素的位序。若这样的元素不存在，则返回值为 0。 SetCurElem(&p, e)

初始条件：线性表 L 已存在，且非空。操作结果：用元数 e 更新 p 所指结点中元数的值。 GetCurElem(p) 初始条件：线性表 L 已存在，且非空。操作结果：返回 p 所指结点中数据元数的值。 InsFirst (&L, h, s) 初始条件：线性表 L 已存在，h 结点在 L 中。操作结果：在 L 的 s 所指结点插入在 h 结点之后， L 的长度加 1 。 DelFirst (&L, h, q) 初始条件：线性表 L 已存在且非空，q 结点在 L 中且不是尾结点操作结果：删除链表 L 中的 h 结点之后的结点 q，L 的长度减 1。 MakeNode(&p, e) 操作结果：创建了一个结点 p，其 data 部分为 e。 FreeNode(&p) 初始条件：结点 p 存在且非空。操作结果：释放结点 p 空间。 Append(LinkList &L,Link s) 初始条件：线性表 L 已存在。操作结果：s 及 s 以后的结点链接到了原 L 之后，L 的长度增加链上的结点数。 ListEmpty(L) 初始条件：线性表 L 已存在。操作结果：若线性链表 L 为空表，则返回 TRUE,否则返回 FALSE。 GetHead(L) 初始条件：线性表 L 已存在。操作结果：返回线性链表 L 中头结点的位置。 NextPos(L, p) 初始条件：线性表 L 已存在。操作结果：返回 p 所指结点的直接后继的位置，若没后继，则返回 NULL。 int cmp(a, b) 初始条件：存在两个元数。操作结果：比较 a，b 的数值，分别返回-1，0，1。 } ADT LinkList 2.一元多项式的抽象数据类型定义为： m≥0 ADT Polynomial{ 数据对象：D＝{ ai | ai∈TermSet, i=1,2,...,m, TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1＝{ |ai-1, ai∈D, 且 ai-1 中的指数值

AddPolyn（&Pa，&Pb）初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式 Pb。 SubtractPolyn(&Pa,&Pb) 初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式 Pb。 MultiplyPolyn(&Pa,&Pb) 初始条件：一元多项式 Pa 和 Pb 已存在。操作结果：完成多项式相乘运算，即： Pa=Pa × Pb ，并销毁一元多项式 Pb 。 DerivPolyn(&Pa) 初始条件：一元多项式 Pa 已存在。操作结果：多项式求导。 CalPolyn(Pa , x) 初始条件：一元多项式 Pa 已存在。操作结果：求多项式在 x 处的值。 PrintPolyn(p, m) 初始条件：一元多项式 p 已存在，且已知多项式项数。操作结果：打印输出一元多项式 p 的项数、系数和指数。 Expression(p, m) 初始条件：一元多项式 p 已存在，且已知多项式项数。操作结果：打印输出一元多项式的类数学表达式。 SortPolyn(&p) 初始条件：一元多项式 p 已存在。操作结果：对多项式 p 进行排序 }ADT Polynomial 3.本程序包含 4 个模块： (1)主程序模块： int main(){ 初始化；接受命令； while（命令！=推出）{ 处理命令；接受命令； } return 0; } (2)一元多项式单元模块——实现一元多项式的抽象数据类型；（3）链表单元模块——实现链表的抽象数据类型； (4)结点结构单元模块——定义链表的节点结构。各模块之间的调用关系如下：主程序模块结点结构单元模块一元多项式单元模块三、详细设计链表单元模块

1.设计好的数据类型： typedef struct{ //项的表示，多项式的项作为 Linklist 的数据元素 float coef; int expn; //系数 //指数 } term, ElemType;//两个类名：term 用于本 ADT，ElemType 为 Linklist 的数据对象名 typedef struct LNode {//结点类型 ElemType data; struct LNode *next; } *Link, *Position; typedef struct{//链表类型 Link head,tail; int len; //分别指向线性链表中的头结点和最后一个结点 //指示线性链表中数据个数 } LinkList; typedef LinkList polynomial;//基于带头结点的线性链表定义的多项式数据类型 2.基于链表、结点的操作(部分伪码如下) // 分配由 p 指向值为 e 的结点,并返回 OK,若分配失败,则返回 ERROR。 Status MakeNode(Link &p, ElemType e); //释放 p 所指结点 void FreeNode(Link &p); //构造一个空的线性链表 L Status InitList(LinkList &L); { L.head=L.tail=(Link)malloc(sizeof(LNode)); L.len=0; L.head->next=L.tail->next=NULL; return OK; } // 返回线性表 L 中头结点的位置。 Position GetHead(LinkList &L); //已知 p 指向线性链表 L 中的一个结点，返回 p 所指结点的直接后驱的位置 //若无后继，返回 NULL Position Nextpos(LinkList &L,Link p); //已知 p 指向线性表 L 中的一个结点,返回 p 所指结点中数据元素的值。 ElemType GetCurElem(Link p);

//已知 p 指向线性链表 L 中的一个结点,用 e 更新 p 所指结点中数据元素的值。 Status SetCurElem(Link &p,float e); //已知 h 指向线性链表的某个结点,将 q 所指的结点插入在 h 之后。 Status InsFirst(Link h,Link q); { s->next=h->next; h->next=s; L.len++; if(!s->next) L.tail=s; return OK; } //已知 h 指向线性链表的头结点,删除线性链表第一个指结点并以 q 返回 Status DelFirst(Link h,Link &q); //若线性链表 L 为空,则返回 TRUE,否则返回 FALSE。 Status ListEmpty(LinkList L); { if(L.head==L.tail==NULL) return TRUE; else return FALSE; } //将指针 s 所指的一连串结点连接在线性表 L 的最后一个结点之后,并改变链表 L 的尾指针指向新的尾结点。 Status Append(polynomial &L,Link s); { i=0; q=s; while(s) {//找到新的 tail，计数 s 长度 p=s; s=s->next; i++; } L.tail->next=q; L.tail=p; L.len+=i; return OK; } //判断已知链表中，是否存在相同的元素 e，若存在返回 TURE，且 q 指示 L 中第一个与 e 相同的结点元素；

//否则返回 FALSE,并 q 指示 L 中第一个稍大于 e 的元素的直接前驱的位置 Status LocateElem(LinkList L,ElemType e,Position &q); { p=L.head; while(p->next) { s=p; p=p->next; m=p->data; if(cmp(e,m )==0) { q=p; return TRUE; } } q=p; return FALSE; } //整表删除 void ClearList(LinkList &L); { if(L.head!=L.tail) { p=q=L.head->next; L.head->next=NULL; while(p!=L.tail) { p=q->next; free(q); q=p; } free(q); L.tail=L.head; L.len=0; } return OK; } //依 a 的指数值<（或=）(或>）b 的指数数值，分别返回-1，0，+1 int cmp(term a, term b) ; { if(a.expnb.expn)

return 1; } 3.基于多项式的操作（部分伪码如下） //输入 m 项的系数和指数，建立表示一元多项式的有序链表 P void CreatPolyn(polynomial &p,int m); { InitList(p); h=GetHead(p); e.coef=0.0; e.expn=-1; SetCurElem(h,e); for(int i=1;i<=m;i++){ cout<<"请输入第"<>e.coef>>e.expn; cout<data.coef+=e.coef; ++c; } } m=m-c; } //销毁一元多项式 P void DestroyPolyn(polynomial &p); { while(p.head ->next!=NULL) { k=p.head; p.head =p.head ->next; free(k); } free(&p); } //打印输出一元多项式 P void PrintPolyn(polynomial p); { ha=GetHead(p); cout<

cout<

资料库

一元稀疏多项式计算器-数据结构课程设计.docx

相关推荐

课程资源

热门标签

最新资料