《数据结构与算法的java实现》由会员分享，可在线阅读，更多相关《数据结构与算法的java实现（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法的JavaJava实现 北京理工大学计算机学院 金旭亮 线性表(Linear Table)(Linear Table) . . . . . 神经衰弱 17 男 790634 张立立 健康 21 男 790633 刘建平 一般 20 女 790632 陈 红 健康 18 男 790631 王小林 健康情况 年龄 性 别 学 号 姓 名 以下是一张学生健康情况登记表 各学生信息之间的关系是线性的，整个信息集合可视为 一张“线性表” 在JavaJava中实现线性表 如果数据项是固定的，则直接使用数组实现 如果数据项数可变，则通常使用ArrayList类 如果有频繁的数据插入与删除操作，
2、则使用链表 实现 整个表对应于一个类，表中的每行数据对应一个 这个类的实例。 2013/10/22 金旭亮Java系列课程(2013版） 4 动态数组编程技能训练 编写一个控制台程序，用ArrayList保存前页PPT 所示之线性表。 要求： 2013/10/22 金旭亮Java系列课程(2013版） 5 1.定义一个Student类封装所有信息 2.程序定义一组命令，支持对ArrayList中Student对象的 “增”、“删”、“改”、“查”操作。 自引用类 “自己引用自己”的类 2013/10/22 金旭亮Java系列课程(2013版） 6 class MyClassMyClass My
3、ClassMyClass obj; 自引用类自引用类 SelfSelf- -ReferentialReferential ClassClass 在没有指针的面向对象编程语言中，自引用类可 以起到类似于指针的作用 用自引用类实现链表 class Node public int data; public Node nextNode; 2013/10/22 金旭亮Java系列课程(2013版） 7 A B C D header 链表实例 实例： List.java EmptyListException.java ListTest.java 2013/10/22 金旭亮Java系列课程(2013版）
4、8 链表编程基本技能训练- -1 1 编写一个程序，此程序读入一个英文句子，拆分 出其中的单词，按原始顺序生成一个单向循环链 表 2013/10/22 金旭亮Java系列课程(2013版） 9 在此链表中查找某个单词，报告其位置 链表编程基本技能训练- -2 2 修改前一页幻灯片中的代码，将其改为双向 链表 2013/10/22 金旭亮Java系列课程(2013版） 10 利用双向链表，完成将一个句子倒序输出的 功能。 栈（stackstack） 栈顶 栈底 an an-1 . a2 a1 pop push 栈(Stack)是限制在表的一端进行插入和删除运算的线性表， 具有后进先出（LIFO：
5、Last In First Out）特性。向其加入 元素叫“入栈（push）”，取出元素叫“出栈（pop）”。 用JavaJava实现栈 在Java中，可以使用线性表作为内部存储机制， 进一步封装实现堆栈。 实例： （1）StackInheritance.java StackInheritanceTest.java （2）StackComposition.java StackCompositionTest.java 2013/10/22 金旭亮Java系列课程(2013版） 13 从“堆栈”实例中看到 实现复用的两种基本思路之一：组合。 2013/10/22 金旭亮Java系列课程(2013版
6、） 14 从“堆栈”实例中看到 实现复用的两种基本思路之二：继承 2013/10/22 金旭亮Java系列课程(2013版） 15 栈编程基本技能训练 1.编写一个程序，此程序读入一个英文句子，然后 将栈其倒序输出。对比前面使用双向链表的类似 编程练习，你认为这两种实现方式哪种好？ 2.使用堆栈检验括号的匹配 2013/10/22 金旭亮Java系列课程(2013版） 16 假设假设在表达式中在表达式中 （）（）或（或（ ） 等为正确的格式，等为正确的格式， （ ）或（）或（ ）或）或 （）（）) ) 均为不正确的格式均为不正确的格式。 编程编程完成检验一个表达式中括号是否匹配的任务完成检验一
7、个表达式中括号是否匹配的任务。 队列（QueueQueue） 出队 入队 队头 队尾 队列(Queue)是一种运算受限的线性表。它只允许 在表的一端进行插入，而在另一端进行删除。允许删 除的一端称为队头(front)，允许插入的一端称为队 尾(rear)。 用JavaJava实现队列 实现队列的最简单方式是在内部包 容一个链表。 2013/10/22 金旭亮Java系列课程(2013版） 19 front rear QueueInheritance.java QueueInheritanceTest.java 实例： 项目实战 当前银行储蓄所普遍采用了取号排队的方式，请 编写一个“仿真”程序，
8、模拟这一“储户取号排 队顺序办理银行业务”的现实生活场景。 2013/10/22 金旭亮Java系列课程(2013版） 20 提示： 这个仿真程序中包容一个等待队列和多个工作队列。 注意储户是随机到来的，而每个工作人员办理不同储户的时间 有长有短。 真正做到与真实系统高度一致，需要先掌握Java多线程开发的 知识。 树（TreeTree） 树 树是一种在软件开发中常用的非线性结构。树中 包容多个节点，节点之间有关联，具有明显的层 次关系. 2013/10/22 金旭亮Java系列课程(2013版） 22 A J I C B D H G F E 二叉树 二叉树是由n(n=0)个结点的有限集合构成
9、，此集合或者为空集，或 者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是 二叉树。 可以使用自引用类实现二叉树 2013/10/22 金旭亮Java系列课程(2013版） 23 class class TreeNode private Object data; private TreeNode lchild; private TreeNode rchild 遍历二叉树 访问二叉树的所有节点，称为“二叉树的遍历”， 有三种典型的遍历方法 2013/10/22 金旭亮Java系列课程(2013版） 24 Inorder traversal（中序） 若二叉树不空，则： （1）中序遍历左子
10、树； （2）访问根结点； （3）中序遍历右子树。 Preorder traversal（前序） 若二叉树不空，则： （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 Postorder traversal（后序） 若二叉树不空，则： （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 二叉树编程训练 使用自引用类实现一个二叉树，并且对此树进行 深度前序遍历（即从根节点出发，先访问根节点， 如果有左右节点，先访问左节点，再访问右节点， 对每个节点重复此过程）。 2013/10/22 金旭亮Java系列课程(2013版） 25 A B C D E 前序遍历结果：前
11、序遍历结果： ABCDEABCDE 多叉树的面向对象实现方案 2013/10/22 金旭亮Java系列课程(2013版） 26 A B C D E F G H I J K L M N O 对于拥有多个分支的 多叉树，可以给每个 节点添加一个线性表 保存它的所有直接子 节点，采用递归的方 式实现多叉树 多叉树编程实践 Windows/Linux的文件系统是一种“多叉 树”，请编写程序列出指定文件夹下的所有 文件及子文件夹。 2013/10/22 金旭亮Java系列课程(2013版） 27 提示：提示： 使用使用JDKJDK中的中的FileFile类可以列出指定文件夹下的所有文件及类可以列出指定文
12、件夹下的所有文件及 子文件夹，可以使用递归的方法完成这一编程任务。子文件夹，可以使用递归的方法完成这一编程任务。 自动机 自动机 自动机是一种特殊的数据结构，它由若干个状态 组成，各个状态之间可以相互转换。 2013/10/22 金旭亮Java系列课程(2013版） 29 中间状 态1 初始状 态 结束状 态 中间状 态2 中间状 态n DemoDemo：实现状态机 2013/10/22 金旭亮Java系列课程(2013版） 30 状态机编程训练：从字符串中抽取出数字 有效的数字的四种情况：1，1.5，-1, -1.5 可设计一个自动机识别以上四种情况 金旭亮Java系列课程(2013版） 3
13、1 2013/10/22 项目实战训练 P P n n (x) = (x) = p pn n x xn n + p+ pn n- -1 1 x xn n- -1 1 + p+ p1 1 x + px + p0 0 Q Q m m (x) = (x) = q qm m x xm m + q+ qm m- -1 1 x xm m- -1 1+ q+ q1 1x + qx + q0 0 背景知识： 数学上,一元多项式（指数为正整数）可按降幂写成： 其中：pn 、qm不为 0 一元多项式相加运算规则：指数相同的项系数相加 A (x) = 5 x 17 + 9 x 8 +3x+7 B (x) = 9 x 8 +22 x 7 +8 x C (x) = A (x) + B (x) = 5 x 17+ 22 x 7 + 11x +7 示例： 2013/10/22 金旭亮Java系列课程(2013版） 32 项目实战训练 基本要求：基本要求： 编写程序完成一元多项式的常规计算： （1）多项式加减 （2）多项式相乘 （3）一元二次多项式的因式分解 自行设计程序的输入和输出方式 扩充要求：扩充要求： 查询相关资料，完成： （1）一元高次方程根的近似解 （2）绘制一元高次函数的图像 2013/10/22 金旭亮Java系列课程(2013版） 33
