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

薃实验报告三线性表的链式存储薀班级:2010XXX姓名:HoogLe学号:2010XXXX专业:XXXX螆2858505197@螂实验目的:芀掌握单链表的基本操作的实现方法。虿掌握循环单链表的基本操作实现。膅掌握两有序链表的归并操作算法。薂实验内容:(请采用模板类及模板函数实现)莂1、线性表链式存储结构及基本操作算法实现螇[实现提示](同时可参见教材p64-p73页的ADT描述及算法实现及ppt)函数、类名称等可自定义,部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。薅所加载的库函数或常量定义:芃#include<iostream>蒃usingnamespacestd;腿(1)单链表存储结构类的定义:肄template<classT>肃classLinkList{芀public:芈 LinkList();//初始化带头结点空单链表构造函数实现螇 LinkList(Ta[],intn);//利用数组初始化带头结点的单链表构造函数实现螃 ~LinkList();节 intlength();//求单链表表长算法蚀 Tget(inti);//获得单链表中第i个结点的值算法膇 intlocate(Ttemp);薄 voidinsert(inti,Ttemp);//在带头结点单链表的第i个位置前插入元素e算法聿 TDelete(inti);//在带头结点单链表中删除第i个元素算法螈 voidprint();//遍历单链表元素算法薆 boolisEmpty();//判单链表表空算法芄 voiddeleleAll();//删除链表中所有结点算法(这里不是析构函数,但功能相同)膀private:袇 Node<T>*head;羆};羅(2)初始化带头结点空单链表构造函数实现膂输入:无艿前置条件:无蒅动作:初始化一个带头结点的空链表螅输出:无罿后置条件:头指针指向头结点。莈//初始化带头结点空单链表构造函数实现袄template<classT>蒅LinkList<T>::LinkList(){肁 head=newNode<T>;蚀 head->next=NULL;薈}羂肂(3)利用数组初始化带头结点的单链表构造函数实现袈输入:已存储数据的数组及数组中元素的个数羇前置条件:无螂动作:利用头插或尾插法创建带头结点的单链表衿输出:无羇后置条件:头指针指向头结点,且数组中的元素为链表中各结点的数据成员。莆//利用数组初始化带头结点的单链表构造函数实现蒂template<classT>羁LinkList<T>::LinkList(Ta[],intn){艿head=newNode<T>;袆head->next=NULL;膃for(inti=0;i<n;i++)肂{蒇Node<T>*s=newNode<T>;芅s->data=a[i];羃s->next=head->next;衿head->next=s;螀 }蚅}蚄(4)在带头结点单链表的第i个位置前插入元素e算法袁输入:插入位置i,待插入元素e袈前置条件:i的值要合法莈动作:在带头结点的单链表中第i个位置之前插入元素e蒄输出:无羂后置条件:单链表中增加了一个结点肇//在带头结点单链表的第i个位置前插入元素e算法袇template<classT>膄voidLinkList<T>::insert(inti,Ttemp){螀 Node<T>*p=head;荿 intcount=0;芇 while(p&&count<i-1)羅 {螁 p=p->next;蒇 count++;蚆 }蚅 if(p==NULL)cout<<"i不合法,越界!";袂 else{袀 Node<T>*s=newNode<T>;肅 s->data=temp;莅 s->next=p->next;蚀 p->next=s;羈 }薅}袂(5)在带头结点单链表中删除第i个元素算法蚁输入:删除第i个结点,待存放删除结点值变量e肆前置条件:单链表不空,i的值要合法羄动作:在带头结点的单链表中删除第i个结点,并返回该结点的值(由e传出)。蚂输出:无螂后置条件:单链表中减少了一个结点葿//在带头结点单链表中删除第i个元素算法蚈template<classT>莃TLinkList<T>::Delete(inti){薀 Node<T>*p=head;薇 intcount=0;肇 while(p&&count<i-1){膃 p=p->next;蚁 count++;羀 }蒆 if(p==NULL)cout<<"i不合法,越界!";袃 else{蚃 Node<T>*s=p->next;肈 Tx=s->data;羆 p->next=s->next;薄 returnx;蒀 }蒀}莅(6)遍历单链表元素算法莄输入:无薁前置条件:单链表不空蕿动作:遍历输出单链表中的各元素