天津理工大学数据结构实验报告1

1实验报告学院（系）名称：计算机与通信工程学院姓名学号专业计算机科学与技术班级实验项目实验一：线性表应用课程名称数据结构与算法课程代码0661013实验时间2017年3月9日第1-2节3月10日第5-6节实验地点7-219考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○内容极少○无报告○有○无○有○无一、实验目的理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。二、实验题目与要求1．一元稀疏多项式简单的计算器1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）要求:（1）采用单链表存储结构一元稀疏多项式（2）输入并建立多项式（3）输出多项式（4）实现多项式加、减运算3）分析算法时间复杂度3．单链表基本操作练习1）问题描述：在主程序中提供下列菜单：1…建立链表2…连接链表3…输出链表0…结束2）实验要求：算法中包含下列过程，分别完成相应的功能：2CreateLinklist():从键盘输入数据，创建单链表ContLinklist()：将前面建立的两个单链表首尾相连OutputLinklist()：输出显示单链表3）分析算法时间复杂度三、实验过程与实验结果1．一元稀疏多项式简单的计算器数据结构定义typedefstructPolyNode{floatcoef;intexp;structPolyNode*next;}PolyNode;typedefPolyNode*Polynomial;算法设计思路简介用带头节点的单链表分别表示两个多项式L和p，同时新建一个链表N把两个多项式相加后的结果存放在N表中。所有链表均按指数从小到大顺序排列。链表N中的节点N1另外生成，把运算后的结果赋给N1，用尾部插入法将N1插入到链表N中，每次要将新节点N1插入到链表N尾部，因此给链表N声明一个尾指针N0始终指向链表N的尾节点。操作完成，按要求输出。算法描述：初始时，指针L1指向L链表的头节点，P1指向p链表的头结点，从头开始扫描两个相加多项式链表的表头节点，循环操作，直到其中一个单链表中的节点全部搜索结束为止。比较指针L1和P1指向的指数，共有三种情况：（1）L1-exp==P1-exp；则两个多项式的系数相加减，得到的新和多项式节点插入到链表N中。L1、P1指针后移；（2）L1-expP1-exp；则将该L1所指节点赋给N1插入到链表N中。L1、P1指针后移；（3）L1-expP1-exp；则将该P1所指节点赋给N1插入到链表N中。L1、P1指针后移。算法的实现和测试结果：输入:L1:53656700;L2:23354700;输出：L1:5x^3+6x^5+6x^7；L2:2x^3+3x^5+4x^7；L1+L2:7x^3+9x^5+10x^7；L1-L2:3x^3+3x^5+2x^73算法时间复杂度分析该程序中建立单链表过程采用了单链表的后插入操作，其时间复杂度T(n)=O(1)；当两个多项式相加减的时候，设L,p多项式分别有m、n项，其算法时间复杂度T(n)=O(m+n)。3．单链表基本操作练习数据结构定义typedefintElemType;structLNode{ElemTypedata;structLNode*next;};typedefLNode*LinkList;算法设计思路简介首先初始化两个带头结点的单链表L1,L2，要想实现两个链表的合并，可以将L2看成一个节点，将它插入到L1上即可。第一步遍历L1链表到最后一个，然后把第二个链表的地址赋值给它的next，即可实现。算法描述：初始时，指针L1指向L1链表的头节点，令L1=L1-next，L2=L2-next，然后从头开始扫描直到L1单链表中为空，此时令L1-next=L2，即把L2链表的地址赋给了L1的next，实现合并操作。最后通过Output函数将合并后的链表输出，依次将链表中的data域输出即可。算法的实现和测试结果：输入:L1:962482360;L2:54315980;输出：962482365431598；算法时间复杂度分析设L1链表共有n项，其循环操作就是遍历L1整个表，所以该算法时间复杂度T(n)=O(n)。四、收获与体会通过这次线性表的应用实验，我对于单链表的结构有了更深层次的理解，真正动手体会到怎样将查找、插入和删除这些基本操作应用在线性表中从而解决相关问题。同时我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。五、源代码清单1．一元稀疏多项式简单的计算器#includeiostreamusingnamespacestd;4typedefstructPolyNode{floatcoef;intexp;structPolyNode*next;}PolyNode;typedefPolyNode*Polynomial;PolynomialCreatePolyNode(){PolynomialL,p,s;floatcoef;intexp;L=newPolyNode;L-next=NULL;s=L;coutPleaseinputcoefandexpfromthekeyboard:;cincoefexp;while(coef!=0){p=newPolyNode;p-coef=coef;p-exp=exp;p-next=NULL;s-next=p;s=p;cincoefexp;}returnL;}PolynomialAddPolyNode(PolynomialL,Polynomialp){PolynomialL1,p1,N,N0,N1;N=newPolyNode;N-next=NULL;L1=L-next;p1=p-next;N0=N;while(L1!=NULL&&p1!=NULL){N1=newPolyNode;N1-next=NULL;if(L1-expp1-exp){N1-exp=L1-exp;N1-coef=L1-coef;N0-next=N1;5N0=N1;L1=L1-next;}elseif(L1-expp1-exp){N1-coef=p1-coef;N1-exp=p1-exp;N0-next=N1;N0=N1;p1=p1-next;}elseif(L1-exp==p1-exp){N1-exp=L1-exp;N1-coef=L1-coef+p1-coef;N0-next=N1;N0=N1;L1=L1-next;p1=p1-next;}}if(L1==NULL){while(p1!=NULL){N1=newPolyNode;N1-next=NULL;N1-coef=p1-coef;N1-exp=p1-exp;N0-next=N1;N0=N1;p1=p1-next;}returnN;}elseif(p1==NULL){while(L1!=NULL){N1=newPolyNode;N1-next=NULL;N1-exp=L1-exp;N1-coef=L1-coef;N0-next=N1;N0=N1;L1=L1-next;6}returnN;}}PolynomialReducePolyNode(PolynomialL,Polynomialp){PolynomialL1,p1,N,N0,N1;N=newPolyNode;N-next=NULL;L1=L-next;p1=p-next;N0=N;while(L1!=NULL&&p1!=NULL){N1=newPolyNode;N1-next=NULL;if(L1-expp1-exp){N1-coef=L1-coef;N1-exp=L1-exp;N0-next=N1;N0=N1;L1=L1-next;}elseif(L1-expp1-exp){N1-coef=-p1-coef;N1-exp=p1-exp;N0-next=N1;N0=N1;p1=p1-next;}elseif(L1-exp==p1-exp){N1-exp=L1-exp;N1-coef=L1-coef-p1-coef;N0-next=N1;N0=N1;L1=L1-next;p1=p1-next;}}if(L1==NULL){while(p1!=NULL){7N1=newPolyNode;N1-next=NULL;N1-coef=p1-coef;N1-exp=p1-exp;N0-next=N1;N0=N1;p1=p1-next;}}elseif(p1==NULL){while(L1!=NULL){N1=newPolyNode;N1-next=NULL;N1-exp=L1-exp;N1-coef=L1-coef;N0-next=N1;N0=N1;L1=L1-next;}}returnN;}voidShowPolyNode(PolynomialP){Polynomialx;x=P-next;if(x!=NULL){if(x-coef==0)cout;if(x-exp==0)coutx-coef;elseif(x-exp!=0)coutx-coefx^x-exp;x=x-next;}while(x!=NULL){if(x-coef0)cout--x-coefx^x-exp;if(x-coef0)cout+x-coefx^x-exp;x=x-next;}8}intmain(){PolynomialL1,L2,N1,N2;L1=CreatePolyNode();coutPolynomialL1is:endl;ShowPolyNode(L1);coutendl;cout************************************************endl;L2=CreatePolyNode();coutPolynomialL2is:endl;ShowPolyNode(L2);coutendl;cout************************************************endl;N1=AddPolyNode(L1,L2);coutPolynomialL1+L2is:endl;ShowPolyNode(N1);coutendl;cout************************************************endl;N2=ReducePolyNode(L1,L2);coutPolynomialL1-L2is：endl;ShowPolyNode(N2);coutendl;return0;}3．单链表基本操作练习#includeiostreamusingnamespacestd;typedefintElemType;structLNode{ElemTypedata;structLNode*next;};typedefLNode*LinkList;LinkListCreateLinkList(){LinkListL;LinkListp,