# 数据结构实验

**Repository Path**: xiao-zihuo/data-structure-experiment

## Basic Information

- **Project Name**: 数据结构实验
- **Description**: 2021年 SCAU华南农业大学 信息管理与信息系统 数据结构实验
作者:汪天沛Paper
- **Primary Language**: Java
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 2
- **Created**: 2022-11-08
- **Last Updated**: 2022-11-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构实验

#### 介绍

2021年 SCAU华南农业大学 信息管理与信息系统 数据结构实验 作者:汪天沛Paper

#### Test01

（1） IsSorted.java判断已按升序排序。 实现isSorted()方法判断整数（对象）数组元素是否已按升序排序，生命如下： Public static boolean isSorted(int[]  table)
//判断整数数组是否已按升序排序 Public static boolean isSorted(Comparable[] table)// 判断对象数组是否已按升序排序 （2） Reverse.java数组逆置。
将一个已知数组中所有元素的次序颠倒为相反次序，求算法的时间复杂度和空间复杂度。 （3） Gcd.java用递归算法求两个整数的最大公因数。 设有不全为0的两个整数a和b,记gcd(a,b)
为他们的最大公因数，即同时能整除a和b的公因数中的最大者。按照欧几里德（Euclid）的辗转相除法。 用递归算法实现gcd(a,b),并给下列调用： ①求两个整数a，b的最小公倍数；②求三个数a,b,c的最大公约数

#### Test02

1） SortedSeqList.java设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作，元素插入位置由其值决定。 2）
SinglyLinkedList.java在SinglyLinkedList或HSLingkedList类中增加下列成员方法 public SinglyLinkedList(E[] element)
//由指定数组中的多个对象构造单链表 public SinglyLinkedList(SinglyLinkedList list)    //以单链表list构造新的单链表，复制单链表 public void concat(
SinglyLinkedList list)           //将指定单链表list链接在当前单链表之后 public Node<E> search(E element)
//若查找到指定对象，则返回结点，否则返回null public boolean contain(E element)    //以查找结果判断单链表是否包含指定对象 public boolean remove(E element)
//移去首次出现的指定对象 public boolean replace(Object obj, E element)     //将单链表中的obj对象替换为对象element public boolean equals(Object
obj)        //比较两条单链表是否相等 3） CirSinglyLinkedList声明循环单链表类CircSinglyLinkedList，实现LList接口中的方法。 4）
DoublyLinkedList.java声明双链表类DoublyLinkedList，实现LList接口中的方法。 5） SortedDoublyLinkedList.java声明排序的双链表类。 6）
CHDoublelyLinkedList.java声明循环双链表类CHDoublelyLinkedList，实现LList接口中的方法。 public class CHDoublelyLinkedList<E> implements
LList<E>     //带头结点的循环双链表类 7） JosephusProblem.java分别采用循环单链表、双链表或循环双链表求解约瑟夫环问题，并分析各操作效率。
9) PolynomialLinkedList.java多项式相加

一条单链表可以表示一个一元多项式，每个结点包含三个域：指数域、系数域和后继结点链。表示多项式3x4-6x2+5x-10的单链表如图所示。给定两个多项式，实现两个多项式的相加算法。 10） RandomList.java有效管理一个1~
n的随机数序列，要求生成初始序列，保证序列中的元素值不重复，当增加或删除一个元素的时候，使序列元素值动态更新。例如，一个MP3播放器使用速记方式播放10首歌曲，曲目播放次序就是由1~
10组成的一个随机数序列，当增加或删除一首歌的时候，要及时更新序列中元素值，不重复播放

#### Test03

（1）
DecimalToBinary.java使用一个栈，将十进制转换成二进制。（2）CircSinglyLinkedQueue.java&CircSinglyLinkedQueue.java分别用循环单链表、循环双链表结构设计队列，并讨论他们之间的差别。
（3） PhoneCallQueue.java使用3个队列分别保留手机最近10个“未接来电”、“已接来电”、“以拨电话”。 （4） Maze.java走迷宫。
一个迷宫如图所示，他有一个入口和一个出口，其中白色单元表示通路，黑色单元表示不通路。试寻找一条从入口到出口的路径，每一部只能从一个白色单元走到相邻的白色单元，直至出口。分别用站和队列求解问题。 （5）
KnightTravel.java骑士游历 骑士游历问题是指，在国际象棋的棋盘（8行*
8列）上，一个马要遍历棋盘，即走到棋盘上的每一格，并且每隔只到达一次。设码在棋盘的某一位置（x,y）上，按照“走马日”的规则，下一步有8个方向走，如图所示。若给定起始位置（x0,y0）,使用站和队列探索出一条马遍历棋盘的路劲。

#### Test04

（1） 在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。 ① 输入叶子结点。 ② 求二叉树中叶子结点个数。 ③ 将每个结点的左子树与右子树交换。 ④ 验证二叉树的性质3：n0=n2+1。 ⑤
输出值大于k的结点。 ⑥ 已知先根和中根次序遍历序列构造二叉树。 ⑦ 以广义表表示构造二叉树。 ⑧ 判断两颗二叉树是否相等。 ⑨ 求结点所在的层次。 ⑩ 求一颗二叉树在后根次序遍历下第一个访问的结点。 ⑪ 复制一颗二叉树。 ⑫
判断一颗二叉树是否为完全二叉树。 ⑬ 实现二叉树后根次序遍历的非递归算法。 （2） 声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。 ① 构造一颗三叉链表表示的二叉树。 ② 返回指定结点的父母结点。 ③
返回指定结点的所有祖先结点。 ④ 返回两结点最近的共同祖先结点。 （3） 在一颗中序线索二叉树中，实现以下操作。 ① 调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树 。 ② 按后根次序遍历中序线索二叉树。 ③
在构造二叉树时进行线索化。 ④ 插入、删除操作。