数据结构实验报告

HUBEIHUBEI UNIVERSITYUNIVERSITY OFOF AUTOMOTIVEAUTOMOTIVE TECHNOLOGYTECHNOLOGY 数据结构数据结构 实实 验验 报报 告告 实验项目实验一实验类别基础篇 学生姓名宋大超学生学号 201501149 完成日期 2016 10 9 指导教师袁科 实验成绩评阅日期 评阅教师 实验一 线性表基本操作的编程实现 实验目的实验目的 线性表基本操作的编程实现 要求 线性表基本操作的编程实现 2学时 验证型 掌握线性表的建立 遍历 插入 删 除等基本操作的编程实现 也可以进一步编程实现查找 逆序 排序等操作 存储结构可 以在顺序结构或链表结构中任选 可以完成部分主要功能 也可以用菜单进行管理完成大 部分功能 还鼓励学生利用基本操作进行一些更实际的应用型程序设计 实验性质实验性质 验证性实验 学时数 2H 实验内容实验内容 把线性表的顺序存储和链表存储的数据插入 删除运算其中某项进行程序实现 建议 实现键盘输入数据以实现程序的通用性 为了体现功能的正常性 至少要编制遍历数据的 函数 注意事项注意事项 1 开发语言 使用C 2 可以自己增加其他功能 实验分析 说明过程实验分析 说明过程 本次实验主要是检验单链表数据的插入与删除 实验的第一部分是要求将学生 e 的信息插入到第 i 个 学生的前面 也就是在两个节点之间建立新的节点 我们此次实验有两个要求 第一个是将一个新的学生 信息插入到原来的学生信息当中去 第二个要求是要删除一个学生的信息 以下我将通过示意图和文字的 方式说明这次实验的完成方法 需要说明的是此处的 i 表示学生信息的一个序号元素 在第 i 个学生信息插入时 就得把第 i 个学生之后的所有节点依次向后移动一个位置 在将新的节点 X 插入到第 i 的位置 1Stu 1 2Stu 2 3Stu 3 4Stu 4 nStu n 1Stu 1 2Stu 2 3Stu 3 4Stu 4 5e nStu n 如上图所示 例如将学生 e 的信息插入到第五个位置 我们先将指针指向最后一个位置 由于要插入一个 新的节点 原来数组的长度发生了变化 数据的存储空间位置也随之发生了变化 为此 我们将最后一个 节点向后移动 利用 for 循环将第五个节点之后的依次向后移动 直到所有的元素都向后移动了一位 对于顺序链表的删除工作实际上与其插入工作相反 只需要将表中第 i 1 个到第 n 个节点的所有元素 依次向后移动一个位置 1Stu 1 2Stu 2 3Stu 3 4Stu 4 5Stu 5 1Stu 1 2Stu 2 3Stu 4 4Stu 5 如上图所举例的那样 当我们删除第三个元素是 第三个元素后面的元素依次向前移动了一位 我们 可以直接找到第 i 个元素后面的位置将其向前移动一个 思考题思考题 一 线性表的顺序存储和链表存储的差异 优缺点分析 线性表的顺序存储和链表存储的差异 优缺点分析 答 1 差异 线性表的顺序存储的特点是逻辑上相邻的数据元素 物理存储位置也相邻 并且 顺序表的存储空间 需预先分配 它是静态分配内存 顺序表的存储空间是静态分配的 在程序执行之前必须明确规定它的存 储规模 也就是说事先对 MaxSize 要有合适的设定 设定过大会造成存储空间的费 过小造成溢出 因此 当对线性表的长度或存储规模难以估计时 不宜采用顺序表 线性表的链表存储是在逻辑上相邻的数据元素 物理存储位置不一定相邻 它使用指针实现元素之间 的逻辑关系 并且 链表的存储空间是动态分配的 链表的动态分配则可以克服需要预先设定空间大小的 缺点 链表不需要预留存储空间 也不需要知道表长如何变化 只要内存空间尚有空闲 就可以再程序运 行时随时地动态分配空间 不需要时还可以动态回收 因此 当线性表的长度变化较大或者难以估计其存 储规模时 宜采用动态链表作为存储结构 2 优缺点 线性表的线性表的顺序存储优点顺序存储优点 方法简单 如数组 容易实现 1 不用为表示节点间的逻辑关系而增加额外的存储开销 2 顺序表具有按元素序号随机访问的特点 3 线性表的顺序存储缺点 在顺序表中做插入 删除操作时 移动表中的大量元素 因此对n较大的顺序表效率低 1 需要预先分配足够大的存储空间 估计过大 可能会导致顺序表后部大量闲置 预先分 2 配过小 又会造成溢出 线性表的线性表的链式存储优点链式存储优点 插入 删除运算方便 只需调整指针的指向即可 1 能够动态分配内存 不需要预选分配好空间 能更加有效率的利用空间资源 2 线性表的顺序存储缺点 每次访问链表时只能从头节点开始 不能做到随机访问 1 要占用额外的存储空间存储元素之间的关系 存储密度降低 2 二二 哪些操作引发了数据的移动 哪些操作引发了数据的移动 答 数据的插入 删除 排序 归并等 三三 算法的时间效率是如何体现的算法的时间效率是如何体现的 答 通过时间频度和时间复杂度来体现的 四四 链表的指针是如何后移的 如何加强程序的健壮性 链表的指针是如何后移的 如何加强程序的健壮性 答 1 假如指针p指向某个结点 那么p p next 就可以使指针后移 就是把p所指向结点的 指针域的值重新给指针p 2 增加程序的容错控制 算法尽量避免一些隐患错误 降低时间复杂度 尽量少执行一些 复杂的操作 提高算法的效率等 实验小结实验小结 一 一 重难点重难点 对于我来说由于基础不够扎实 所以最难理解应该是此次实验里面关于 length 的理解 我觉得 此次实验的关于数据的插入与删除算法上的理解很容易 也简单 主要是关于其中的 length 有 很多不明白的地方 最开始定义的时候 int 型 而这里的 length 既可以作为一种指针 也可以作 为一种长度 及相当于数组的下标 只要理解了 length 整个实验就好做了 二 二 心得与体会心得与体会 由于基本功不扎实 导致在做实验的时候遇到很多的困难 好在在之后的询问中 也大概理解 了之前的问题 通过这次实验 使我对 C 语言相关知识理解更加透彻明了 特别是对指针 结 构体的理解使我见识到指针的强大与灵活性 以前在 C 语言上的欠债我觉得我会补起来的 三 三 收获收获 我觉得此次最大的收获就是关于结构体指针的理解 结构体指针的应用太广泛了 几乎贯穿整 个数据结构的全本书 所以 对于指针的理解和应用非常重要 为此我将不懈努力学好 C 语言 这门课 实验代码实验代码 include include include define MAXSIZE 100 根据需要自己设定一个班级能够容纳的最大学生数 typedef struct stu int num 学生学号 char name 10 学生姓名 float score 学生成绩 STUDENT 存放单个学生信息的结构体类型 typedef struct list STUDENT stu MAXSIZE 存放学生的数组定义 静态分配空间 int length 记录班级实际学生个数 LIST 存放班级学生信息的顺序表类型 void listcreate LIST Li int m 初始化班级的学生信息 m 为该班级的初始人数 int i Li length 0 for i 1 istu i num 输入第 i 个学生的学号 printf 姓名 scanf s Li stu i name 输入第 i 个学生的姓名 printf 成绩 scanf f 输入第 i 个学生的成绩 Li length 学生人数加 1 int listinsert LIST Li int i 将学生插入到班级 Li 的第 i 个位置 插入一个学生信息 int j STUDENT e if Li length MAXSIZE 1 测试存储空间是否被占满 printf 无更多的存储空间 n return 0 if i Li length 2 插入位置检验 如果错误就返回 0 退出程序 printf 插入位置有误 n return 0 else printf 请输入插入的学生信息 n printf 学号 scanf d printf 姓名 scanf s e name printf 成绩 scanf f for j Li length j i j Li stu j 1 Li stu j 利用 for 循环将第 i 个及其后面的元素依次往后移动 Li stu i e 移开位置后将学生 e 放入到 i 位置 Li length 完成插入后 学生实际人数加 1 return 1 int listdel LIST Li int i 删除一个学生信息 删除第 i 个学生的信息 if iLi length 删除位置检验 如果错误就返回 0 退出程序 return 0 else for ilength i 利用 for 循环将准备删除的第 i 个及其后面的元素依次往 前移动 Li stu i Li stu i 1 Li length 删除第 i 个学生后 学生人数减 1 return 1 void listdisplay LIST L 显示所有学生信息 int i printf 班级学生信息如下 n printf 学号 姓名 成绩 n for i 1 i L length i printf 10d 10s 10 2f n L stu i num L stu i name L stu i score void showmenu 显示菜单 printf 欢迎使用成绩管理小软件 n printf t1 创建学生信息 n printf t2 插入学生信息 n printf t3 删除学生信息 n printf t4 显示学生信息 n printf t5 退出程序 n void main int no stu count pos LIST stu info while 1 showmenu printf 请输入你的选择 scanf d switch no case 1 printf 班级信息初始化 按任意键继续 n getch printf 请输入班级学生原始人数 scanf d listcreate system cls showmenu listdisplay stu info printf 班级信息初始化已经完成 按任意键继续 n getch system cls break case 2 printf 插入前班级信息 n listdisplay stu info printf 请输入插入位置 scanf d listinsert printf 插入后班级信息 n listdisplay stu info printf 插入已经完成 按任意键继续 n getch system cls break case 3 printf