数据结构实验报告-线性结构及其应用.docx

《数据结构》实验报告

PAGE1

哈尔滨工业大学(深圳)

《数据结构》实验报告

实验一

线性结构及其应用

学院:计算机科学与技术

姓名:

学号:

专业:

计算机科学与技术

日期:

2020-04-05

一、问题分析

题目要求收集两个班的学生成绩信息并按降序排列，其中每个学生的数据包括班级，学号和成绩信息，需要用一个结构体作为整体存储。并且数据是可以不断添加进来的，可以用两个线性表分别来存储两个班级的学生信息。但是如果用数组等顺序存储的方式来存储数据，每次存储一位学生的信息都要进行大量移动操作，并且学生数量未知，用顺序存储可能造成资源的浪费。这时利用链表的插入和删除操作时间复杂度仅为O（1）的良好特性，并且可以根据实际情况动态扩展内存，可以选择线性链表为存储结构。合并两个班级的学生信息，可以用链表的归并算法，因为两个链表都是有序的，归并的时间复杂度为O（n）。

二、详细设计

2.1设计思想

1、选择线性链表做为存储结构。

每一个节点包含学生的三个信息信息和一个指向下一个节点的指针，节点与节点之间通过降序连接起来。每次要插入一个元素，先动态申请内存，遍历链表找到第一个不比它成绩值大的元素，在它前面插入该元素（要考虑插入位置为链表头和尾的特殊情况）。这样就可以按降序建立一个班级的链表，不用每次增加元素都要进行排序，十分方便。两个班级的链表分别用两个头指针管理，可以构造一个指针数组来存储这两个头指针，这样在不只是2个班级的情况下只需增加数组的大小即可。

2、链表的遍历

遍历时先判断是否为空表，如果不为空则用一个新指针指向第一个节点，通过节点与节点之间的联系便可以遍历链表。遍历链表时可以进行匹配学号操作，实现按照学号查询成绩和删除学生信息。也可以打印全部学生信息。

3、链表的合并和反转

运用归并算法进行两个有序链表的合并。分别用两个指针指向两个链表的头结点，大的就添加为一个新链表的节点，循环比较。这样就可以得到一个合并了两个班级信息的新链表。反转则利用两个指针，第一个指向合并后的新链表节点，第二个指向一个逆序建立链表的反转节点，先复制原合并链表指针指向节点的数据，让他指向反转指针指向的节点，再让反转指针指向这个新节点。循环后便可以O(n)的时间复杂度构建一个反转链表。

2.2存储结构及操作

(1)存储结构（一般为自定义的数据类型，比如单链表，栈等。）

链表节点结构体StudentLinkedListNode

内容包括ClassID（班级）,StuID（学号）,Grade(成绩，以上均为int类型)，指向结构体StudentLinkedListNode的指针next。

(2)涉及的操作（一般为自定义函数，可不写过程，但要注明该函数的含义。）

函数名

参数

功能

返回值

printLinkedListNode

链表节点指针

打印一个节点学生的各项数据

无

outputStudentLinkedList

链表头指针

打印这个头指针指向链表的所有节点值（三项信息）

无

studentLinkedListCreate

学生班级，学号和成绩

根据参数新建一个节点

指向新节点的指针

studentLinkedListCopy

链表节点指针

根据节点指针的内容值复制出一个新节点

指向新节点的指针

studentLinkedListAdd

链表头指针，要插入的链表节点指针

按照降序将该节点插入到合适位置

链表头指针

searchByID

链表头指针，要查找的学号

遍历链表查找是否存在有该学号对应的学生信息，有就输出该学生信息

无

deleteByID

链表头指针，要删除的学号

遍历链表查找是否存在有该学号对应的学生信息，有就删除该节点

链表头指针

mergeLinkedList

链表头指针数组

合并两个班级的成绩情况

合并后的链表头指针

reverseLinkedList

链表头指针

反转这个链表

反转后的链表头指针

isExistStudentId

链表头指针，要查重的学号

遍历链表确认是否有重复的学号

布尔值，存在返回真，不存在返回假

2.3程序整体流程

整体流程：

核心算法流程：

（1）插入节点studentLinkedListAdd：

（2）遍历链表（查找，删除，查找）

searchByID

deleteByID

outputStudentLinkedList：

（3）合并链表

mergeLinkedList

（4）翻转链表

reverseLinkedList

三、用户手册

如：(1)输入数据的方式；(2)实现各种功能的操作方式等。

进入程序，首先会出现一个选择操作菜