雙向鏈表
單向鏈表的缺點
從前面的練習題，包括實作單向鏈表中會發現 單向鏈表 的以下問題：
-
查找方向 只能是單向
-
不能自我洗掉
需要靠輔助節點，要找到洗掉節點的上一個節點和洗掉節點，才能完成洗掉
而以上問題，雙向鏈表：
- 可以雙向查找
- 可以自我洗掉
雙向鏈表的思路分析
雙向鏈表的結構如上圖所示，每個節點都有 pre 和 next 變數，所以它可以往前查找或則往后查找，
那么下面先分析下雙向鏈表的：遍歷、添加、洗掉 操作思路，之后再去實作：
-
遍歷：和單向鏈表類似，只是可以雙向遍歷了
-
修改：和單向鏈表一樣的方式
-
添加：默認添加到雙向鏈表的最后一個節點
- temp.next = newNode
- newNode.pre = temp
-
洗掉
如上圖所示，雙向鏈表可以自我洗掉：
- 遍歷找到要洗掉的那個節點 temp
temp.next.pre = temp.pretemp.pre.next = temp.next
代碼實作
//定義節點
class HeroNode2{
public int no;//英雄編號
public String name;//英雄名稱
public String nickName;//英雄花名
public HeroNode2 next;//當前節點的下一個節點
public HeroNode2 pre;//指向當前節點的前一個節點
public HeroNode2(int no,String name,String nickName){
this.no = no;
this.name = name;
this.nickName = nickName;
}
//方便遍歷顯示資訊
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
//定義雙向鏈表
class DoubleLinkedList{
private HeroNode2 head;//定義頭節點
public DoubleLinkedList(){
head = new HeroNode2(0,"","");//創建雙向鏈表的頭節點
}
//回傳頭節點
public HeroNode2 getHead(){
return head;
}
//雙向鏈表的遍歷
public void list(){
//借助輔助變數遍歷
HeroNode2 temp = head.next;
while(true){
if(temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
//雙向鏈表的添加元素，添加在最后，無序添加
public void add(HeroNode2 h){
HeroNode2 temp = head;//獲取頭節點
while(true){
if(temp.next == null){
break;//找到最后一個元素
}
temp = temp.next;
}
//添加雙向鏈表節點
temp.next = h;
h.pre = temp;
}
//有序添加元素
public void addOrder(HeroNode2 h){
HeroNode2 temp = head;
boolean flag = false;//是否存在重復添加元素
while(true){
if(temp.next == null){
break;//已經遍歷到結尾
}
if(temp.next.no > h.no){
break;//找到要添加的位置
}else if(temp.next.no == h.no){
flag = true;
break;//重復添加
}
temp = temp.next;
}
if(flag){
//重復添加
System.out.printf("添加失敗，元素節點%d已經存在",h.no);
}
//添加元素
h.pre = temp;
h.next = temp.next;
if(temp.next != null){//如果添加的元素不是最后一個
temp.next.pre = h;
}
temp.next = h;
}
//修改節點資訊
public void update(HeroNode2 h){
if(head.next == null){
System.out.println("單鏈表為空，修改失敗");
return;
}
HeroNode2 temp = head.next;
boolean flag = false;//用于記錄是否找到要修改的元素
while(true){
if(temp == null){//已經遍歷到最后
break;
}else if(temp.no == h.no){//找到要修改的元素
flag = true;
break;
}
temp = temp.next;
}
if(flag){//修改資訊
temp.name = h.name;
temp.nickName = h.nickName;
}else{
System.out.printf("修改失敗，沒有找到%d節點元素",h.no);
}
}
//洗掉指定節點
public void remove(int no){
if(head.next == null){
System.out.println("鏈表為空，洗掉失敗");
return;
}
HeroNode2 temp = head.next;//從第一個元素開始查找
boolean flag = false;//記錄是否找到對應節點
while(true){
if(temp == null){//已經遍歷到最后
break;
}else if(temp.no == no){//找到要洗掉的元素節點
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.pre.next = temp.next;
if(temp.next != null){
temp.next.pre = temp.pre;
}
}else{//沒有找到要洗掉的節點
System.out.printf("洗掉失敗，沒有找到要%d節點",no);
}
}
}
單向環形鏈表-Josephu 問題
應用場景-約瑟夫問題
約瑟夫（Josephu）問題，也就是丟手帕問題，他的規則如下
- 有編號為 1 ~ n 的 n 個人圍坐在一起
- 約定編號為 K( 1 <= k <=n) 的人從 1 開始報數
- 數到 m 的那個人出列，它的下一位又從 1 開始報數
回圈以上程序，直到所有人都出列，并列出出列人的編號，
該問題其實可以使用 單回圈鏈表（單向環形鏈表）來解決，思路如下：
- 先構成一個有 n 個節點的單回圈鏈表
- 然后由 k 節點起從 1 開始計數
- 計數到 m 時，對應節點從鏈表中洗掉，然后從下一個節點又從 1 開始計數
回圈以上程序，直到最后一個節點從鏈表中洗掉，演算法結束
單向環形鏈表介紹
約瑟夫問題示意圖
需求如下：
n=5：有 5 個人k=1：從第一個人開始數m=2：數兩次
-
第一輪：2 出佇列，1.next = 3
還剩下：1、3、4、5
-
第二輪：4 出佇列，3.next = 5；（從 3 開始報數，第 2 個的出佇列，也就是 4）
還剩下：1、3、5
-
第三輪：1 出佇列，5.next = 3
還剩下：3、5
-
第四輪：5 出佇列，3.next = 3
還剩下：3，自己的 next 就是自己
-
第五輪：3 出佇列，佇列中無元素，結束
那么最終的出佇列順序就是：2、4、1、5、3
約舍夫問題可以使用陣列來解決，這里使用單向環形鏈表，比較好理解
創建環形鏈表的思路圖解
環形鏈表添加思路
- 第 1 個節點被添加進來時
使用一個 first 變數來表示這是第一個節點，和帶頭節點的鏈表類似，第一個節點不能去改變他，使用 curBody 變數來輔助我們解決添加的程序，并讓 first 指向自己，形成一個環形
- 第 2 個節點被添加進來時
將該節點加入到已有的環形變數表
- 第 3 個節點被添加進來時
遍歷環形鏈表
- 先讓一個輔助變數 cur，指向 first 節點
- 通過一個 while 回圈遍歷該，當 cur.next = first 時，就遍歷完了
環形鏈表實作代碼
//定義節點
class Boy{
private int no;//當前節點編號
private Boy next;//當前節點的下一個節點
public Boy(int no){
this.no = no;
}
public 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;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
//定義環形單鏈表
class CircleSingleLinkedList{
private Boy first;
//添加指定個數的節點
public void addBoy(int nums){
if(nums < 1){
System.out.println("節點個數必須大于1");
return;
}
Boy curBoy = null;
for(int i = 1; i <= nums; i++){
Boy h = new Boy(i);
if(i == 1){
//添加元素為第一個元素
first = h;//first指向第一個元素
h.setNext(first);//將當前節點的下一個節點設定為頭節點
curBoy = h;//將輔助變數指向頭節點
}else{
//添加元素不是第一個元素
curBoy.setNext(h);
h.setNext(first);//將當前節點的下一個節點指向頭部
curBoy = curBoy.getNext();//將輔助變數指標后移
}
}
}
//遍歷節點
public void showBoy(){
if(first == null){
System.out.println("當前環形單鏈表為空");
return;
}
//定義輔助變數，幫助遍歷
Boy curBoy = first;
while(true){
System.out.println(curBoy);
if(curBoy.getNext() == first){
break;//遍歷結束
}
//指標后移
curBoy = curBoy.getNext();
}
}
}
出圈思路分析
還是以這個需求來分析：
用戶輸入如下：
n=5：有 5 個人k=1：從第一個人開始數m=2：數兩次
-
初始化時，需要一個 helper 輔助節點來表示first的前一個節點，如下圖所示
-
將 first 和 helper 定位到 k （從第幾個小孩開始報數）將 first 和 helper 移動 k-1 次
-
小孩報數時：移動 first 到出圈的節點上，hepler 始終在 first 后面
讓 first 和 helper 同時移動 m-1 次，是因為 開始數數的人 也要占用一個位置：比如上圖，從 first 開始，在編號 2 時，就數了 2 下了，它該出圈
- 小孩出圈
先將 first = first.next，然后將 helper.next = first，那么就如上圖所示了，出圈的 first 被孤立出圈了，別人沒有參考它了
注意：只有 小孩報數和出圈是重復 的，其他的只是這個游戲開始前的一些設定，
出圈代碼實作
//出圈實作
/**
*
* @param startNo 第幾個開始數
* @param countNum 每次數幾個
* @param nums 單向環形鏈表的總節點數
*/
public void countBoy(int startNo,int countNum,int nums){
if(first == null || countNum < 1 || countNum > nums){
System.out.println("引數不正確或者環形單鏈表為空");
return;
}
//將helper移動到first前一個節點
Boy helper = first;
while(true){
if(helper.getNext() == first){
break;
}
helper = helper.getNext();//指標后移
}
//將first,helper移動到startNo處，需要將first，helper一起移動startNo-1次
for(int j = 0; j < startNo-1; j++){
first = first.getNext();
helper = helper.getNext();
}
//找出圈元素
while(true){
if(helper == first){
break;
}
for(int i = 0; i < countNum -1; i++){
//移動指定次數
first = first.getNext();
helper = helper.getNext();
}
//出圈元素
System.out.printf("小孩%d出圈\n",first.getNo());
//洗掉元素,first指標后移，洗掉指定元素
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中小孩編號:%d\n",first.getNo());
}
堆疊
堆疊快速入門
計算器需求
如上圖：輸入一個運算式 7*2*2-5+1-5+3-3，然后計算出他的結果，
問：計算機底層是如何運算得到結果的？對于計算機而言他接受到的是一個 字串，怎么計算出來的？
針對這個問題，我們討論的就是 堆疊
堆疊介紹
stack 堆疊，是一個 先入后出（FILO，First In Last Out）的 有序串列，
是限制 線性表 中元素的插入和洗掉只能在線性表的 **同一端 **進行的一種特殊線性表：
- 堆疊頂（Top）：允許插入和洗掉的一端，為 變化的一端，稱為堆疊頂
- 堆疊底（Bottom）：另一端為 固定的一端，稱為堆疊底
根據上述定義，可知：
- 最先 放入堆疊中元素在 堆疊底
- **最后 **放入堆疊中元素在 堆疊頂
而洗掉元素則剛好相反：
- 最先 放入堆疊中元素，最后 洗掉
- 最后 放入堆疊中元素，最先 洗掉
可以參考下圖的，入堆疊和出堆疊圖示：
堆疊的應用場景
-
子程式的呼叫
在跳往子程式前，會先將 下個指令的地址 存到堆疊中，直到子程式執行完后再 將地址取出，以 回到原來的程式中，
如方法中呼叫方法，
-
處理遞回呼叫
和子程式呼叫類似，只是除了存盤下一個指令的地址外，也將引數、區域變數等資料存入堆疊中，
-
運算式的轉換（中綴運算式轉后綴運算式）與求值（實際解決）
-
二叉樹的遍歷
-
圖形的深度優先（depth-first）搜索法
陣列模擬堆疊
//使用陣列模擬堆疊
class ArrayStack{
private int maxTop;//表示堆疊的最大容量
private int[] stack;//存盤堆疊中資料
private int top = -1;//指向堆疊頂元素，默認值-1
public ArrayStack(int maxTop){
this.maxTop = maxTop;
stack = new int[maxTop];//創建堆疊陣列
}
//判斷堆疊是否滿
public boolean isFull(){
return top == maxTop - 1;
}
//判斷堆疊空
public boolean isEmpty(){
return top == -1;
}
//入堆疊
public void push(int num){
//先判斷堆疊是否滿了
if(isFull()){
System.out.println("入堆疊失敗，堆疊滿");
return;
}
stack[++top] = num;
}
//出堆疊
public int pop(){
if(isEmpty()){
throw new RuntimeException("堆疊中沒有資料");
}
return stack[top--];
}
//顯示堆疊中所有資料
public void list(){
if(isEmpty()){
System.out.println("堆疊中沒有資料");
return;
}
for(int i = top; i >= 0; i--){
System.out.printf("stack[%d] = %d\n",i,stack[i]);
}
}
}
//測驗代碼
//測驗堆疊
ArrayStack stack = new ArrayStack(4);
Scanner scanner = new Scanner(System.in);
String order = "";
boolean flag = true;
while(flag){
System.out.println("show 顯示所有資料");
System.out.println("push 入堆疊");
System.out.println("pop 出堆疊");
System.out.println("exit 退出程式");
System.out.println("請輸入一個指令:");
order = scanner.next();
switch (order){
case "show":
stack.list();
break;
case "push":
System.out.println("請輸入一個資料:");
int num = scanner.nextInt();
stack.push(num);
break;
case "pop":
try {
int result = stack.pop();
System.out.println(result);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "exit":
flag = false;
scanner.close();
break;
default:
break;
}
}
System.out.println("程式退出");
鏈表模擬堆疊
//定義鏈表節點
class Node{
int data;//存盤資料
Node next;//指向下一個鏈表
public Node(int data){
this.data = https://www.cnblogs.com/wyzstudy/archive/2021/10/10/data;
}
@Override
public String toString() {
return"Node{" +
"data="https://www.cnblogs.com/wyzstudy/archive/2021/10/10/+ data +'}';
}
}
//使用鏈表定義堆疊
class LinkedListStack{
private Node top;//定義一個堆疊頂指標，指向鏈表的第一個元素，也就是堆疊頂元素
private int maxTop;//堆疊的最大長度
private int size = 0;//記錄堆疊中元素的個數
public LinkedListStack(int maxTop){
this.maxTop = maxTop;
}
//判斷是否為空
public boolean isEmpty(){
return size == 0;
}
//判斷是否為滿
public boolean isFull(){
return size == maxTop;
}
//入堆疊
public void push(int num){
//判斷堆疊是否滿
if(isFull()){
System.out.println("堆疊滿，添加失敗");
return;
}
Node h = new Node(num);
h.next = top;
top = h;
size++;//元素個數增加
}
//出堆疊
public int pop(){
if(isEmpty()){
throw new RuntimeException("出堆疊失敗，堆疊為空");
}
Node temp = top;
top = top.next;//指標后移
size--;//元素個數減少
return temp.data;
}
//遍歷堆疊中元素
public void list(){
if(isEmpty()){
System.out.println("堆疊中沒有資料");
return;
}
Node temp = top;
for(int i = size - 1; i >= 0; i--){
System.out.printf("stack[%d] = %d\n",i,temp.data);
temp = temp.next;//指標后移
}
}
//獲取堆疊中元素個數
public int size(){
return size;
}
}
//測驗代碼
LinkedListStack stack = new LinkedListStack(4);
Scanner scanner = new Scanner(System.in);
String order = "";
boolean flag = true;
while(flag){
System.out.println("show 顯示所有資料");
System.out.println("push 入堆疊");
System.out.println("pop 出堆疊");
System.out.println("size 獲取堆疊長度");
System.out.println("exit 退出程式");
System.out.println("請輸入一個指令:");
order = scanner.next();
switch (order){
case "show":
stack.list();
break;
case "push":
System.out.println("請輸入一個資料:");
int num = scanner.nextInt();
stack.push(num);
break;
case "pop":
try {
int result = stack.pop();
System.out.println(result);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "size":
System.out.println(stack.size());
break;
case "exit":
flag = false;
scanner.close();
break;
default:
break;
}
}
System.out.println("程式退出");
綜合計算器
使用堆疊來實作綜合計算器，比如，輸入一個運算式：7*2*2-5+1-5+3-3 ，計算出這個運算式的結果
什么是中綴運算式
中綴運算式是一個通用的 算術 或 邏輯公式表示方法， 運算子 是以 中綴形式 處于運算元的 中間（例：3 + 4），中綴運算式是人們常用的算術表示方法，
思路分析
如上圖：
-
需要先掃描字串，可以通過一個 index 變數來輔助掃描
-
如果 發現是一個數字，直接入數堆疊
-
如果 發現是一個運算子，分以下情況：
- 當符號堆疊為空的時候，將符號直接添加到堆疊中
- 當符號堆疊不為空的時候，比較當前符號與符號堆疊頂元素的優先級進行比較，如果大于符號堆疊元素優先級則直接添加到符號堆疊中，小于等于符號堆疊中元素時，則從符號堆疊中彈出一個符號，從數堆疊中彈出兩個數，進行計算，將結果加入數堆疊，再將當前符號添加到符號堆疊
-
當掃描完畢時：
- 順序的從數堆疊中彈出 2 個數，
- 從符號堆疊中彈出 1 個運算子
- 將他們進行計算，然后把計算結果壓入數堆疊中
然后重復上面的三個步驟
-
最后在數堆疊中只會存在一個數值，它就是結果，
代碼實作
//使用陣列模擬堆疊
class ArrayStack2{
private int maxTop;//表示堆疊的最大容量
private int[] stack;//存盤堆疊中資料
private int top = -1;//指向堆疊頂元素，默認值-1
public ArrayStack2(int maxTop){
this.maxTop = maxTop;
stack = new int[maxTop];//創建堆疊陣列
}
//判斷堆疊是否滿
public boolean isFull(){
return top == maxTop - 1;
}
//判斷堆疊空
public boolean isEmpty(){
return top == -1;
}
//入堆疊
public void push(int num){
//先判斷堆疊是否滿了
if(isFull()){
System.out.println("入堆疊失敗，堆疊滿");
return;
}
stack[++top] = num;
}
//出堆疊
public int pop(){
if(isEmpty()){
throw new RuntimeException("堆疊中沒有資料");
}
return stack[top--];
}
//顯示堆疊中所有資料
public void list(){
if(isEmpty()){
System.out.println("堆疊中沒有資料");
return;
}
for(int i = top; i >= 0; i--){
System.out.printf("stack[%d] = %d\n",i,stack[i]);
}
}
//判斷是不是字符
public boolean isOper(int oper){
return oper == '+' || oper == '-' || oper == '*' || oper == '/';
}
//獲取堆疊頂元素
public int getHead(){
return stack[top];
}
//計算
/**
*
* @param num1 第一個是num1
* @param num2 第二個是num2
* @param oper 第三個是運算子
* @return 計算結果
*/
public int cal(int num1,int num2,int oper){
int result = 0;
switch(oper){
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
}
return result;
}
//判斷符號的優先級，每個符號的優先級由我們自己定義設定
public static int priority(int oper){
if(oper == '*' || oper == '/'){
return 1;
}else if(oper == '+' || oper == '-'){
return 0;
}else{
return -1;
}
}
}
//Calculator類實作
public class Calculator {
public static void main(String[] args) {
//要計算的算式
String express = "7*8-8+2*3+4-7";
//定義兩個堆疊，一個用來保存數，一個用來保存符號
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
int index = 0;//用于遍歷運算式的索引
int num1 = 0;//用于保存彈出來的數1
int num2 = 0;
int result = 0;//保存結果
int oper = 0;//保存符號
char ch = ' ';//掃描每次得到的資料
//1.需要先掃描字串，可以通過一個 index 變數來輔助掃描
while(true){
ch = express.substring(index,index+1).charAt(0);
//判斷是不是符號
if(numStack.isOper(ch)){
//當我們遍歷的資料是符號的情況
if(operStack.isEmpty()){
//查看堆疊是否為空，為空，直接將符號添加
operStack.push(ch);
}else{
//進行比較添加,如果當前符號的優先級大于，堆疊頂元素的優先級，直接添加，否則
//彈出數堆疊兩個數進行計算，彈出符號堆疊符號，進行運算，將結果加入數堆疊，
// 然后再將現在符號加入符號堆疊
if(ArrayStack2.priority(ch) > ArrayStack2.priority(operStack.getHead())){
//大于情況，直接添加
operStack.push(ch);
}else{
//小于或者等于情況
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.cal(num1,num2,oper);
numStack.push(result);
operStack.push(ch);
}
}
}else{
//當我們遍歷的資料是數字的時候
numStack.push(ch - 48);//這里一定要減48，不減48添加的是對應數字的asci碼的對應數字
}
index++;
if(index >= express.length()){
break;//掃描完成
}
}
//當掃描完畢時，從符號堆疊，數堆疊彈出資料進行計算
while(true){
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.cal(num1,num2,oper);
numStack.push(result);
if(operStack.isEmpty()){//符號堆疊全部彈出以后，計算結束
break;
}
}
//當遍歷完成以后，數堆疊中的資料就是計算結果
System.out.printf("%s = %d\n",express,numStack.pop());
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/308238.html
標籤：其他