实验二 单链表基本操作的实现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软件将其打开，点击运行即可！
升级会员 