实验一 线性表基本操作的编程实现.pdf

《实验一 线性表基本操作的编程实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY数据结构实验报告这里一定填写清楚自己选择的实验层次。（基础、提高或者挑战）实验项目实验类别基础篇学生姓名学生学号完成日期指导教师实验成绩评阅日期评阅教师实验一线性表基本操作的编程实现【实验目的】线性表基本操作的编程实现要求：线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更

2、实际的应用型程序设计。【实验性质】验证性实验（学时数：2H）【实验内容】把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。【注意事项】1.开发语言：使用C。2.可以自己增加其他功能。【实验分析、说明过程】在第i个学生信息插入时，把第i个学生之后的所有节点依次向后移动一个位置。再将新的节点X插入到第i的位置。由于要插入一个新的节点，原来数组的长度发生了变化。数据的存储空间位置也随之发生了变化，为此，我们将最后一个节点向后移动，利用for循环插入节点之后的依次向后

3、移动，直到所有的元素都向后移动了一位。对于顺序链表的删除实际上与其插入相反，只需要将表中第i+1个到第n个节点的所有元素依次向前移动一个位置。【思考问题】1.线性表的顺序存储和链表存储的差异？优缺点分析？线性表的顺序表：指的是用一组地址连续的存储单元，依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征：①线性表中的所有元素所占的存储空间是连续的。②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表逻辑上相邻、物理也相邻。优点：①无须为表示结点间的逻辑关系而增加额外的存储空间。②可以方便的随机存取表中的任一结点。③存储密度大（＝1），存储空间

4、利用率高。缺点：①插入和删除运算不方便，需移动大量元素。②由于要求占用连续的存储空间，存储分配只能按最大存储空间预先进行，致使存储空间不能得到充分利用。③表的容量难以扩充。线性表的链式存储：指用一组任意的存储单元存储线性表中的数据元素。线性表的链式存储结构具备的基本特征：链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：①插入、删除操作很方便，可通过修改结点的指针实现，无须移动元素。②方便扩充存储空间。缺点：①不能随机存取元素。②存储密度小（小于1），存储空间利用率低。2.那些操作引发了数据的移动？

5、插入、删除、排序、归并。3、算法的时间效率是如何体现的？通过时间频度和时间复杂度来体现的。4、链表的指针是如何后移的？如何加强程序的健壮性？p=p->next使指针后移，就是把p所指向结点的指针域的值重新给指针p。增加程序的容错控制；算法尽量避免一些隐患错误；降低时间复杂度；尽量少执行一些复杂的操作；提高算法的效率等。【实验小结】(总结本次实验的重难点及心得、体会、收获)通过这次写实验，我理解了这门课的本质。数据结构像是身体的骨骼，而C语言是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C语言

6、，将各种操作描述出来构成算法。数据结构+算法=程序设计。在这次设计的过程中，我还遇到了很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C的程序设计，在执行时出现了问题。后来问同学，指出我的错误，获益不少。我又重新整理思路，把顺序表的基本操作写好了。【附录-实验代码】#include#include#include#defineMAXSIZE100//根据需要自己设定一个班级能够容纳的最大学生数typedefstructstu{intnum;//学生学号charname[10];//学生姓名float

7、score;//学生成绩}STUDENT;//存放单个学生信息的结构体类型typedefstructlist{STUDENTstu[MAXSIZE];//存放学生的数组定义，静态分配空间intlength;//记录班级实际学生个数}LIST;//存放班级学生信息的顺序表类型voidlistcreate(LIST*Li,intm)//初始化班级的学生信息//m为该班级的初始人数{inti;Li->length=0;for(i=1;i<=m;i++)//输入m个学生的所有信息{printf("请输入第%d个学生的信息:",i);printf("学号=");sca