实验3 线性表的链式存储fanglichun

《实验3 线性表的链式存储fanglichun》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、d;template//模板类型为datatypeclasslinklist;//前视定义,否则有元类无法定义templateclassnode//节点类{friendclasslinklist;//定义有元类private:datatypedata;//该结点的数据域node*next;//指向下一结点的指针};templateclasslinklist//链表类{private:node*head;//定义头指针public:link

3、list();//无参构造函数linklist(datatypea[],intn);//有参构造函数~linklist();//析构函数intlength();//求当前链表的元素个数datatypegetdata(inti);//获取第i个结点的元素//intlocate(Tx);//按位查找datatypeInsert(inti,datatypeitem);datatypeDelete(inti);//删除第i个结点的元素voidprintlist();//便利链表元素intempty();//判断链表是否为空voiddestroy();//删除所有结点元素};/*（2）初始化带头

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

5、linklist::linklist(datatypea[],intn)//带参数的构造函数的实{node*s;head=newnode;head->next=NULL;//头指针初始化为空for(inti=0;i;s->data=a[i];s->next=head->next;head->next=s;}}/*（４）在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i，待插入元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置

6、条件：单链表中增加了一个结点*/templatedatatypelinklist::Insert(inti,datatypeitem)//在第i个结点元素前插入元素item{node*p;intj;//计数器p=head;j=0;//指针p初始化while(p&&jnext;//指针p后移j++;}//找插入点if(!p)throw"i不合法!";else{node*s;s=newnode;//申请一个结点s->data=item;/将插入元素保存在P结点中s

7、->next=p->next;p->next=s;returnitem;//返回插入元素}}/*（５）在带头结点单链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单链表不空，i的值要合法动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。输出：无后置条件：单链表中减少了一个结点*/templatedatatypelinklist::Delete(