凡科建站下载,网站评估内容 优帮云,互联网 社区教育网站建设论文,山东银汇建设集团网站数据结构#xff1a;
线性结构#xff1a;
顺序存储方式#xff0c;顺序表
常见的顺序存储结构有#xff1a;数组、队列、链表、栈
链式存储方式#xff0c;链表 队列#xff1a;
队列可以使用数组结构或者链表结构来存储#xff0c;先入先出#xff0c;后进后出。…数据结构
线性结构
顺序存储方式顺序表
常见的顺序存储结构有数组、队列、链表、栈
链式存储方式链表 队列
队列可以使用数组结构或者链表结构来存储先入先出后进后出。
数组结构的队列
public class Demo {public static void main(String[] args) {CircleArrayQueue arrayQueue new CircleArrayQueue(3);char key;Scanner scanner new Scanner(System.in);boolean loop true;while (loop) {System.out.println(s(show)显示队列);System.out.println(e(exit)退出程序);System.out.println(a(add)添加数据到队列);System.out.println(g(get)从队列取出数据);System.out.println(h(head)查看队列头的数据);key scanner.next().charAt(0);switch (key) {case s:arrayQueue.showQueue();break;case a:System.out.println(请输入一个数字);int value scanner.nextInt();arrayQueue.addQueue(value);break;case g:try {int res arrayQueue.getQueue();System.out.println(取出的数据为 res);} catch (Exception e) {System.out.println(e.getMessage());}break;case e:loop false;scanner.close();System.out.println(程序退出...);break;case h:try {int res arrayQueue.headQueue();System.out.println(查看的数据为 res);} catch (Exception e) {System.out.println(e.getMessage());}break;default:break;}}}
}class CircleArrayQueue {private int maxSize;// 指向队列头的位置private int front;// 指向队列尾的数据的下一个的位置它指向的队尾的数据代表有值的private int rear;private int[] arr;public CircleArrayQueue(int arrMaxSize) {// 实际上队列有maxSize个元素因为空出了一个位置maxSize arrMaxSize 1;arr new int[maxSize];front rear 0;}public boolean isFull() {return (rear 1) % maxSize front;}public boolean isEmpty() {return front rear;}public void addQueue(int n) {if (isFull()) {System.out.println(队列为满不能加入数据);return;}arr[rear] n;rear;if (rear % maxSize 0) {rear 0;}}public int getQueue() {if (isEmpty()) {throw new RuntimeException(队列为空不能取值);}int res arr[front];front;if (front % maxSize 0) {front 0;}return res;}public void showQueue() {if (isEmpty()) {System.out.println(队列为空没有数据);return;}
// for (int i front; i ! rear; i (i 1) % maxSize) {for (int i front; i front size(); i) {System.out.printf(arr[%d]%d\n, i % maxSize, arr[i % maxSize]);}}public int headQueue() {if (isEmpty()) {throw new RuntimeException(队列为空没有头数据);}return arr[front];}private int size() {return (rear maxSize - front) % maxSize;}
}
链表结构的队列
public class SingleLinkListDemo {public static void main(String[] args) {HeroNode hero1 new HeroNode(1, 宋江, 及时雨);HeroNode hero2 new HeroNode(2, 卢俊义, 玉麒麟);HeroNode hero3 new HeroNode(3, 吴用, 智多星);SingleLinkList singleLinkList new SingleLinkList();singleLinkList.add(hero3);singleLinkList.add(hero2);singleLinkList.add(hero1);
// singleLinkList.add(hero3);
// HeroNode newHero new HeroNode(3, 张三, 法外狂徒);
// singleLinkList.update(newHero);HeroNode delHero1 new HeroNode(1, , );singleLinkList.del(delHero1);singleLinkList.reverse();singleLinkList.list();}
}class SingleLinkList {private HeroNode headNode new HeroNode(0, , );// 非递归反转public void reverse3() {if (headNode.getNext() null || headNode.getNext().getNext() null) {return;}HeroNode nextNode1, nextNode2, nextNode3;nextNode1 headNode.getNext();nextNode2 nextNode1.getNext();nextNode3 nextNode2.getNext();nextNode2.setNext(nextNode1);nextNode1.setNext(null);while (nextNode3 ! null) {nextNode1 nextNode2;nextNode2 nextNode3;nextNode3 nextNode3.getNext();nextNode2.setNext(nextNode1);}headNode.setNext(nextNode2);}// 递归反转public void reverse() {HeroNode nextNode headNode.getNext();headNode.setNext(reverse2(headNode.getNext()));nextNode.setNext(null);}private HeroNode reverse2(HeroNode heroNode) {if (heroNode.getNext() ! null) {HeroNode lastNode reverse2(heroNode.getNext());heroNode.getNext().setNext(heroNode);return lastNode;}return heroNode;}public void del(HeroNode delHeroNode) {if (headNode.getNext() null) {System.out.println(链表为空);return;}HeroNode preNode, nextNode;preNode headNode;nextNode headNode.getNext();while (nextNode ! null) {if (nextNode.getNo() delHeroNode.getNo()) {preNode.setNext(nextNode.getNext());// nextNode.setNext(null);return;}preNode nextNode;nextNode nextNode.getNext();}System.out.println(删除编号 delHeroNode.getNo() 的元素没有找到);}public void update(HeroNode newHeroNode) {if (headNode.getNext() null) {System.out.println(链表为空);return;}HeroNode preNode, nextNode;preNode headNode;nextNode headNode.getNext();while (nextNode ! null) {if (nextNode.getNo() newHeroNode.getNo()) {newHeroNode.setNext(nextNode.getNext());preNode.setNext(newHeroNode);return;}preNode nextNode;nextNode nextNode.getNext();}System.out.println(编号 newHeroNode.getNo() 的元素没有找到);}public void add(HeroNode heroNode) {HeroNode nextNode, preNode;preNode headNode;nextNode headNode.getNext();// 头插法if (nextNode null) {headNode.setNext(heroNode);heroNode.setNext(null);return;}// 中插法while (nextNode ! null) {if (heroNode.getNo() nextNode.getNo()) {preNode.setNext(heroNode);heroNode.setNext(nextNode);return;}// 相同的数据不能进行插入if (heroNode.getNo() nextNode.getNo()) {System.out.println(编号 heroNode.getNo() 已存在不能添加);return;}preNode nextNode;nextNode nextNode.getNext();}// 尾插法preNode.setNext(heroNode);heroNode.setNext(null);}public void list() {HeroNode tmpNode headNode.getNext();if (tmpNode null) {System.out.println(链表为空);return;}while (tmpNode ! null) {System.out.println(node tmpNode --);tmpNode tmpNode.getNext();}}
}Data
class HeroNode {private int no;private String name;private String nickName;private HeroNode next;public HeroNode(int hNo, String hName, String hNickName) {this.no hNo;this.name hName;this.nickName hNickName;}Overridepublic String toString() {return HeroNode{ no no , name name \ , nickName nickName \ };}
}链表的面试题
单向链表应用场景
约瑟夫环问题
代码
package org.example.josephu;public class Josephu {public static void main(String[] args) {CircleSingleLinkedList list new CircleSingleLinkedList();list.addBoy(5);list.countBoy(1, 2, 5);
// list.showBoy();}
}class CircleSingleLinkedList {private Boy first null;public void addBoy(int nums) {if (nums 2) {System.out.println(nums的值不正确);return;}Boy curBoy null;for (int i 0; i nums; i) {Boy boy new Boy(i 1);if (i 0) {first boy;first.setNext(first);curBoy first;} else {curBoy.setNext(boy);boy.setNext(first);curBoy boy;}}}public void showBoy() {if (first null) {System.out.println(链表为空);return;}Boy curBoy first;do {System.out.println(编号 curBoy.getNo() --);curBoy curBoy.getNext();} while (curBoy ! first);}/*** param startNo 从第几个开始* param countNum 数几下* param nums 最初有多少个小孩*/public void countBoy(int startNo, int countNum, int nums) {if (first null || startNo 1 || startNo nums) {System.out.println(参数输入有误请重新输入);return;}Boy helper first;while (helper.getNext() ! first) {helper helper.getNext();}for (int i 0; i startNo - 1; i) {first first.getNext();helper helper.getNext();}while (helper ! first) {for (int i 0; i countNum - 1; i) {first first.getNext();helper helper.getNext();}System.out.println(小孩 first.getNo() 出圈);first first.getNext();helper.setNext(first);
// nums--;}System.out.println(最后留在圈中的小孩编号 first.getNo());}
}class Boy {private int no;private Boy next;public Boy(int no) {this.no no;}//#region get|setpublic int getNo() {return no;}public void setNo(int no) {this.no no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next next;}//#endregion
}栈结构
代码
package org.example.stack;import java.sql.SQLOutput;
import java.util.Scanner;public class ArrayStackDemo {public static void main(String[] args) {ArrayStack stack new ArrayStack(4);String key;boolean loop true;Scanner scanner new Scanner(System.in);while (loop) {System.out.println(show表示显示栈);System.out.println(exit表示退出栈);System.out.println(push表示压栈);System.out.println(pop表示出栈);System.out.println(请输入你的选择);key scanner.next();switch (key) {case s:stack.list();break;case e:loop false;break;case pu:try {System.out.println(请输入要压栈的数据);int value scanner.nextInt();stack.push(value);} catch (Exception e) {System.out.println(e.getMessage());}break;case po:try {System.out.println(stack.pop());} catch (Exception e) {System.out.println(e.getMessage());}break;default:System.out.println(输入有误);break;}}System.out.println(程序退出了...);}
}class ArrayStack {private int maxSize;private int[] stack;private int top -1;public ArrayStack(int maxSize) {this.maxSize maxSize;stack new int[maxSize];}public boolean isFull() {return top maxSize - 1;}public boolean isEmpty() {return top -1;}public void push(int value) {if (isFull()) {System.out.println(栈满);return;}top;stack[top] value;}public int pop() {if (isEmpty()) {throw new RuntimeException(栈空没有数据);}int res stack[top];top--;return res;}public void list() {if (isEmpty()) {System.out.println(栈空没有数据);return;}for (int i top; i 0; i--) {System.out.printf(a[%d]%d\n, i, stack[i]);}}
}用栈实现一个简单的计算器
中缀表达式人阅读的表达式。 package org.example.stack;public class Calculator {public static void main(String[] args) {String expression 7*2*2-51-53-4;ArrayStack2 numStack new ArrayStack2(10);ArrayStack2 operStack new ArrayStack2(10);int index 0;int num1 0;int num2 0;int oper 0;int res 0;char ch ;while (true) {ch expression.substring(index, index 1).charAt(0);if (operStack.isOper(ch)) {if (!operStack.isEmpty()) {if (operStack.priority(ch) operStack.priority(operStack.peek())) {num1 numStack.pop();num2 numStack.pop();oper operStack.pop();res numStack.cal(num1, num2, (char) oper);numStack.push(res);operStack.push(ch);} else {operStack.push(ch);}} else {operStack.push(ch);}} else {// numStack.push(ch - 0);int keepNum ch - 0;while (index expression.length() - 1) {index;ch expression.substring(index, index 1).charAt(0);if (!operStack.isOper(ch)) {keepNum keepNum * 10 (ch - 0);} else {index--;break;}}numStack.push(keepNum);}index;if (index expression.length()) {break;}}while (true) {if (operStack.isEmpty()) {break;}num1 numStack.pop();num2 numStack.pop();oper operStack.pop();res numStack.cal(num1, num2, (char) oper);numStack.push(res);}System.out.printf(表达式 %s %d\n, expression, numStack.pop());}
}class ArrayStack2 {private int maxSize;private int[] stack;private int top -1;public ArrayStack2(int maxSize) {this.maxSize maxSize;stack new int[maxSize];}public boolean isFull() {return top maxSize - 1;}public boolean isEmpty() {return top -1;}public void push(int value) {if (isFull()) {System.out.println(栈满);return;}top;stack[top] value;}public int pop() {if (isEmpty()) {throw new RuntimeException(栈空没有数据);}int res stack[top];top--;return res;}public void list() {if (isEmpty()) {System.out.println(栈空没有数据);return;}for (int i top; i 0; i--) {System.out.printf(a[%d]%d\n, i, stack[i]);}}public int priority(int oper) {if (oper * || oper /) {return 1;} else if (oper || oper -) {return 0;}return -1;}public boolean isOper(char val) {return val || val - || val * || val /;}public int cal(int num1, int num2, char oper) {int res 0;switch (oper) {case :res num1 num2;break;case -:res num2 - num1;break;case *:res num1 * num2;break;case /:res num2 / num1;break;default:break;}return res;}public int peek() {return stack[top];}
}
非线性结构
常见的非线性结构有二维数组、多维数组、广义表、树结构、图结构
