《数据结构》课程实验报告 (21)

《《数据结构》课程实验报告 (21)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程实验报告课程名称：数据结构专业班级：信息安全1302班学号：姓名：指导教师：报告日期：2015年5月14日计算机科学与技术学院目录1课程实验概述12实验一基于顺序结构的线性表实现22.1问题描述22.2系统设计22.3系统实现102.4效率分析123实验二基于链式结构的线性表实现133.1问题描述133.2系统设计133.3系统实现233.4效率分析254实验三基于二叉链表的二叉树实现264.1问题描述264.2系统设计264.3系统实现454.4效率分析475实验总结与评价481课程实验概述一、实验目的（1）加深对数据

2、结构和算法的理解，进一步提高学生的编程能力；（2）培养和提高学生分析问题和解决问题的能力；（3）整理资料，撰写规范的实验报告二、实验内容数据结构上机有三个实验，这三个实验分别是：（1）基于顺序存储结构，实现线性表的基本的、常见的运算；（2）基于链式存储结构，实现线性表的基本的、常见的运算；（3）基于二叉链表，实现二叉树的基本的、常见的运算。三、实验要求（1）独立完成，完全雷同者记0分；（2）撰写实验报告，每个实验报告包括如下内容–问题描述，系统设计，系统实现，效率分析；（3）《实验报告》和《源程序》，以班为单位提交光盘。47

3、2实验一基于顺序结构的线性表实现2.1问题描述基于顺序存储结构，实现线性表的基本的、常见的运算2.2系统设计2.2.1需求分析1.本演示程序中，结点的元素限定为int类型。结点输入由ListInsert函数实现，用户可以选择插入点和插入的数据。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入程序规定的运算命令，相应的输入数据和运算结果显示在其后。3.程序执行的命令包括：1.IntiaList；2.DestroyList；3.ClearList；4.ListEmpty；5.Li

4、stLength；6.GetElem；7.LocatElem；8.PriorElem；9.NextElem；10.ListInsert；11.ListDelete；12.ListTrabverse0.Exit。2.2.2概要设计1.本程序包含两个模块：（1）主程序模块：voidmain(){初始化（清屏和显示菜单）；do{接受命令；处理命令；}while（“命令”=“退出”）；}（2）基于顺序结构的线性表单元模块——实现基于顺序结构的线性表的抽象数据类型。2.各模块之间的调用关系如下：主程序模块基于顺序结构的线性表单元模块2

5、.2.3详细设计1.根据基于顺序结构的线性表的基本操作的特点，基于顺序结构的线性表采用数组实现。47基于顺序结构的线性表的类型定义如下：typedefintstatus;typedefstruct{intitem1;}Elemtype;//结点类型typedefstruct{Elemtype*elem;intlength;intlistsize;}SqList;//基于顺序结构的线性表类型基于顺序结构的线性表的基本操作设置如下：statusIntiaList(SqList*L);//构造一个空的线性表statusDestro

6、yList(SqList*L);//销毁线性表LstatusClearList(SqList*L);//将L重置为空表，L->elem置为NULL，L->length=0statusListEmpty(SqListL);//若L为空表，则返回TRUE,否则返回FALSEstatusListLength(SqListL);//返回L中数据元素的个数statusGetElem(SqListL,inti,Elemtype*e);//用e返回L中第i个数据元素的值//i的合法值为[1,ListLength(L)]statusLoca

7、tElem(SqListL,Elemtypee,status(*compare)(Elemtypex,Elemtypey));//在顺序线性表L中查找第一个值与e满足compare()的元素的位序//若找到，则返回其在L中的位序，否则返回0statusPriorElem(SqListL,Elemtypecur,Elemtype*pre_e);//若cur是L的数据元素，且不是第一个，则用pre_e返回cur的前驱，否则操作失败，pre_e无定义statusNextElem(SqListL,Elemtypecur,Elemty

8、pe*next_e);//若cur是L的数据元素，且不是最后一个，则用next_e返回cur的后继，否则操作失败，pre_e无定义statusListInsert(SqList*L,inti,Elemtypee);//在顺序线性L中第i个位置之前插入新的元素e//i的合法值为[1,List