java数据结构2
线性队列
功能实现
增加元素
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列已满");
}
rear++;
arr[rear] = n;
}
出列操作
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
front++;
return arr[front];
}
显示队列的情况
public void showQueue() {
if (isEmpty()) {
System.out.println("队列空的，没有数据~~");
}else{
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr["+i+"]="+arr[i]);
}
}
}
查看队列头元素
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front + 1];
}
退出操作
case 'e':
scanner.close();
loop = false;
break;
环形队列
功能实现
在线性队列的基础上让最后一位的下一位索引赋值为0
增加元素
public void addQueue(int number) {
if (isFull()) {
System.out.println("队列已满");
}else{
arr[rear] = number;
//让rear在0-maxSize-1范围内循环改变
rear = (rear + 1) % maxSize;
}
}
出列操作
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空，不能取数据");
}
//先取出首元素再后移一位
int value = arr[front];
//让front在0-maxSize-1范围内循环改变
front = (front + 1) % maxSize;
return value;
}
显示队列情况
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = front; i < front + size() ; i++) {
System.out.printf("arr["+i%maxSize+"]="+arr[i % maxSize]);
}
}
//...
public int size() {
//相当于再maxSize给个元素后再加相同数量的元素，对应位置来取值
return (rear + maxSize - front) % maxSize;
}
查看队列头元素
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arr[front];
}
判断队列是否为空和已满
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
链表
（1）链表是以节点的方式来存储,是链式存储
（2）每个节点包含 data 域， next 域：指向下一个节点.
（3）如图：发现链表的各个节点不一定是连续存储.
（4）链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
水浒英雄管理
功能实现
实现对链表的增删改查
HeroNode类
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next; // next 默认为null
public HeroNode(int hNo, String hName, String hNickname) {
no = hNo;
name = hName;
nickname = hNickname;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
SingleLinkedList类
对英雄进行管理
功能实现都在这里
class SingleLinkedList{
private HeroNode head=new HeroNode(0, "", "");
//将对象装到链表最后
public void add(HeroNode heroNode) {
HeroNode temp=head;
while (temp.next!=null) {
temp=temp.next;
}
temp.next=heroNode;
}
//根据编号来装进链表
public void addByOrder(HeroNode heroNode) {
// TODO Auto-generated method stub
HeroNode temp=head;
boolean flag=true;
while (true) {
if (temp.next==null) {
break;
}
if (temp.next.no>heroNode.no) {
break;
}else if(temp.next.no==heroNode.no){
flag=false;//说明已经存在编号为heroNode.no的英雄了
break;
}
temp=temp.next;
}
if (flag) {
heroNode.next=temp.next;
temp.next=heroNode;
}else {
System.out.println("该节点已存在");
}
}
//根据编号更新对象的内容
public void update(HeroNode newHeroNode) {
if(head.next == null) {
System.out.println("链表为空~");
return;
}
HeroNode temp=head;
while (true) {
if (temp.next.no==newHeroNode.no) {
newHeroNode.next=temp.next;
temp.next=newHeroNode;
break;
}else if (temp.next==null) {
System.out.println("没有找到该英雄");
break;
}else {
temp=temp.next;
}
}
}
//根据编号删除对象
public void del(int no) {
if(head.next == null) {
System.out.println("链表为空~");
return;
}
HeroNode temp=head;
while (true) {
if (temp.next.no==no) {
temp.next=temp.next.next;
break;
}else if(temp.next==null){
System.out.println("没有找到该英雄");
break;
}else {
temp=temp.next;
}
}
}
//输出全部对象
public void list() {
if(head.next == null) {
System.out.println("链表为空~");
return;
}
HeroNode temp=head.next;
while (true) {
System.out.println(temp.toString());
if (temp.next==null) {
break;
}else {
temp=temp.next;
}
}
}
}
测试类
public class SingleLinkedListTest {
public static void main(String[] args) {
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
SingleLinkedList linkList=new SingleLinkedList();
linkList.add(hero1);
linkList.add(hero2);
linkList.add(hero3);
linkList.add(hero4);
linkList.list();
linkList.del(3);
linkList.list();
linkList.addByOrder(hero3);
linkList.list();
}
}