实验05线性表的链式表示和实现.docx

实验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<<"元素的值：

"<data<

return0;

}

/*遍历一个单链表*/

voidTraverseList（LNode*H）

{

LNode*p=H->next;

while（p!

=NULL）{

cout<data<<"";

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（itemdata）

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->datadata）

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）;

}