[计算机软件及应用]数据结构实验报告.doc

编号： 江西理工大学 数据结构课程设计报告 班 级： 网络112班 学 号： 09 姓 名： 李秀光 时 间： 2012年12月31日 2012年1月11日 指导教师： 涂燕琼 井福荣 2013年01月30目 录第一章 数制转换1一、需求分析11、输入的形式和输入值的范围12、输出的形式13、程序所能达到的功能14、测试数据1二、概要设计21、抽象数据类型的定义22、主程序的流程以及各程序模块之间的层次调用关系2三、详细设计21、数据类型22、伪码算法33、流程图54、调试分析65、用户使用说明66、测试结果77、附录8第二章 一元多项式11一、需求分析111、输入的形式和输入值的范围112、输出的形式113、程序所能达到的功能114、测试数据12二、概要设计121、抽象数据类型的定义122、主程序的流程以及各程序模块之间的层次调用关系13三、详细设计131、数据类型132、伪码算法143、流程图174、调试分析185、用户使用说明186、测试结果197、附录20第一章 数制转换一、需求分析1、输入的形式和输入值的范围n和f的输入形式均为int型，n和f的输入范围均为1327672、输出的形式十六进制10-15输出A-E，超过十六进制时按16以上数值按原值输出。3、程序所能达到的功能把十进制数n转换成任意进制数f（对于输入的任意一个非负十进制整数，输出与其等值的任意进制数（如二，四，八，十六进制）。4、测试数据n（十进制）f（进制）输出值22210110354411202537681240032767167FFF二、概要设计1、抽象数据类型的定义ADT Stack基本操作：InitStack(&S)操作结果：构造一个空栈s。Push(&S,e)初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。Pop(SqStack &S)初始操作：栈s已存在且非空。操作结果：删除s的栈顶元素，并用e返回其值。StackEmpty(SqStack S)初始条件：栈s已存在。操作结果：若栈为空则返回1，否则返回0。ADT Stack2、主程序的流程以及各程序模块之间的层次调用关系见（三、详细设计3、流程图）三、详细设计1、数据类型/ = = = = = ADT Stack 的表示与实现 = = = = = / - - - - - 数制转换 - - - - -/#define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10/存储空间分配增量typedef struct int *base;int *top;int stacksize;SqStack;/ - - - - - 基本操作的函数原型说明 - - - - - /void InitStack(SqStack &S)/构造一个空栈svoid Push(SqStack &S,int e)/插入e为新的栈顶元素int Pop(SqStack &S)/删除s的栈顶元素，并用e返回其值int StackEmpty(SqStack S)/若栈为空则返回1，否则返回0void conversion(int n,int f)/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 2、伪码算法/ - - - - - 基本操作的算法描述 - - - - - /void InitStack(SqStack &S)/构造一个空栈sS.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int);if(!S.base) exit(-2);S.top = S.base;S.stacksize = STACK_INIT_SIZE;/ InitStackvoid Push(SqStack &S,int e)/插入元素e为新的栈顶元素if(S.top- S.base = S.stacksize)S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int);if(!S.base) exit(-2);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;/ Pushint Pop(SqStack &S)/删除s的栈顶元素，并用e返回其值 int e;if(S.top = S.base) return 0;e = *-S.top;return e;/Popint StackEmpty(SqStack S)/若栈为空则返回1，否则返回0if(S.top = S.base) return 1;else return 0;/ StackEmpty/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 void conversion(int n,int f)InitStack(S);while(n)Push(S,n%f);n = n/f;while(!StackEmpty(S)Pop(S,e)printf(%d,e);/ conversion3、流程图输入n和fq=y|q=Y打印标题开始输出：要换转的十进制数错误Yn0输入qNf0 Y输出：请输入正确的进制位！NInitStack()初始化栈 Yn!=0NPush(S,n%f) YNNn=n/f!StackEmpty(S) Y输出转换后的数值结束4、调试分析（1）调试过程中遇到的问题和解决方法在调试过程中主要遇到一些符号打错或输出、输出和函数之类的名称打错或漏打，根据第一行提示的错误然后进行修改，修改之后再运行调试，如此循环，直到彻底正常运行，后面就是优化见面的问题了。（2）算法的时空分析和改进设想算法时间复杂度：f(n)改进设想：可在输出时将10的数字用A-Z输出。（3）经验和体会等从这是实验当中，我体会最深的是编程要特别仔细，因为稍不注意就可能打错字母，这些错误有时在调试当中特别难找，就是一个小小的字母可能也要让你花上好长时间来修改，还有就是要形成自己的编程风格，这样的代码看起来不至于那么乱，给有人条理的感觉，也便于代码的维护。5、用户使用说明运行输入n和f（n和f均大于0） n和f正确输入，然后打印输出n转换成f进制后的数值 输入q（输入q=（y|Y）则继续转换，否则结束） 结束。6、测试结果7、附录（1）带注释的源程序#include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct int *base;int *top;int stacksize;SqStack;/构造一个空栈 void InitStack(SqStack &S)S.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int);if(!S.base) exit(-2);S.top = S.base;S.stacksize = STACK_INIT_SIZE;/插入e为新的栈顶元素 void Push(SqStack &S,int e)if(S.top- S.base = S.stacksize)S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int);if(!S.base) exit(-2);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;/删除s的栈顶元素，并用e返回其值 int Pop(SqStack &S)int e;if(S.top = S.base) return 0;e = *-S.top;return e;/若栈为空则返回1，否则返回0 int StackEmpty(SqStack S)if(S.top = S.base) return 1;else return 0;/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 void conversion(int n,int f)int e;SqStack S;InitStack(S);while(n)Push(S,n%f);n = n/f;while(!StackEmpty(S)switch(e = Pop(S)case 10:printf(A);break;case 11:printf(B);break;case 12:printf(C);break;case 13:printf(D);break;case 14:printf(E);break;case 15:printf(F);break;default:printf(%d,e);break;printf(nn);/操作，输入要转换的十进制数与要转换成的进制位 void Operate()int n,f;char q = y;while(q = y | q = Y)printf(请输入要转换的十进制数值：);scanf(%d,&n);printf(n请输入要转换成的进制位：);scanf(%d,&f);printf(n%d转换成%d进制数：,n,f);if(n 0)if(f 0)conversion(n,f);elseprintf(请输入正确的进制位！nn);elseprintf(要换转的十进制数错误。nn);printf(是否继续？（y/n）：);scanf(%s,&q);printf(n);/标题 void title()printf(ttt*n);printf(ttt*t数 制 转 换t *n);printf(ttt*n);int main()title();printf(n);Operate();（2）程序文件名的清单数制转换.cpp第二章 一元多项式一、需求分析1、输入的形式和输入值的范围choose、m（非零项个数）和expn（指数）的输入形式均为int型，coef（系数） 的输入形式为float型，choose的输入值为1、2和0，m和expn的输入范围均为132767，coef的输入范围为3.4E38。2、输出的形式例：3.00X8+8.00X7-5.00X5+1.00X2-2.35X13、程序所能达到的功能任务：能够按照指数降序排列建立并输出多项式。能够完成两个多项式的相加、相减，并将结果输入。4、测试数据 一元多项式运算一元多项式结果-x2+x3+2x2+3x3+4x54x5+4x3+1x2x3-2x4+5.2x+x25x4+3.2x-7x4+1x3+1x2+8.4x1-2x2+3x3+4x4-xx2+4x3+x43x4-1x3-1x2-x1二、概要设计1、抽象数据类型的定义ADT Polynomial基本操作： CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一个一元多项式pDestroyPolyn (&P)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。 PrintPolyn(P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。 AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：多项式减法：Pa=Pa-Pb，并销毁一元多项式PbADT Polynomial2、主程序的流程以及各程序模块之间的层次调用关系见（三、详细设计3、流程图）三、详细设计1、数据类型/ = = = = = ADT Polynomial的表示与实现 = = = = = / - - - - - 一元多项式 - - - - -/typedef struct /项的表示，多项式的项作为LinkList的数据元素 float coef;/系数 int expn;/指数 term,ElemType;/term用于本ADT，ElemType用于LinkList的数据对象名typedef LinkList polynomial;/用带表头结点的有序链表表示多项式/ - - - - - 基本操作的函数原型说明 - - - - - / void CreatPolyn(polynomial &P,int m)/输入m项的系数和指数，建立表示一元多项式的有序链表p int DestroyPolyn(polynomial p)/销毁一元多项式p void PrintPolyn(polynomial P)/打印输出一元多项式pvoid AddPolyn(polynomial *Pa,polynomial *Pb)/多项式加法：Pa=Pa+Pb，并销毁一元多项式Pb void SubtractPolyn(polynomial *Pa,polynomial *Pb)/多项式减法：Pa=Pa-Pb，并销毁一元多项式Pb 2、伪码算法/ - - - - - 基本操作的算法描述(部分重要操作) - - - - - / int cmp(term a,term b) /依a的指数值)b的指数值，分别返回-1，0，和+1 /cmpvoid CreatPolyn(polynomial &P,int m) /输入m项的系数和指数，建立表示一元多项式的有序链表p InitList(P);h = GetHead(P);e.coef = 0.0;e.expn = -1;SetCurElem(h,e);/设置头结点的数据元素 printf(系数 指数n);for(i = 1;i next) /为一元多项式减法做准备，将系数全部取反，然后执行一元多项式的加法。 p = p-next;p-data.coef *= -1;/while/ Oppositevoid SubtractPolyn(polynomial *Pa,polynomial *Pb)/多项式减法：Pa=Pa-Pb，并销毁一元多项式PbOpposite(*Pb);/先为一元多项式Pb系数全部取反AddPolyn(Pa,Pb);/执行一元多项式的加法，取反后相当于减法。/ SubtractPolynvoid Sort(polynomial P) /将链表升序排序转换成降序排序 tailNode = P.tail;/tailNode标记P链表的尾结点 while(P.head-next != tailNode)/当P的头结点下一个结点（第一个元素从是头结点的下一个元素）不等/于尾结点时执行 curNode = P.head-next;while(curNode != tailNode)/if(curNode-data.expn next-data.expn)/当当前元素的指数小于下一个元素的指数时执行交换 e = curNode-data;curNode-data = curNode-next-data;curNode-next-data = e;/ifnewNode = curNode;/while循环到最后时newNode指向tailNode的前一个结点 curNode = curNode-next;/将eNode结点下移 /whiletailNode = newNode;/将tailNode结点前移（此时最大的指数已经移到尾结点） /while/ Sort开始3、流程图打印标题f=y | f=Y打印菜单YNchoose输入f0 1、2InitList(P)输入mSetCurElem(h,e)（输入第二个一元多项式）2将一元多项式Pb的全部系数取反i = 1;i = m;+iN1（第1次N执行输入m）!Pa&! Pb&qaY输入e.coef和e.expn Y打印输出Pacmp(a,b)!LocateElemP(P,e,&q,cmp) N -1 -2Sort()将Pa的升序转换成降序0删除Pa和Pb系数和指数将Pb的系数加到Pa的系数YMakeNode(&s,e)Append(Pa,qb)FreeNode(&hb) N! Pb销毁链表PbInsFirst(&P,q,s)结束YY4、调试分析（1）调试过程中遇到的问题和解决方法在调试过程中主要遇到一些符号打错或输出、输出和函数之类的名称打错或漏打，根据第一行提示的错误然后进行修改，修改之后再运行调试，如此循环，直到彻底正常运行，后面就是优化见面的问题了。（2）改进设想增加两个一元多项式的乘法和除法操作，简化代码，减少时间和空间复杂度。（3）经验和体会等从这是实验当中，我体会最深的是编程要特别仔细，因为稍不注意就可能打错字母，这些错误有时在调试当中特别难找，就是一个小小的字母可能也要让你花上好长时间来修改，还有就是要形成自己的编程风格，这样的代码看起来不至于那么乱，给有人条理的感觉，也便于代码的维护，还有就是函数调用的问题，函数调用多了容易出现错误，函数写多了也容易忘记，这就要求程序员有良好的注释习惯。5、用户使用说明运行 选择操作（1，2，0） 输入第一个一元多项式非零项的个数m输入第一个一元多项式的系数和项数（系数 项数） 输入第一个二元多项式非零项的个数m 输入第二个一元多项式的系数和项数（系数 项数） 打印输出运算后的一元多项式 输入f 若f=y|f=Y 则继续选择操作 否则结束程序。6、测试结果7、附录（1）带注释的源程序#include #include #define DestroyPolyn DestroyList#define PolynLength ListLengthtypedef struct /项的表示，多项式的项作为LinkList的数据元素 float coef;/系数 int expn;/指数 term,ElemType;/term用于本ADT，ElemType用于LinkList的数据对象名typedef struct LNode /结点类型 ElemType data;struct LNode *next;*Link,*Position;typedef struct _LinkList /链表类型 Link head,tail;/head指向头结点，tail指向最后一个结点 int len;/指向线性链表中数据元素的个数 LinkList;typedef LinkList polynomial;/用带表头结点的有序链表表示多项式/依a的指数值)b的指数值，分别返回-1，0，和+1 int cmp(term a,term b) if(a.expn = b.expn)return 0;else return (a.expn b.expn) ? 1:-1; /构造一个空地线性链表 Lvoid InitList(LinkList &L) Link p;p = (Link)malloc(sizeof(LNode);/生成头结点 if(p)p-next = NULL;/将头尾结点都分配好，并将其下一结点置空 L.head = L.tail = p;L.len = 0;/初始为0 /返回线性链表L中头结点的位置 Position GetHead(LinkList L) return L.head;/已知p指向线性链表中的一个结点，返回e更新p所指结点中数据元素的值void SetCurElem(Link &p,ElemType e) p-data = e; /已知p指向线性链表中地一个结点，返回p所指结点中数据元素地位置地值 ElemType GetCurElem(Link p)return p-data;/若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中/第一个值为e地结点的位置，并返回1；否则q指示第一个与e满足判定函数/compare()取值0地元素地前驱地位置。并返回0.（用于一元多项式） int LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType) Link p = L.head,pp;dopp = p;p = p-next;while(p&(compare(p-data,e)data.expndata,e)0)/到表尾或compare(p-data,e)0 *q = pp;return 0;else*q = p;return 1;/分配由p指向地值为e地结点，并返回1；若分配失败。则返回0 int MakeNode(Link *p,ElemType e) *p = (Link)malloc(sizeof(LNode);/动态分配一个Link空间 if(!*p) return 0;(*p)-data = e;return 1;/h指向L地一个结点，把h当做头结点，将s所指结点插入在第一个结点之前 int InsFirst(LinkList *L,Link h,Link s) s-next = h-next;h-next = s;if(h = (*L).tail)/如果h指向尾结点 (*L).tail = h-next;/修改尾指针 (*L).len+;return 1;/若线性链表L为空表，则返回1，否则返回0 int ListEmpty(LinkList L)if(L.len) return 0;else return 1;/已知p指向线性链表L中地一个结点，返回p所指结点地直接后继地位置/若无后继，则返回NULL Position NextPos(Link p)return p-next;/h指向L地一个结点，把h当做头结点，删除链表中地第一个结点并以q返回。/若链表为空（h指向表尾结点），q = NULL,返回0 int DelFirst(LinkList *L,Link h,Link *q)*q = h-next;if(*q)/链表非空 h-next = (*q)-next;if(!h-next)/删除尾结点 (*L).tail = h;/修改尾指针 (*L).len-;return 1;else return 0;/链表空 /释放p所指结点 void FreeNode(Link *p)free(*p);/先释放存储空间，然后置空 *p = NULL;/将指针s(s-data为第一个数据元素)所指(彼此以指针项链，以NULL结尾)地/一串结点连接在线性链表L地最后一个结点之后，并改变链表L地尾指针指向新地尾结点 int Append(LinkList *L,Link s)int i = 1;/记录s为头地串结点个数 (*L).tail-next = s;/尾结点指向s while(s-next)s = s-next;i+;(*L).tail = s;(*L).len += i;return 1;/将线性链表L重置为空表（头尾结点相同为空表），并释放远链表地结点/空间，不释放头尾即诶但，只是置空 int ClearList(LinkList *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;return 1;/销毁线性链表L，L不再存在 int DestroyList(LinkList *L)ClearList(L);/清空链表（头尾结点并没有释放） FreeNode(&(*L).head);/再释放头尾结点 (*L).tail = NULL;(*L).len = 0;return 1;/输入m项的系数和指数，建立表示一元多项式的有序链表p void CreatPolyn(polynomial &P,int m) Position h,q,s;term e;int i;InitList(P);h = GetHead(P);e.coef = 0.0;e.expn = -1;SetCurElem(h,e);/设置头结点的数据元素 printf(系数 指数n);for(i = 1;i data.coef += qb-data.coef;/修改Pa当前结点地系数值 if(qa-data.coef != 0.0)SetCurElem(qa,qa-data);ha = qa;else /删除多项式Pa中当前结点 DelFirst(Pa,ha,&qa);FreeNode(&qa);DelFirst(Pb,hb,&qb);FreeNode(&qb);qb = NextPos(hb);qa = NextPos(ha);break;case 1:/多项式Pb中当前结点地指数值小 DelFirst(Pb,hb,&qb);InsFirst(Pa,ha,qb);qb = NextPos(hb);ha = NextPos(ha);break;if(!ListEmpty(*Pb)Append(Pa,qb);/链接Pb中剩余结点FreeNode(&hb);/释放Pb头结点 DestroyPolyn(Pb);/销毁Pb /一元多项式系数取反 void Opposite(polynomial Pa)Position p;p = Pa.head;while(p-next) /为一元多项式减法做准备，将系数取反，然后执行一元多项式的加法。 p = p-next;p-data.coef *= -1;/多项式减法：Pa=Pa-Pb，并销毁一元多项式Pb void SubtractPolyn(polynomial *Pa,polynomial *Pb)Opposite(*Pb);AddPolyn(Pa,Pb);/将链表升序排序转换成降序排序void Sort(polynomial P) Link curNode,tailNode,newNode; term e; tailNode = P.tail;/tailNode标记P链表的尾结点 while(P.head-next != tailNode)/当P的头结点下一个结点（第一个元素从是头结点的下一个元素）不等/于尾结点时执行 curNode = P.head-next;while(curNode != tailNode)/if(curNode-data.expn next-data.expn)/当当前元素的指数小于下一个元素的指数时执行交换 e = curNode-data;curNode-data = curNode-next-data;curNode-next-data = e;newNod