Java语言程序设计基础教程课件(第12章)

第12章
常见数据结构的Java实现
链表的基本操作 栈 树集 树映射 散列表 散列集 向量
12.1链表
线性表是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关系是一对一的关系，即除了 第一个和最后一个数据元素之外，其它数据元素都是首 尾相接的。线性表的逻辑结构简单，便于实现和操作。 因此，线性表这种数据结构在实际应用中是广泛采用的 一种数据结构。 线性表的逻辑结构是n个数据元素的有限序列： (a1, a2 ,a3,…an) n为线性表的长度(n≥0)，n=0的表称为空表。
程序运行结果如下所示：
12.1.2 LinkedList类中的常用方法 类中的常用方法
LinkedList的常用方法包括： public boolean add(Object element) //向链表末尾添加一个新的节点， 该节点中的数据是参数element指定的对象。 public void add(int index, Object element ) //向链表指定位置添加节 点，该节点中的数据是参数element指定的对象。 public void addFirst(Object element) //向链表头添加新节点，该节点 中的数据是参数element指定的对象。 public void addLast(Object element) //向链表尾添加新节点，该节点 中的数据是参数element指定的对象。 public Object removeFirst() //删除第一个节点，并返回这个节点中的 对象。 public Object removeLast() //删除最后一个节点，并返回这个节点中 的对象。
使用Iterator接口遍历链表： 接口遍历链表： 使用 接口遍历链表
一个链表对象可以使用iterator()方法获取 Iterator变量， Iterator对象中每个数据成员刚 好是链表节点中的数据，而且这些数据成员是 按顺序存放在Iterator对象中的， Iterator对象 使用next()方法可以得到其中的数据成员。 在例子12-1和例子12-2中我们借助get方法实 现了遍历链表。我们可以借助Iterator对象实现 遍历链表，一个链表对象可以使用iterator()方 法获取一个Iterator对象，后者使用next()方法 遍历链表。在下面的例子12-3中，我们把学生 的成绩存放在一个链表中，并实现了遍历链表。
12.2.1栈的常用方法
使用java.util包中的Stack类创建一个堆栈对象，堆栈对 象可以使用以下方法： public Object push(Object data) //输入数据，实现压栈 操作 public Object pop() //输出数据，实现弹栈操作 public boolean empty() //测试堆栈是否为空。如果空， 返回true，否则返回false public object peek() //查看堆栈顶端的数据，但不删除 该数据。 public int search(Object data) //返回对象在栈中的位置， 最顶端的位置是１，向下依次增加，如果堆栈不含此数 据，则返回-1。
for (int i = 0; i < number; i++) { String temp = (String) list.get(i); System.out.println("第" + i + "节点中的数据：" + temp); } list.remove(0); list.remove(1); list.set(0, "open"); number = list.size(); System.out.println("现在链表中有" + number + "个节点："); for (int i = 0; i < number; i++) { String temp = (String) list.get(i); System.out.println("第" + i + "节点中的数据：" + temp); } } }
程序运行后的效果如下所示：
12.2 栈
栈（Stack）也是一种特殊的线性表，是限定 仅在表尾进行插入和删除运算的线性表，是一 种后进先出（LIFO）的数据结构。只能在一 端进行输入或输出数据的操作，堆栈把第一个 放入该堆栈的数据放在最底下，而把后续放入 的数据放在已有数据的顶上，表尾称为栈顶 （top），表头称为栈底（bottom）。栈的物 理存储可以用顺序存储结构，也可以用链式存 储结构。向堆栈中输入数据的操作称为“压 栈”，从栈中输出数据的操作称为“弹栈”。
public Object remove (int index) //删除指定位置的节点 public Object get (int index) //得到指定位置的节点 public Object getFirst() //得到链表第一个节点的对象。 public Object getLast() //得到链表最后一个节点的对象。 int indexOf(Object element)：返回节点对象element在链表中首次 出现的位置，如果链表中无此节点对象则返回-1。 public int lastIndexOf(Object element)：返回节点对象element在 链表中最后出现的位置，如果链表中无此节点对象则返回-1。 public Object set(int index,Object element) //将当前链表index位 置节点中的对象替换成参数element指定的对象，返回被替换对象。 public int size( ) //返回量表的ቤተ መጻሕፍቲ ባይዱ度，即节点的个数。 public boolean contains(Object element)：判断链表节点对象中是 否含有element。
【例12-1】本例构造一个含有４个节点的链表，并输出节点 中的数据。
import java.util.*; public class LinkListOne { public static void main(String args[]) { LinkedList mylist = new LinkedList(); mylist.add("It");// 链表中的第一个节点。 mylist.add("is");// 链表中的第二个节点。 mylist.add("a");// 链表中的第三个节点。 mylist.add("door");// 链表中的第四个节点。 int number = mylist.size();// 获取链表的长度。 for (int i = 0; i < number; i++) { String temp = (String) mylist.get(i); System.out.println("第" + i + "节点中的数据:" + temp); } } }
【例12-3】这个例子中，把学生的成绩存放在一个链表中， 并实现了遍历链表。
import java.util.*; class Student { String name; int number; float score; Student(String name, int number, float score) { = name; this.number = number; this.score = score; } }
【例12-2】本例包含了 】本例包含了LinkedList类 类 中的一些常用方法。 中的一些常用方法。
import java.util.*; public class ep12_2 { public static void main(String args[]) { LinkedList list = new LinkedList(); list.add("is"); list.add("a"); int number = list.size(); System.out.println("现在链表中有" + number + "个节点："); for (int i = 0; i < number; i++) { String temp = (String) list.get(i); System.out.println("第" + i + "节点中的数据：" + temp); } list.add(0, "It"); number = list.size(); list.add(number - 1, "door"); number = list.size(); System.out.println("现在链表中有" + number + "个节点：");
public class LinkListThree { public static void main(String args[]) { LinkedList mylist = new LinkedList(); Student stu_1 = new Student("赵好民", 9012, 80.0f), stu_2 = new Student( "钱小青", 9013, 90.0f), stu_3 = new Student("孙 力枚", 9014, 78.0f), stu_4 = new Student( "周左右", 9015, 55.0f); mylist.add(stu_1); mylist.add(stu_2); mylist.add(stu_3); mylist.add(stu_4); Iterator iter = mylist.iterator(); while (iter.hasNext()) { Student te = (Student) iter.next(); System.out.println( + " " + te.number + " " + te.score); } } }