数据库相关有用信息.doc

青 岛 理 工 大 学课程实验报告课程名称数据结构班级软件112实验日期2013年4月15号姓名何金荣学号201107225实验成绩实验名称线性表的应用-一元多项式的计算实验目的及要求（1） 通过一元稀疏多项式的表示和计算，熟练掌握线性表的基本操作，以及用线性链表表示线性表的存储结构操作的实现。（2） 使学生掌握链表的最基本和最主要的操作：插入和删除操作。（3） 熟悉C+的基本编程方法，掌握集成编译环境的调试方法。（4） 学习指针，异常处理的使用。（5） 学习使用线性表解决实际问题的能力。实验环境硬件平台：普通个人PC机软件平台：Windows7 旗舰版 操作系统 编程环境：VisualC+6.0编程软件实验内容利用线性表实现一个一元多项式PolynonmialF(X)=a0+a1*x+a2*x+a3*x+.+an*xn实现一元稀疏多项式的如下运算：(1)由函数CreatPolyn()建立一元多项式有序表(2) 由AddPolyn()函数，执行两个一元稀疏多项式相加运算(3) 由SubtractPolyn()函数，执行两个一元稀疏多项式相减运算(4) 由MultiplyPolyn（）函数，执行两个一元稀疏多项式相乘运算(5) 通过PrintPolyn()函数，打印输出一元多项式算法描述及实验步骤 实验步骤：(1) 首先定义一个数据结构体，建立单链表(2) 输入m项的系数和指数，建立表示一元多项式的有序链表P(3) 输入第一个一元多项式p(4) 输入第二个一元多项式q(5) 打印输出两个多项式的和P(6) 输入第三个一元多项式h(7) 打印输出两个多项式的差P(8) 输入第四个一元多项式j(9) 打印输出两个多项式的乘积p(10) 销毁链表，将链表置为空表算法思想：测试主函数流程： 开始 设置第三个多项式的项数p和每项系数及指数输出第三个多项式q由AddPolyn()函数进行两多项式相加得P输出相加的多项式结果p 结束 图2-两多项式相加 开始 设置第三个多项式的项数p和每项系数及指数输出第三个多项式q由SubtractPolyn函数进行两多项式相减得P输出相减的多项式结果p 结束 图2-两多项式相减开始 输出第四个多项式的项数及每项的系数和指数输出第四个一元多项式K由MultiplyPolyn函数进行两多项式的乘积算法得P输出计算后的多项式结果P结束 图3-两多项式相乘 算法描述： /*/* 定义数据结构 */*/ typedef struct /* 项的表示，多项式的项作为LinkList的数据元素 */ float coef; /* 系数 */ int expn; /* 指数 */ term,ElemType; /* 两个类型名：term用于本ADT，ElemType为LinkList的数据对象名 */ /*/* 建立一元多项式有序表 */*/ void CreatPolyn(polynomial *P,int m) /* 建立链表 */ /* 输入m项的系数和指数，建立表示一元多项式的有序链表P */ Position q,s; term e; int i; InitList(P); printf(请依次输入%d个系数，指数：n,m); for(i=1;inext; /* q指向第1个结点 */ printf( 系数 指数n); while(q) printf(%f %dn,q-data.coef,q-data.expn); q=q-next; /*/ * 一元多项式相加 */*/ void AddPolyn(polynomial *Pa,polynomial *Pb) /* 多项式相加 */ /* 多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb */ Position ha,hb,qa,qb; term a,b; ha=GetHead(*Pa); hb=GetHead(*Pb); /* ha和hb分别指向Pa和Pb的头结点 */ qa=NextPos(ha); qb=NextPos(hb); /* qa和qb分别指向Pa和Pb中当前结点(现为第1个结点) */ while(!ListEmpty(*Pa)&!ListEmpty(*Pb)&qa) /* Pa和Pb均非空且ha没指向尾结点(qa!=0) */ a=GetCurElem(qa); b=GetCurElem(qb); /* a和b为两表中当前比较元素 */ switch(cmp(a,b) case -1:ha=qa; /* 多项式Pa中当前结点的指数值小 */ qa=NextPos(ha); /* ha和qa均向后移1个结点 */ break; case 0: qa-data.coef+=qb-data.coef; /* 两者的指数值相等，修改Pa当前结点的系数值 */ if(qa-data.coef=0) /* 删除多项式Pa中当前结点 */ DelFirst(Pa,ha,&qa); FreeNode(&qa); else ha=qa; DelFirst(Pb,hb,&qb); FreeNode(&qb); qb=NextPos(hb); qa=NextPos(ha); break; case 1: DelFirst(Pb,hb,&qb); /* 多项式Pb中当前结点的指数值小 */ InsFirst(Pa,ha,qb); ha=ha-next; qb=NextPos(hb); if(!ListEmpty(*Pb) (*Pb).tail=hb; Append(Pa,qb); /* 链接Pb中剩余结点 */ DestroyPolyn(Pb); /* 销毁Pb */ /*/* 多项式相减 */*/ void SubtractPolyn(polynomial *Pa,polynomial *Pb) /* 多项式减法：Pa=Pa-Pb，并销毁一元多项式Pb */ Opposite(*Pb); /* 一元多项式Pa系数取反 */ AddPolyn(Pa,Pb); /*一元多项式相加*/ 两个多项式的减法实现：并没有单独的建立一个子函数来实现这个功能,和多项式的相加一样,依然调用的是多项式加法的函数,只是在调用前,把多项式二的系数全部变为相反数c.coef=-c.coef;然后多项式一和多项式二相加,这样就实现了多项式的相减,开始我建立一个实现多项式减法的子函数,最后为了程序的简洁最后还是改成了调用多项式相加函数 ./*/* 一元多项式相乘 */*/ void MultiplyPolyn(polynomial *Pa,polynomial *Pb) /* 多项式乘法：Pa=PaPb，并销毁一元多项式Pb */ polynomial Pc; Position qa,qb; term a,b,c; InitList(&Pc); qa=GetHead(*Pa); qa=qa-next; while(qa) a=GetCurElem(qa); qb=GetHead(*Pb); qb=qb-next; while(qb) b=GetCurElem(qb); c.coef=a.coef*b.coef; c.expn=a.expn+b.expn; OrderInsertMerge(&Pc,c,cmp); qb=qb-next; qa=qa-next; DestroyPolyn(Pb); /* 销毁Pb */ ClearList(Pa); /* 将Pa重置为空表 */ (*Pa).head=Pc.head; (*Pa).tail=Pc.tail; (*Pa).len=Pc.len; 调试过程及实验结果1 刚开始的时候，我先创建链表，在运行时程序报“错误mimi.c17:未定义的符号null在initlink函数中”和“警告mimi.c17:不可移动的指针（地址常数）赋值在initlink函数中”，在我查阅C语言的课本说NULL实际是由stdio.h头文件中的一条宏定义命令定义的。但是在我的程序中却报错，最后我记得C语言是识别大小写的，如果将null改为NULL程序就不会报错的。2 其实该实验的重心是实现两个一元多项式的相加，相减，相乘，在我首次编好程序后，运行发现结果中的相加结果只进行了一次的相加，后面的几个项是原La的项，最后我只能再重新编写该函数。3 在函数addPolyn中我发现好多语句是相似的，想用一个函数来实现这样的功能，可惜没有想到好的函数。.算法的时空分析各操作的算法时间复杂度比较合理 cmpexpn为O(1outputPolyn, SubtractPolyn，MultPolyn为O(n),addPolyn为0（n1+n2）注：n为链表的长度，n1为一元多项式A的长度，n2为一元多项式B的长度。4 调试中遇到的问题与解决办法 （1）、语法错误及修改编译中出现的语法问题主要在于子函数和变量的定义，括号的配对，关键字和函数名的书写，以及库函数的规范使用，这些问题都可以通过提示对应的将其解决.5 我通过调试运行后发现:计算完成打印结果后马上就会退出。程序在运行起来以后没有一个可以让程序暂时停止的地方,比如要求用户输入,或者什么的,程序顺序执行之后就退出了。 6.运行之后，结果如下：(1) 输入多项式的非零项的个数，进入下一步指令，输入系数和指数。(2) 打印出一元多项式相加后的结果：(3) 再输入一个多项式，与上一个多项式进行相减。(4) 打印输出相减后的结果。(5) 再输入一个多项式，与上一个多项式进行相乘。(6) 打印输出相乘后的结果。按任意键退出。(7) 举出多项式相加后的界面：(8) 算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，乘法的时间复杂度为O(m*n),其中m，n分别表示二个一元多项式的项数。 总结 总结一元多项式的表示与其运算设计，运行结果能表达多项式，包括其系数及指数，也实现了多项式的相加、相减以及相乘，运行结果符合一元多项式的在实际运用中的运算法则。使用该程序能快捷方便计算出多个复杂的一元多项式的计算，体现了本设计的可行性以及实用性。1.调试时出现的问题及解决的方法 输出多项式的时候有些问题，但经过查看是由于输出时没有将各种情况考虑全面的结果。 相加相减操作：在刚开始的时候，只考虑了p、q指针均非现一个还非空但另一个已经遍历完毕的情况，故后又设计让非空的链表继续进行运算，解决了问题。 在插入结点的时候出现了一些问题，开始时运动头插法，但发现只能按指数从大到小的顺序输入，后来添加了排序及合并同类项的算法，使得输入更为方便 开始算减法的时候只考虑将加法中的+改为-就可以，发现当B指数大于A时，指数高的项没有减去，后来将减法看成加一个负数得以解决。2.心得体会 通过本次实验，我熟悉了链表的相关操作，包括链表的建立、头插法、排序法；同时由于多项式的运算中会出现许多种不同的情况，在这方面也锻炼了我的思维严密性。在编写程序的过程中，编译的时候出现了一些错误，但都经过自己的钻研以及与同学探讨成功解决。3.下一步的改进本程序没有完成多项式的除法，求导等功能，以后会逐步完善。界面不够友好，加强人机交互应当设置一元多项式类，方便日后的使用4. 对于数据结构这门课程，我觉得老师讲的很仔细，而且很敬业，关心我们每一个学生，生怕讲快了，不断地问我们懂不懂，我觉得这一点现在很少有老师做到这一点了，不管是再讲算法，还是定义一些结构体，都讲得很到位，但是我觉得老师在一个程序的整体框架上有点讲快了，希望老师有时间的话，给我们在仔细讲讲，望老师不责学生的冒昧，纳吾贱言！ 附录 #include #include /* malloc()等 */ #include #include #include /* floor(),ceil(),abs() */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int Boolean; typedef struct LNode /* 结点类型 */ ElemType data; struct LNode *next; LNode,*Link,*Position; typedef struct LinkList /* 链表类型 */ Link head,tail; /* 分别指向线性链表中的头结点和最后一个结点 */ int len; /* 指示线性链表中数据元素的个数 */ LinkList; typedef struct /* 项的表示，多项式的项作为LinkList的数据元素 */ float coef; /* 系数 */ int expn; /* 指数 */ term,ElemType; /* 两个类型名：term用于本ADT，ElemType为LinkList的数据对象名 */ void MakeNode(Link *p,ElemType e) /* 分配由p指向的值为e的结点。若分配失败，则退出 */ *p=(Link)malloc(sizeof(LNode); if(!*p) exit(ERROR); (*p)-data=e; void FreeNode(Link *p) /* 释放p所指结点 */ free(*p); *p=NULL; void InitList(LinkList *L) /* 构造一个空的线性链表L */ Link p; p=(Link)malloc(sizeof(LNode); /* 生成头结点 */ if(p) p-next=NULL; (*L).head=(*L).tail=p; (*L).len=0; else exit(ERROR); void ClearList(LinkList *L) /* 将线性链表L重置为空表，并释放原链表的结点空间 */ Link p,q; 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; void DestroyList(LinkList *L) /* 销毁线性链表L，L不再存在 */ ClearList(L); /* 清空链表 */ FreeNode(&(*L).head); (*L).tail=NULL; (*L).len=0; void InsFirst(LinkList *L,Link h,Link s) /* 形参增加L,因为需修改L */ /* h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前 */ s-next=h-next; h-next=s; if(h=(*L).tail) /* h指向尾结点 */ (*L).tail=h-next; /* 修改尾指针 */ (*L).len+; Status DelFirst(LinkList *L,Link h,Link *q) /* 形参增加L,因为需修改L */ /* h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。 */ /* 若链表为空(h指向尾结点)，q=NULL，返回FALSE */ *q=h-next; if(*q) /* 链表非空 */ h-next=(*q)-next; if(!h-next) /* 删除尾结点 */ (*L).tail=h; /* 修改尾指针 */ (*L).len-; return OK; else return FALSE; /* 链表空 */ void Append(LinkList *L,Link s) /* 将指针s(s-data为第一个数据元素)所指(彼此以指针相链，以NULL结尾)的 */ /* 一串结点链接在线性链表L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点 */ int i=1; (*L).tail-next=s; while(s-next) s=s-next; i+; (*L).tail=s; (*L).len+=i; Position PriorPos(LinkList L,Link p) /* 已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置。若无前驱，则返回NULL */ Link q; q=L.head-next; if(q=p) /* 无前驱 */ return NULL; else while(q-next!=p) /* q不是p的直接前驱 */ q=q-next; return q; Status Remove(LinkList *L,Link *q) /* 删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点 */ Link p=(*L).head; if(*L).len=0) /* 空表 */ *q=NULL; return FALSE; while(p-next!=(*L).tail) p=p-next; *q=(*L).tail; p-next=NULL; (*L).tail=p; (*L).len-; return OK; void InsBefore(LinkList *L,Link *p,Link s) /* 已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前， */ /* 并修改指针p指向新插入的结点 */ Link q; q=PriorPos(*L,*p); /* q是p的前驱 */ if(!q) /* p无前驱 */ q=(*L).head; s-next=*p; q-next=s; *p=s; (*L).len+; void InsAfter(LinkList *L,Link *p,Link s) /* 已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后， */ /* 并修改指针p指向新插入的结点 */ if(*p=(*L).tail) /* 修改尾指针 */ (*L).tail=s; s-next=(*p)-next; (*p)-next=s; *p=s; (*L).len+; void SetCurElem(Link p,ElemType e) /* 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值 */ p-data=e; ElemType GetCurElem(Link p) /* 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 */ return p-data; Status ListEmpty(LinkList L) /* 若线性链表L为空表，则返回TRUE，否则返回FALSE */ if(L.len) return FALSE; else return TRUE; int ListLength(LinkList L) /* 返回线性链表L中元素个数 */ return L.len; Position GetHead(LinkList L) /* 返回线性链表L中头结点的位置 */ return L.head; Position GetLast(LinkList L) /* 返回线性链表L中最后一个结点的位置 */ return L.tail; Position NextPos(Link p) /* 已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置。若无后继，则返回NULL */ return p-next; Status LocatePos(LinkList L,int i,Link *p) /* 返回p指示线性链表L中第i个结点的位置，并返回OK，i值不合法时返回ERROR。i=0为头结点 */ int j; if(iL.len) return ERROR; else *p=L.head; for(j=1;jnext; return OK; Position LocateElem(LinkList L,ElemType e,Status (*compare)(ElemType,ElemType) /* 返回线性链表L中第1个与e满足函数compare()判定关系的元素的位置， */ /* 若不存在这样的元素，则返回NULL */ Link p=L.head; do p=p-next; while(p&!(compare(p-data,e); /* 没到表尾且没找到满足关系的元素 */ return p; void ListTraverse(LinkList L,void(*visit)(ElemType) /* 依次对L的每个数据元素调用函数visit() */ Link p=L.head-next; int j; for(j=1;jdata); p=p-next; printf(n); void OrderInsert(LinkList *L,ElemType e,int (*comp)(ElemType,ElemType) /* 已知L为有序线性链表，将元素e按非降序插入在L中。(用于一元多项式) */ Link o,p,q; q=(*L).head; p=q-next; while(p!=NULL&comp(p-data,e)next; o=(Link)malloc(sizeof(LNode); /* 生成结点 */ o-data=e; /* 赋值 */ q-next=o; /* 插入 */ o-next=p; (*L).len+; /* 表长加1 */ if(!p) /* 插在表尾 */ (*L).tail=o; /* 修改尾结点 */ Status LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType) /* 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中 */ /* 第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数 */ /* compare()取值0的元素的前驱的位置。并返回FALSE。(用于一元多项式) */ Link p=L.head,pp; do pp=p; p=p-next; while(p&(compare(p-data,e)data.expndata,e)0) /* 到表尾或compare(p-data,e)0 */ *q=pp; return FALSE; else /* 找到 */ *q=p; return TRUE; /* bo2-7.c 多项式 ) */ #includec2-5.h #includebo2-6.h typedef LinkList polynomial; #define DestroyPolyn DestroyList #define PolynLength ListLength void OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term) /* 按有序判定函数compare()的约定，将值为e的结点插入或合并到升序链表L的适当位置 */ Position q,s; if(LocateElemP(*L,e,&q,compare) /* L中存在该指数项 */ q-data.coef+=e.coef; /* 改变当前结点系数的值 */ if(!q-data.coef) /* 系数为0 */ /* 删除多项式L中当前结点 */ s=PriorPos(*L,q); /* s为当前结点的前驱 */ if(!s) /* q无前驱 */ s=(*L).head; DelFirst(L,s,&q); FreeNode(&q); else /* 生成该指数项并插入链表 */ MakeNode(&s,e); /* 生成结点 */ InsFirst(L,q,s); int cmp(term a,term b) /* CreatPolyn()的实参 */ /* 依a的指数值b的指数值，分别返回-1、0或+1 */ if(a.expn=b.expn) return 0; else return (a.expn-b.expn)/abs(a.expn-b.expn); void CreatPolyn(polynomial *P,int m) /* 建立链表 */ /* 输入m项的系数和指数，建立表示一元多项式的有序链表P */ Position q,s; term e; int i; InitList(P); printf(请依次输入%d个系数,指数： ,m); for(i=1;inext; /* q指向第1个结点 */ printf( 系数 指数n); while(q) printf(%f %dn,q-data.coef,q-data.expn); q=q-next; void AddPolyn(polynomial *Pa,polynomial *Pb) /* 多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb */ Position ha,hb,qa,qb; term a,b; ha=GetHead(*Pa); hb=GetHead(*Pb); /* ha和hb分别指向Pa和Pb的头结点 */ qa=NextPos(ha); qb=NextPos(hb); /* qa和qb分别指向Pa和Pb中当前结点(现为第1个结点) */ while(!ListEmpty(*Pa)&!ListEmpty(*Pb)&qa) /* Pa和Pb均非空且ha没指向尾结点(qa!=0) */ a=GetCurElem(qa); b=GetCurElem(qb); /* a和b为两表中当前比较元素 */ switch(cmp(a,b) case -1:ha=qa; /* 多项式Pa中当前结点的指数值小 */ qa=NextPos(ha); /* ha和qa均向后移1个结点 */ break; case 0: qa-data.coef+=qb-data.coef; /* 两者的指数值相等，修改Pa当前结点的系数值 */ if(qa-data.coef=0) /* 删除多项式Pa中当前结点 */ DelFirst(Pa,ha,&qa); FreeNode(&qa); else ha=qa; DelFirst(Pb,hb,&qb); FreeNode(&qb); qb=NextPos(hb); qa=NextPos(ha); break; case 1: DelFirst(Pb,hb,&qb); /* 多项式Pb中当前结点的指数值小 */ InsFirst(Pa,ha,qb); ha=ha-next; qb=NextPos(hb); if(!ListEmpty(*Pb) (*Pb).tail=hb; Append(Pa,qb); /* 链接Pb中剩余结点 */ DestroyPolyn(Pb); /* 销毁Pb */ void Opposite(polynomial Pa) /* 一元多项式Pa系数取反 */ Position p; p=Pa.head;