《数据结构》实验指导(09-10一)

因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验一线性表及其应用实验目的（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法实验环境（1）Windows2000，或WindowsXP（简体中文）（2）TurboC3.0及以上，或TurboPascal5.5及以上，或VisualC++6.0，或C++Builder6.0，或VisualC#2005及以上，或Delphi6.0及以上操作系统环境和编程环境（集成开发环境）任选以上所列之一。实验内容设计一个实现一元多项式简单运算的程序。要求完成：1）多项式的建立，2）多项式的输出，3）多项式的相加运算，4）多项式的乘积运算。解题思路：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储多项式中某一项的系数和指数，建立单链表时指数低的结点列于指数高的结点之后，即线性表的元素按指数递减有序排列。在多项式求和运算时，将指数相同的项的系数相加，其和非0则存储该项。乘积运算时，运用循环将2个多项式的各项交叉相乘，存储每2项的积（系数的积，指数的和）于新建立的结点，之后将这些结点中指数相同的各项系数之和非0的项合并为1个结点，最后释放多余的临时结点。实现步骤：以C++Builder环境为例，实现步骤如下：1．新建一个Win32ConsoleApplication程序项目。2．在代码编辑窗口编写程序代码，含义如注释说明：#includeiostream.h#includecmath.htypedefstructnode//定义单链表结点的数据类型mulpoly{doublecoef;//表示系数intexp;//表示指数structnode*next;//指向下一项结点的指针}mulpoly;mulpoly*create()//逐项输入系数和指数，建立单链表的函数{mulpoly*h,*p,*q;h=newmulpoly;//建立头结点p=h;//头结点作为初始的前驱doublex,y;while(1)//循环建立各项结点，直到输入指数是零为止{coutInputacoefficient:;cinx;//输入系数因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结coutInputanexponent:;ciny;//输入指数if(x){q=newmulpoly;q-coef=x;q-exp=y;//存系数和指数p-next=q;//前驱的next指向新建结点p=q;//下一个结点的前驱即当前结点}if(y1e-6)break;}p-next=NULL;//最后一项结点无后继returnh;//返回头指针}voidoutput(mulpoly*h)//遍历单链表，输出一元多项式的函数{mulpoly*p;coutY=;p=h-next;if(p==NULL)cout0;//多项式为0else//输出多项式的第1项{coutp-coef;if(p-exp!=0)coutX;if(p-exp1)cout^p-exp;p=p-next;}while(p!=NULL)//逐项输出后续各项{if(p-coef0)cout+;coutp-coef;if(p-exp!=0)coutX;if(p-exp1)cout^p-exp;p=p-next;}coutendl;}mulpoly*poly_add(mulpoly*a,mulpoly*b)//两个多项式求和的函数{mulpoly*c,*pa,*pb,*pc,*q;c=newmulpoly;//建立结果多项式单链表的头结点pc=c;pa=a-next;pb=b-next;while((pa!=NULL)&&(pb!=NULL)){if(pa-exppb-exp)//被加项的指数较大{q=newmulpoly;q-coef=pa-coef;q-exp=pa-exp;pa=pa-next;pc-next=q;pc=q;}elseif(pa-exppb-exp)//被加项的指数较小因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结{q=newmulpoly;q-coef=pb-coef;q-exp=pb-exp;pb=pb-next;pc-next=q;pc=q;}elseif(fabs(pa-coef+pb-coef)1e-8)//指数相同，系数之和非零{q=newmulpoly;q-coef=pa-coef+pb-coef;q-exp=pa-exp;pa=pa-next;pb=pb-next;pc-next=q;pc=q;}else//系数之和为零{pa=pa-next;pb=pb-next;}}while(pa!=NULL)//链接多项式a的剩余项{q=newmulpoly;q-coef=pa-coef;q-exp=pa-exp;pa=pa-next;pc-next=q;pc=q;}while(pb!=NULL)//链接多项式b的剩余项{q=newmulpoly;q-coef=pb-coef;q-exp=pb-exp;pb=pb-next;pc-next=q;pc=q;}pc-next=NULL;returnc;//返回头结点}mulpoly*poly_multiply(mulpoly*a,mulpoly*b)//两个多项式乘积的函数{mulpoly*c,*pa,*pb,*pc,*q,*p;intj,maxe;doublem_coef;if((a-next==NULL)||(b-next==NULL))returnNULL;//某个多项式为0，乘积亦为0c=newmulpoly;//建立结果多项式单链表的头结点pc=c;pa=a-next;maxe=(a-next-exp)+(b-next-exp);//最高指数while(pa!=NULL)//双层循环使之各项相乘{pb=b-next;while(pb!=NULL){q=newmulpoly;//为存储每次乘积建立一个结点q-coef=(pa-coef)*(pb-coef);q-exp=pa-exp+pb-exp;pc-next=q;pc=q;pb=pb-next;因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结}pa=pa-next;}pc-next=NULL;pa=c;pc=c-next;//暂存乘积的第一项地址for(j=maxe;j=0;j--)//合并指数相同的各项{p=pc;m_coef=0.0;while(p!=NULL){if(p-exp==j)m_coef+=p-coef;p=p-next;}if(fabs(m_coef)1e-6)//系数之和非零，建立新的结点存储结果项{q=newmulpoly;q-coef=m_coef;q-exp=j;pa-next=q;pa=q;}}pa-next=NULL;while(pc!=NULL)//释放第一次乘积运算的各项结点{p=pc;pc=pc-next;deletep;//free(p);}returnc;}voidmain()//主函数{mulpoly*ha,*hb,*hc,*hd;coutInputeachitemofamultipoly:\n;ha=create();coutInputeachitemofanothermultipoly:\n;hb=create();hc=poly_add(ha,hb);coutThesumofamultipoly:;output(ha);coutandanotherone:;output(hb);coutis:;output(hc);coutendl;hd=poly_multiply(ha,hb);coutTheirmultiplyis:;output(hd);coutendl;return;}3．保存程序项目。因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结在D盘根目录上建立一个以学号命名的文件夹，将程序项目的各种文件保存其中。4．编译、调试和执行。以上例程的运行结果如下图所示：因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究，下面就将自己在本学年中教育科研工作方面的情况总结实验二哈夫曼树及哈夫曼编码译码的实现实验目的（1）掌握树的有关操作算法（2）熟悉树的基本存储方法（3）学习利用树求解实际问题实验环境（1）Windows2000，或WindowsXP（简体中文）（2）TurboC3.0及以上，或TurboPascal5.5及以上，或VisualC++6.0，或C++Builder6.0，或VisualC#2005及以上，或Delphi6.0及以上操作系统环境和编程环境（集成开发环境）任选以上所列之一。实验内容已知某通信系统中只使用A、B、C、D、E、F、G、H等8种字符，且各字符使用的频率依次为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，试设计和输出其哈夫曼编码，并实现编码和译码的运算。解题思路：以上述8种字符作为叶子结点，各字符使用的频率作为各叶子结点的权值，用Hunffman算法构建哈夫曼树。采用顺序存储结构（数组）存储哈夫曼树及构树过程的信息，由于8个叶子结点的哈夫曼树共有15个结点，数组的大小为15。在构成哈夫曼树之后，为求哈夫曼编码需从叶子出发走一条从叶子到根的路径，而为译码需从根出发走一条从根到叶子的路径。则对于每个节点，既需知其双亲的信息，又需知其左、右孩子的信息。由此，数组元素结点应包含权值weight、双亲指针（下标）parent、左孩子指针lch、右孩子指针rch。同时，另定义一个存储哈夫曼编码结果的二维数组。为使每一个字符编码都不是另一个字符编码的前缀，规定哈夫曼树中左分枝以“0”编码，右分枝以“1”编码。实现步骤：以C++Builder环境为例，实现步骤如下：1．新建一个Win32ConsoleApplication程序项目。2．在代码编辑窗口编写程序代码，含义如注释说明：#includeiostream.hconstshortintn=8;charch[n]={'A','B','C','D','E','F','G','H'};doublew[n]={0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11};typedefstructnode{doubleweight;shortintparent,lch,rch;}huffnode;//哈夫曼树结点的数据类型typedefstructcodenode因为教育科研是教育教学改革和发展的第一生产力。“科研兴数，科研兴校”，我时刻铭记心间。因而在自己的实际工作中自觉或不自觉地就进行了教育科学研究