实验3线性表的链式存储

1、实验报告三 线性表的链式存储班级： 2010251 姓名： 李鑫 学号： 20103277 专业： 信息安全 一、 实验目的：（1） 掌握单链表的基本操作的实现方法。（2） 掌握循环单链表的基本操作实现。（3） 掌握两有序链表的归并操作算法。二、 实验内容：（请采用模板类及模板函数实现）1、线性表链式存储结构及基本操作算法实现实现提示 （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义：（1） 单链表存储结构类的定义：/文件包含在LinList.h中template &l

2、t;class datatype>class LinkList;template <class datatype>class Nodefriend class LinkList<datatype>private:Node<datatype> *next;datatype data;template <class datatype>class LinkListpublic:LinkList();/建立只有头结点的空链表LinkList(datatype a,int n);/建立有n个元素的单链表LinkList();/析构函数,释放整个链表空

3、间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();/是否为空，空返回1，否则返回0void DeleteAll();/删除所有的元素private:Node<datatype>

4、; *head;/单链表的头指针;（2）初始化带头结点空单链表构造函数实现输入：无前置条件：无动作：初始化一个带头结点的空链表输出：无后置条件：头指针指向头结点。template <class datatype>LinkList<datatype>:LinkList()head=new Node<datatype>head->next=NULL;（）利用数组初始化带头结点的单链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据

5、成员。template <class datatype>LinkList<datatype>:LinkList(datatype a,int n)head=new Node<datatype>head->next=NULL;Node<datatype> *s;for (int i=0;i<n;i+)s=new Node<datatype> s->data=ai;s->next=head->next;head->next=s;（）在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i，待插入元素

6、e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中增加了一个结点 template <class datatype>void LinkList<datatype>:Insert(int i,datatype x)Node<datatype> *p=head;int j=0;while(p&&j<i)p=p->next;j+;if(!p) throw "i不合法"elseNode<datatype> *s=new Node<datatype>

7、;s->data=x;s->next=p->next;p->next=s;（）在带头结点单链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单链表不空，i的值要合法动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单链表中减少了一个结点 template <class datatype>datatype LinkList<datatype>:Delete(int i)Node<datatype> *p;p=head;int j=0;while(p&&j

8、<i-1)p=p->next;j+;if (!p|!p->next)throw "i不合法" elseNode<datatype> *q;datatype x;q=p->next;x=q->data;p->next=q->next;delete q;return x;（）遍历单链表元素算法输入：无前置条件：单链表不空动作：遍历输出单链表中的各元素。输出：无后置条件：无template <class datatype>void LinkList<datatype>:PrintList()Node&l

9、t;datatype> *p;p=head;if (!p->next)cout<<"表为空"elsewhile(p->next)p=p->next;cout<<p->data<<" "/*Node<datatype> *p=head->next;while(p)cout<<p->data<<" "p=p->next;*/（）求单链表表长算法。输入：无前置条件：无动作：求单链表中元素个数。输出：返回元素个数后置条件：无

10、template <class datatype>int LinkList<datatype>:Length()Node<datatype> *p;int i=0;p=head->next;while(p)i+;p=p->next;return i;（）判单链表表空算法输入：无前置条件：无动作：判表是否为空。输出：为空时返回，不为空时返回0后置条件：无template <class datatype>bool LinkList<datatype>:IsEmpty()if (head->next=NULL) retur

11、n 1;/if(!head->next) return 1;return 0;/*if(this->Length()=0)return 1;*/（）获得单链表中第i个结点的值算法输入：无前置条件：i不空，i合法动作：找到第i个结点。输出：返回第i个结点的元素值。后置条件：无template <class datatype>datatype LinkList<datatype>:Get(int i)Node<datatype> *p=head->next;int j=1;while(p&&j<i)/为ip=p->n

12、ext;j+;if(!p) throw "i不合法"else return p->data; / p->next->data;错误(10)删除链表中所有结点算法（这里不是析构函数，但功能相同）输入：无前置条件：单链表存在动作：清除单链表中所有的结点。输出：无后置条件：头指针指向空template <class datatype>void LinkList<datatype>:DeleteAll()/*Node<datatype> *p;while(head->next)p=head->next;head-&g

13、t;next=p->next;delete p;*/Node<datatype> *p,*q; p=head; while (p) q=p; p=p->next; delete q; head->next=NULL; (11)上机实现以上基本操作，写出main()程序：参考p72void main()int s=10,9,8,7,6,5,4,3,2,1;int n=10;cout<<"构造函数插入元素："<<endl;LinkList<int> mylist1(s,10);mylist1.PrintList(

14、);cout<<endl;cout<<"删除全部元素后为："<<endl;mylist1.DeleteAll();mylist1.PrintList();cout<<endl<<"单链表为空(1是，0不是):"<<mylist1.IsEmpty()<<endl;LinkList<int> mylist;cout<<endl<<"非构造函数插入元素："<<endl;for(int i=0;i<10;i

15、+)mylist.Insert(i,si);/mylist.Insert(0,10);/mylist.Insert(1,9);mylist.PrintList();cout<<endl;cout<<"表长为："<<mylist.Length()<<endl;cout<<"得到第3个元素为："<<mylist.Get(3)<<endl;cout<<"删除第7个元素为："<<mylist.Delete(7)<<endl;

16、cout<<"单链表为："mylist.PrintList();cout<<endl;cout<<"第5个元素后插入99后单链表为："mylist.Insert(5,99);cout<<endl;mylist.PrintList();cout<<endl;粘贴测试数据及运行结果：2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。（）利用数组初始化带头结点的单循环链表构造函数实现输入：已存储数据的数组及数组中元素的个数前置条件：无动作：利用头插或尾插法创建带头结点的单循环

17、链表输出：无后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。template <class datatype>class LinkList;template <class datatype>class Nodefriend class LinkList<datatype>private:Node<datatype> *next;datatype data;template <class datatype>class LinkListpublic:LinkList();/建立只有头结点的空链表Lin

18、kList(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();/voi

19、d DeleteAll();/void sort();private:Node<datatype> *head;/单链表的头指针;template <class datatype>LinkList<datatype>:LinkList()head=new Node<datatype>head->next=head;template <class datatype>LinkList<datatype>:LinkList(datatype a,int n)head=new Node<datatype>head

20、->next=head;Node<datatype> *s;for (int i=0;i<n;i+)s=new Node<datatype> s->data=ai;s->next=head->next;head->next=s;（）在带头结点单循环链表的第i个位置前插入元素e算法输入：插入位置i，待插入元素e前置条件：i的值要合法动作：在带头结点的单循环链表中第i个位置之前插入元素e输出：无后置条件：单循环链表中增加了一个结点 template <class datatype>void LinkList<dataty

21、pe>:Insert(int i,datatype x)/1<=i<=n;Node<datatype> *p=head;int j=0;while(p->next!=head&&j<i-1)p=p->next;j+;if(j!=i-1) throw "i不合法"elseNode<datatype> *s=new Node<datatype>s->data=x;s->next=p->next;p->next=s;（）在带头结点单循环链表中删除第i个元素算法输入：删除

22、第i个结点，待存放删除结点值变量e前置条件：单循环链表不空，i的值要合法动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单循环链表中减少了一个结点 template <class datatype>datatype LinkList<datatype>:Delete(int i)Node<datatype> *p;p=head;int j=0;while(p->next!=head&&j<i-1)p=p->next;j+;if (j!=i-1|p->next=head)/c

23、out<<"i不合法"throw "i不合法" elseNode<datatype> *q;datatype x;q=p->next;x=q->data;p->next=q->next;delete q;return x;（）遍历单循环链表元素算法输入：无前置条件：单循环链表不空动作：遍历输出单循环链表中的各元素。输出：无后置条件：无template <class datatype>void LinkList<datatype>:PrintList()Node<datatype

24、> *p;p=head;if (p->next=head)cout<<"表为空"elsewhile(p->next!=head)p=p->next;cout<<p->data<<" "/*Node<datatype> *p=head->next;while(p)cout<<p->data<<" "p=p->next;*/()上机实现以上基本操作，写出main()程序：#include <iostream.h&g

25、t;#include "LinList.h"void main()int a=1,5,8,2,9,4,3,6,7,10,n=10;LinkList<int> mylist(a,10);cout<<"循环链表为："<<endl;mylist.PrintList();cout<<endl;cout<<"在第一个元素前插入20后为："<<endl;mylist.Insert(1,20);mylist.PrintList();cout<<endl;cout&l

26、t;<"在第三个元素前插入30后为："<<endl;mylist.Insert(3,30);mylist.PrintList();cout<<endl;cout<<"删除第一个元素后为："<<endl;mylist.Delete(1);mylist.PrintList();cout<<endl;cout<<"删除最后一个元素后为："<<endl;mylist.Delete(11);mylist.PrintList();cout<<en

27、dl;粘贴测试数据及运行结果：、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。模板函数：#include <iostream.h>#include <stdlib.h>#include "LinList.h"template <class datatype>void LinkList<datatype>:sort()Node<datatype> *r=head->next;datatyp

28、e temp;/*for (i=0;i<Length();i+)Node<datatype> *s=r->next;for(j=i+1;j<Length();j+)if (r->data>s->data)temp=r->data;r->data=s->data;s->data=temp;s=s->next;/delete q;delete s;r=r->next;delete r;*/while(r)Node<datatype> *s=r->next;while(s)if (r->dat

29、a>s->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<int> mylist1(La,10);LinkList<int> mylist2(Lb,8);cout<<"La链表为："<<end

30、l;mylist1.PrintList();cout<<endl;cout<<"Lb链表为："<<endl;mylist2.PrintList();cout<<endl;cout<<"排序后，La链表为："<<endl;mylist1.sort();mylist1.PrintList();cout<<endl;cout<<"排序后，Lb链表为："<<endl;mylist2.sort();mylist2.PrintList();cout<<endl;cout<<"将Lb链表插入La链表后为："<<endl;for (int i=1;i<mylist2.Length()+1;i+)mylist1.Insert(mylist1.Length(),mylist2.