2021春软件构造lab1-小结

本文主要是介绍2021春软件构造lab1-小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

在完成lab1时，为了保证程序的健壮性，利用了java语言提供的强大的可变长数组接口List，以及在BFS中使用了队列这一常见数据结构，队列在java中也被声明为接口。在编码过程中，对接口的具体实现不熟练，下对接口的具体实现做出相关总结。

常见接口的具体实现及相关分析

List接口

常用方法如下图所示：
list常用方法
大部分方法可以见名知义。
List接口有两种流行的实现方式：

ArrayList：是一种可变长数组实现，优点：get和set花费常数时间；缺点：增删代价昂贵，需要移动整个数组。
LinkedList：是一种链表实现，优点：在增删的位置已知的情况下，代价很小；缺点：get的调用是昂贵的。LinkedList提供addFirst、removeLast等方法，有效增删。

Stack类

Stack在java中没有声明特定接口，常用方法如下图所示：
stack方法

Stack本身是一个受限链表，故可以采用LinkedList实现，只针对表头元素进行操作即等价为栈，应声明为Deque接口，接口中有特定的栈方法，这是java文档中推荐的stack实现方式。声明方式如下：

	Deque<Integer> stack = new LinkedList<>();stack.push(1);stack.poll();

Java中有stack类，基于Vector实现，直接调用即可。

Queue接口

队列的常用方法如下图所示：
队列方法

其中，poll为出队，offer为入队。
常用实现方法：

同理，队列也是受限列表，也可用LinkedList实现。可声明为Queue接口，也可声明为Deque接口，Deque接口实现了Queue接口，为双端队列。
另一种队列的实现方法也可以用数组实现，实现类为ArrayDeque，其实是双端队列的一个实现类。
具体声明方法如下：

	public static void main(String[] args) {// TODO Auto-generated method stubDeque<Integer> q1 = new LinkedList<>();q1.offer(5);Deque<Integer> q2 = new ArrayDeque<>();q2.offer(6);}

小结

至此可以发现，LinkedList类的实现是十分强大的，它除了实现基本的List接口外，还实现了Deque接口，也实现了Deque接口内的栈方法。

Map接口

Map是键值对的集合，与python中的字典类似。Map的常见方法如下图所示：
map方法
常用的方法有：get-取对应key的值，keySet-遍历Map用，put-插入键值对
java类库中提供一些实现类，如下：

HashMap
使用位桶和链表实现（jdk1.8后改用红黑树存储而非链表）
TreeMap
TreeMap会对Key进行排序，使用TreeMap存储，再使用iterator进行输出时，会发现其默认采用key由小到大的顺序输出键值对，如果想要按照其他的方式来排序，override 它的compartor接口。底层结构是红黑树，一种特殊的平衡二叉树。
LinkedHashMap
LinkedHashMap底层用的是双向链表与Hash表来进行的存储。相对于其他的无序的map实现类，还有像TreeMap这样的排序类，linkedHashMap最大的特点在于有序，但是它的有序主要体现在先进先出FIFIO上。
实现示意图如下图所示：

Set接口

Set映射到数学上的集合，即无重复元素的一组元素。概念并不陌生。
Set的常见方法如下图所示：
Set方法

而java为Set提供了三种具体的实现类，我们应根据具体场景进行效率分析而选用哪一个实现类，总结如下：如你的需求是要一个能快速访问的Set，那么就要用HashSet,如果你要一个排序Set，那么你应该用TreeSet,如果你要记录下插入时的顺序时，你应该使用LinkedHashSet。
4. HashSet
HashSet的底层实现是Hash算法。在一个对象要被添加到集合中的时候,会被系统分配一个哈希值,系统首先会根据这个对象的哈希值去和集合中的对象去比较,如果哈希值不同就可以加入,如果相同，就去比较两个字符串的值是否一样,如果一样就不能加入,因此把重复的对象是无法加入HashSet的。
5. TreeSet
TreeSet的底层实现是二叉树，因此在实现集合接口的基础上，它还利于排序
6. LinkedHashSet
在HashSet的基础上，还能记录插入顺序。
下面给出相关实现的一些实例代码：

	public static void main(String[] args) {// TODO Auto-generated method stubSet<Integer> s1 = new HashSet<>();Set<Integer> s2 = new TreeSet<>();Set<Integer> s3 = new LinkedHashSet<>();s1.add(5);s1.add(2);s1.add(5);System.out.println(s1);} 
//结果为[2,5],符合集合定义。