实验二 单链表基本操作的实现Word文件下载.docx
- 文档编号:6163835
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:18
- 大小:55.48KB
实验二 单链表基本操作的实现Word文件下载.docx
《实验二 单链表基本操作的实现Word文件下载.docx》由会员分享,可在线阅读,更多相关《实验二 单链表基本操作的实现Word文件下载.docx(18页珍藏版)》请在冰点文库上搜索。
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
Linkhead,tail;
intlen;
PositionMakeNode_L(Link&
p,ElemTypee)//创建结点
{
p=(Link)malloc(sizeof(LNode));
if(!
p)returnERROR;
p->
data=e;
next=NULL;
returnp;
}
voidFreeNode_L(Link&
q)//释放结点
free(q);
StatusInitList_L(LinkList&
L){
//初始化L为一个带头结点的空链表,头尾指针指向头结点,表长赋
ElemTypee;
e=-1;
//实际应用中此初始化语句需要修改
MakeNode_L(L.head,e))returnERROR;
//开辟头结点
L.tail=L.head;
L.len=0;
returnOK;
}//InitList_L
StatusDestroyList_L(LinkList&
L){//销毁链表L
Linkp;
while(p=L.head->
next){//依次释放有序链表中第一个元素至最后一个元素所占用空间;
L.head->
next=p->
next;
free(p);
}
free(L.head);
L.head=NULL;
L.tail=NULL;
cout<
<
endl<
"
Thelisthasbeendestroyed!
endl;
}//DestroyList_L
StatusClearList_L(LinkList&
L){//清空线性单链表
Linkp,q;
p=L.head->
while(p)
{
q=p->
p=q;
L.len=0;
StatusInsFirst_L(LinkList&
L,Links)//在首元素前插入一个结点
s->
next=L.head->
L.head->
next)
L.tail=s;
L.head->
next=s;
L.len++;
StatusDelFirst_L(LinkList&
L,Linkh,Link&
q)//删除首结点
h=L.head;
q=L.head->
if(q)
h->
next=q->
q->
if(!
h->
L.tail=h;
L.len--;
returnOK;
else
returnERROR;
StatusAppend_L(LinkList&
L,Links)//将两个链表跟一个字符串连接起来
Linkq;
next=q=s;
L.tail->
while(q->
q=q->
L.tail=q;
PositionRemove_L(LinkList&
L,Link&
q)//删除尾结点
p=L.head;
next)cout<
TheLinkListisempty!
while(p->
next!
=L.tail)
p=p->
q=L.tail;
L.tail=p;
returnq;
StatusInsBefore_L(LinkList&
p,Links)//在p指向的结点前插入一个结点
q=L.head;
if(p==L.head)cout<
不能在这个地方插入元素!
while(q->
=p)
q=q->
s->
next=p;
StatusInsAfter_L(LinkList&
p,Links)//在p指向的结点后插入一个结点
if(p==L.tail)L.tail=s;
StatusSetCurElem_L(Link&
p,ElemTypee)//改变p指向的结点的内容
ElemTypeGetCurElem_L(Linkp)//获取p指向的结点的内容
returnp->
data;
intListLength_L(LinkListL)//获取单链表的长度值
returnL.len;
StatusListEmpty_L(LinkListL)//判断单链表是否为空,是返回,否返回
if(L.head==L.tail)returnTRUE;
elsereturnFALSE;
PositionGetHead_L(LinkListL)//获取头指针的地址
returnL.head;
PositionGetLast_L(LinkListL)//获取尾指针的地址
returnL.tail;
PositionPriorPos_L(LinkListL,Linkp)//获取p的前驱
if(p==L.head->
next)returnNULL;
PositionNextPos_L(LinkListL,Linkp)//获取p的后继
p->
StatusLocatePos_L(LinkListL,inti,Link&
p)//查找p在单链表中的位置i
intj;
if(i<
1)returnERROR;
for(j=1;
j<
i;
j++)
p=p->
Statuscompare(ElemTypex,ElemTypey)//比较函数
if(x==y)
return1;
return0;
StatusLocateElem_L(LinkListL,ElemTypee,Link&
p)//返回跟e相同的值,没有的话返回空指针
inti=0;
do
i++;
}while(p&
&
!
compare(p->
data,e));
if(p)
cout<
i<
Itisnotinhere!
StatusListTraverse_L(LinkListL,Status(*visit(ElemType)))//每一个元素调用visit()函数
while(p->
visit(p->
data);
StatusListInsert_L(LinkList&
L,inti,ElemTypee)//在第i个位置后插入一个元素
Linkp,s;
s=(Link)malloc(sizeof(LNode));
StatusListDelete_L(LinkList&
L,inti)//删除第i个元素的结点
if(i>
L.len)returnERROR;
i-1;
next->
L.len--;
StatusMergeList_L(LinkListLa,LinkListLb,LinkList&
Lc)//将两个字符串连接起来
Linkp,q,t;
p=La.head->
q=Lb.head->
while(p&
q){
if(p->
data<
q->
data){
MakeNode_L(t,p->
InsFirst_L(Lc,t);
}
else{
MakeNode_L(t,q->
while(p){
MakeNode_L(t,p->
InsFirst_L(Lc,t);
while(q){
MakeNode_L(t,q->
【测试数据及实验结果】
intmain(){
LinkListla,lb,lc;
Linkp,q,s,k,t;
InitList_L(la);
InitList_L(lb);
InitList_L(lc);
建立一个有个数据的顺序表La,各节点值依次为:
4,6,8,10,12,….,38,40"
-----------------------------------"
for(inti=20;
i>
=1;
i--){
MakeNode_L(p,2*i);
InsFirst_L(la,p);
q=la.head->
setw(3)<
删除,节点"
----------------------------------"
ListDelete_L(la,8);
ListDelete_L(la,30);
表长为:
la.len<
在第五个结点后插入一个结点"
ListInsert_L(la,5,11);
分别查找值为,45的元素"
LocateElem_L(la,28,s);
LocateElem_L(la,45,s);
建立线性表Lb,各结点值依次为:
3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78"
for(inti=7;
=0;
MakeNode_L(p,i*10+8);
InsFirst_L(lb,p);
MakeNode_L(p,i*10+3);
q=lb.head->
将La和Lb合并为线性表Lc"
MergeList_L(la,lb,lc);
输出La,Lb,Lc的以及各表的表长"
}cout<
q=lc.tail;
while(q){
cout<
q=PriorPos_L(lc,q);
清空线性表La,Lb;
输出La,Lb的表长"
lb.len<
lc.len<
ClearList_L(la);
ClearList_L(lb);
return0;
【实验小结】
举例说明求解什么样的问题用顺序存储,什么样的问题用链式存储较好?
答:
使用顺序存储结构的情况:
(1)空间利用率较高;
(2)存取某个元素速度快;
(3)插入元素和删除元素存在元素移动,速度慢,耗时;
(4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现"
溢出"
问题.当元素个数远少于预先分配的空间时,空间浪费巨大。
在存取元素频繁,但删除或插入操作较少的情况宜用顺序表。
例如建立一个班学生的资料,一般学生人数变动较少,而对资料的调用较多,股宜用顺序表。
使用链式存储结构的情况:
(1)占用额外的空间以存储指针(浪费空间);
(2)存取某个元素速度慢;
(3)插入元素和删除元素速度快;
(4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。
【源代码说明】
1.文件名:
.cpp
2.操作说明:
只需使用visualc++6.0软件将其打开,点击运行即可!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验二 单链表基本操作的实现 实验 单链表 基本 操作 实现