Java數據結構與算法之雙向鏈表、環形鏈表及約瑟夫問題的示例分析

這篇文章給大家分享的是有關Java數據結構與算法之雙向鏈表、環形鏈表及約瑟夫問題的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

一、雙向鏈表

使用帶head頭的雙向鏈表實現 - 水滸英雄排行榜管理單向鏈表的缺點分析：

1. 單向鏈表，查找的方向只能是一個方向，而雙向鏈表可以向前或者向后查找。

2. 單向鏈表不能自我刪除，需要靠輔助節點，而雙向鏈表，則可以自我刪除，所以前面我們單鏈表刪除節點時，總是找到temp,temp時待刪除節點的前一個節點(認真體會)。

分析雙向鏈表的遍歷，添加，修改，刪除的操作思路

1.遍歷和單鏈表一樣只是可以向前，也可以向后查找

2.添加(默認添加到雙向鏈表的最后)

• 先找到雙向鏈表的最后這個節點

• temp.next = newHeroNode

• newHeroNode.pre = temp

3.修改思路和原理與單向鏈表一樣

4.刪除

• 因為時雙向鏈表，因此，我們可以實現自我刪除某個節點

• 直接找到要刪除的這個節點，比如temp

• temp.pre.next = temp.next

• temp.next.pre = temp.pre

public class DoubleLinkedListDemo {
	public static void main(String[] args) {
		// 測試
		System.out.println("雙向鏈表的測試");
		// 先創建節點
		HeroNode2 hero1 = new HeroNode2(1, "宋江", "及時雨");
		HeroNode2 hero2 = new HeroNode2(2, "盧俊義", "玉麒麟");
		HeroNode2 hero3 = new HeroNode2(3, "吳用", "智多星");
		HeroNode2 hero4 = new HeroNode2(4, "林沖", "豹子頭");
		// 創建一個雙向鏈表
		DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
		// 加入
		doubleLinkedList.add(hero1);
		doubleLinkedList.add(hero2);
		doubleLinkedList.add(hero3);
		doubleLinkedList.add(hero4);
		doubleLinkedList.list();
		// 修改
		HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入云龍");
		doubleLinkedList.update(newHeroNode);
		System.out.println("修改后的鏈表情況");
		doubleLinkedList.list();
		// 刪除
		doubleLinkedList.del(3);
		System.out.println("刪除后的鏈表情況~~");
		doubleLinkedList.list();
	}
}
//創建一個雙向鏈表的類
class DoubleLinkedList {
	// 先初始化一個頭節點，頭節點不要動，不存放具體的數據
	private HeroNode2 head = new HeroNode2(0, "", "");
	// 返回頭節點
	public HeroNode2 getHead() {
		return head;
	}
	// 顯示鏈表[遍歷]
	public void list() {
		// 判斷鏈表是否為空
		if (head.next == null) {
			System.out.println("鏈表為空");
			return;
		}
		// 因為頭節點，不能動，因此我們需要一個輔助變量來遍歷
		HeroNode2 temp = head.next;
		while (true) {
			// 判斷是否到鏈表最后
			if (temp == null) {
				break;
			}
			// 輸出節點的信息
			System.out.println(temp);
			// 將temp后移，一定小心
			temp = temp.next;
		}
	}
	// 添加一個節點到雙向鏈表的最后
	public void add(HeroNode2 heroNode) {
		// 因為head節點不能動，因此我們需要一個輔助變量temp
		HeroNode2 temp = head;
		// 遍歷鏈表，找到最后
		while (true) {
			// 找到鏈表的最后
			if (temp.next == null) {
				break;
			}
			// 如果沒有找到最后，將temp后移
			temp = temp.next;
		}
		// 當退出while循環時，temp就指向了鏈表的最后
		// 形成一個雙向鏈表
		temp.next = heroNode;
		heroNode.pre = temp;
	}
	// 修改一個節點的內容，雙向鏈表的節點內容修改和單向鏈表一樣
	// 只是節點類型改成HeroNode2
	public void update(HeroNode2 newHeroNode) {
		// 判斷是否空
		if (head.next == null) {
			System.out.println("鏈表為空~~");
			return;
		}
		// 找到需要修改的節點，根據no編號
		// 定義一個輔助變量
		HeroNode2 temp = head.next;
		boolean flag = false;// 表示是否找到該節點
		while (true) {
			if (temp == null) {
				break;// 已經遍歷完鏈表
			}
			if (temp.no == newHeroNode.no) {
				// 找到
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 根據flag判斷是否找到要修改的節點
		if (flag) {
			temp.name = newHeroNode.name;
			temp.nickname = newHeroNode.nickname;
		} else {// 沒有找到
			System.out.printf("沒有找到編號 %d 的節點，不能修改\n", newHeroNode.no);
		}
	}
	// 從雙向鏈表中刪除一個節點
	// 說明
	// 1. 對于雙向鏈表，我們可以直接找到要刪除的這個節點
	// 2. 找到后，自我刪除即可
	public void del(int no) {
		// 判斷當前鏈表是否為空
		if (head.next == null) {// 空鏈表
			System.out.println("鏈表為空，無法刪除");
			return;
		}
		HeroNode2 temp = head.next;// 輔助變量(指針),指向第一個節點(與單向鏈表不同)
		boolean flag = false;// 標志是否找到待刪除節點
		while (true) {
			if (temp.next == null) {// 已經到鏈表的最后節點的next
				break;
			}
			if (temp.next.no == no) {
				// 找到的待刪除節點的前一個節點temp
				flag = true;
				break;
			}
			temp = temp.next;// temp后移，遍歷
		}
		// 判斷flag
		if (flag) {// 找到
			// 可以刪除
			temp.pre.next = temp.next;
			// 如果是最后一個節點，就不需要執行下面的這句話，否則出現空指針
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.printf("要刪除的 %d 節點不存在\n", no);
		}
	}
}
//定義HeroNode2,每個HeroNode對象就是一個節點
class HeroNode2 {
	public int no;
	public String name;
	public String nickname;
	public HeroNode2 next;// 指向下一個節點,默認為null
	public HeroNode2 pre;// 指向前一個節點,默認為null
	// 構造器
	public HeroNode2(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}
	// 為了顯示方便，我們重寫toString
	@Override
	public String toString() {
		return "HeroNode2 [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}

二、環形鏈表及其應用：約瑟夫問題

環形鏈表圖示

構建一個單向的環形鏈表思路

1.先創建第一個節點，讓 first 指向該節點，并形成環形

2.后面當我們每創建一個新的節點，就把該節點加入到已有的環形鏈表中即可。

遍歷環形鏈表

1.先讓一個輔助指針(變量)curBoy,指向 first 節點

2.然后通過一個 while 循環遍歷該環形鏈表即可 cur.Boy.next == first 結束

約瑟夫問題

1.創建一個輔助指針(變量)helper,事先應該指向環形鏈表的最后這個節點。

2.小孩報數前，先讓 first 和 helper 移動 k -1次（移動到報數的小孩）

3.當小孩報數時，讓 first 和 helper 指針同時的移動 m - 1次

4.這時就可以將 first 指向的小孩節點出圈

first = first.next

helper.next = first

原來 first 指向的節點就沒有任何引用，就會被回收

public class Josepfu {
	public static void main(String[] args) {
		// 測試看看構建環形鏈表，和遍歷是否ok
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);// 加入5個小孩節點
		circleSingleLinkedList.showBoy();
		// 測試小孩出圈是否正確
		circleSingleLinkedList.countBoy(1, 2, 5);// 2->4->1->5->3
	}
}
//創建一個環形的單向鏈表
class CircleSingleLinkedList {
	// 創建一個first節點，當前沒有編號
	private Boy first = null;
 
	// 添加小孩節點，構建一個環形的鏈表
	public void addBoy(int nums) {
		// nums 做一個數據校驗
		if (nums < 1) {
			System.out.println("nums的值不正確");
			return;
		}
		Boy curBoy = null;// 輔助指針，幫助構建環形鏈表
		// 使用for來創建環形鏈表
		for (int i = 1; i <= nums; i++) {
			// 根據編號，創建小孩節點
			Boy boy = new Boy(i);
			// 如果是第一個小孩
			if (i == 1) {
				first = boy;
				first.setNext(first);// 構成環(暫時是一個節點的環)
				curBoy = first;// 讓curBoy指向第一個小孩
			} else {// 這塊的操作看不懂，可以回去看一下當時老師視頻里的流程圖，特別好理解！！！！！！！！！！
				curBoy.setNext(boy);
				boy.setNext(first);
				curBoy = boy;
			}
		}
	}
	// 遍歷當前的環形鏈表
	public void showBoy() {
		// 判斷鏈表是否為空
		if (first == null) {
			System.out.println("沒有任何小孩~~");
			return;
		}
		// 因為first不能動，因此我們仍然使用一個輔助指針完成遍歷
		Boy curBoy = first;
		while (true) {
			System.out.printf("小孩的編號 %d \n", curBoy.getNo());
			if (curBoy.getNext() == first) {// 說明已經遍歷完畢
				break;
			}
			curBoy = curBoy.getNext();// curBoy后移
		}
	}
	// 根據用戶的輸入，計算出小孩出圈的順序
	/**
	 * @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;
		// 需要創建一個輔助指針(變量)helper,事先應該指向環形鏈表的最后這個節點
		while (true) {
			if (helper.getNext() == first) {// 說明helper指向最后小孩節點
				break;
			}
			helper = helper.getNext();
		}
		// 小孩報數前，先讓first 和 helper 移動 k - 1次
		for (int j = 0; j < startNo - 1; j++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		// 當小孩報數時，讓 first 和 helper 指針同時的移動 m -1次，然后出圈
		// 這里是一個循環操作，直到圈中只有一個節點
		while (true) {
			if (helper == first) {// 說明圈中只有一個節點
				break;
			}
			// 讓first 和 helper 指針同時的移動 countNum - 1
			for (int j = 0; j < countNum - 1; j++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			// 這時first指向的節點，就是要出圈的小孩節點
			System.out.printf("小孩%d出圈\n", first.getNo());
			// 這時將first指向的小孩節點出圈
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.printf("最后留在圈中的小孩編號%d \n", first.getNo());
	}
}
//創建一個Boy類，表示一個節點
class Boy {
	private int no;// 編號
	private Boy next;// 指向下一個節點，默認null
 
	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;
	}
}

感謝各位的閱讀！關于“Java數據結構與算法之雙向鏈表、環形鏈表及約瑟夫問題的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！