西安石油大学数据结构数据结构程序设计报告 设计一个一元稀疏多项式简单计算器和集合的并

1、 数据结构课程设计 题目一：设计一个一元稀疏多项式简单计算器 题目二：集合的并，交和差运算 班 级： 计1101 姓 名： 张文江 学 期：2012-2013 上机实验报告（一） 一、 题目：设计一元稀疏多项式简单计数器 二、问题描述： （1）定义两个单链表用于存储两个多项式，存储好在输出时按指数降序输出。 （2）按指数降序排列时要注意指数的比较以及指数相同与不同时的计算方法。 （3）设计出其运算的加、减函数。 （4）再设计一个释放空间的函数用于退出系统操作。 （5）设计一个测试主函数，实现对基于顺序队列结构的一元多项式算法的测试。 （6）为了界面显示友好期间可以设计一下输出后的界面格式。 三

2、、基本要求： （1）输入并建立多项式，输出多项式，序列按指数降序排列； （2）多项式a和b相加，建立多项式a+b，输出相加的多项式； （3）多项式a和b相减，建立多项式a-b，输出相减的多项式； （4）用带头结点的单链表存储多项式。 四、测试数据： （1）(2x+5x8-3.1x11)+(7-5x8+11x9) （2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) （3）(x+x2+x3)+0 （4）(x+x3)-(-x-x-3) 五、算法思想： 利用单链表来存储多项式，因此这里需要创建两个单链表分别用于存储多项式a和b，然后逐项在链表中按指数降序排列插入；

3、利用数学中的加法方法，比较两个多项式，利用指数进行比较，进行减法计算方法时利用加法的逆运算实现，最后将输入的多项式按不同的要求提示进行函数调用实现。 六、模块划分： 头文件为： # include # include /结点结构体 typedef struct PolyNode float coef; /系数域 int exp; /指数域 struct PolyNode *next; /指针域 *Poly,PolyNode; /1、按指数降序插入多项式 void Insert(Poly p,Poly h) /2、创建多项式(带有头结点且有m项) Poly Create(Poly head, i

4、nt m) /3、对两个多项式进行比较判别 /4、实现多项式相加 /5、实现多项式相减（思想：兩数相减=两个正数的相反数相减） /6、输出多项式 void Print(Poly P) /7、销毁多项式(使用完后用于退出，释放空间) 测试主int main() int m,n,flag=0; Poly pa=0,pb=0,pc,pd; /输出菜单 printf(*n); printf( 1.输入多项式 2.输出多项式a和b 3.建立多项式a+b 4.建立多项式a-b 5.退出程序 n); printf(*n); for(;flag=0) printf(执行操作为:) ; scanf(%d,&fl

5、ag); if(flag=1) /定义各式的头指针，pa与pb在使用前付初值NULL printf(请输入a的项数:) ; scanf(%d,&m); pa=CreateList(pa,m); /建立多项式a printf(请输入b的项数: ); scanf(%d,&n); pb=CreateList(pb,n); /建立多项式b if(flag=2) printf(多项式a为:); OutputList(pa); printf(多项式b为:); OutputList(pb); continue; if(flag=3) pc=AddPoly(pa,pb); printf(多项式a+b为：);

6、OutputList(pc); DestroyList(pc); continue; if(flag=4) pd=SubtractPoly(pa,pb); printf(多项式a-b为：); OutputList(pd); DestroyList(pd); continue; if(flag=5) break; if(flag5) printf(输入错误!请重新选择!n); continue; DestroyList(pa); DestroyList(pb); return 0; 函数： 七、源程序： int main() int m,n,flag=0; Poly pa=0,pb=0,pc,p

7、d; /输出菜单 printf(*n); printf( 1.输入多项式 2.输出多项式a和b 3.建立多项式a+b 4.建立多项式a-b 5.退出程序 n); printf(*n); for(;flag=0) printf(执行操作为:) ; scanf(%d,&flag); if(flag=1) /定义各式的头指针，pa与pb在使用前付初值NULL printf(请输入a的项数:) ; scanf(%d,&m); pa=CreateList(pa,m); /建立多项式a printf(请输入b的项数: ); scanf(%d,&n); pb=CreateList(pb,n); /建立多项式

8、b if(flag=2) printf(多项式a为:); OutputList(pa); printf(多项式b为:); OutputList(pb); continue; if(flag=3) pc=AddPoly(pa,pb); printf(多项式a+b为：); OutputList(pc); DestroyList(pc); continue; if(flag=4) pd=SubtractPoly(pa,pb); printf(多项式a-b为：); OutputList(pd); DestroyList(pd); continue; if(flag=5) break; if(flag5

9、) printf(输入错误!请重新选择!n); continue; DestroyList(pa); DestroyList(pb); return 0; 八、测试情况：（1） （2）测试结果分析： 程序设计结果和人工模拟分析过程完全相同，说明程序正确。 （3）思想感悟： 经过这次的课程设计，我学到了好多，也越发的感觉到自己不知道的东西很多，一开始，对多项式的创建一窍不通，感觉很难，无法入手，后来，经过上网查询，与队友的讨论，逐渐有了头绪，慢慢写出了程序，第一次运行时，错误很多，改了好多次，终于成功了，让我感觉到了团队的力量！ 上级实验报告（二） 一、题目：集合的并、交和差运算 二、问题描述：

10、 （1）创建单链表用于存储集合，存储好集合在输出时按字母排好顺序输出。 （2）设计出其运算的合并、求交、求差函数。 （3）再设计一个释放空间的函数用于退出系统操作。 （4）设计一个测试主函数，实现对基于顺序队列结构的集合运算的测试。 （5）为了界面显示友好期间可以设计一下输出后的界面格式。 三、基本功能 编制一个能演示执行集合的并、交和差运算的程序。 四、基本要求 (1) 集合的元素限定为小写字母字符a.z； (2) 演示程序以用户和计算机的对话方式执行。 五、测试数据 (1) Set1 = ”magazine”, Set2 = ”paper”, Set1Set2 = ”aegimnprz”,

11、 Set1Set2 = ”ae”, Set1-Set2 = ”gimnz”； (2) Set1 = ”012oper4a6tion89”, Set2 = ”error data”, Set1Set2 = ”adeinoprt”, Set1Set2 = ”aeort”, Set1-Set2 = ”inp”。 六、算法思想： 创建一个单链表用于存储一个集合，限定集合元素字母为“a”“z”，计算出集合的长度以用于对集合中的元素排序，排序时从第一个元素开始逐个向后比较。计算时，合并思想为：将两个集合进行比较，有相同元素时只输入一个，元素不同时均输入；求交思想：两个集合比较将相同的元素输出；求差思想：用

12、第一个集合中的元素和第二个集合比较，如果相同就删除，最后输出剩余的元素。利用销毁和清空方法释放占据的空间，最后在主函数中将集合按不同的要求提示进行函数调用实现。 七、模块划分： 头文件： #include #include #define ElemType char /宏定义一个字符型的元素类型，以下使用不用定义 /定义集合结构体 typedef struct ElemNode ElemType elem; /集合元素域 struct ElemNode *next; *Set,ElemNode; /1、计算一个集合的长度用于对集合排序 int Length(Set src) /2、创建一个从a

13、-z字母集合 void Create(Set dest) /3、清空一个集合 void Empty(Set dest) /4、销毁集合 void Destroy(Set dest) /5、对一个字母集合进行从小到大的排序 void Sort(Set dest) /6、打印集合的所有元素 void Display(Set src) /7、判断元素是否存在于集合中 int ExistElem(Set dest, ElemType e) /8、删除集合中的一个元素一次 void DelElem(Set dest, ElemType e) /9、在链表尾部追加一个元素 void AddElem(Set

14、 dest, ElemType e) /10、集合合并运算 void Add(Set dest, Set src1, Set src2) /11、集合求交集运算 void Mul(Set dest, Set src1, Set src2) /12、集合求差运算 void Subtract(Set dest, Set src1, Set src2) /测试主函数 int main() 八、源程序： #include #include #define ElemType char /宏定义一个字符型的元素类型，以下使用不用定义 /定义集合结构体 typedef struct ElemNode Ele

15、mType elem; /集合元素域 struct ElemNode *next; *Set,ElemNode; /1、计算一个集合的长度用于对集合排序 int Length(Set src) int i=0; while(src-next != NULL) /集合元素不为空时i+1 i+; src=src-next; /依次向后 return i; /2、创建一个从a-z字母集合 void Create(Set dest) ElemType ch; Set p = dest,n; for(;) ch = getchar(); /输入字符 if(ch = n) /遇到换行（一个集合输入完成）就

16、返回终止 break; if(ch122) /输入的字符不属于a-z 就终止运行,用于实现限定元素功能 continue; n = (Set)malloc(sizeof(ElemNode); /为集合n分配存储空间 p-next = n; n-elem = ch; /将字符插入集合 n-next = NULL; p = n; return ; /3、清空一个集合 void Empty(Set dest) Set p,n; while(dest-next != NULL) p = dest; n = p-next; for(;n-next!=NULL;) p = n; n = n-next; f

17、ree(n); p-next = NULL; /4、销毁集合 void Destroy(Set dest) Empty(dest); free(dest); /5、对一个字母集合进行从小到大的排序 void Sort(Set dest) int i,j,l,flag; Set p,q,n; l=Length(dest); if(l0 & flag=1;i-) flag = 0; p = dest; q = p-next; n = q-next; for(j=0;jelemn-elem) flag = 1; p-next = n; q-next = n-next; n-next = q; q =

18、 p-next; n = q-next; p = q; q = n; n = n-next; /6、打印集合的所有元素 void Display(Set src) Set p; if(src-next = NULL) printf( ); return ; p = src; p = p-next; putchar(p-elem); while(p-next != NULL); /7、判断元素是否存在于集合中 int ExistElem(Set dest, ElemType e) Set p=dest; if(Length(p)=0) return 0; else p=p-next; while

19、(p-elem != e) if(p-next=NULL) return 0; p=p-next; return 1; /8、删除集合中的一个元素一次 void DelElem(Set dest, ElemType e) Set p=dest,q; if(Length(p)=0) return ; q=p-next; if(Length(p)=1) p-next=NULL; free(q); while(q-elem!=e) p=p-next; q=q-next; if(q-next=NULL) p-next=NULL; free(q); Else p-next=q-next; /9、在链表尾

20、部追加一个元素 void AddElem(Set dest, ElemType e) Set p=dest, n; while(p-next!=NULL) p=p-next; n=(Set)malloc(sizeof(ElemNode); p-next=n; n-elem=e; n-next=NULL; /10、集合合并运算 void Add(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i=0,j=0,len1 = Length(src1),len2=Length(src2); src1=src1-next; src2=s

21、rc2-next; while(ilen1 & jelem elem) i+; if(!ExistElem(dest, src1-elem) AddElem(dest, src1-elem); src1 = src1-next; else src1 = src1-next; else j+; if(!ExistElem(dest, src2-elem) AddElem(dest, src2-elem); src2 = src2-next; else src2 = src2-next; while(ielem) AddElem(dest, src1-elem); src1 = src1-next

22、; while(jelem) AddElem(dest, src2-elem); src2 = src2-next; /11、集合求交集运算 void Mul(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i=0,j=0; int len1=Length(src1),len2=Length(src2); src1=src1-next;src2=src2-next; while(ilen1&jelemelem) i+;src1=src1-next; else if(src1-elemsrc2-elem) j+;src2=src

23、2-next; else i+;j+; if(!ExistElem(dest, src1-elem) AddElem(dest, src1-elem); src1=src1-next; src2=src2-next; /12、集合求差运算 void Subtract(Set dest, Set src1, Set src2) Sort(src1); Sort(src2); int i = 0; int len = Length(src1); src1 = src1-next; while(ielem) if(!ExistElem(dest, src1-elem) AddElem(dest, s

24、rc1-elem); src1 = src1-next; else src1 = src1-next; /测试主函数 int main() int a,f; Set dest=(Set)malloc(sizeof(ElemNode); Set src1=(Set)malloc(sizeof(ElemNode); Set src2=(Set)malloc(sizeof(ElemNode); dest-next=NULL; printf(*n); printf(* t欢迎使用集合运算系统 *n); printf(* 请输入两个集合：n); Create(src1); Create(src2); printf(* Set1 = ); Display(src1); printf(n); printf(* S