数据结构课程实验报告(12)

1、课程设计报告标题：数据结构课程名称：数据结构专业课：信息安全1302学生编号。u201315140姓氏：石丰指导员：周世扬报告日期：2015年5月10日计算机科学与技术学院目录1我们的实验概述12实验1基于序列结构的线性表的实现22.1问题描述22.2系统设计2.2.1背景22.2.2系统要求2.3系统实施22.3.1顺序表的动态分配存储结构和部分量的定义22.3.2相关函数的描述和一些函数的基本算法思想32.3.3实验预期和程序运行结果52.4效率分析123实验2基于链式结构的线性表的实现133.1问题描述133.2系统设计133.2.1背景133.2.2系统要求133.3系统实施133.3

2、.1顺序表的动态分配存储结构和部分量的定义133.3.2相关函数的描述和一些函数的基本算法思想133.3.3实验预期和程序运行结果153.4效率分析224实验3基于二进制链表的二叉树实现244.1问题描述244.2系统设计244.2.1背景244.2.2系统要求244.3系统实施244.3.1顺序表和部分总距离的动态分配和存储结构244.3.2相关功能和基本算法思想的描述254.3.3实验预期和程序运行结果264.4效率分析345实验总结与评价356附录366.1实验1代码366.2实验2代码436.3实验3代码521课程实验概述本次数据结构计算机实验是对我们平时所学综合知识的综合考察，是课堂

3、、自学和实践效果的集中体现。这个实验分为三个小实验。报告遵循基于序列结构的线性表、基于链结构的线性表和基于二进制链表的二叉树的顺序。每个小实验分为四个部分：问题描述、系统设计、系统实现和效率分析。问题描述部分详细描述了实验主题并确立了问题的背景；系统设计部分分析问题，阐述解决问题的原则，设计一个可演示的系统；系统实现了一些演示系统功能，并验证了系统功能是否符合预期，能否解决问题描述中的需求；效率分析部分对系统效率进行分析，并提出优化方法。计算机科学是一门理论与实践相结合的学科，在学习过程中不能放弃实验。数据结构的计算机实验可以提高学生设计、编写和调试程序的能力，使学生掌握数据组织方法和计算机表

4、示方法，从而选择合适的数据逻辑和存储结构，设计相应的运算操作，将实际问题转化为计算机的内部表示和处理方法，掌握时间和空间复杂度分析的基本技术。因此，数据结构计算机实验是一门非常重要的基础实验课程。实验1基于序列结构的线性表的实现2.1问题描述线性列表是最常用和最简单的数据结构。线性表是一种非常灵活的数据结构，其长度可以根据需要增加或缩短，即线性表的数据元素不仅可以访问，还可以插入和删除。线性表的顺序表示是指具有一组连续地址的存储单元的线性表的数据元素的顺序存储。2.2系统设计2.2.1背景运行环境：windows编程语言：c开发环境：开发中心2.2.2系统要求为了设计一个具有顺序存储结构的线性

5、表，需要一个系统来演示，该系统可以执行表的创建、表的销毁、表的置零、空表的判断、表的长度计算、元素读取、前驱读取、后继读取、元素搜索、元素插入、元素删除和遍历线性表。2.3系统实施2.3.1顺序表的动态分配存储结构和部分量的定义#定义真1#定义false 0#定义确定1#定义error 0#定义infastable-1#定义overflow -2 /全局数量定义typedef int状态；typedef int elemtype/数据元素类型定义#定义list_init_size 100 /定义初始表格长度# define listindex 10/定义表格长度的增量typedef结构 /序列

6、表的定义(序列结构)elemtype * elemint长度；int listsize sqlist2.3.2相关函数的描述和一些函数的基本算法思想状态intlist(sqlist l)；状态销毁列表(sqlist l)；状态clearlist(sqlist l)；状态列表空(sql列表)；int list length(sql list l)；状态getelem(sqlist l，int i，elem type e)；status locateleem(sqlist l，elemtype e)；状态优先级(sqlist 1，elemtype cur，elemtype pre _ e)；状态下

7、一个元素(sqlist 1，elemtype cur，elemtype next _ e)；状态列表插入(sql列表，int i，elemtype e)；状态列表删除(sql列表，int i，elemtype e)；状态列表(sql列表)；状态intlist(sql list)/功能描述：创建一个空的序列表l/算法思想：应用存储空间的大小为list_init_size，表的长度设置为0，创建成功后返回ok，应用失败后返回overflow。状态销毁列表(sql列表)/功能描述：破坏序列表l，释放空间/算法思想：如果表存在，释放存储空间，将表长度设置为0，返回ok；表不存在，返回错误状态clear

8、list(sql list)/功能描述：清空序列表/算法思想：如果表存在，将表长度设置为0，返回ok；表不存在，返回错误状态列表空(sql列表)/功能描述：判断表是否为空/算法思想：如果表存在且不为空，返回真；如果表为空，则返回假；如果表不存在，返回errorint list length(sql list l)/功能描述：计算表格长度/算法思想：如果表存在，返回l长度；表不存在，返回错误状态getelem(sql list，int i，elemtype e)/功能描述：读取ith元素/算法思想：读取ith元素，直接在这个子函数中打印出来；如果是il.length，返回overflowstat

9、us locateleem(sql list l，elemtype e)/函数描述：获取e在l中的位置i/算法思想：打印出符合e的l中所有元素的位置。状态优先级(sql列表，类型e)/功能描述：在l中获取e的前身。/算法思想：如果e是第一个元素，打印e不带前驱，否则打印e的前驱状态下一个元素(sql列表，元素类型e)/函数描述：获取l中e的后继。/算法思想：打印e的后继元素，如果e是尾部元素，则打印没有后继元素的e状态列表插入(sql列表，int i，elemtype e)/功能描述：在序列表l的第i个位置插入元素e/算法思想：如果il.length，返回overflow；如果l.length

10、=list_init_size，则应用list indentation的空间；在位置i插入元素e，然后将元素向后移动一位，表格长度将增加一位状态列表删除(sql列表，int i)/功能描述：删除序列表l中的ith元素/算法思想：如果il.length，返回overflow；删除第一个位置的元素e，打印e，然后分别向前移动一个位置状态列表(sql列表)/功能描述：遍历序列表并打印出来/算法思想：遍历序列表并打印出来2.3.3实验预期和程序运行结果图2.1界面如果创建了序列表，则分别销毁和清空序列表图2.2创建序列表图2.3存在和销毁顺序列表图2.4表格存在，空白订单表格如果没有创建序列表，分别销

11、毁和清空序列表图2.5表格不存在，销毁订单表格图2.6该表不存在，订单表为空在这个程序中，序列表是通过函数状态列表插入(sqlist l，int i，elementtype e)输入的，输入结构是位置数据(i，e)。当输入为(1，111) (2，222) (3，333) (1，333) (5，333)时，理论遍历结果为(1)图2.7遍历结果从上面可以看出，程序是正确的，然后用这组数据对其他函数进行了实验图2.8确定表是否为空图2.9计算表长度图2.10阅读元素图2.11获取元素位置图2.12获得元素前体图2.13获取元素序列删除第一个元素后(删除的元素是333)，理论遍历结果是(1，111)(

12、2，222)(3，333)(4，444)图2.14删除元素图2.15删除后的结果从上面可以看出，这个程序是正确的2.4效率分析状态列表插入(sql列表，int i，elemtype e)；状态列表删除(sql列表，int i，elemtype e)；插入和删除功能，该算法的时间复杂度与插入或删除元素后元素的移动有关，即它取决于插入和删除的位置，并且在每个位置操作的机会相等，平均移动一半(n/2)个元素，所以时间复杂度为o(n)状态getelem(sqlist l，int i，elem type e)；status locateleem(sqlist l，elemtype e)；状态优先级(sq

13、list 1，elemtype cur，elemtype pre _ e)；状态下一个元素(sqlist 1，elemtype cur，elemtype next _ e)；上述函数都是查找函数，时间复杂度由定位时的周期数决定，时间复杂度也是o(n)状态列表(sql列表)；遍历函数的复杂度由表的长度决定，复杂度为o(n)其他函数的复杂度为0(1)3实验2基于链式结构的线性表的实现3.1问题描述线性表的链式存储结构使用一组任意的存储单元来存储线性表的数据元素。3.2系统设计3.2.1背景运行环境：windows编程语言：c开发环境：开发中心3.2.2系统要求设计一个链式存储结构的线性表，需要一个

14、系统来演示，该系统可以进行表的创建、表的销毁、表的置零、空表的判断、表的长度计算、元素的读取、前驱的读取、后继的读取、元素的搜索、元素的插入、元素的删除以及遍历线性表3.3系统实施3.3.1顺序表的动态分配存储结构和部分量的定义#定义真1#定义false 0#定义确定1#定义error 0#定义infastable-1#定义overflow -2 /全局数量定义typedef int状态；typedef int elemtype/数据元素类型定义typedef结构列表节点 /链结构定义电子类型数据；结构列表节点*下一个；列表节点，* lilist3.3.2相关函数的描述和一些函数的基本算法思想状态列表(lililist l)状态销毁列表(lilist l)状态清除列表(