实验3-线性表的链式存储.doc

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

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

2、tatype>classLinkList;templateclassNode{friendclassLinkList;private:Node*next;datatypedata;};templateclassLinkList{public:LinkList();//建立只有头结点的空链表LinkList(datatypea[],intn);//建立有n个元素的单链表~LinkList(){};//析构函数,释放整个链表空间intLength();//求单链表的长度datatyp

3、eGet(inti);//取单链表中第i个结点的元素值intLocation(datatypex);//求单链表中值为x的元素序号voidInsert(inti,datatypex);//在单链表中第i个位置插入元素值为x的结点datatypeDelete(inti);//在单链表中删除第i个结点voidPrintList();//遍历单链表，按序号依次输出各元素boolIsEmpty();//是否为空，空返回1，否则返回0voidDeleteAll();//删除所有的元素private:Node*head;//单链表的头指针};（2）初始化带头结点空单链表

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

5、e>::LinkList(datatypea[],intn){head=newNode;head->next=NULL;Node*s;for(inti=0;i;s->data=a[i];s->next=head->next;head->next=s;}}（４）在带头结点单链表的第i个位置前插入元素e算法输入：插入位置i，待插入元素e前置条件：i的值要合法动作：在带头结点的单链表中第i个位置之前插入元素e输出：无后置条件：单链表中增加了一个结点template

6、>voidLinkList::Insert(inti,datatypex){Node*p=head;intj=0;while(p&&jnext;j++;}if(!p)throw"i不合法";else{Node*s=newNode;s->data=x;s->next=p->next;p->next=s;}}（５）在带头结点单链表中删除第i个元素算法输入：删除第i个结点，待存放删除结点值变量e前置条件：单链表不空，i的值要合法动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（

7、由e传出）。输出：无后置条件：单链表中减少了一个结点templatedatatypeLinkList::Delete(inti){Node*p;p=head;intj=0;while(p&&jnext;j++;}if(!p

8、

9、!p->next){throw"i不合法";}else{Node*q;datatypex;q=p->next;x=q->data;p->next=q->nex