数据结构实验报告三线性表的链式存储

实验报告三线性表的链式存储班级：2010XXX姓名：HoogLe学号：2010XXXX专业：[e-mail]一、实验目的：（1）掌握单链表的基本操作的实现方法。（2）掌握循环单链表的基本操作实现。（3）掌握两有序链表的归并操作算法。二、实验内容：（请采用模板类及模板函数实现）1、线性表链式存储结构及基本操作算法实现[实现提示]（同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义：#includeiostreamusingnamespacestd;（1）单链表存储结构类的定义：templateclassTclassLinkList{public:LinkList();//初始化带头结点空单链表构造函数实现LinkList(Ta[],intn);//利用数组初始化带头结点的单链表构造函数实现~LinkList();intlength();//求单链表表长算法Tget(inti);//获得单链表中第i个结点的值算法intlocate(Ttemp);voidinsert(inti,Ttemp);//在带头结点单链表的第i个位置前插入元素e算法TDelete(inti);//在带头结点单链表中删除第i个元素算法voidprint();//遍历单链表元素算法boolisEmpty();//判单链表表空算法voiddeleleAll();//删除链表中所有结点算法（这里不是析构函数，但功能相同）private:NodeT*head;};（2）初始化带头结点空单链表构造函数实现输入：无前置条件：无动作：初始化一个带头结点的空链表输出：无后置条件：头指针指向头结点。//初始化带头结点空单链表构造函数实现templateclassTLinkListT::LinkList(){head=newNodeT;head-next=NULL;}（３）利用数组初始化带头结点的单链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。//利用数组初始化带头结点的单链表构造函数实现templateclassTLinkListT::LinkList(Ta[],intn){head=newNodeT;head-next=NULL;for(inti=0;in;i++){NodeT*s=newNodeT;s-data=a[i];s-next=head-next;head-next=s;}}（４）在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i，待插入元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中增加了一个结点//在带头结点单链表的第i个位置前插入元素e算法templateclassTvoidLinkListT::insert(inti,Ttemp){NodeT*p=head;intcount=0;while(p&&counti-1){p=p-next;count++;}if(p==NULL)couti不合法，越界!;else{NodeT*s=newNodeT;s-data=temp;s-next=p-next;p-next=s;}}（５）在带头结点单链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单链表不空，i的值要合法动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单链表中减少了一个结点//在带头结点单链表中删除第i个元素算法templateclassTTLinkListT::Delete(inti){NodeT*p=head;intcount=0;while(p&&counti-1){p=p-next;count++;}if(p==NULL)couti不合法，越界!;else{NodeT*s=p-next;Tx=s-data;p-next=s-next;returnx;}}（６）遍历单链表元素算法输入：无前置条件：单链表不空动作：遍历输出单链表中的各元素。输出：无后置条件：无//遍历单链表元素算法templateclassTvoidLinkListT::print(){NodeT*p=head-next;while(p){coutp-data;p=p-next;}coutendl;}（７）求单链表表长算法。输入：无前置条件：无动作：求单链表中元素个数。输出：返回元素个数后置条件：无//求单链表表长算法templateclassTintLinkListT::length(){NodeT*p=head;intcount=0;while(p){p=p-next;count++;}return--count;}（８）判单链表表空算法输入：无前置条件：无动作：判表是否为空。输出：为空时返回１，不为空时返回0后置条件：无//判断非空templateclassTboolLinkListT::isEmpty(){NodeT*p=head-next;if(p)returntrue;elsereturnfalse;}（９）获得单链表中第i个结点的值算法输入：无前置条件：i不空，i合法动作：找到第i个结点。输出：返回第i个结点的元素值。后置条件：无//获得单链表中第i个结点的值算法templateclassTTLinkListT::get(inti){NodeT*p=head;intcount=0;while(p&&counti){p=p-next;count++;}if(p==NULL)couti不合法，越界!;else{returnp-data;}}(10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无前置条件：单链表存在动作：清除单链表中所有的结点。输出：无后置条件：头指针指向空//删除所有元素templateclassTvoidLinkListT::deleleAll(){NodeT*p=head;while(p){NodeT*t=p;p=p-next;t-next=NULL;}}(11)上机实现以上基本操作，写出main()程序：参考p72voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,0};//测试带参数的构造函数（前端插入！）LinkListintlist1(a,10);//测试插入if(list1.isEmpty()){cout链表不为空!endl;}else{cout链表为空!endl;}list1.print();cout测试插入endl;list1.insert(5,20);list1.print();cout测试表长endl;coutlist1.length()endl;cout测试删除endl;coutlist1.Delete(5)endl;list1.print();cout测试得到第5个元素endl;coutlist1.get(5)endl;cout测试删除所有元素!endl;list1.deleleAll();list1.print();}粘贴测试数据及运行结果：2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。templateclassTclassLinkList{public:LinkList(Ta[],intn);//利用数组初始化带头结点的单循环链表构造函数实现voidinsert(inti,Ttemp);//在带头结点单循环链表的第i个位置前插入元素e算法TDelete(inti);//在带头结点单循环链表中删除第i个元素算法voidprint();//遍历单循环链表元素算法private:NodeT*head;intlength;};（１）利用数组初始化带头结点的单循环链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单循环链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。//利用数组初始化带头结点的单循环链表构造函数实现templateclassTLinkListT::LinkList(Ta[],intn){head=newNodeT;head-next=head;length=0;for(inti=0;in;i++){NodeT*s=newNodeT;s-data=a[i];s-next=head-next;head-next=s;length++;}}（２）在带头结点单循环链表的第i个位置前插入元素e算法输入：插入位置i，待插入元素e前置条件：i的值要合法动作：在带头结点的单循环链表中第i个位置之前插入元素e输出：无后置条件：单循环链表中增加了一个结点//在带头结点单循环链表的第i个位置前插入元素e算法templateclassTvoidLinkListT::insert(inti,Ttemp){coutthis-lengthendl;NodeT*p=head;intcount=0;if(ilength)couti不合法，越界!;else{while(counti-1){p=p-next;count++;}NodeT*s=newNodeT;s-data=temp;s-next=p-next;p-next=s;}}（３）在带头结点单循环链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单循环链表不空，i的值要合法动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单循环链表中减少了一个结点//在带头结点单循环链表中删除第i个元素算法templateclassTTLinkListT::Delete(inti){NodeT*p=head;intcount=0;if(ilength)couti不合法，越界!endl;else{while(counti-1){p=p-next;count++;}NodeT*s=p-next;Tx=s-data;p-next=s-next;returnx;}}（４）遍历单循环链表元素算法输入：无前置条件：单循环链表不空动作：遍历输出单循环链表中的各元素。输出：无后置条件：无//遍历单循环链表元素算法templateclassTvoidLinkListT::print(){NodeT*p=head-next;while(p!=head){coutp-data;p=p-next;}coutendl;}(５)上机实现以上基本操作，写出main()程序：voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,0};//测试带参数的构造函数（前端插入！）LinkListintlist1(a,10);list1.print();cout测试插入endl;list1.insert(5,20);list1.print();cout测试删除操作endl;list1.Delete(5);list1.print();}粘贴测试数据及运行结果：３、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表