链表实验报告

重庆工商大学

《数据结构》课程实验报告封面

专业班级：___ ___ 学号：__ _____

学生姓名：______ _ ______ 实验室：__________________

实验题目：_______ 双链表的基本操作方法_______________

指导教师：______ ______ 成绩：__________________

日期：2013年_9 月____日第_ 4_ 周星期__3_节次____

评分表

实验报告的内容与要求

一、实验题目

双链表的基本操作

二、实验目的

了解双链表的结构特点及有关概念，掌握双链表的基本操作算法。

三、实验内容

实现双链表的初始化、销毁、建立、插入、删除和查找等基本操作。

四、实验要点与要求

1. 处理的数据类型即ElemType的类型：

基本版要求：整型、字符型

扩展版要求：字符串型（基础较好的同学）

2. 参数类型分别用指针、引用和引用型指针

五、算法思想

和顺序表不同的是，链表不需要占用一整块事先分配的固定的内存空间，而是采用动态空间链接的方式进行。在每个存储节点都包含了元素本身的信息(数据域)和元素之间的逻辑联系(指针域)，就双链表而言，其指针域包含了前驱指针和后续指针，分别用于指向当前节点的上一个节点和下一个节点，故而，对双链表进行操作的时候，要考虑其前驱指针和后续指针的指向，否则容易引起混乱。在链表的操作中，首先最重要的是定义一个头结点，因为指向头结点的指针唯一标识该链表，本次程序采用了不包含任何数据的头节点定义方式。

六、算法描述及流程图

由于程序的分支较多，需要实现的功能也不尽相同，和顺序表一样，我选择了其中插入数据的分支来具体描述其算法，并比较链表和顺序表的操作上的不同：

do{

c=ListLength(L);

cout<<"\n请输入您需要插入的节点位置(0<number<="<<c+1<<"):";

cin>>number;

cout<<"插入的数据:";

if(number<0||number>l+1){cout<<"输入错误！"<<endl;break;

cin>>date;

ListInsert(L,number,date);

cout<<"\n是否需要继续插入？\n";

cout<<" 1.是 0.否"<<endl;

cout<<"请选择:";

cin>>ctrl;

}while(ctrl==1);break;

bool ListInsert(DLinkList *&L,int i,ElemType e)//插入数据

{

int j=0;

DLinkList *p=L,*s;

while(j<i-1&&p!=NULL)

{

j++;

p=p->next;

}

if(p==NULL)

return false;

else{

s=(DLinkList *)malloc(sizeof(DLinkList));

s->date=e;

s->next=p->next;

if(p->next!=NULL)

p->next->prior=s;

p->next=s;

s->prior=p;

cout<<"插入成功！"<<endl;

return true;

}

首先，和顺序表一样的是，整个输入分支采用do-while循环进行控制，以便于我们可以多次输入；分支开始的时候，需要用输入插入的元素的位置，并通过一个if条件句判断用户输入的节点位置是否合法，如果节点位置不合法，则提示错误并提前结束分支，返回主菜单。节点位置合法则提示用户输入需要插入的数据，完成后调用ListInsert函数对链表进行插入，和顺序表不一样的是插入的具体实现方式：在插入之前，分配一个指向空节点的指针s和指向头结点的指针p，用p指针找到插入位置的上一个节点位置，如果找到开始执行插入操作，否则退出。插入开始，把用户输入的数据存储在节点s中，把p节点的后继指针指向的节点赋值给s的后继指针，如果p的next域不是空节点，修改其前驱指针指向s；把p的后继指针指向s，s的前驱指针指向p，则s指向的数据就成功插入到链表之中了。

基本流程图如下：

七、实验数据及实验结果

由于程序和顺序表一样定义为char类型，故而测试的数据和顺序表一样：输入整型，浮点型，字符型，字符串这几种不同类型的数据后，程序的不同输出结果，并且根据顺序表节点数为正整数的特征，测试了输入浮点数，字符，字符串，负数这几种情况下的输出结果。

对于插入的数据来说总共测试了以下几种数据测试数据及结果如下：

对于节点，主要测试了以下几种特殊状态的值

实验数据及结果如下:

通过对于程序处理异常数据的结果进行分析，我发现和双链表的错误和顺序表一样，都是数据类型的不兼容引起程序崩溃

八、实验总结与体会

程序实现了双链表的基本操作，和顺序表相比较，链表的操作更灵活，没有固定的长度限制，只要内存足够，就可以链接数据。大大提高了程序的灵活性和数据处理能力，但是我也发现，链表的指针指向很容易出错，如果指向不对，就会引起系统混乱出现数据异常或者是编译不通过的情况，这样一来对于逻辑要求又有了更高的要求。

九、源代码

#include<iostream>

#include<malloc.h>

using namespace std;

typedef char ElemType;

typedef struct DNode

{

ElemType date;//数据域

struct DNode *prior; //前驱指针

struct DNode *next; //后继指针

}DLinkList;

//函数声明

extern void InitList(DLinkList *&L);//初始化双链表

extern void DestroyList(DLinkList *&L);//销毁双链表

extern int ListLength(DLinkList *L);//链表求长

extern void DispList(DLinkList *L);//输出链表

extern bool GetElem(DLinkList *L,int i,ElemType &e);//按位置查找

extern int LocateElem(DLinkList *L,ElemType e);//按元素查找

extern bool ListInsert(DLinkList *&L,int i,ElemType e);//插入数据

extern bool ListDelete(DLinkList *L,int i,ElemType &e);//删除第i个位置的元素

//函数定义

void InitList(DLinkList *&L)//初始化链表

{

L=(DLinkList *)malloc(sizeof(DLinkList));

L->next=L->prior=NULL;

cout<<"新建成功！"<<endl;

}

int ListLength(DLinkList *L)//链表求长

{

int i=0;

DLinkList *p=L->next;

while(p!=NULL)

{

p=p->next;

i++;

}

return i;

}

void DispList(DLinkList *L)//输出链表

{

DLinkList *p=L->next;

int c;

c=ListLength(L);

if(c==0)cout<<" 链表为空，请插入数据！\n"<<endl;

else{

while(p!=NULL)

{

cout<<p->date<<" ";

p=p->next;

}

cout<<endl;

}

bool GetElem(DLinkList *L,int i,ElemType &e)//按位置查找

{

int j=0;

DLinkList *p=L;

while(j<i&&p!=NULL)

{

j++;

p=p->next;

}

if(p==NULL)

return false;

else

{

e=p->date;

return true;

}

int LocateElem(DLinkList *L,ElemType e)//按元素师查找

{

int i=1;

DLinkList *p=L->next;

while(p!=NULL && p->date!=e)

{

p=p->next;

i++;

}

if(p==NULL)

return 0;

else return i;

}

bool ListInsert(DLinkList *&L,int i,ElemType e)//插入数据

{

int j=0;

DLinkList *p=L,*s;

while(j<i-1&&p!=NULL)

{

j++;

p=p->next;

}

if(p==NULL)

return false;

else{

s=(DLinkList *)malloc(sizeof(DLinkList));

s->date=e;

s->next=p->next;

if(p->next!=NULL)

p->next->prior=s;

p->next=s;

s->prior=p;

cout<<"插入成功！"<<endl;

return true;

}

bool ListDelete(DLinkList *L,int i,ElemType &e)//删除第i个元素

{

int j=0;

DLinkList *p=L,*s;

while(j<i-1&&p!=NULL)

{

j++;

p=p->next;

}

if(p==NULL)

return false;

else

{

s=p->next;

if(s==NULL)

return false;

p->next=s->next;

if(s->next!=NULL)

p->next->prior=p;

free(s);

cout<<"删除成功！"<<endl;

return true;

}

//测试函数

int main()

{

DLinkList *L;

int choose;//主菜单选择分支

int number;//存储数据位置

ElemType date;//储存数据

int c;//顺序表长度

int ctrl;//函数继续控制变量

for(;;)

{

cout<<" "<<endl;

cout<<" *-*-*-**-*-*-**-*-*-*"<<endl;

cout<<" * 欢迎使用双向链表*"<<endl;

cout<<" * 1.新建链表 *"<<endl;

cout<<" * 2.数据插入 *"<<endl;

cout<<" * 3.位置查找 *"<<endl;

cout<<" * 4.元素查找 *"<<endl;

cout<<" * 5.删除数据 *"<<endl;

cout<<" * 6.遍历链表 *"<<endl;

cout<<" * 7.退出程序 *"<<endl;

cout<<" *-*-*-**-*-*-**-*-*-*"<<endl;

cout<<"请选择:";

cin>>choose;

switch(choose){

case 1:InitList(L);break;

case 2:

do{

c=ListLength(L);

cout<<"\n请输入您需要插入的节点位置(0<number<="<<c+1<<"):";

cin>>number;

if(number<0||number>c+1){cout<<"输入错误！"<<endl;break;}

cout<<"插入的数据:";

cin>>date;

ListInsert(L,number,date);

cout<<"\n是否需要继续插入？\n";

cout<<" 1.是 0.否"<<endl;

cout<<"请选择:";

cin>>ctrl;

}while(ctrl==1);break;

case 3:

do{

for(;;){

cout<<"\n请输入您需要查询的节点:";

cin>>number;

if(number<=0){cout<<"\n节点不合法！\n";}

else break;

}

date=GetElem(L,number,date);

if(GetElem(L,number,date)&&date!=NULL)

cout<<"该节点所在数据是:"<<date<<endl;

else cout<<"\n无此节点或节点无数据！\n"<<endl;

cout<<"\n是否需要继续查询？\n1.是 0.否"<<endl;

cout<<"请选择:";

cin>>ctrl;

}while(ctrl==1);break;

case 4:

do{

cout<<"\n请输入您需要查询的数据值:";

cin>>date;

number=LocateElem(L,date);

if(LocateElem(L,date)&&number>0)

cout<<"该数据所在节点为:"<<number<<endl;

else cout<<"\n不存在该数据！\n"<<endl;

cout<<"\n是否需要继续查询？\n1.是 0.否"<<endl;

cout<<"请选择:";

cin>>ctrl;

}while(ctrl==1);break;

case 5:

do{

cout<<"\n请选择您需要删除的节点:";

cin>>number;

ListDelete(L,number,date);

cout<<"\n是否继续删除？"<<endl;

cout<<" 1.是 0.否 \n请选择:"<<endl;

cin>>ctrl;

}while(ctrl==1);break;

case 6:cout<<"\n双向链表所有数据:";DispList(L);cout<<endl;break;

case 7:cout<<"感谢您的使用,再见！\n\n"<<endl;exit(0);

}//switch尾

}//for尾

}//main尾

相关推荐

链表实验报告

目录

实验报告的内容与要求

一、实验题目

二、实验目的

三、实验内容

四、实验要点与要求

五、算法思想

六、算法描述及流程图

七、实验数据及实验结果

八、实验总结与体会

九、源代码

专栏推荐