雙向鏈表咬荷、環(huán)形鏈表解決約瑟夫問(wèn)題
雙向鏈表
之前在 學(xué)會(huì)用Java實(shí)現(xiàn)一個(gè)單向鏈表 博客中已經(jīng)介紹過(guò)單向鏈表
雙向鏈表的區(qū)別在于场梆，每一個(gè)節(jié)點(diǎn)不光有指向下一個(gè)節(jié)點(diǎn)的指針奠衔，也有指向上一個(gè)節(jié)點(diǎn)的指針
相比較而言嚎货，雙向鏈表的好處在于雹熬，遍歷時(shí)有前驅(qū)有后繼腰涧，可進(jìn)可退葵姥；缺點(diǎn)在于增加象浑、刪除節(jié)點(diǎn)時(shí)步驟更多了，每個(gè)節(jié)點(diǎn)也需要多分配一個(gè)指針的存儲(chǔ)空間
用Java實(shí)現(xiàn)雙向鏈表
實(shí)現(xiàn)雙向鏈表琅豆，和單向鏈表很相似愉豺，區(qū)別在于節(jié)點(diǎn)對(duì)象多一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針，同時(shí)增加茫因、刪除節(jié)點(diǎn)的操作多了幾個(gè)步驟蚪拦；而遍歷、修改幾乎沒有區(qū)別
還是用梁山好漢的例子冻押；首先創(chuàng)建單個(gè)節(jié)點(diǎn)對(duì)象
/**
* 定義一個(gè)HeroNode2對(duì)象驰贷，就是一個(gè)雙向鏈表中的節(jié)點(diǎn)
*/
class HeroNode2{
/**
* 英雄排名
*/
public int no;
/**
* 名字
*/
public String name;
/**
* 稱號(hào)
*/
public String nickname;
/**
* 指向下一個(gè)英雄
*/
public HeroNode2 next;
/**
* 指向上一個(gè)英雄
*/
public HeroNode2 pre;
/**
* 構(gòu)造器 創(chuàng)建一個(gè)梁山好漢
* @param no 排名
* @param name 姓名
* @param nickname 稱號(hào)
*/
public HeroNode2(int no,String name,String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
/**
* 重寫ToString打印雙向鏈表
*/
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
然后,DoubleLinkedList類表示一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表
添加上增刪改查的方法
添加和刪除時(shí)，需要考慮好前后關(guān)系洛巢，最多可能影響到四個(gè)指針
具體可閱讀代碼中的注釋加以理解
/**
* 雙向鏈表類
*/
class DoubleLinkedList{
/**
* 先初始化一個(gè)頭節(jié)點(diǎn)括袒，頭節(jié)點(diǎn)不動(dòng)，也不存放具體數(shù)據(jù)
*/
private final HeroNode2 head = new HeroNode2(0,"","");
/**
* 根據(jù)編號(hào)從雙向鏈表中刪除節(jié)點(diǎn)
* @param no 要?jiǎng)h除的節(jié)點(diǎn)編號(hào)
*/
public void delete(int no){
//遍歷稿茉，讓指針始終指向要遍歷的節(jié)點(diǎn)
HeroNode2 temp = head.next;
while (temp!=null){
//判斷當(dāng)前遍歷的節(jié)點(diǎn)是否是要?jiǎng)h除的節(jié)點(diǎn)锹锰，如果是進(jìn)行刪除，給出刪除成功提示漓库，并結(jié)束方法恃慧，如果不是繼續(xù)遍歷下一個(gè)
if (temp.no == no) {
//將上一個(gè)的下一個(gè)指向要?jiǎng)h除的下一個(gè)
temp.pre.next = temp.next;
//這里需要判斷如果要?jiǎng)h除的不是最后一個(gè)，將下一個(gè)的上一個(gè)指向要?jiǎng)h除的上一個(gè)
if (temp.next!=null){
temp.next.pre = temp.pre;
}
System.out.println("刪除成功");
return;
}
temp = temp.next;
}
//退出循環(huán)后還沒有結(jié)束渺蒿，表示沒有找到要?jiǎng)h除的節(jié)點(diǎn)
System.out.println("未找到要?jiǎng)h除的節(jié)點(diǎn)"+no);
}
/**
* 根據(jù)編號(hào)痢士，修改節(jié)點(diǎn)，編號(hào)不能修改
* @param newHeroNode 修改后的英雄信息
*/
public void update(HeroNode2 newHeroNode){
//1.遍歷鏈表茂装，找到要修改的編號(hào)no對(duì)應(yīng)的節(jié)點(diǎn)
HeroNode2 temp = head.next;
while (temp != null){
//有節(jié)點(diǎn)等待遍歷怠蹂，判斷no是否相同
if (temp.no == newHeroNode.no){
//相同進(jìn)行修改，打印修改成功提示训唱，并直接結(jié)束方法
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
System.out.println("修改成功");
return;
}
//不相同繼續(xù)遍歷下一個(gè)
temp = temp.next;
}
//全部遍歷完都沒有成功修改退出方法褥蚯，表示沒有找到要修改的編號(hào)
System.out.println("未找到編號(hào)"+newHeroNode.no+"的英雄，如有需要請(qǐng)直接填加");
}
/**
* 添加節(jié)點(diǎn)到雙向鏈表（添加到尾部）
*/
public void add(HeroNode2 heroNode){
//找到當(dāng)前鏈表最后一個(gè)節(jié)點(diǎn)况增，把next指向這個(gè)新的節(jié)點(diǎn)
//遍歷鏈表的臨時(shí)變量赞庶，指向當(dāng)前正遍歷到的節(jié)點(diǎn)，從head開始
HeroNode2 temp = head;
//判斷當(dāng)前temp是否存在next不存在說(shuō)明當(dāng)前temp指向的節(jié)點(diǎn)就是最后一個(gè)節(jié)點(diǎn)
while (temp.next != null) {
//存在就會(huì)進(jìn)入循環(huán)澳骤，繼續(xù)遍歷歧强，將temp指向當(dāng)前temp的next
temp = temp.next;
}
//當(dāng)退出了循環(huán)之后，當(dāng)前temp就是當(dāng)前鏈表最后一個(gè)節(jié)點(diǎn),將他的next指向正在新增的節(jié)點(diǎn),將新增的pre指向temp
temp.next = heroNode;
heroNode.pre = temp;
}
/**
* 添加節(jié)點(diǎn)到雙向鏈表（該方法會(huì)按排名的順序排序）
*/
public void addByOrder(HeroNode2 heroNode){
//找到當(dāng)前鏈表最后一個(gè)節(jié)點(diǎn)为肮，把next指向這個(gè)新的節(jié)點(diǎn)
//遍歷鏈表的臨時(shí)變量摊册，指向當(dāng)前正遍歷到的前一個(gè)節(jié)點(diǎn)，從head開始
HeroNode2 temp = head;
//判斷當(dāng)前temp是否存在next不存在說(shuō)明當(dāng)前temp指向的節(jié)點(diǎn)就是最后一個(gè)節(jié)點(diǎn)
while (temp.next != null) {
//存在就會(huì)進(jìn)入循環(huán)颊艳，先判斷排名關(guān)系茅特。如果和遍歷到的節(jié)點(diǎn)排名和新插入的相同忘分，拋出異常提示
if (temp.next.no == heroNode.no){
throw new RuntimeException("不能插入排名相同的節(jié)點(diǎn)");
}
//如果遍歷到的節(jié)點(diǎn)排名大于當(dāng)前插入節(jié)點(diǎn)的排名，說(shuō)明新節(jié)點(diǎn)剛好應(yīng)該在上一個(gè)節(jié)點(diǎn)和正在遍歷的節(jié)點(diǎn)之間白修，執(zhí)行插入操作后返回結(jié)束方法
if (temp.next.no > heroNode.no){
//當(dāng)前插入節(jié)點(diǎn)的下一個(gè)指向當(dāng)前遍歷到的第一個(gè)比他排名高的節(jié)點(diǎn)
heroNode.next = temp.next;
//當(dāng)前插入節(jié)點(diǎn)的前一個(gè)指向當(dāng)前遍歷節(jié)點(diǎn)的前一個(gè)
heroNode.pre = temp;
//將當(dāng)前遍歷節(jié)點(diǎn)的前一個(gè)的下一個(gè)指向當(dāng)前插入的節(jié)點(diǎn)
temp.next = heroNode;
//將當(dāng)前遍歷節(jié)點(diǎn)的前一個(gè)指向當(dāng)前插入的節(jié)點(diǎn)
temp.next.pre = heroNode;
return;
}
//如果排名比正在遍歷的大說(shuō)明還需要繼續(xù)遍歷妒峦，將temp指向當(dāng)前temp的next進(jìn)行下一次循環(huán)
temp = temp.next;
}
//當(dāng)退出了循環(huán)之后還沒有找到應(yīng)該存放的位子，當(dāng)前temp.next為空temp就是當(dāng)前鏈表最后一個(gè)節(jié)點(diǎn)
//將他的next指向正在新增的節(jié)點(diǎn)
temp.next = heroNode;
//將新增的節(jié)點(diǎn)pre指向最后一個(gè)節(jié)點(diǎn)
heroNode.pre = temp;
}
/**
* 顯示鏈表【遍歷】
*/
public void show(){
System.out.println("----------------------------------------------");
//先判斷鏈表是否為空
if (head.next == null){
System.out.println("鏈表為空");
return;
}
//遍歷鏈表的臨時(shí)變量兵睛，指向當(dāng)前正遍歷到的節(jié)點(diǎn)肯骇，從head的next開始，也就是從第一個(gè)開始
HeroNode2 temp = head.next;
//當(dāng)前正遍歷到的節(jié)點(diǎn)不為空的時(shí)候祖很，打印當(dāng)前節(jié)點(diǎn)笛丙，并將temp指向next繼續(xù)參與遍歷，直到temp為空表示遍歷結(jié)束
while (temp != null){
System.out.println(temp);
temp = temp.next;
}
System.out.println("----------------------------------------------");
}
}
環(huán)形鏈表解決約瑟夫問(wèn)題
約瑟夫問(wèn)題：
設(shè)編號(hào)為1假颇，2胚鸯，3...n的n個(gè)人圍坐一圈
約定編號(hào)為k（1<=k<=n）的人從1開始報(bào)數(shù)，數(shù)到m的人出列笨鸡，從下一個(gè)人開始繼續(xù)從1報(bào)數(shù)蠢琳，數(shù)到m再出列，依次類推镜豹，直到所有人都出列，由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列
分析：圍坐一圈的人蓝牲，報(bào)數(shù)只朝一個(gè)方向趟脂，那么如果將一個(gè)單向鏈表首尾相連，即可模擬出這一場(chǎng)景
然后開始遍歷這個(gè)環(huán)形鏈表例衍，找到要出列的人記錄下來(lái)昔期，然后從鏈表中刪除，再?gòu)南乱粋€(gè)人開始繼續(xù)遍歷佛玄，直到鏈表為空硼一，即解決了這個(gè)問(wèn)題
這個(gè)問(wèn)題中，圍坐的人作為鏈表中的節(jié)點(diǎn)對(duì)象梦抢，只需要一個(gè)編號(hào)no屬性般贼，和一個(gè)指向下一節(jié)點(diǎn)的指針即可
創(chuàng)建出Boy類
/**
* boy類表示一個(gè)環(huán)形鏈表中的節(jié)點(diǎn)對(duì)象
*/
class Boy{
/**
* 編號(hào)
*/
private int no;
/**
* 指向下一個(gè)節(jié)點(diǎn)，默認(rèn)null
*/
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;
}
}
還需要一個(gè)類來(lái)表示環(huán)形鏈表
需要用到兩個(gè)指針奥吩，一個(gè)指向第一個(gè)節(jié)點(diǎn)一個(gè)指向最后一個(gè)節(jié)點(diǎn)
需要一個(gè)屬性來(lái)記錄當(dāng)前鏈表中總節(jié)點(diǎn)數(shù)（剩余圍坐人數(shù)）
指向第一個(gè)節(jié)點(diǎn)的指針用于確定開始遍歷的位置哼蛆，指向最后一個(gè)節(jié)點(diǎn)的指針用于判斷遍歷是否結(jié)束，否則環(huán)形鏈表的遍歷會(huì)成為死循環(huán)
創(chuàng)建一個(gè)類SingleCircleLinkedList霞赫，表示環(huán)形鏈表
1.構(gòu)造器根據(jù)一圈圍了多少人腮介，初始化一個(gè)包含了多少個(gè)Boy節(jié)點(diǎn)的環(huán)形鏈表
2.方法showList()，打印當(dāng)前鏈表
3.方法countBoy(int startNo,int countNo)端衰，打印出圈順序
/**
* 創(chuàng)建單向環(huán)形鏈表類
*/
class SingleCircleLinkedList{
//創(chuàng)建一個(gè)first節(jié)點(diǎn)叠洗，指向第一個(gè)節(jié)點(diǎn),初始為空
private Boy first = null;
//創(chuàng)建一個(gè)last節(jié)點(diǎn)甘改，指向最后一個(gè)節(jié)點(diǎn)，初始為空
private Boy last = null;
private int nums = 0;
/**
* 添加小孩節(jié)點(diǎn)
* （尾插法,只能作為創(chuàng)建使用）
*
* @param nums 添加的小孩數(shù)量
*/
public SingleCircleLinkedList(int nums){
//對(duì)nums做入?yún)⑿ｒ?yàn),最少需要一個(gè)節(jié)點(diǎn)
if (nums<1){
System.out.println("創(chuàng)建環(huán)形鏈表至少需要1個(gè)節(jié)點(diǎn)");
return;
}
//創(chuàng)建環(huán)形鏈表
//至少創(chuàng)建一個(gè)節(jié)點(diǎn)灭抑，而且第一個(gè)節(jié)點(diǎn)需要區(qū)別對(duì)待十艾，那就先創(chuàng)建出來(lái)，直接新建編號(hào)1節(jié)點(diǎn)讓指針first指向第一個(gè)節(jié)點(diǎn)
first = new Boy(1);
//自己指向自己名挥，形成環(huán)狀
first.setNext(first);
//將最后一個(gè)也指向當(dāng)前節(jié)點(diǎn)
last = first;
//然后再循環(huán)插入后續(xù)節(jié)點(diǎn)
for (int i = 2; i <= nums; i++) {
//根據(jù)編號(hào)創(chuàng)建小孩節(jié)點(diǎn)
Boy boy = new Boy(i);
//如果不是第一個(gè)節(jié)點(diǎn)疟羹，將最后一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的next指向first節(jié)點(diǎn)禀倔，再將最后一個(gè)節(jié)點(diǎn)更改為指向新節(jié)點(diǎn)
last.setNext(boy);
boy.setNext(first);
last = boy;
}
//保存一下環(huán)形鏈表總節(jié)點(diǎn)數(shù)量
this.nums = nums;
}
/**
* 打印出循環(huán)鏈表的情況
*/
public void showList(){
//判斷環(huán)形鏈表是否為空
if (nums==0){
System.out.println("當(dāng)前鏈表為空");
return;
}
//打印鏈表節(jié)點(diǎn)總數(shù)
System.out.println("當(dāng)前鏈表總節(jié)點(diǎn)數(shù)為："+nums);
//構(gòu)建字符串作為最終的打印
StringBuilder builder = new StringBuilder();
//創(chuàng)建輔助指針遍歷打印鏈表
Boy curBoy = first;
while (curBoy!=last){
builder.append(curBoy.getNo()).append(" ").append("--> ");
curBoy = curBoy.getNext();
}
//退出循環(huán)時(shí)說(shuō)明輔助指針已經(jīng)指向了最后一個(gè)榄融，打印最后一個(gè)指向第一個(gè)即可
builder.append(curBoy.getNo()).append(" ").append("--> ").append(curBoy.getNext().getNo());
System.out.println(builder);
}
/**
* 打印出圈順序
* @param startNo 從幾號(hào)開始數(shù)
* @param countNo 數(shù)幾個(gè)出列
*/
public void countBoy(int startNo,int countNo){
//判斷鏈表是否為空
if (nums==0){
System.out.println("鏈表為空");
return;
}
//數(shù)據(jù)校驗(yàn),只能從1到nums開始報(bào)數(shù)
if (startNo<1 || startNo>nums) {
System.out.println("開始報(bào)數(shù)人不存在與鏈表中");
return;
}
//校驗(yàn)結(jié)束，創(chuàng)建一個(gè)輔助指針幫助遍歷計(jì)算小孩出圈
Boy helper = first;
//先找到開始節(jié)點(diǎn),用helper指向
while (helper.getNo() != startNo) {
helper = helper.getNext();
}
//然后開始尋找要出列的前一個(gè)節(jié)點(diǎn)救湖，先記錄出列節(jié)點(diǎn)的編號(hào)愧杯，然后執(zhí)行節(jié)點(diǎn)的出列，讓nums-1,將helper指向新的要開始報(bào)數(shù)的節(jié)點(diǎn)
//出列次數(shù)計(jì)數(shù)器
int times = 1;
while (nums !=0){
//找到出列節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)鞋既，用helper指向
int no = helper.getNo();
for (int i = no; i < no+countNo-2; i++) {
helper = helper.getNext();
}
//記錄節(jié)點(diǎn)編號(hào)
System.out.println("第"+times+"次出列的編號(hào)為："+helper.getNext().getNo());
//出列次數(shù)加1
times++;
//執(zhí)行出列操作,將要出列的前一個(gè)指向要出列的下一個(gè)即可,此時(shí)helper依然指向的是要出列的前一個(gè),它的下一個(gè)為下一次開始報(bào)數(shù)的節(jié)點(diǎn)
//TODO 當(dāng)要?jiǎng)h除的節(jié)點(diǎn)為first或last時(shí)力九，需要移動(dòng)first和last的指向，否則還會(huì)存環(huán)形鏈表邑闺，以及移除最后一個(gè)的時(shí)候也需要切斷他自己和自己的聯(lián)系
helper.setNext(helper.getNext().getNext());
//出列了一個(gè)節(jié)點(diǎn)跌前，鏈表總節(jié)點(diǎn)數(shù)減一
nums--;
//helper指向新的開始報(bào)數(shù)節(jié)點(diǎn)
helper = helper.getNext();
}
}
}
