欢迎来到天天文库
浏览记录
ID:55635192
大小:109.48 KB
页数:12页
时间:2020-05-21
《数据结构实验报告三线性表的链式存储.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、实验报告三线性表的链式存储班级:2010XXX姓名:HoogLe学号:2010XXXX专业:XXXX@qq.com一、实验目的:(1)掌握单链表的基本操作的实现方法。(2)掌握循环单链表的基本操作实现。(3)掌握两有序链表的归并操作算法。二、实验内容:(请采用模板类及模板函数实现)1、线性表链式存储结构及基本操作算法实现[实现提示](同时可参见教材p64-p73页的ADT描述及算法实现及ppt)函数、类名称等可自定义,部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义:#includeusingnamespacestd;(1)单链表存储结
2、构类的定义:templateclassLinkList{public:LinkList();//初始化带头结点空单链表构造函数实现LinkList(Ta[],intn);//利用数组初始化带头结点的单链表构造函数实现~LinkList();intlength();//求单链表表长算法Tget(inti);//获得单链表中第i个结点的值算法intlocate(Ttemp);voidinsert(inti,Ttemp);//在带头结点单链表的第i个位置前插入元素e算法TDelete(inti);//在带头结点单链表中删除第i个元素算法voidprint();//遍历单链表元素算法b
3、oolisEmpty();//判单链表表空算法voiddeleleAll();//删除链表中所有结点算法(这里不是析构函数,但功能相同)private:Node*head;};(2)初始化带头结点空单链表构造函数实现输入:无前置条件:无动作:初始化一个带头结点的空链表输出:无后置条件:头指针指向头结点。//初始化带头结点空单链表构造函数实现templateLinkList::LinkList(){head=newNode;head->next=NULL;}(3)利用数组初始化带头结点的单链表构造函数实现输入:已存储数据的数组及数组中元素的个数前置条件:无动作:
4、利用头插或尾插法创建带头结点的单链表输出:无后置条件:头指针指向头结点,且数组中的元素为链表中各结点的数据成员。//利用数组初始化带头结点的单链表构造函数实现templateLinkList::LinkList(Ta[],intn){head=newNode;head->next=NULL;for(inti=0;i*s=newNode;s->data=a[i];s->next=head->next;head->next=s;}}(4)在带头结点单链表的第i个位置前插入元素e算法输入:插入位置i,待插入元素e前置条件:i的值要合法动
5、作:在带头结点的单链表中第i个位置之前插入元素e输出:无后置条件:单链表中增加了一个结点//在带头结点单链表的第i个位置前插入元素e算法templatevoidLinkList::insert(inti,Ttemp){Node*p=head;intcount=0;while(p&&countnext;count++;}if(p==NULL)cout<<"i不合法,越界!";else{Node*s=newNode;s->data=temp;s->next=p->next;p->next=s;}}(5)在带头结点单链表中删除第i个元素算
6、法输入:删除第i个结点,待存放删除结点值变量e前置条件:单链表不空,i的值要合法动作:在带头结点的单链表中删除第i个结点,并返回该结点的值(由e传出)。输出:无后置条件:单链表中减少了一个结点//在带头结点单链表中删除第i个元素算法templateTLinkList::Delete(inti){Node*p=head;intcount=0;while(p&&countnext;count++;}if(p==NULL)cout<<"i不合法,越界!";else{Node*s=p->next;Tx=s->data;p->next=s->nex
7、t;returnx;}}(6)遍历单链表元素算法输入:无前置条件:单链表不空动作:遍历输出单链表中的各元素。输出:无后置条件:无//遍历单链表元素算法templatevoidLinkList::print(){Node*p=head->next;while(p){cout<data<<"";p=p->next;}cout<
此文档下载收益归作者所有