北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx
- 文档编号:13133234
- 上传时间:2023-06-11
- 格式:DOCX
- 页数:26
- 大小:143.54KB
北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx
《北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx》由会员分享,可在线阅读,更多相关《北京邮电大学 数据结构 实验一 带头结点的单链表构造.docx(26页珍藏版)》请在冰点文库上搜索。
北京邮电大学数据结构实验一带头结点的单链表构造
数据结构实验报告
实验名称:
实验1——单链表的构造
学生姓名:
XXXXNB
班级:
XXXX
班内序号:
学号:
XXXX
日期:
XXXXX
1.实验要求
根据线性表的抽象数据类型的定义,完成带头结点的单链表的基本功能。
单链表的基本功能:
1、构造:
使用头插法、尾插法两种方法
2、插入:
要求建立的链表按照关键字从小到大有序
3、删除
4、查找
5、获取链表长度
6、销毁
7、其他:
可自行定义
编写测试main()函数测试线性表的正确性。
2.程序分
编程完成单链表的一般性功能如单链表的构造:
使用头插法、尾插法两种方法插入:
要求建立的链表按照关键字从小到大有序,删除,查找,获取链表长度,销毁
用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。
本程序为使用方便,几乎不用特殊的命令,只需按提示输入即可,适合更多的用户使用。
2.1存储结构
单链表的存储结构:
2.2关键算法分析
1.头插法
自然语言描述:
a.在堆中建立新结点
b.将a[i]写入到新结点的数据域
c.修改新结点的指针域
d.修改头结点的指针域,将新结点加入链表中
//在构建之初为了链表的美观性构造,进行了排序
代码描述:
//头插法构造函数
template
LinkList
:
LinkList(Ta[],intn)
{
for(inti=n-1;i>=1;i--)//冒泡排序,对数组进行从小到大排序
{
for(intj=0;j
{
if(a[j]>a[j+1])
{
Tt=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
front=newNode
front->next=NULL;//构造空单链表
for(inti=n-1;i>=0;i--)
{
Node
s->data=a[i];//将a[i]写入新结点的数据域
s->next=front->next;//修改新结点的指针域
front->next=s;//修改头结点的指针域,将新结点加入到链表中
}
}
2.尾插法
自然语言描述:
a.在堆中建立新结点
b.将a[i]写入到新结点的数据域
c.将新结点加入到链表中
d.修改修改尾指针
代码描述:
//尾插法构造函数
template
LinkList
:
LinkList(Ta[],intn)
{
front=newNode
Node
for(inti=0;i { Node s->data=a[i]; r->next=s; r=s; } r->next=NULL; } 时间复杂度: O(n) 3.析构函数 自然语言描述: a.新建立一个指针,指向头结点 b.移动a中建立的指针 c.逐个释放指针 代码描述: template LinkList : ~LinkList()//析构函数,销毁链表 { Node while(p) { front=p; p=p->next; deletefront; } } 4.按位查找函数 自然语言描述: a.初始化工作指针p和计数器j,p指向第一个结点,j=1 b.循环以下操作,直到p为空或者j等于1 b1: p指向下一个结点 b2: j加1 c.若p为空,说明第i个元素不存在,抛出异常 d.否则,说明p指向的元素就是所查找的元素,返回元素地址 代码描述: template Node : Get(inti)//按位查找 { Node intj=0; while(p) { if(j { p=p->next; j++; } elsebreak; } if(! p)throw"查找位置非法"; elsereturnp; } 时间复杂度: O(n) 5.按值查找函数 自然语言描述: a.初始化工作指针p和计数器j,p指向第一个结点,j=1 b.循环以下操作,找到这个元素或者p指向最后一个结点 b1.判断p指向的结点是不是要查找的值,如果是,返回j; b2.否则p指向下一个结点,并且j的值加一 c.如果找到最后一个结点还没有找到要查找的元素,返回查找失败信息代码描述: template intLinkList : Locate(Tx)//按值查找 { Node intj=1; while(p) { if(p->data==x)returnj; else { p=p->next; j++; } } return-1; } 时间复杂度: O(n) 6.插入函数 自然语言描述: a.在堆中建立新结点 b.将要插入的结点的数据写入到新结点的数据域 c.修改新结点的指针域 d.修改前一个指针的指针域,使其指向新插入的结点的位置 代码描述: template voidLinkList : Insert(inti,Tx)//插入函数 { Node if(p) { Node s->data=x; s->next=p->next; p->next=s; } elsethrow"插入位置非法"; } 时间复杂度: O(n) 7.按位删除函数 自然语言描述: a.从第一个结点开始,查找要删除的位数i前一个位置i-1的结点 b.设q指向第i个元素 c.将q元素从链表中删除 d.保存q元素的数据 e.释放q元素 代码描述: template TLinkList : Delete(inti)//删除函数 { Node Node Tx=q->data; p->next=q->next; deleteq; returnx; } 8.遍历打印函数 自然语言描述: a.判断该链表是否为空链表,如果是,报错 b.如果不是空链表,新建立一个temp指针 c.将temp指针指向头结点 d.打印temp指针的data域 e.逐个往后移动temp指针,直到temp指针的指向的指针的next域为空 代码描述: template voidLinkList : PrintList()//打印链表 { Node while(p) { cout< p=p->next; } cout< } 9.获取链表长度函数 自然语言描述: a.判断该链表是否为空链表,如果是,输出长度0 b.如果不是空链表,新建立一个temp指针,初始化整形数n为0 c.将temp指针指向头结点 d.判断temp指针指向的结点的next域是否为空,如果不是,n加一,否则returnn e.使temp指针逐个后移,重复d操作,直到temp指针指向的结点的next域为0,返回n 代码描述: template intLinkList : GetLength()//分析链表长度 { Node inti=0; while(p) { p=p->next; i++; } returni-1; } 2.3其他 异常处理 采用trycatch函数处理异常 如在插入时的异常处理: template voidLinkList : Insert(inti,Tx) { Node if(i! =1)p=Get(i-1); try { if(p) { Node s->data=x; s->next=p->next; p->next=s; } elsethrowi; } catch(inti) { cout<<"插入到位置"< } } 3.程序运行结果 主函数流程图: 是 否 是否退出 测试截图: 初始化链表,菜单创建 执行功能: 4.总结 .调试时出现了一些问题如: 异常抛出的处理,书中并未很好的提及异常处理,通过查阅资料,选择用trycatch函数对解决。 2.心得体会 了解了单链表的基本的操作函数实现,对链式存储结构有了较好的认识 3.下一步的改进 可以增加完善报错机制,增强程序的健壮性 完整源代码: //单链表的构造 #include usingnamespacestd; template structNode { Tdata;//数据域 structNode }; template classLinkList { public: LinkList(){front=newNode LinkList(Ta[],intn);//有参构造函数,使用含有n个元素的数组a初始化单链表 ~LinkList();//析构函数,(其在voidmain函数最后一句语句之后自动执行,旨在释放栈空间) voidPrintList();//按次序遍历线性表中的各个数据元素 intGetLength();//获取线性表的长度 Node intLocate(Tx);//查找线性表中值为x的元素,找到后返回其位置 voidInsert(inti,Tx);//后插,在线性表的第i个位置上插入值为x的新元素 voidinsert(inti,Tx);//前插,在线性表的第i个位置上插入值为x的新元素 TDelete(inti);//删除线性表第i个元素,并将该元素返回 private: Node }; //头插法构造函数 template LinkList : LinkList(Ta[],intn) { for(inti=n-1;i>=1;i--)//冒泡排序,对数组进行从小到大排序 { for(intj=0;j { if(a[j]>a[j+1]) { Tt=a[j+1]; a[j+1]=a[j]; a[j]=t; } } } front=newNode front->next=NULL;//构造空单链表 for(inti=n-1;i>=0;i--) { Node s->data=a[i];//将a[i]写入新结点的数据域 s->next=front->next;//修改新结点的指针域 front->next=s;//修改头结点的指针域,将新结点加入到链表中 } } //尾插法构造函数 //template //LinkList : LinkList(Ta[],intn) //{ //front=newNode //Node //for(inti=0;i //{ //Node //s->data=a[i]; //r->next=s; //r=s; //} //r->next=NULL; //} template voidLinkList : PrintList()//遍历线性表元素并打印到屏幕 { Node while(p) { cout< p=p->next; } cout< } template LinkList : ~LinkList()//析构函数 { Node while(p)//要释放的结点存在 { front=p; p=p->next; deletefront;//释放结点 } } template Node : Get(inti)//获取线性表第i个位置上的元素结点地址 { Node intk=1; while(p&&(k! =i)) { p=p->next; k++; } returnp; } template intLinkList : Locate(Tx)//按值查找某元素的位置 { Node intk=1; while(p&&(p->data! =x)) { p=p->next; k++; } returnk; } //后插 template voidLinkList : Insert(inti,Tx) { Node if(i! =1)p=Get(i-1); try { if(p) { Node s->data=x; s->next=p->next; p->next=s; } elsethrowi; } catch(inti) { cout<<"插入到位置"< } } template TLinkList : Delete(inti) { Node if(i! =1)p=Get(i-1);//若不是在第一个位置删除,获取第i-1个元素的地址 try { if(p&&(p->next)) { Node p->next=q->next; Tx=q->data; deleteq; returnx; } elsethrowi; } catch(inti) { cout<<"删除位置"< } } template intLinkList : GetLength() { Node inti; for(i=0;p! =NULL;i++) { p=p->next; } returni; } voidmain() { intm=1; inta[7]={3,2,1,4,6,5,7}; LinkList cout<<"排序后的链表为: "; list.PrintList(); cout<<"\t\t**************************************************"< <<"\t\t※※"< <<"\t\t※对该单链表的操作※"< <<"\t\t※※"< <<"\t\t※1.获取线性表的长度※"< <<"\t\t※※"< <<"\t\t※2.查找值为x的元素,并返回其位置※"< <<"\t\t※※"< <<"\t\t※3.在线性表的第i个位置上插入值为x的新元素※"< <<"\t\t※※"< <<"\t\t※4.删除线性表第i个元素,并将该元素返回※"< <<"\t\t※※"< <<"\t\t**************************************************"< while(m! =0) { cout<<"\t\t\t选择你需要的功能: "; intchoice; cin>>choice;//输入需要的功能 switch(choice) { case1: cout<<"线性表的长度为: "< break; case2: //查找值为x的元素,并返回其位置 { cout<<"请输入想查找的元素的值: "< intvalue; cin>>value; intlocation=list.Locate(value); cout<<"该元素的位置为: "< } break; case3: //在线性表的第i个位置上插入值为x的新元素 { cout<<"请输入想插入的位置值: "< intlocation_2;//位置值 cin>>location_2; cout<<"请输入想插入的新元素的值"< intvalue_1;//元素值 cin>>value_1; list.Insert(location_2,value_1); cout<<"执行插入操作后的链表为: "< list.PrintList(); } break; case4: //删除线性表第i个元素,并将该元素返回 { cout<<"请输入想要删除的元素的位置值: "< intlocation_3; cin>>location_3; intvalue_2=list.Delete(location_3); cout<<"删除的元素值为: "< } break; default: cout<<"! ! 无此功能项"< break; } cout<<"※※※那您是否想继续? 继续请输入1不想继续请输入0※※※"< cin>>m; } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北京邮电大学 数据结构 实验一 带头结点的单链表构造 北京邮电 大学 实验 带头 结点 单链表 构造