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

《天津理工大学数据结构实验报告1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、人4阶大死殓报告学院（系）名称：计算机与通信工程学院姓名学号专业计算机科学与技术班级实验项目实验一：线性表应用课程名称数据结构与算法课程代码0661013实验时间2017年3月9日第1-2节3月10B第5・6节实验地点7-219蠶实验过程25分程序运行20分回答问题15分实验报告30分考勤违纪情况5分成绩成绩栏其它批改意见：教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。□功能完善，□功能不全□有小错□无法运行O正确O基本正确O有提示O无法冋答O完整O较完娜O—般O内容极少O无报告

2、O有0无O/jO无一、实验目的理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基木操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。二、实验题目与要求1.一元稀疏多项式简单的计算器1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器2）要求：（1）采用单链表存储结构一元稀疏多项式（2）输入并建立多项式（3）输出多项式（4）实现多项式加、减运算3）分析算法时间复杂度3.单链表基本操作练习

3、1）问题描述：在主程序中提供下列菜单：1…建立链表2…连接链表3…输出链表0…结束2）实验要求：算法中包含下列过程，分别完成相应的功能：CreateLinklist():从键盘输入数据，创建单链表ContLinklist()：将前面建立的两个单链表首尾相连OutputLinklist():输出显示单链表3)分析算法时间复杂度三、实验过程与实验结果1.一元稀疏多项式简单的计算器>数据结构定义typedefstructPolyNode{floatcoef;intexp;structPolyNode*next;}Po

4、lyNode;typedefPolyNode^Polynomial;>算法设计思路简介用带头节点的单链表分别表示两个多项式L和p,同时新建一个链表N把两个多项式相加后的结果存放在N表中。所有链表均按指数从小到大顺序排列。链表N中的节点N1另外生成，把运算后的结果赋给N1,用尾部插入法将N1插入到链表N屮，每次要将新节点N1插入到链表N尾部，因此给链表N声明一个尾指针NO始终指向链表N的尾节点。操作完成，按要求输出。>算法描述：初始时，指针L1指向L链表的头节点，P1指向p链表的头结点，从头开始扫描两个相加多项式

5、链表的表头节点，循环操作，直到其屮一个单链表屮的节点全部搜索结束为止。比较指针L1和P1指向的指数，共有三种情况：(1)Ll->exp=Pl->exp；则两个多项式的系数相加减，得到的新和多项式节点插入到链表N中。L1、P1指针后移；(1)Ll->expexp；则将该L1所指节点赋给N1插入到链表N中。LI、P1指针后移;(2)Ll->exp>Pl->exp；则将该Pl所指节点赋给N1插入到链表N中。LI、P1指针后移。>算法的实现和测试结果：输入：Ll:53656700;L2:23354700;输出

6、:LI:5xA3+6xA5+6xA7；L2:2xA3+3xA5+4xA7；L1+L2:7xA3+9xA5+10xA7；L1-L2:3xA3+3xA5+2xA7nE:CONTDebugCONT.exe11Pleaseinputcoefandexpfronthekeyboard：53656700PolynomialLIis:5x^3+6xA5+6x^7Pleaseinputcoefandexpfronthekeyboard：23354700PolynomialL2is:2x^3+3xA5+4x^7Polyno

7、mialLI+L2is:7x^3*9x^5*10x^7PolynomialLI-L2is:Pressanykeytocontinue>算法时间复杂度分析该程序中建立单链表过程采用了单链表的后插入操作，其吋间复杂度T(n)=O(l)；当两个多项式相加减的时候，设L,p多项式分别有m>n项,其算法时间复杂度T(n)=O(m+n)o3.单链表基木操作练习>数据结构定义typedefintElemType;structLNode{ElemTypedata;structLNode*next;}；typedefLNode*

8、LinkList;>算法设计思路简介首先初始化两个带头结点的单链表L1,L2,要想实现两个链表的合并，可以将L2看成一个节点，将它插入到L1上即可。第一步遍历L1琏表到最后一个，然后把第二个链表的地址赋值给它的next,即可实现。>算法描述：初始时,指针L1指向L1链表的头节点,令Ll=Ll->next,L2=L2->next,然后从头开始扫描直到L1单链表屮为空，此时令Ll->nex