记得关注，点赞，转发……………………………………………………………………………………………………………………………………………………………………………………………………………………
分享继续
堆栈：先进后出。First In Last Out FILO。
队列：先进先出。First In First Out FIFO。
队列结构代码如下：
package ustc.maxiaolun.list.linkedlist;
import java.util.LinkedList;
/*
* 描述一个队列数据结构。内部使用的是LinkedList。
*/
public class MyQueue {
private LinkedList link;
MyQueue() {
link = new LinkedList();
}
/**
* 添加元素的方法。
*/
public void myAdd(Object obj) {
// 内部使用的是LinkedList的方法。
link.addFirst(obj);
}
/**
* 获取队列元素的方法。
*/
public Object myGet() {
return link.removeLast();
}
/**
* 集合中是否有元素的方法。
*/
public boolean isNull() {
return link.isEmpty();
}
}
堆栈结构代码如下：
package ustc.maxiaolun.list.linkedlist;
import java.util.LinkedList;
/*
* 实现一个堆栈结构。内部使用的是LinkedList。
*/
public class MyStack {
private LinkedList link;
MyStack() {
link = new LinkedList();
}
public void myAdd(Object obj) {
link.addFirst(obj);
}
public Object myGet() {
return link.removeFirst();
}
public boolean isNull() {
return link.isEmpty();
}
}
测试：
package ustc.maxiaolun.list.linkedlist;
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] args) {
/*
* 练习：请通过LInkedList实现一个堆栈，或者队列数据结构。
* 堆栈：先进后出。First In Last Out FILO.
* 队列：先进先出。First In First Out FIFO.
*/
//1.创建自定义的队列对象。
MyQueue queue = new MyQueue();
//2.添加元素。
queue.myAdd("abc1");
queue.myAdd("abc2");
queue.myAdd("abc3");
queue.myAdd("abc4");
//3.获取所有元素。先进先出。
while(!queue.isNull())
System.out.println(queue.myGet());
System.out.println("--------------------------");
//1.创建自定义的堆栈对象。
MyStack stack = new MyStack();
//2.添加元素。
stack.myAdd("def5");
stack.myAdd("def6");
stack.myAdd("def7");
stack.myAdd("def8");
//3.获取所有元素。先进后出。
while(!stack.isNull())
System.out.println(stack.myGet());
}
}
练习1：带猜数字游戏的用户登录注册案例--集合版。
需求分析：
需求：用户登录注册案例。
按照如下的操作，可以让我们更符号面向对象思想
A:有哪些类呢?
B:每个类有哪些东西呢?
C:类与类之间的关系是什么呢?
分析：
A:有哪些类呢?
用户类
测试类
B:每个类有哪些东西呢?
用户类：
成员变量：用户名，密码
构造方法：无参构造
成员方法：getXxx()/setXxx()
登录，注册
假如用户类的内容比较对，将来维护起来就比较麻烦，为了更清晰的分类，我们就把用户又划分成了两类
用户基本描述类
成员变量：用户名，密码
构造方法：无参构造
成员方法：getXxx()/setXxx()
用户操作类
登录，注册
测试类：
main方法。
C:类与类之间的关系是什么呢?
在测试类中创建用户操作类和用户基本描述类的对象，并使用其功能。
分包：
A:功能划分
B:模块划分
C:先按模块划分，再按功能划分
今天我们选择按照功能划分：
用户基本描述类包 ustc.maxiaolun.pojo
用户操作接口 ustc.maxiaolun.dao
用户操作类包 ustc.maxiaolun.dao.impl
本文中是集合实现，后续会有IO实现、GUI实现和数据库实现。
用户测试类 ustc.maxiaolun.test
代码如下：
package ustc.maxiaolun.pojo;
/**
* 这是用户基本描述类
*
* @author 马小伦
* @version V1.0
*
*/
public class User {
// 用户名
private String username;
// 密码
private String password;
public User() {
super();
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public String getPassword() {
return password;
}
public void setPassword(String password) {
this.password = password;
}
}
package ustc.maxiaolun.dao;
import ustc.maxiaolun.pojo.User;
/**
* 这时针对用户进行操作的接口
*
* @author 马小伦
* @version V1.0
*
*/
public interface UserDao {
/**
* 这是用户登录功能
*
* @param username
* 用户名
* @param password
* 密码
* @return 返回登陆是否成功
*/
public abstract boolean isLogin(String username, String password);
/**
* 这是用户注册功能
*
* @param user
* 要注册的用户信息
*/
public abstract void regist(User user);
}
package ustc.maxiaolun.dao.impl;
import java.util.ArrayList;
import ustc.maxiaolun.dao.UserDao;
import ustc.maxiaolun.pojo.User;
/**
* 这是用户操作的具体实现类(集合版)
*
* @author 马小伦
* @version V1.0
*
*/
public class UserDaoImpl implements UserDao {
//为了让多个方法能够使用同一个集合，就把集合定义为成员变量。
//为了不让外人看到，用private
//为了让多个对象共享同一个成员变量，用static
private static ArrayList<User> array = new ArrayList<User>();
@Override
public boolean isLogin(String username, String password) {
//遍历集合，获取每一个用户，并判断用户的用户名和密码是否和传递过来的匹配
boolean flag = false;
for(User u : array){
if(u.getUsername().equalsIgnoreCase(username) && u.getPassword().equalsIgnoreCase(password)){
flag = true;
break;
}
}
return flag;
}
@Override
public void regist(User user) {
//把用户信息存入集合
array.add(user);
}
}
package ustc.maxiaolun.test;
import java.util.Scanner;
import ustc.maxiaolun.dao.UserDao;
import ustc.maxiaolun.dao.impl.UserDaoImpl;
import ustc.maxiaolun.game.GuessNumber;
import ustc.maxiaolun.pojo.User;
/**
* 用户测试类
*
* @author 马小伦
* @version V1.0
*
* 新增加了两个小问题：
* A.多个对象共享同一个成员变量，用静态
* B.循环里面如果有switch，并且在switch里面有break，那么结束的不是循环，而是switch语句
*
*/
public class UserTest {
public static void main(String[] args) {
//为了能够回来
while (true) {
// 欢迎界面，给出选择项
System.out.println("--------------欢迎光临--------------");
System.out.println("1 登陆");
System.out.println("2 注册");
System.out.println("3 退出");
System.out.println("请输入你的选择：");
//键盘录入选择，根据选择做不同的操作
Scanner sc = new Scanner(System.in);
//为了后面的录入信息的方便，所有的数据录入全部用字符串接收
String choiceString = sc.nextLine();
//switch语句的多个地方要使用，我就定义到外面
UserDao ud = new UserDaoImpl();//多态
//经过简单的思考，我选择了switch
switch (choiceString) {
case "1":
//登陆界面，请输入用户名和密码
System.out.println("--------------登录界面--------------");
System.out.println("请输入用户名：");
String username = sc.nextLine();
System.out.println("请输入密码：");
String password = sc.nextLine();
//调用登录功能
boolean flag = ud.isLogin(username, password);
if (flag) {
System.out.println("登陆成功，可以开始玩游戏了");
System.out.println("你玩么？y/n");
while(true){
String resultString = sc.nextLine();
if(resultString.equalsIgnoreCase("y")){
GuessNumber.start();
System.out.println("你还玩么？y/n");
}else{
break;
}
}
System.out.println("谢谢使用，欢迎下次再来");
System.exit(0);
//break;这里写break,结束的是switch
} else {
System.out.println("用户名或者密码有误，登录失败");
}
break;
case "2":
//注册界面，请输入用户名和密码
System.out.println("--------------注册界面--------------");
System.out.println("请输入用户名：");
String newUserName = sc.nextLine();
System.out.println("请输入密码：");
String newPassword = sc.nextLine();
//把用户名和密码封装到一个对象中
User user = new User();
user.setUsername(newUserName);
user.setPassword(newPassword);
//调用注册功能
ud.regist(user);
System.out.println("注册成功");
break;
case "3":
default:
System.out.println("谢谢使用，欢迎下次再来");
System.exit(0);
}
}
}
}
其中的猜数字游戏代码为：
package ustc.maxiaolun.game;
import java.util.Scanner;
/**
* 这是猜数字小游戏
*
* @author 马小伦
*
*/
public class GuessNumber {
private GuessNumber() {
}
public static void start() {
int num = (int) (Math.random() * 100) + 1;
int count = 0;
while (true) {
System.out.println("请输入数据(1-100):");
Scanner sc = new Scanner(System.in);
int guessNum = sc.nextInt();
count++;
if (guessNum > num) {
System.out.println("你猜的数据" + guessNum + "大了");
} else if (guessNum < num) {
System.out.println("你猜的数据" + guessNum + "小了");
} else {
System.out.println("恭喜你，" + count + "次就猜中了");
break;
}
}
}
}
程序运行结果如下：
Set<E>接口
java.util.Set<E>接口，一个不包含重复元素的 collection。更确切地讲，set 不包含满足e1.equals(e2) 的元素对e1 和e2，并且最多包含一个 null 元素。
Set：不允许重复元素。和Collection的方法相同。Set集合取出方法只有一个：迭代器。
|--HashSet：底层数据结构是哈希表(散列表)。无序，比数组查询的效率高。线程不同步的。
-->根据哈希冲突的特点，为了保证哈希表中元素的唯一性，
该容器中存储元素所属类应该复写Object类的hashCode、equals方法。
|--LinkedhashSet：有序，HashSet的子类。
|--TreeSet：底层数据结构是二叉树。可以对Set集合的元素按照指定规则进行排序。线程不同步的。
-->add方法新添加元素必须可以同容器已有元素进行比较，
所以元素所属类应该实现Comparable接口的compareTo方法，以完成排序。
或者添加Comparator比较器，实现compare方法。
代码示例：
package ustc.maxiaolun.set.demo;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class HashSetDemo {
public static void main(String[] args) {
//1.创建一个Set容器对象。
Set set = new HashSet();
//Set set = new LinkedHashSet();如果改成LinkedHashSet，可以实现有序。
//2.添加元素。
set.add("haha");
set.add("nba");
set.add("abc");
set.add("nba");
set.add("heihei");
//3.只能用迭代器取出。
for (Iterator it = set.iterator(); it.hasNext();) {
System.out.println(it.next());
}
}
}
HashSet<E>类
java.util.HashSet<E>类实现Set 接口，由哈希表（实际上是一个HashMap 实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null 元素。
堆内存的底层实现就是一种哈希表结构，需要通过哈希算法来计算对象在该结构中存储的地址。这个方法每个对象都具备，叫做hashCode()方法，隶属于java.lang.Objecct类。hashCode本身调用的是wondows系统本地的算法，也可以自己定义。
哈希表的原理：
1.对对象元素中的关键字(对象中的特有数据)，进行哈希算法的运算，并得出一个具体的算法值，这个值称为哈希值。
2.哈希值就是这个元素的位置。
3.如果哈希值出现冲突，再次判断这个关键字对应的对象是否相同。
如果对象相同，就不存储，因为元素重复。如果对象不同，就存储，在原来对象的哈希值基础 +1顺延。
4.存储哈希值的结构，我们称为哈希表。
5.既然哈希表是根据哈希值存储的，为了提高效率，最好保证对象的关键字是唯一的。
这样可以尽量少的判断关键字对应的对象是否相同，提高了哈希表的操作效率。
哈希表的特点：
1.不允许存储重复元素，因为会发生查找的不确定性。
2.不保证存入和取出的顺序一致，即不保证有序。
3.比数组查询的效率高。
哈希冲突：
当哈希算法算出的两个元素的值相同时，称为哈希冲突。冲突后，需要对元素进行进一步的判断。判断的是元素的内容，equals。如果不同，还要继续计算新的位置，比如地址链接法，相当于挂一个链表扩展下来。
如何保证哈希表中元素的唯一性？
元素必须覆盖hashCode和equals方法。
覆盖hashCode方法是为了根据元素自身的特点确定哈希值。
覆盖equals方法，是为了解决哈希值的冲突。
如何实现有序？
LinkedHashSet类，可以实现有序。
废话不所说，下面我来举一个例子演示。
练习：往HashSet中存储学生对象(姓名，年龄)。同姓名、同年龄视为同一个人，不存。
思路：
1.描述学生。
2.定义容器。
3.将学生对象存储到容器中。
package ustc.maxiaolun.domian;
public class Student {
private String name;
private int age;
public Student() {
super();
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
/*
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
*/
//覆盖hashCode方法。根据对象自身的特点定义哈希值。
public int hashCode(){
final int NUMBER = 31;
return name.hashCode()+ age*NUMBER;
}
//需要定义对象自身判断内容相同的依据。覆盖equals方法。
public boolean equals(Object obj){
if (this == obj)
return true;
if(!(obj instanceof Student))
throw new ClassCastException(obj.getClass().getName()+"类型错误");
Student stu = (Student)obj;
return this.name.equals(stu.name) && this.age == stu.age;
}
}
package ustc.maxiaolun.set.demo;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import ustc.maxiaolun.domian.Student;
public class HashSetTest {
public static void main(String[] args) {
/*
* 练习：往HashSet中存储学生对象(姓名，年龄)。同姓名、同年龄视为同一个人，不存。
* 1.描述学生。
* 2.定义容器。
* 3.将学生对象存储到容器中。
*
* 发现存储了同姓名、同年龄的学生是可以的。
* 原因是每一次存储学生对象，都先调用hashCode()方法获取哈希值。
* 但此时调用的是Object类中的hashCode。所以同姓名同年龄了，但因为是不同的对象，哈希值也不同。
* 这就是同姓名同年龄存入的原因。
*
* 解决：
* 需要根据学生对象自身的特点来定义哈希值。
* 所以就需要覆盖hashCode方法。
*
* 发现，当hashCode返回值相同时，会调用equals方法比较两个对象是否相等。
* 还是会出现同姓名同年龄的对象，因为子类没有复写equals方法，
* 直接用Object类的equals方法仅仅比较了两个对象的地址值。
* 这就是同姓名同年龄还会存入的原因。
*
* 解决：
* 需要定义对象自身判断内容相同的依据。
* 所以就需要覆盖equals方法。
*
* 效率问题：
* 尽量减少哈希算法求得的哈希值的冲突。减少equals方法的调用。
*/
//1.创建容器对象。
Set set = new HashSet();
//2.存储学生对象。
set.add(new Student("xiaoqiang",20));
set.add(new Student("wangcai",27));
set.add(new Student("xiaoming",22));
set.add(new Student("xiaoqiang",20));
set.add(new Student("daniu",24));
set.add(new Student("xiaoming",22));
//3.获取所有学生。
for (Iterator it = set.iterator(); it.hasNext();) {
Student stu = (Student) it.next();
System.out.println(stu.getName()+":"+stu.getAge());
}
}
}
ArrayList存储元素依赖的是equals方法。比如remove、contains底层判断用的都是equals方法。
HashSet判断元素是否相同：依据的是hashCode和equals方法。如果哈希冲突(哈希值相同)，再判断元素的equals方法。如果equals方法返回true，不存；返回false，存储！
TreeSet<E>类
java.util.Set<E>类基于TreeMap的NavigableSet实现。使用元素的自然顺序(Comparable的compareTo方法)对元素进行排序，或者根据创建 set 时提供的自定义比较器(Comparator的compare方法)进行排序，具体取决于使用的构造方法。此实现为基本操作（add、remove和contains）提供受保证的 log(n)时间开销。
TreeSet：可以对元素排序。
有序：存入和取出的顺序一致。--> List
排序：升序or降序。--> TreeSet
代码示例：
package ustc.maxiaolun.set.demo;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
import ustc.maxiaolun.domian.Student;
public class TreeSetDemo {
public static void main(String[] args) {
Set set = new TreeSet();
set.add("abc");
set.add("heihei");
set.add("nba");
set.add("haha");
set.add("heihei");
for (Iterator it = set.iterator(); it.hasNext();) {
System.out.println(it.next());
}
}
}
程序输出：
那如果往TreeSet集合中存入的是自定义元素呢？
TreeSet排序方式：
需要元素自身具备比较功能。所以元素需要实现Comparable接口。覆盖compareTo方法。如果元素不具备比较性，在运行时会发生ClassCastException异常。
TreeSet能够进行排序。但是自定义的Person类并没有给出排序的规则。即普通的自定义类不具备排序的功能，所以要实现Comparable接口，强制让元素具备比较性，复写compareTo方法。
如何保证元素唯一性？
参考的就是比较方法(比如compareTo)的返回值是否是0。是0，就是重复元素，不存。
注意：在进行比较时，如果判断元素不唯一，比如，同姓名同年龄，才视为同一个人。
在判断时，需要分主要条件和次要条件，当主要条件相同时，再判断次要条件，按照次要条件排序。
示例：往TreeSet集合存入上一节所描述的学生类对象。要求按照年龄进行排序。
package ustc.maxiaolun.domian;
/*
* 学生类本身继承自Object类，具备一些方法。
* 我们想要学生类具备比较的方法，就应该在学生类的基础上进行功能的扩展。
* 比较的功能已经在Comparable接口中定义下来了，学生类只需要实现Comparable接口即可。
* 记住：需要对象具备比较性，只要让对象实现comparable接口即可。
*/
public class Student implements Comparable{
private String name;
private int age;
public Student() {
super();
}
public Student(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
/*
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
*/
//覆盖hashCode方法。根据对象自身的特点定义哈希值。
public int hashCode(){
final int NUMBER = 31;
return name.hashCode()+ age*NUMBER;
}
//需要定义对象自身判断内容相同的依据。覆盖equals方法。
public boolean equals(Object obj){
if (this == obj)
return true;
if(!(obj instanceof Student))
throw new ClassCastException(obj.getClass().getName()+"类型错误");
Student stu = (Student)obj;
return this.name.equals(stu.name) && this.age == stu.age;
}
//实现了comparable接口，学生就具备了比较功能。该功能是自然排序使用的方法。
//自然排序就以年龄的升序排序为主。
//既然是同姓名同年龄是同一个人，视为重复元素，要判断的要素就有两个。
//既然是按照年龄进行排序。所以先判断年龄，再判断姓名。
@Override
public int compareTo(Object o) {
Student stu = (Student)o;
System.out.println(this.name+":"+this.age+"......"+stu.name+":"+stu.age);
if(this.age > stu.age)
return 1;
if(this.age < stu.age)
return -1;
//return 0;//0表示重复元素，不存。
return this.name.compareTo(stu.name);//进一步细化条件，只有姓名、年龄都一样，才是重复元素。
/*
主要条件：
return this.age - stu.age;
*/
/*
主要条件+次要条件：
int temp = this.age - stu.age;
return temp==0?this.name.compareTo(stu.age):temp;
*/
}
}
package ustc.maxiaolun.set.demo;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
import ustc.maxiaolun.domian.Student;
public class TreeSetDemo {
public static void main(String[] args) {
Set set = new TreeSet();
set.add(new Student("xiaoqiang",20));//java.lang.ClassCastException 类型转换异常
//问题：因为学生要排序，就需要比较，而没有定义比较方法，无法完成排序。
//解决：add方法中实现比较功能,使用的是Comparable接口的比较方法。
//comparable接口抽取并定义规则，强行对实现它的每个类的对象进行整体排序，实现我的类就得实现我的compareTo方法，否则不能创建对象。
set.add(new Student("daniu",24));
set.add(new Student("xiaoming",22));
set.add(new Student("huanhuan",22));//根据复写的compareTo方法，huanhuan和xiaoming两个对象属于重复元素(进一步细化条件之前,compareTo返回值为0即视为重复)，又TreeSet容器不存重复元素，所以huanhuan没有存进去。
set.add(new Student("tudou",18));
set.add(new Student("dahuang",19));
/*set.add(new Student("lisi02", 22));
set.add(new Student("lisi007", 20));
set.add(new Student("lisi09", 19));
set.add(new Student("lisi08", 19));
set.add(new Student("lisi11", 40));
set.add(new Student("lisi16", 30));
set.add(new Student("lisi12", 36));
set.add(new Student("lisi10", 29));
set.add(new Student("lisi22", 90));
*/
for (Iterator it = set.iterator(); it.hasNext();) {
Student stu = (Student)it.next();
System.out.println(stu.getName()+":"+stu.getAge());
}
}
}
如何实现有序？
保证二叉树只return一边，比如：
public int compareTo(Object o){
if (this.age == o.age)
return 0;//保证TreeSet不存入自定义的重复元素。
return 1;//保证添加的元素都存入二叉树的右子树。
}
TreeSet二叉树建立过程：
TreeSet底层是二叉树结构，二叉树结构特点是可以排序。并且对二叉树的建立过程内部优化，以减少比较次数。例子中将已排序的xiaoming:22作为根节点，是基于折半的排序思想。xiaoqiang:20、xiaoming:22、daniu:24已经按照顺序存好，为了提高效率，在已排序的数组中去找一个新元素存放的位置，折半的方法最快。所以第四个进来的元素huanhuan:22会先和中间的xiaoming:22比较，然后确定往大的方向还是小的方向走。按照改进前的规则，huanhuan:22和xiaoming:22属重复元素，不存。tudou:18进来，再和已排序的中间元素xiaoming:22比较。比xiaoming:22小，往小的方向走，接着和xiaoqiang:20比较，比它小，tudou:18放在xiaoqiang:20左子树位置上。此时，已排序的依次为：tudou:18、xiaoqiang:20、xiaoming:22、daniu:24。中间元素为xiaoming:22。
dahuang:19先和xiaoming:22比，比它小；再和xiaoqiang:20比，比它小；接着和tudou:18比，比它大，放在tudou:18的右子树上。
建树完毕，TreeSet容器存入元素完毕。
…………………未完待续………………
更多内容尽在：www.njzhenghou.com
桂ICP备2021005359号-1 桂公网安备 2021005359号
