重庆工商大学
《数据结构》 课程实验报告封面
专业班级：___ ___ 学 号：__ _____
学生姓名：______ _ ______ 实验室：__________________
实验题目：_______ 双链表的基本操作方法_______________
指导教师：______ ______ 成 绩：__________________
日期：2013年_9 月____日 第_ 4_ 周 星期__3_节次____
评分表
目录
实验题目 ---------------------------------------------------------------------------------- 1
实验目的 ---------------------------------------------------------------------------------- 1
实验内容 ---------------------------------------------------------------------------------- 1
实验要点与要求 ------------------------------------------------------------------------- 1
算法思想 ---------------------------------------------------------------------------------- 1
算法描述 ---------------------------------------------------------------------------------- 1
算法流程图 ---------------------------------------------------------------------------------- 4
实验测试与结果 ------------------------------------------------------------------------- 5
总结体会 ---------------------------------------------------------------------------------- 5
源代码 ---------------------------------------------------------------------------------- 6
实验报告的内容与要求
一、实验题目
双链表的基本操作
二、实验目的
了解双链表的结构特点及有关概念，掌握双链表的基本操作算法。
三、实验内容
实现双链表的初始化、销毁、建立、插入、删除和查找等基本操作。
四、实验要点与要求
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尾