信息12-1班 201211041039 庄建——课程设计报告.doc

算法与数据结构课程设计报告成绩：_算法与数据结构课程设计报告学院名称 理学院 专业班级信息12-1 学生姓名 庄建 导师姓名 贾秋亭 目录1、模块2：一元多项式计算2、模块8：建立二叉树，层序、先序遍历3、模块9：赫夫曼树的建立1、模块2：一元多项式计算（1）系统分析建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果（2）概要设计存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。1 单连表的抽象数据类型定义： ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=| ai-1, aiD,i=2,n 基本操作： InitList（L） /操作结果：构造一个空的线性表 CreatPolyn(&L) /操作结果：构造一个以单连表存储的多项试 DispPolyn(L) /操作结果：显示多项试 Polyn(&pa,&pb) /操作结果：显示两个多项试相加，相减的结果 ADT List 2 本程序包含模块： typedef struct LNode /定义单链表 LNode,*LinkList; void InitList(LinkList &L) /定义一个空表 void CreatPolyn(LinkList &L) /用单链表定义一个多项式 void DispPolyn(LinkList L) /显示输入的多项式 void Polyn(LinkList &pa,LinkList &pb) void main() /定义一个单连表； coutendl *欢迎来到一元多项式计算程序 * endl; LNode *L1,*L2; Polyn(L1,L2); 2.1 加，减操作模块实现加减操作 各模块之间的调用关系如下： 主程序模块 加法操作模块 减法操作模块用户菜单多项式链表各函数退出指针数组主函数基本算法：1、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入 图表 1开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 合并同类项结束否是是否输入正确 2、多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法流程图如图2所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。图表 2开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项 3、多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图3所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。 图表 3开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项 1. 根据题目要求采用单连表存储结构 typedef struct LNode /定义单链表 LNode,*LinkList; void InitList(LinkList &L) /定义一个空表 void CreatPolyn(LinkList &L) /用单链表定义一个多项式 void DispPolyn(LinkList L) /显示输入的多项式 void Polyn(LinkList &pa,LinkList &pb) 2主函数 main void main() LNode *L1,*L2; Polyn(L1,L2); 2. 函数的调用关系层次结构多项式 Polyn 用单链表定义多项式 CreatPolyn 定义一个空表 InitList 显示输入的多项式 DispPolyn五. 调试分析采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过程 中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两个多 项式的相加、相减;将从新得到的单连表结果输出；该算法的时间复杂度为两个 多项式的项式之和(3)详细设计#include#includetypedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点 else Polyn q1,q2; 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; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolynvoid DestroyPolyn(Polyn p)/销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指针后移 q2=q2-next; void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; /while printf(n);/PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-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多项式非空/comparePolyn 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; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolynPolyn 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;/SubtractPolynint main() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULL printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输入b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式a /输出菜单 printf(*n); printf(操作提示：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn); printf(t4.退出n*n); for(;flag=0) printf(执行操作：); scanf(%d,&flag); if(flag=1) printf(多项式a：);PrintPolyn(pa); printf(多项式b：);PrintPolyn(pb);continue; if(flag=2) pc=AddPolyn(pa,pb); printf(多项式a+b：);PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=3) pd=SubtractPolyn(pa,pb); printf(多项式a-b：);PrintPolyn(pd); DestroyPolyn(pd);continue; if(flag=4) break; if(flag4) printf(Error!n);continue; /for DestroyPolyn(pa); DestroyPolyn(pb); return 0; (4)测试记录测试的数据及结果(5)总结：算法的时间复杂度及改进：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加减运算。一元多项式计算是一个的单链表的运用， 通过这个程序可以测我们以前的学习情 况，看看我们是否对单链表真正的理解。一元多项式计算器的基本功能定为：(1) 建立多项式 (2) 输出多项式 (3) 两个多项式相加，建立并输出和多项式 (4) 两 个多项式相减，建立并输出差多项式能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；2、模块8：建立二叉树，层序、先序遍历（1）系统分析要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；程序功能包括，建立二叉树，输出二叉树，对二叉树进行层序遍历和先序遍历。（2）概要设计或程序流程图主函数设计void main ()BTNode * b,*p;CreateBTNode (b,a(b(d,e),c(f,g) );printf(1)输出二叉树:);DispBTNode (b);printf(n);printf(2)层次遍历序列：);TravLevel(b);printf(n);printf(3)先序遍历序列：);PreOrder(b);printf(n);用递归算法的先序遍历函数void PreOrder(BTNode *b)if(b!=NULL)printf (%c,b-data);PreOrder(b-lchild);PreOrder(b-rchild);（3）详细设计或源代码说明#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;struct node *lchild;struct node *rchild;BTNode;void CreateBTNode(BTNode *&b,char *str)/创建二叉树BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;ch=strj;while (ch!=0)switch (ch)case(:top+;Sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)b=p;elseswitch(k)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)/括号表示法输出二叉树if (b!=NULL)printf (%C,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispBTNode(b-rchild);printf();void TravLevel(BTNode *b)/层次遍历BTNode *QuMaxSize;int front,rear;front=rear=0;if(b!=NULL)printf(%c,b-data);rear+;Qurear=b;while (rear!=front)front=(front+1)%MaxSize;b=Qufront;if(b-lchild!=NULL)printf(%c,b-lchild-data);rear=(rear+1)%MaxSize;Qurear=b-lchild;if(b-rchild!=NULL)printf (%c,b-rchild-data);rear=(rear+1)%MaxSize;Qurear=b-rchild;printf(n);void PreOrder(BTNode *b)/用递归算法的先序遍历函数if(b!=NULL)printf (%c,b-data);PreOrder(b-lchild);PreOrder(b-rchild);void main ()BTNode * b,*p;CreateBTNode (b,a(b(d,e),c(f,g) );printf(1)输出二叉树:);DispBTNode (b);printf(n);printf(2)层次遍历序列：);TravLevel(b);printf(n);printf(3)先序遍历序列：);PreOrder(b);printf(n);（4） 测试记录（5）总结因为本程序最终要与其他两个程序合并在一起，在主界面进行选择。所以在进入主界面时要在本程序的主函数处修改字符，否则在调用本程序时主函数会发生冲突。3、模块9：赫夫曼树的建立（1）系统分析 建立函数输入二叉树，能够输出所输入权值的赫夫曼编码。（2）概要设计或程序流程图 通过控制台输入的形式得到建立赫夫曼树需要的参数调用生成赫夫曼树的算法来生成赫夫曼树，这个过程中还不断的调用select方法来寻找当前结点中权值最小的结点来生成树的新结点，然后添加到树中去通过用户的选择来输出赫夫曼树，其输出的形式为：每个自符对应的赫夫曼编码。（3） 详细设计或源代码说明# include # include # include # include # include # define MAX_LENGTH 100typedef char *HuffmanCode;/数据结构typedef struct int weight; /权值 int parent,lchild,rchild; /双亲，左右孩子HTNode,*HuffmanTree;/select函数void Select(HuffmanTree HT,int i,int &s1,int &s2) /在建立赫夫曼树的所有结点中选择权值最小的两个结点存放在s1,s2中int j,k=1;while(HTk.parent!=0) k+;s1=k;for(j=1;j=i;+j)if(HTj.parent=0&HTj.weightHTs1.weight)s1=j;k=1;while(HTk.parent!=0|k=s1)k+;s2=k;for(j=1;j=i;+j)if(HTj.parent=0&HTj.weightHTs2.weight&j!=s1)s2=j; /构建赫夫曼树void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n) int m,i,s1,s2,start,c,f;HuffmanTree p;if(n=1)return;m=2*n-1; /由得到的叶子数而计算结点总数HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/分配存储空间for(p=HT+1,i=1;iweight=*w; /为结点初始化权值p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0; /初始化双亲和左右孩子，使他们成为孤立的for(i=n+1;i=m;+i) Select(HT,i-1,s1,s2); /调用select函数HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/新结点的权值是s1和s2权值的和 /赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char *);char *cd;cd=(char *)malloc(n*sizeof(char);cdn-1=0;coutendlHuffmanTree编码是：endl;for(i=1;i=n;+i) /从底下往上寻回编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);coutHTi Huffman code is: HCiendl;free(cd); ;/主函数部分void main() HuffmanTree HT;HuffmanCode HC;int n,i;int *w,WMAX_LENGTH;cout*本程序实现的是赫夫曼树的建立以及编码*;coutendln;cout请输入各元素的权值:endl;for(i=0;in;+i)coutHTiWi;w=W;HuffmanCoding(HT,HC,w,n);（4） 测试记录 当建立一个含有5个初始结点，权值分别为2，4，6，8，10的赫夫曼树的测试结果：（5）总结算法时间复杂度：O(n2)此处只是赫夫曼树的建立和输出算法的实现，一个完整的赫夫曼编/译码系统其实可以进一步完善，并且可以实现相关编码解码的功能。这也是赫夫曼树在生活中用到最多的地方。总程序：# include # include # include # include # include # define MAX_LENGTH 100typedef char *HuffmanCode;void e();/-模块2-void a(); typedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点 else Polyn q1,q2; 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; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /调用Insert函数插入结点 return head;/CreatePolynvoid DestroyPolyn(Polyn p)/销毁多项式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2;/指针后移 q2=q2-next; void PrintPolyn(Polyn P) Polyn q=P-next; int flag=1;/项数计数器 if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+); /系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; /while printf(n);/PrintPolynint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-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多项式非空/comparePolyn 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; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolynPolyn 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;/SubtractPolynvoid a() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULL printf(*模块2一元多项式计算*n); printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输入b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式a /输出菜单 printf(*n); printf(操作提示：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn); printf(t4.退出n*n); for(;flag=0) printf(执行操作：); scanf(%d,&flag); if(flag=1) printf(多项式a：);PrintPolyn(pa); printf(多项式b：);PrintPolyn(pb);continue; if(flag=2) pc=AddPolyn(pa,pb); printf(多项式a+b：);PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=3) pd=SubtractPolyn(pa,pb); printf(多项式a-b：);PrintPolyn(pd); DestroyPolyn(pd);continue; if(flag=4) break; if(flag4) printf(Error!n);continue; /for DestroyPolyn(pa); DestroyPolyn(pb); e();/-模块8-void b(); #include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;struct node *lchild;struct node *rchild;BTNode;void CreateBTNode(BTNode *&b,char *str)/创建二叉树BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0;char ch;b=NULL;c