数据结构上机实验 单链表.docx
- 文档编号:10894062
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:12
- 大小:16.33KB
数据结构上机实验 单链表.docx
《数据结构上机实验 单链表.docx》由会员分享,可在线阅读,更多相关《数据结构上机实验 单链表.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构上机实验单链表
数据结构上机实验
实验名称:
单链表实验
姓名我爱学习网
学号
专业班级独家提供
一.实验目的
⑴掌握线性表的链接存储结构;
⑵验证单链表及其基本操作的实现;
⑶进一步掌握数据结构及算法的程序实现的基本方法。
二.实验内容
⑴用头插法(或尾插法)建立带头结点的单链表;
⑵对已建立的单链表实现插入、删除、查找等基本操作。
三.设计与编码
1.理论知识:
(1)定义单链表的结点结构,定义单链表的数据类型,单链表类LinkList,包括插入,删除,查找等基本操作,为便于一个输出函数依次输出单链表的元素。
(2)体会加入模板后程序的变化,加入求线性表的长度等基本操作,重新给定测试数据,验证抛出异常机制;将单链表的结点结构用结点类实现。
(3)单链表存储,每一个非零项对应单链表中的一个结点,且单链表应按指数递增有序排列。
(4)将线性表的抽象数据类型定义在单链表存储结构下用c++的类实现。
由于线性表的数据元素不确定,所以采用c++的模板机制。
(5)遍历单链表是指按序号依次访问单链表的所有结点且仅访问一次。
(6)由于单链表类中没有存储线性的长度,因此,不能直接求得线性表的长度。
(7)在单链表中,即使知道被访问结点的位置,也不能像顺序表那样直接按序号访问,只能从头指针出发顺next域逐个结点往下搜索
2.算法与设计
(1)单链表遍历算法PrintList
template
voidLinkList
:
PrintList(){
Node
while(p!
=NULL){
cout<
if(p->next!
=NULL)
cout<<"+";
p=p->next;
}
cout< } (2)单链表插入算法Insert template voidLinkList : Insert(inti,Tx){ Node intj=1; while(p! =NULL&&j p=p->next; j++; } if(p! =NULL){ s=newNode s->data=x; s->next=p->next; p->next=s; } (3)单链表删除算法Delete template TLinkList : Delete(inti){ Tx; Node for(intj=0;j p=p->next; } x=p->data; q=p->next; p->next=q->next; deleteq; returnx; } (4)单链表查找算法Locate template intLinkList : Locate(Tx){ Node intn=1; while(p! =NULL){ if(p->data==x)returnn; p=p->next; n++; } return0; } 3.编码 Elem.cpp: #include"Elem.h" LinkList.cpp: #include"LinkList.h" #include template LinkList : LinkList(){ first=newNode first->next=NULL; } template LinkList : LinkList(Ta[],intn){ first=newNode first->next=NULL; for(inti=0;i Node p->data=a[n-i-1]; p->next=first->next; first->next=p; } } template voidLinkList : Insert(inti,Tx){ Node intj=1; while(p! =NULL&&j p=p->next; j++; } if(p! =NULL){ s=newNode s->data=x; s->next=p->next; p->next=s; } } template TLinkList : Delete(inti){ Tx; Node for(intj=0;j p=p->next; } x=p->data; q=p->next; p->next=q->next; deleteq; returnx; } template intLinkList : Locate(Tx){ Node intn=1; while(p! =NULL){ if(p->data==x)returnn; p=p->next; n++; } return0; } template voidLinkList : PrintList(){ Node while(p! =NULL){ cout< if(p->next! =NULL) cout<<"+"; p=p->next; } cout< } template LinkList : ~LinkList(){ Node while(first! =NULL){ p=first; first=first->next; deletep; } } LinkList_main.cpp: #include #include"LinkList.h" #include"LinkList.cpp" #include"Elem.h" voidAdd(LinkList voidmain(){ LinkList eleme; e.coef=10; e.exp=0; a.Insert(1,e); e.coef=20; e.exp=2; a.Insert(2,e); e.coef=10; e.exp=1; b.Insert(1,e); e.coef=20; e.exp=2; b.Insert(2,e); Add(a,b); a.PrintList(); } Yudxs.cpp: #include"LinkList.cpp" #include"Elem.h" #include voidAdd(LinkList Node Node Node Node while(p! =NULL&&q! =NULL){ if(p->data.exp pre=p; p=p->next; }elseif(p->data.exp>q->data.exp){ Node pre->next=q; q->next=p; q=v; }else{ p->data.coef=p->data.coef+q->data.coef; if(p->data.coef==0){ pre->next=p->next; deletep; p=pre->next; }else{ pre=p; p=p->next; } qre->next=q->next; deleteq; q=qre->next; }// } if(q! =NULL)pre->next=q; } Elem.h: #ifndefELEM_H #defineELEM_H #include classelem{ public: intcoef; intexp; friendostream&operator<<(ostream&out,elem&e){ out< returnout; } }; #endif LinkList.h: #ifndefLINKLIST_H #defineLINKLIST_H template classNode{ public: Tdata; Node }; template classLinkList{ public: LinkList(); LinkList(Ta[],intn); ~LinkList(); intLocate(Tx); voidInsert(inti,Tx); TDelete(inti); voidPrintList(); public: Node }; #endif 四.运行于测试 1.遇到问题: 没有发现问题 2.测试数据: LinkList eleme; e.coef=10; e.exp=0; a.Insert(1,e); e.coef=20; e.exp=2; a.Insert(2,e); e.coef=10; e.exp=1; b.Insert(1,e); e.coef=20; e.exp=2; b.Insert(2,e); Add(a,b); a.PrintList(); 测试结果: 10a0+10a1+40a2 3.运行结果: 10a0+10a1+40a2 五.总结与心得 1.进一步体会了单链表的存储结构,对其基本操作和实现有一定的理解。 2.能进一步理解算法与程序的关系,能够将单链表算法转化为对应的程序。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构上机实验 单链表 数据结构 上机 实验