《实验3-线性表的链式存储(共15页).doc》由会员分享，可在线阅读，更多相关《实验3-线性表的链式存储(共15页).doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上实验报告三 线性表的链式存储班级： 姓名： 李鑫 学号： 专业： 信息安全 一、 实验目的：（1） 掌握单链表的基本操作的实现方法。（2） 掌握循环单链表的基本操作实现。（3） 掌握两有序链表的归并操作算法。二、 实验内容：（请采用模板类及模板函数实现）1、线性表链式存储结构及基本操作算法实现实现提示 （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义：（1） 单链表存储结构类的定义：/文件包含在LinList.h中template class
2、LinkList;template class Nodefriend class LinkList;private:Node *next;datatype data;template class LinkListpublic:LinkList();/建立只有头结点的空链表LinkList(datatype a,int n);/建立有n个元素的单链表LinkList();/析构函数,释放整个链表空间int Length();/求单链表的长度datatype Get(int i);/取单链表中第i个结点的元素值int Location(datatype x);/求单链表中值为x的元素序号void
3、Insert(int i,datatype x);/在单链表中第i个位置插入元素值为x的结点datatype Delete(int i);/在单链表中删除第i个结点void PrintList();/遍历单链表，按序号依次输出各元素bool IsEmpty();/是否为空，空返回1，否则返回0void DeleteAll();/删除所有的元素private:Node *head;/单链表的头指针;（2）初始化带头结点空单链表构造函数实现输入：无前置条件：无动作：初始化一个带头结点的空链表输出：无后置条件：头指针指向头结点。template LinkList:LinkList()head=new
4、 Node;head-next=NULL;（）利用数组初始化带头结点的单链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。template LinkList:LinkList(datatype a,int n)head=new Node;head-next=NULL;Node *s;for (int i=0;in;i+)s=new Node; s-data=ai;s-next=head-next;head-next=s;（）在带头结点单链表的第i个位置前插入元
5、素e算法输入：插入位置i，待插入元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中增加了一个结点 template void LinkList:Insert(int i,datatype x)Node *p=head;int j=0;while(p&jnext;j+;if(!p) throw i不合法;elseNode *s=new Node;s-data=x;s-next=p-next;p-next=s;（）在带头结点单链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单链表不空，i的值要合法动作：在带头结点的
6、单链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单链表中减少了一个结点 template datatype LinkList:Delete(int i)Node *p;p=head;int j=0;while(p&jnext;j+;if (!p|!p-next)throw i不合法; elseNode *q;datatype x;q=p-next;x=q-data;p-next=q-next;delete q;return x;（）遍历单链表元素算法输入：无前置条件：单链表不空动作：遍历输出单链表中的各元素。输出：无后置条件：无template void LinkLis
7、t:PrintList()Node *p;p=head;if (!p-next)coutnext)p=p-next;coutdata ;/*Node *p=head-next;while(p)coutdatanext;*/（）求单链表表长算法。输入：无前置条件：无动作：求单链表中元素个数。输出：返回元素个数后置条件：无template int LinkList:Length()Node *p;int i=0;p=head-next;while(p)i+;p=p-next;return i;（）判单链表表空算法输入：无前置条件：无动作：判表是否为空。输出：为空时返回，不为空时返回0后置条件：无t
8、emplate bool LinkList:IsEmpty()if (head-next=NULL) return 1;/if(!head-next) return 1;return 0;/*if(this-Length()=0)return 1;*/（）获得单链表中第i个结点的值算法输入：无前置条件：i不空，i合法动作：找到第i个结点。输出：返回第i个结点的元素值。后置条件：无template datatype LinkList:Get(int i)Node *p=head-next;int j=1;while(p&jnext;j+;if(!p) throw i不合法;else return
9、 p-data; / p-next-data;错误(10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无前置条件：单链表存在动作：清除单链表中所有的结点。输出：无后置条件：头指针指向空template void LinkList:DeleteAll()/*Node *p;while(head-next)p=head-next;head-next=p-next;delete p;*/Node *p,*q; p=head; while (p) q=p; p=p-next; delete q; head-next=NULL; (11)上机实现以上基本操作，写出main()程序：参考p
10、72void main()int s=10,9,8,7,6,5,4,3,2,1;int n=10;cout构造函数插入元素：endl;LinkList mylist1(s,10);mylist1.PrintList();coutendl;cout删除全部元素后为：endl;mylist1.DeleteAll();mylist1.PrintList();coutendl单链表为空(1是，0不是):mylist1.IsEmpty()endl;LinkList mylist;coutendl非构造函数插入元素：endl;for(int i=0;i10;i+)mylist.Insert(i,si);/
11、mylist.Insert(0,10);/mylist.Insert(1,9);mylist.PrintList();coutendl;cout表长为：mylist.Length()endl;cout得到第3个元素为：mylist.Get(3)endl;cout删除第7个元素为：mylist.Delete(7)endl;cout单链表为：;mylist.PrintList();coutendl;cout第5个元素后插入99后单链表为：;mylist.Insert(5,99);coutendl;mylist.PrintList();coutendl;粘贴测试数据及运行结果：2、参考单链表操作定义
12、与实现，自行完成单循环链表的类的定义与相操作操作算法。（）利用数组初始化带头结点的单循环链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单循环链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。template class LinkList;template class Nodefriend class LinkList;private:Node *next;datatype data;template class LinkListpublic:LinkList();/建立只有头结点的空链表L
13、inkList(datatype a,int n);/建立有n个元素的单链表LinkList();/析构函数,释放整个链表空间/int Length();/求单链表的长度/datatype Get(int i);/取单链表中第i个结点的元素值/int Location(datatype x);/求单链表中值为x的元素序号void Insert(int i,datatype x);/在单链表中第i个位置插入元素值为x的结点datatype Delete(int i);/在单链表中删除第i个结点void PrintList();/遍历单链表，按序号依次输出各元素/bool IsEmpty();/v
14、oid DeleteAll();/void sort();private:Node *head;/单链表的头指针;template LinkList:LinkList()head=new Node;head-next=head;template LinkList:LinkList(datatype a,int n)head=new Node;head-next=head;Node *s;for (int i=0;in;i+)s=new Node; s-data=ai;s-next=head-next;head-next=s;（）在带头结点单循环链表的第i个位置前插入元素e算法输入：插入位置i，
15、待插入元素e前置条件：i的值要合法动作：在带头结点的单循环链表中第i个位置之前插入元素e输出：无后置条件：单循环链表中增加了一个结点 template void LinkList:Insert(int i,datatype x)/1=i=n;Node *p=head;int j=0;while(p-next!=head&jnext;j+;if(j!=i-1) throw i不合法;elseNode *s=new Node;s-data=x;s-next=p-next;p-next=s;（）在带头结点单循环链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单循环链表不
16、空，i的值要合法动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单循环链表中减少了一个结点 template datatype LinkList:Delete(int i)Node *p;p=head;int j=0;while(p-next!=head&jnext;j+;if (j!=i-1|p-next=head)/couti不合法;throw i不合法; elseNode *q;datatype x;q=p-next;x=q-data;p-next=q-next;delete q;return x;（）遍历单循环链表元素算法输入：无前置条件：
17、单循环链表不空动作：遍历输出单循环链表中的各元素。输出：无后置条件：无template void LinkList:PrintList()Node *p;p=head;if (p-next=head)coutnext!=head)p=p-next;coutdata ;/*Node *p=head-next;while(p)coutdatanext;*/()上机实现以上基本操作，写出main()程序：#include #include LinList.hvoid main()int a=1,5,8,2,9,4,3,6,7,10,n=10;LinkList mylist(a,10);cout循环链
18、表为：endl;mylist.PrintList();coutendl;cout在第一个元素前插入20后为：endl;mylist.Insert(1,20);mylist.PrintList();coutendl;cout在第三个元素前插入30后为：endl;mylist.Insert(3,30);mylist.PrintList();coutendl;cout删除第一个元素后为：endl;mylist.Delete(1);mylist.PrintList();coutendl;cout删除最后一个元素后为：endl;mylist.Delete(11);mylist.PrintList();c
19、outendl;粘贴测试数据及运行结果：、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。模板函数：#include #include #include LinList.htemplate void LinkList:sort()Node *r=head-next;datatype temp;/*for (i=0;iLength();i+)Node *s=r-next;for(j=i+1;jdatas-data)temp=r-data;r-data=s-data;s-dat
20、a=temp;s=s-next;/delete q;delete s;r=r-next;delete r;*/while(r)Node *s=r-next;while(s)if (r-datas-data)temp=r-data;r-data=s-data;s-data=temp;s=s-next;delete s;r=r-next;delete r;void main()int La=1,5,2,7,6,9,3,8,4,10,n=10;int Lb=3,55,66,77,1,88,2,44,m=8;LinkList mylist1(La,10);LinkList mylist2(Lb,8);
21、coutLa链表为：endl;mylist1.PrintList();coutendl;coutLb链表为：endl;mylist2.PrintList();coutendl;cout排序后，La链表为：endl;mylist1.sort();mylist1.PrintList();coutendl;cout排序后，Lb链表为：endl;mylist2.sort();mylist2.PrintList();coutendl;cout将Lb链表插入La链表后为：endl;for (int i=1;imylist2.Length()+1;i+)mylist1.Insert(mylist1.Length(),mylist2.Get(i);mylist1.PrintList();coutendl;coutLc链表为：endl;mylist1.sort();mylist1.PrintList();coutnext=NULL;/NULL赋给head-next;while(p&jnext=NULL;while(p)i+;p=p-next;这样的循环要注意，很容易产生无限循环。专心-专注-专业