实验一报告要点.doc

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 实 验 报 告 实验项目 实验一 实验类别 挑战篇 学生姓名 卢雄 学生学号 201501147 完成日期 2016-09-30 指导教师 袁科 实验成绩 评阅日期 评阅教师 实验一 线性表基本操作的编程实现 【实验目的】 线性表基本操作的编程实现 要求： 线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。 【注意事项】 1.开发语言：使用C。 2.可以自己增加其他功能。 【实验分析、说明过程】 一、系统功能模块图 二：流程图分析 Y N Y N Y N 三：几点说明 1、单链表的创建是有头结点的，并且采用的尾插法； 2、链表的输出是从首结点开始遍历的； 3、单链表的排序用的是类似冒泡的方法来对链表的元素进行排序的； 4、结点中的数据是以int型为例的，可以改成其他类型； 5、LA与LB合并的关键： 当LA或LB为空时就直接对LA或LB进行排序且输出 当LA与LB都不为空时： while(p-next!=NULL) p=p-next;//p指向LA,把p移到LA的表尾 p-next=q-next;//q指向LB,把LA的表尾接到LB的表头(首节点) 四：运行结果截图： 1、当LA为空时： 2、当LB为空时： 3、当LA、LB都不为空时： 【思考问题】 一：线性表的顺序存储和链表存储的差异？优缺点分析？ 答：1、差异： 线性表的顺序存储的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配，它是静态分配内存。顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。 线性表的链表存储是在逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。链表的动态分配则可以克服需要预先设定空间大小的缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。因此，当线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。 2、优缺点： 线性表的顺序存储优点： 方法简单，如数组，容易实现。 不用为表示节点间的逻辑关系而增加额外的存储开销。 顺序表具有按元素序号随机访问的特点。 线性表的顺序存储缺点：