重庆工商大学
《数据结构》 课程实验报告封面
专业班级：___ ___ 学 号：__ _____
学生姓名：______ _ ______ 实验室：__________________
实验题目：_______ 双链表的基本操作方法_______________
指导教师：______ ______ 成 绩：__________________
日期：2013年_9 月____日 第_ 4_ 周
评分表 序号 1 星期__3_节次____
项目 算法思想 算法描述 实验数据与结果 总结 排版 正确性 友好性 可读性 健壮性 创新与多样性 总分 自评分 互评分 组长评分 教师评分 2 3 10 4 2 63 4 4 4 4 实验报告质量 2 3 4 5 6 源程序质量 10 合计 总分 评分人签字
7 8 9
目录
实验题目 ---------------------------------------------------------------------------------- 1
实验目的 ---------------------------------------------------------------------------------- 1
实验内容 ----------------------------------------------------------------------------------
实验要点与要求 -------------------------------------------------------------------------
算法思想 ----------------------------------------------------------------------------------
算法描述 ----------------------------------------------------------------------------------
算法流程图 ----------------------------------------------------------------------------------
实验测试与结果 -------------------------------------------------------------------------
总结体会 ----------------------------------------------------------------------------------
源代码 ----------------------------------------------------------------------------------
1 1 1 1 4 5 5 6
实验报告的内容与要求
一、实验题目 双链表的基本操作 二、实验目的
了解双链表的结构特点及有关概念，掌握双链表的基本操作算法。 三、实验内容
实现双链表的初始化、销毁、建立、插入、删除和查找等基本操作。 四、实验要点与要求
1. 处理的数据类型即ElemType的类型： 基本版要求：整型、字符型
扩展版要求：字符串型（基础较好的同学）
2. 参数类型分别用指针、引用和引用型指针
五、算法思想
和顺序表不同的是，链表不需要占用一整块事先分配的固定的内存空间，而是采用动态空间链接的方式进行。在每个存储节点都包含了元素本身的信息(数据域)和元素之间的逻辑联系(指针域)，就双链表而言，其指针域包含了前驱指针和后续指针，分别用于指向当前节点的上一个节点和下一个节点，故而，对双链表进行操作的时候，要考虑其前驱指针和后续指针的指向，否则容易引起混乱。在链表的操作中，首先最重要的是定义一个头结点，因为指向头结点的指针唯一标识该链表，本次程序采用了不包含任何数据的头节点定义方式。
六、算法描述及流程图
由于程序的分支较多，需要实现的功能也不尽相同，和顺序表一样，我选择了其中插入数据的分支来具体描述其算法，并比较链表和顺序表的操作上的不同：
do{
第 1 页 共 3 页
c=ListLength(L);
cout<<\"\\n请输入您需要插入的节点位置
(0 if(number<0||number>l+1){cout<<\"输入错误！\"< ListInsert(L,number,date); cout<<\"\\n是否需要继续插入？\\n\"; cout<<\" 1.是 0.否\"< }while(ctrl==1);break; bool ListInsert(DLinkList *&L,int i,ElemType e)//插入数据 { int j=0; DLinkList *p=L,*s; while(j 第 2 页 共 4 页 } 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<<\"插入成功！\"< 第 3 页 共 5 页 基本流程图如下： 分支入口输入节点并判断错误退出输入数据并调用插入函数错误退出P针继续插入P-nextP针P-nexts针插入完成s针插入准备是否继续插入判断 第 4 页 共 6 页 退出 七、实验数据及实验结果 由于程序和顺序表一样定义为char类型，故而测试的数据和顺序表一样：输入整型，浮点型，字符型，字符串这几种不同类型的数据后，程序的不同输出结果，并且根据顺序表节点数为正整数的特征，测试了输入浮点数，字符，字符串，负数这几种情况下的输出结果。 对于插入的数据来说总共测试了以下几种数据测试数据及结果如下： 序号 测试类型 输入数据 期望输出结果 实际输出结果 测试结论 程序对于定义范围内的值可以正确处理 超出定义范围的值会引起程序崩溃或者错误 合法数据 1,2,3,4,a,b1,2,3,4,a,b1,2,3,4,a,,c,d ,c,d -1 1.5 go b,c,d - 死循环，死循环 非法数据 -1 1.5 go 对于节点，主要测试了以下几种特殊状态的值 实验数据及结果如下: 测试类型 非法节点 输入节点 -1 1.5 期望输出结果 实际输出结果 相应节点的数据 输入错误！ 程序执行正确，但存入链表的字符为’.’ 死循环 死循环 测试结论 对负数可以正确处理 浮点型数据转化为3个字符处理 错误的数据类型引起程序错误 非法节点 A asd 相应节点的数据 通过对于程序处理异常数据的结果进行分析，我发现和双链表的错误和顺序表一样，都是数据类型的不兼容引起程序崩溃 八、实验总结与体会 程序实现了双链表的基本操作，和顺序表相比较，链表的操作更灵活，没有固定的长度限制，只要内存足够，就可以链接数据。大大提高了程序的灵活性和数据处理能力，但是我也发现，链表的指针指向很容易出错，如果指向不对，就会引起系统混乱出现数据异常或者是编译不通过的情况，这样一来对于逻辑要求又有了更高的要求。 第 5 页 共 7 页 九、源代码 #include 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);//插入数据 第 6 页 共 8 页 extern bool ListDelete(DLinkList *L,int i,ElemType &e);//删除第i个位置的元素 //函数定义 void InitList(DLinkList *&L)//初始化链表 { } int ListLength(DLinkList *L)//链表求长 { } void DispList(DLinkList *L)//输出链表 { 第 7 页 共 9 页 L=(DLinkList *)malloc(sizeof(DLinkList)); L->next=L->prior=NULL; cout<<\"新建成功！\"< DLinkList *p=L->next; while(p!=NULL) { } return i; p=p->next; i++; } DLinkList *p=L->next; int c; c=ListLength(L); if(c==0)cout<<\" 链表为空，请插入数据！\\n\"< cout< bool GetElem(DLinkList *L,int i,ElemType &e)//按位置查找 { int j=0; DLinkList *p=L; while(j j++; p=p->next; } if(p==NULL) return false; else { } e=p->date; return true; int LocateElem(DLinkList *L,ElemType e)//按元素师查找 { } bool ListInsert(DLinkList *&L,int i,ElemType e)//插入数据 第 9 页 共 11 页 int i=1; DLinkList *p=L->next; while(p!=NULL && p->date!=e) { } if(p==NULL) return 0; p=p->next; i++; else return i; { } 第 10 页 共 12 页 int j=0; DLinkList *p=L,*s; while(j return false; j++; p=p->next; 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<<\"插入成功！\"< int j=0; DLinkList *p=L,*s; while(j return false; j++; p=p->next; else { s=p->next; if(s==NULL) return false; p->next=s->next; if(s->next!=NULL) p->next->prior=p; free(s); cout<<\"删除成功！\"< return true; } } //测试函数 int main() { DLinkList *L; int choose;//主菜单选择分支 int number;//存储数据位置 ElemType date;//储存数据 int c;//顺序表长度 int ctrl;//函数继续控制变量 for(;;) { cout<<\" \"< 第 12 页 共 14 页 * 欢迎使 * 1.新 * 2.数 据插入 *\"< 置查找 *\"< 素查找 *\"< 除数据 *\"< 历链表 *\"< 出程序 *\"< *-*-*-**-*-*-**-*-*-*\"< case 1:InitList(L);break; case 2: do{ c=ListLength(L); cout<<\"\\n请输入您需要插入的节点位置 (0 cin>>number; if(number<0||number>c+1){cout<<\"输入错误！ \"< ListInsert(L,number,date); cout<<\"\\n是否需要继续插入？\\n\"; cout<<\" 1.是 0.否\"< }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<<\"该节点所在数据是:\"< \\n\"< cout<<\"\\n是否需要继续查询？\\n1.是 0.否 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<<\"该数据所在节点为:\"< }while(ctrl==1);break; case 5: do{ 第 15 页 共 17 页 cout<<\"\\n请选择您需要删除的节点:\"; cin>>number; ListDelete(L,number,date); cout<<\"\\n是否继续删除？\"< }while(ctrl==1);break; 6:cout<<\"\\n双向链表所有数 case 据:\";DispList(L);cout< \\n\\n\"< }//for尾 }//main尾 第 16 页 共 18 页 因篇幅问题不能全部显示，请点此查看更多更全内容