实验05线性表的链式表示和实现.docx
- 文档编号:18478415
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:21
- 大小:78.96KB
实验05线性表的链式表示和实现.docx
《实验05线性表的链式表示和实现.docx》由会员分享,可在线阅读,更多相关《实验05线性表的链式表示和实现.docx(21页珍藏版)》请在冰点文库上搜索。
实验05线性表的链式表示和实现
浙江大学城市学院实验报告
课程名称数据结构基础
实验项目名称实验五线性表的链式表示和实现
学生姓名专业班级学号
实验成绩指导老师(签名)日期
一.实验目的和要求
1、掌握线性表的链式存储结构;
2、掌握单链表、循环单链表的一些基本操作实现函数。
二.实验内容
1、设线性表采用带表头附加结点的单链表存储结构,请编写线性表各基本操作的实现函数,把它们存放在头文件LinkList.h中,同时建立一个验证操作实现的主函数文件test2_2.cpp。
编译并调试程序,直到正确运行。
2、选做:
编写一个函数voidMergeList(LNode*&La,LNode*&Lb,LNode*&Lc),实现将两个带表头附加结点的有序单链表La和Lb合并成一个新的带表头附加结点的有序单链表Lc的功能,要求利用原存储空间。
请把该函数添加到头文件LinkList.h中,并在主文件test2_2.cpp中添加相应语句进行测试。
3、填写实验报告,实验报告文件取名为report5.doc。
4、上传实验报告文件report5.doc、源程序文件test2_2.cpp及LinkList.h到Ftp服务器上自己的文件夹下。
三.函数的功能说明及算法思路
/*初始化单链表*/
voidInitList(LNode*&H)
/*删除单链表中的所有结点,使之成为一个空表*/
voidClearList(LNode*&H)
/*得到单链表的长度*/
intLengthList(LNode*H)
/*检查单链表是否为空*/
boolEmptyList(LNode*H)
/*得到单链表中第pos个结点中的元素*/
ElemTypeGetList(LNode*H,intpos)
/*遍历一个单链表*/
voidTraverseList(LNode*H)
/*从单链表中查找等于定值的第1个元素*/
ElemTypeFindList(LNode*&H,ElemType&item)
/*向单链表中按给定条件插入一个元素*/
boolInsertList(LNode*&H,ElemTypeitem,intpos)
/*更新单链表中等于定值的第1个元素*/
boolUpdateList(LNode*&H,constElemType&item,intpos)
/*从单链表中删除符合给定条件的第1个元素*/
boolDeleteList(LNode*&H,ElemTypeitem,intpos)
/*对单链表进行数据排序*/
voidSortList(LNode*&H)
/*合并两个单链表*/
voidMergeList(LNode*&A,LNode*&B)
四.实验结果与分析
五.心得体会
【附录----源程序】
test2_2.cpp
#include
#include
#include
typedefintElemType;
#include"LinkList.h
voidmain()
{
intchoice,select,i;
ElemTypex;
LNode*A;
ElemTypea[10]={27,13,14,7,55,29,21,67,33,36};
InitList(A);
for(i=0;i<10;i++)
InsertList(A,a[i],i+1);
do{
system("cls");
cout<<"*****************************************************"< cout<<"*1.插入元素*"< cout<<"*2.删除元素*"< cout<<"*3.更新元素*"< cout<<"*4.查看链表*"< cout<<"*5.合并链表*"< cout<<"*6.清除链表*"< cout<<"*0.退出*"< cout<<"*****************************************************"< cout<<"请输入您的选择: "; cin>>choice; switch(choice){ case1: do{ system("cls"); cout<<"*********************************"< cout<<"*1.按pos值插入*"< cout<<"*2.按元素值插入*"< cout<<"*0.返回主菜单*"< cout<<"*********************************"< cout<<"请输入您的选择: "; cin>>select; system("cls"); if(select==1){ cout<<"线性表A: "; TraverseList(A); cout<<"输入待插入元素的值及pos值: "; cin>>x>>i; if(InsertList(A,x,i)){ cout<<"插入后线性表A: "; TraverseList(A); } getchar(); } elseif(select==2){ cout<<"线性表A: "; TraverseList(A); SortList(A); cout<<"排序后线性表A: "; TraverseList(A); cout<<"输入待插入元素的值: "; cin>>x; if(InsertList(A,x,0)){ cout<<"插入后线性表A: "; TraverseList(A); } getchar(); } }while(select! =0); break; case2: do{ system("cls"); cout<<"*********************************"< cout<<"*1.按pos值删除*"< cout<<"*2.按元素值删除*"< cout<<"*0.返回主菜单*"< cout<<"*********************************"< cout<<"请输入您的选择: "; cin>>select; system("cls"); if(select==1){ cout<<"线性表A: "; TraverseList(A); cout<<"输入待删除元素的pos值: "; cin>>i; if(DeleteList(A,x,i)){ cout<<"删除后线性表A: "; TraverseList(A); } getchar(); } elseif(select==2){ cout<<"线性表A: "; TraverseList(A); cout<<"输入待删除元素的值: "; cin>>x; if(DeleteList(A,x,0)){ cout<<"删除后线性表A: "; TraverseList(A); } getchar(); } }while(select! =0); break; case3: system("cls"); cout<<"线性表A: "; TraverseList(A); cout<<"输入待更新元素的值及pos值: "; cin>>x>>i; if(UpdateList(A,x,i)){ cout<<"更新后线性表A: "; TraverseList(A); } getchar(); break; case4: do{ system("cls"); cout<<"*********************************"< cout<<"*1.按pos值查看*"< cout<<"*2.按元素值查看*"< cout<<"*0.返回主菜单*"< cout<<"*********************************"< cout<<"请输入您的选择: "; cin>>select; system("cls"); cout<<"线性表A: "; TraverseList(A); if(EmptyList(A)) cout<<"线性表为空! "< else cout<<"线性表A长度: "< if(select==1){ cout<<"输入待查找元素的pos值: "; cin>>i; GetList(A,i); getchar(); } elseif(select==2){ cout<<"输入待查找元素的值: "; cin>>x; FindList(A,x); getchar(); } }while(select! =0); break; case5: system("cls"); LNode*B; InitList(B); cout<<"输入线性表B: "; i=0; cin>>x; while(x! =-1){ i++; InsertList(B,x,i); cin>>x; } system("cls"); cout<<"线性表A: "; TraverseList(A); cout<<"线性表B: "; TraverseList(B); MergeList(A,B); cout<<"合并后线性表A: "; TraverseList(A); getchar(); break; case6: system("cls"); ClearList(A); cout<<"线性表已清除! "< getchar(); break; case0: exit(0); } }while(choice! =0); } LinkList.h typedefstructLNode{ ElemTypedata; LNode*next; }LNode; /*初始化单链表*/ voidInitList(LNode*&H) { H=newLNode; if(! H) exit(0); H->next=NULL; } /*删除单链表中的所有结点,使之成为一个空表*/ voidClearList(LNode*&H) { LNode*p=H->next; while(p! =NULL){ H->next=p->next; deletep; p=H->next; } H->next=NULL; } /*得到单链表的长度*/ intLengthList(LNode*H) { inti=0; while(H->next! =NULL){ i++; H=H->next; } returni; } /*检查单链表是否为空*/ boolEmptyList(LNode*H) { returnH->next==NULL; } /*得到单链表中第pos个结点中的元素*/ ElemTypeGetList(LNode*H,intpos) { inti=0; LNode*p=H->next; while(p! =NULL){ i++; if(i==pos) break; p=p->next; } if(p==NULL) cout<<"pos值无效! "< else cout<<"元素的值: "< return0; } /*遍历一个单链表*/ voidTraverseList(LNode*H) { LNode*p=H->next; while(p! =NULL){ cout< p=p->next; } cout< } /*从单链表中查找等于定值的第1个元素*/ ElemTypeFindList(LNode*&H,ElemType&item) { inti=0; LNode*p=H->next; while(p! =NULL){ i++; if(p->data==item) break; p=p->next; } if(p==NULL) cout<<"元素值不存在! "< else cout<<"元素的pos值: "< return0; } /*向单链表中按给定条件插入一个元素*/ boolInsertList(LNode*&H,ElemTypeitem,intpos) { if(pos<-1){ cout<<"pos值无效! "< returnfalse; } LNode*newp,*p,*q; newp=newLNode; newp->data=item; p=H; q=H->next; if(pos==0){ while(q! =NULL){ if(item break; else{ p=q; q=q->next; } } } elseif(pos==-1) while(q! =NULL){ p=q; q=q->next; } else{ inti=0; while(q! =NULL){ i++; if(i==pos) break; else{ p=q; q=q->next; } } if(q==NULL&&i+1 cout<<"pos值无效! "< returnfalse; } } newp->next=q; p->next=newp; returntrue; } /*更新单链表中等于定值的第1个元素*/ boolUpdateList(LNode*&H,constElemType&item,intpos) { if(pos<-1){ cout<<"pos值无效! "< returnfalse; } inti=0; LNode*p=H->next; while(p! =NULL){ i++; if(i==pos) break; else p=p->next; } if(p==NULL){ cout<<"pos值无效! "< returnfalse; } else{ p->data=item; returntrue; } } /*从单链表中删除符合给定条件的第1个元素*/ boolDeleteList(LNode*&H,ElemTypeitem,intpos) { LNode*p=H,*q=H->next; if(q==NULL){ cerr<<"单链表为空,删除操作无效! "< returnfalse; } if(pos<-1){ cout<<"pos值无效! "< returnfalse; } if(pos==0){ while(q! =NULL){ if(q->data==item) break; else{ p=q; q=q->next; } } if(q==NULL){ cout<<"元素值不存在! "< returnfalse; } } elseif(pos==-1) while(q->next! =NULL){ p=q; q=q->next; } else{ inti=0; while(q! =NULL){ i++; if(i==pos) break; else{ p=q; q=q->next; } } if(q==NULL){ cout<<"pos值无效! "< returnfalse; } } p->next=q->next; deleteq; returntrue; } /*对单链表进行数据排序*/ voidSortList(LNode*&H) { LNode*S; InitList(S); LNode*r=H->next; while(r! =NULL){ LNode*t=r->next; LNode*p=S; LNode*q=S->next; while(q! =NULL){ if(r->data break; else{ p=q; q=q->next; } } if(p==NULL){ r->next=S; S=r; } else{ r->next=q; p->next=r; } r=t; } H=S; } /*合并两个单链表*/ voidMergeList(LNode*&A,LNode*&B) { inti=LengthList(A); LNode*b=B->next; while(b! =NULL){ i++; InsertList(A,b->data,i); b=b->next; } ClearList(B); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验05 线性表的链式表示和实现 实验 05 线性 链式 表示 实现