数据结构基础实验5

课程名称 数据结构基础 实验项目名称 实验五 线性表的链式表示和实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求

1、了解线性表的链式存储结构，学会定义线性表的链式存储结构。 2、掌握单链表、循环单链表的一些基本操作实现函数。

二. 实验内容

1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。 提示：

⑴ 单向链表的存储结构可定义如下：

struct LNode { // 定义单链表节点类型 ElemType data; // 存放结点中的数据信息

LNode *next; // 指示下一个结点地址的指针 }

⑵ 线性表基本操作可包括如下一些：

① void InitList (LNode *&H) //初始化单链表 ② void ClearList(LNode *&H) //清除单链表 ③ int LengthList (LNode *H) //求单链表长度

④ bool EmptyList (LNode *H) //判断单链表是否为空表 ⑤ ElemType GetList (LNode *H, int pos)

//取单链表第 pos 位置上的元素

⑥ void TraverseList(LNode *H) //遍历单链表 ⑦ bool InsertList ( LNode *&H, ElemType item, int pos)

//向单链表插入一个元素

⑧ bool DeleteList ( LNode *&H, ElemType &item, int pos)

//从单链表中删除一个元素

⑶ 带表头附加结点的单链表初始化操作的实现可参考如下： void InitList(LNode *&H)

{ //构造一个空的线性链表H，即为链表设置一个头结点，

//头结点的data数据域不赋任何值，头结点的指针域next则为空

H=(LNode *)malloc(sizeof(LNode)); // 产生头结点H if (!H) exit(0); // 存储分配失败，退出系统 H->next=NULL; // 指针域为空 }

2、选做部分：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) ，实现将两个有序单链表La和 Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。要求把该函数添加到文件LinkList.h中，并在主函数文件test5.cpp中添加相应语句进行测试。

3、填写实验报告，实验报告文件取名为report5.doc。

4、上传实验报告文件report5.doc 、源程序文件test5.cpp及LinkList.h到Ftp服务器上（ ftp://10.61.14.240:5000 ）自己的文件夹下。

三. 函数的功能说明及算法思路 1. void InitList(LNode *&H)

作用：构造一个空的线性链表H，即为链表设置一个头结点， 头结点的data数据域不赋任何值，头结点的指针域next则为空 void InitList(LNode *&H) {

H=(LNode *)malloc(sizeof(LNode)); if (!H) exit(0); H->next=NULL; }

2. void ClearList(LNode *&H) 作用：清除单链表

void ClearList(LNode *&H) {

LNode *cp; LNode *np; cp=H;

while(cp!=NULL){

np=cp->next; delete cp; cp=np;

// 产生头结点H

// 存储分配失败，退出系统

// 指针域为空

}

} H=NULL;

3. int LengthList (LNode *H) 作用：求单链表长度 int LengthList (LNode *H) { }

4. bool EmptyList (LNode *H) 作用：判断单链表是否为空表 bool EmptyList (LNode *H) { }

5. ElemType GetList (LNode *H, int pos) 作用：取单链表第 pos 位置上的元素 ElemType GetList (LNode *H, int pos) {

if(pos<1){

cerr<<\"pos is out range!\"<while(H!=NULL) {

i++; H=H->next;

}

} int i=0; while(H!=NULL){ }

if(H!=NULL)

return H->data; i++;

if(i==pos)break; H=H->next;

else{ }

cerr<<\"pos is out range!\"<6. void TraverseList(LNode *H) 作用：遍历单链表 void TraverseList(LNode *H) { }

7. bool InsertList ( LNode *&H, ElemType item, int pos) 作用：向单链表插入一个元素

bool InsertList ( LNode *&H, ElemType item, int pos) {

if(pos<-1){ while(H!=NULL) { }

cout<data<<\" \"; H=H->next;

}

cout<<\"pos值无效!\"<LNode* newptr; newptr=new LNode;

newptr->data=item;

LNode* cp=H;

LNode* ap=NULL;

if(pos==0){ }

else if(pos==-1)

while(cp!=NULL){ }

ap=cp; cp=cp->next; while(cp!=NULL){ }

if(itemdata)

break;

else{ }

ap=cp; cp=cp->next;

else{

int i=0;

while(cp!=NULL){

i++; if(i==pos)

}

}

break;

else{ }

ap=cp; cp=cp->next;

if(cp==NULL && i+1cout<<\"pos值超出单链表长度加1!\"<if(ap==NULL){ } else{

newptr->next=H; H=newptr;

newptr->next=cp; }

8. bool DeleteList( LNode * &HL, ElemType item, int pos)

作用：从单链表中删除一个元素

bool DeleteList( LNode * &HL, ElemType item, int pos) {

if(HL==NULL){ }

cerr<<\"单链表为空，删除操作无效!\"<return true;

ap->next=newptr;

if(pos<-1){ }

LNode* cp=HL; LNode* ap=NULL; if(pos==0){ }

else if(pos==-1)

while(cp->next!=NULL){ap=cp;cp=cp->next;} else{

int i=0;

while(cp!=NULL){

i++;

if(i==pos)break; else{ }

ap=cp; cp=cp->next;

while(cp!=NULL){ }

if(cp==NULL){ }

cout<<\"单链表中没有相应的节点可删除\"<if(item==cp->data)break; else{ }

ap=cp; cp=cp->next;

cout<<\"pos值无效!\"<}

}

}

if(cp==NULL){ }

cout<<\"pos值无效!\"<if(ap==NULL)HL=HL->next; else ap->next=cp->next; delete cp; return true;

9. void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc)

作用：实现将两个有序单链表La和 Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb

void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) {

int a,b;

a=LengthList(La)+1; b=LengthList(Lb)+1; LNode *Lcnext; Lc->next=NULL; while((a>0)&&(b>0)) {

if(La->datadata) {

Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=La->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; La=La->next;

}

}

a--;

else { }

Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=Lb->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; Lb=Lb->next; b--;

if(a==0)

while(b>0) { }

Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=Lb->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; Lb=Lb->next; b--;

else

while(a>0) {

Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=La->data; Lcnext->next=Lc->next;

}

}

Lc->next=Lcnext; Lc=Lc->next; La=La->next; a--;

四. 实验结果与分析

实验结果符合要求 五. 心得体会

编写函数时没有定义 【附录----源程序】 1. test5.cpp

#include #include #include #include typedef int ElemType;

struct LNode{ ElemType data; LNode *next; };

#include\"LinkList.h\" void main(void)

{

/*----------------------------------------------------------------------*/ int changdu; int kongbiao; int pos; int pos2,item2; int pos3,item3; LNode *pa,*pb,*pc; LNode *c,*chead;

/*----------------------------------------------------------------------*/ int n; LNode *head,*HL,*s,*s2,*p; InitList(HL); HL->next=NULL; head=HL; s2=HL; cout<<\"输入数据，以-1为结束\"<>n;

while (n!=-1) {

s=(LNode *)malloc (sizeof(LNode)); s->data=n;

s->next=s2->next; s2->next=s; s2=s2->next; cin>>n; } p=HL->next;

/*----------------------------------------------------------------------*/ cout<<\"遍历链表得\"</*----------------------------------------------------------------------*/ changdu=LengthList(head); cout<<\"长度为\"</*----------------------------------------------------------------------*/ kongbiao=EmptyList(head); if(kongbiao==0) cout<<\"不是空表\"</*----------------------------------------------------------------------*/ cout<<\"输入pos , 取单链表第pos位置上的元素\"<>pos;

cout</*----------------------------------------------------------------------*/ cout<<\"依次pos item 向单链表插入一个元素\"<>pos2; cin>>item2; InsertList(p,item2,pos2); cout<<\"插入后得\"</*----------------------------------------------------------------------*/ cout<<\"输入pos,item,从单链表中删除一个元素\"<>pos3; cin>>item3; DeleteList(p,item3,pos3); cout<<\"删除后得\"</*----------------------------------------------------------------------*/ ClearList(head); cout</*----------------------------------------------------------------------*/ InitList(HL); HL->next=NULL; head=HL; s2=HL; cout<<\"有序输入La，以-1为结束\"<>n;

while (n!=-1) {

s=(LNode *)malloc (sizeof(LNode)); s->data=n;

s->next=s2->next; s2->next=s; s2=s2->next; cin>>n; } pa=HL->next; cout<<\"La为\"; TraverseList(pa); cout<next=NULL; head=HL; s2=HL;

cout<<\"有序输入La，以-1为结束\"<>n;

while (n!=-1) {

s=(LNode *)malloc (sizeof(LNode)); s->data=n;

s->next=s2->next; s2->next=s; s2=s2->next; cin>>n; } pb=HL->next; cout<<\"Lb为\"; TraverseList(pb); cout</*----------------------------------------------------------------------*/ c=(LNode *)malloc (sizeof(LNode)); pc=(LNode *)malloc (sizeof(LNode)); InitList(chead); chead->next=pc; MergeList(pa,pb,pc); TraverseList((chead->next)->next); ClearList(pa); ClearList(pb);

/*----------------------------------------------------------------------*/ }

2. LinkList.h

/*----------------------------------------------------------------------*/ void InitList(LNode *&H)

{ //构造一个空的线性链表H，即为链表设置一个头结点，

//头结点的data数据域不赋任何值，头结点的指针域next则为空 H=(LNode *)malloc(sizeof(LNode)); // 产生头结点H if (!H) exit(0); // 存储分配失败，退出系统 H->next=NULL; // 指针域为空 }

/*----------------------------------------------------------------------*/ void ClearList(LNode *&H) //清除单链表 { LNode *cp; LNode *np; cp=H;

while(cp!=NULL){ np=cp->next; delete cp; cp=np; } H=NULL; }

/*----------------------------------------------------------------------*/ int LengthList (LNode *H) //求单链表长度 { int i; i=0; while(H!=NULL) { i++; H=H->next; } return i-1; }

/*----------------------------------------------------------------------*/

bool EmptyList (LNode *H) //判断单链表是否为空表 { return H==NULL; }

/*----------------------------------------------------------------------*/

ElemType GetList (LNode *H, int pos) //取单链表第 pos 位置上的元素 { if(pos<1){ cerr<<\"pos is out range!\"<next; } if(H!=NULL) return H->data; else{ cerr<<\"pos is out range!\"<}

/*----------------------------------------------------------------------*/ void TraverseList(LNode *H) //遍历单链表 { while(H!=NULL) { cout<data<<\" \"; H=H->next; } }

/*----------------------------------------------------------------------*/

bool InsertList ( LNode *&H, ElemType item, int pos)//向单链表插入一个元素 { if(pos<-1){ cout<<\"pos值无效!\"<data=item; LNode* cp=H; LNode* ap=NULL; if(pos==0){ while(cp!=NULL){ if(itemdata) break; else{ ap=cp; cp=cp->next; } } } else if(pos==-1) while(cp!=NULL){ ap=cp; cp=cp->next; } else{ int i=0; while(cp!=NULL){ i++; if(i==pos)

break; else{ ap=cp; cp=cp->next; } } if(cp==NULL && i+1next=H; H=newptr; } else{

newptr->next=cp; ap->next=newptr; } return true; }

/*----------------------------------------------------------------------*/ bool DeleteList( LNode * &HL, ElemType item, int pos) { if(HL==NULL){ cerr<<\"单链表为空，删除操作无效!\"<data)break; else{ ap=cp; cp=cp->next; } } if(cp==NULL){

cout<<\"单链表中没有相应的节点可删除\"<next!=NULL){ap=cp;cp=cp->next;} else{ int i=0; while(cp!=NULL){ i++; if(i==pos)break; else{ ap=cp; cp=cp->next; } } if(cp==NULL){ cout<<\"pos值无效!\"<next; else ap->next=cp->next; delete cp; return true; }

/*----------------------------------------------------------------------*/ void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) { int a,b; a=LengthList(La)+1; b=LengthList(Lb)+1; LNode *Lcnext; Lc->next=NULL; while((a>0)&&(b>0)) { if(La->datadata) { Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=La->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; La=La->next; a--;

}

} else { Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=Lb->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; Lb=Lb->next; b--; } }

if(a==0) while(b>0) { Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=Lb->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; Lb=Lb->next; b--; } else while(a>0) { Lcnext=(LNode*)malloc(sizeof(LNode)); Lcnext->data=La->data; Lcnext->next=Lc->next; Lc->next=Lcnext; Lc=Lc->next; La=La->next; a--; }