? ? ?????????????????????????????????????????????????????????????????????????????????????????????????????????????原創(chuàng)者：文思

? ? ? ? ? ? ? ? ? ? ? ? ? 緒論

為何要學(xué)算法？

有個(gè)字符串”大中中國(guó) 中國(guó)我愛(ài) 中中國(guó)我愛(ài) 你中國(guó)我愛(ài)你中國(guó)我愛(ài)你好”，怎樣判斷出”中國(guó)我愛(ài)你”是否存在，如存在則返回位置。非算法思路則是進(jìn)行暴力匹配，依次匹配，遇到不匹配的再?gòu)淖址_(kāi)頭重新依次匹配，如下：

如果你懂KMP算法，則會(huì)很簡(jiǎn)單。

為何要學(xué)數(shù)據(jù)結(jié)構(gòu)？

開(kāi)發(fā)五子棋的存盤(pán)、續(xù)盤(pán)功能，如果使用二位數(shù)組記錄，則像這樣：

因?yàn)槎粩?shù)據(jù)的很多默認(rèn)值是0，因?yàn)橛涗浟撕芏酂o(wú)意義的數(shù)據(jù)，如果優(yōu)化存儲(chǔ)空間就需要稀疏數(shù)組。

左圖棋盤(pán)用二維數(shù)據(jù)則元素個(gè)數(shù)是11*11，優(yōu)化使用稀疏數(shù)組則為9*3，對(duì)比如下：

二位數(shù)組優(yōu)化為稀疏數(shù)組：

這就是數(shù)據(jù)結(jié)構(gòu)與算法的重要性。不同的數(shù)據(jù)結(jié)構(gòu)有不同的算法，算法是為數(shù)據(jù)結(jié)構(gòu)服務(wù)的。

數(shù)據(jù)結(jié)構(gòu)分兩種：

線性結(jié)構(gòu)

?????? 這是最常用的數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是數(shù)據(jù)元素之間是一對(duì)一的線性關(guān)系(a[0]=30)。體現(xiàn)為數(shù)組、隊(duì)列、鏈表、棧等。線性結(jié)構(gòu)有兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

非線性結(jié)構(gòu)

?????? 數(shù)據(jù)元素之間不是一對(duì)一的線性關(guān)系。體現(xiàn)為二維數(shù)組、廣義表、樹(shù)結(jié)構(gòu)等。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? I 線性結(jié)構(gòu)

? ? ?這是最常用的數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是數(shù)據(jù)元素之間是一對(duì)一的線性關(guān)系(a[0]=30)。體現(xiàn)為數(shù)組、隊(duì)列、鏈表、棧等。

? ? ? 線性結(jié)構(gòu)有兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

? ? ? 順序存儲(chǔ)的線性表稱(chēng)為順序表，表中的存儲(chǔ)元素是連續(xù)的(更主要指元素的地址是連續(xù)的)。

? ? ? 優(yōu)點(diǎn)：存儲(chǔ)密度大=1，存儲(chǔ)空間利用概率高。

? ? ? 鏈?zhǔn)酱鎯?chǔ)的線性表稱(chēng)為鏈表，表中存儲(chǔ)的元素不一定是聯(lián)系的，元素節(jié)點(diǎn)中存放的是數(shù)據(jù)元素以及相鄰元素的地址信息。

? ? ? 優(yōu)點(diǎn)：插入或刪除元素方便效率高，使用靈活???

備注：鏈?zhǔn)揭鎯?chǔ)相鄰元素地址非常重要，因?yàn)槿绻c相鄰元素沒(méi)有關(guān)系就是一個(gè)個(gè)孤立的元素就無(wú)法溝通鏈?zhǔn)浇Y(jié)構(gòu)了，看到上述加粗字體，應(yīng)聯(lián)想到與順序存儲(chǔ)結(jié)構(gòu)在查找、插入效率上的區(qū)別，想象其結(jié)構(gòu)圖形更能推論出鏈?zhǔn)皆诓檎疑蠈?duì)算法依賴(lài)的重要。

?????? 想象順序存儲(chǔ)結(jié)構(gòu)：相鄰的數(shù)據(jù)元素，物理存儲(chǔ)位置也相鄰，依次排列，在順序表中做插入、刪除操作時(shí)，平均移動(dòng)表中的一半元素(要看插入和刪除的位置)，因此對(duì)n較大的順序表效率低。即插入或刪除元素效率不高，適合查找操作。

? ? ? ?想象鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：插入、刪除運(yùn)算應(yīng)該方便，因?yàn)槠渌夭挥靡来挝灰啤５驗(yàn)閿?shù)據(jù)之前沒(méi)有依次排列所以存儲(chǔ)密度低。即存儲(chǔ)空間利用率低，適合插入、刪除元素操作，查找效率一般。

? ? ? 總結(jié)：數(shù)據(jù)量小的時(shí)候首選順序存儲(chǔ)結(jié)構(gòu)，比如ArrayList，數(shù)據(jù)量大且插入、刪除頻繁時(shí)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，比如LinkedList。

一、稀疏數(shù)組與隊(duì)列

當(dāng)一個(gè)數(shù)組中大部分元素為同一個(gè)值的數(shù)組時(shí)，可以用稀疏數(shù)組來(lái)保存。

稀疏數(shù)組的處理方法是:

1、記錄數(shù)組一共有幾行幾列，有多少個(gè)不同的值

2、把具有不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模

?????? 舉例：

將一個(gè)五子棋轉(zhuǎn)換為二位數(shù)組：

再用稀疏數(shù)組方式進(jìn)行優(yōu)化數(shù)據(jù)結(jié)構(gòu)為：

二位數(shù)組轉(zhuǎn)稀疏數(shù)在程序過(guò)程：

1、遍歷原始的二位火速就，得到有效數(shù)據(jù)的個(gè)數(shù)(sum)

2、根據(jù)有效數(shù)據(jù)個(gè)數(shù)創(chuàng)建稀疏數(shù)組spareArr int[sum+1][3]

3、將二維數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組

package com.wensi.sparsearray;

public class SparseArray {

? public static void main(String[] args) {

???? //1創(chuàng)建大小為11*11的原始二位數(shù)組

???? //0標(biāo)識(shí)無(wú)棋子,1標(biāo)識(shí)黑子,2標(biāo)識(shí)藍(lán)字

???? int chessArr[][] = newint[11][11];

???? chessArr[1][2] = 1;

???? chessArr[2][3] = 2;

???? for(int[] row: chessArr){

??????? for(int data: row){

?????????? System.out.print(" "+data);

??????? }

??????? System.out.println();

???? }

???? //二維數(shù)組轉(zhuǎn)稀疏

???? //創(chuàng)建稀疏數(shù)組

???? int sum = 0;

???? for(int[] row: chessArr){

??????? for(int data: row){

?????????? if(data != 0) {

????????????? sum++;

?????????? }

??????? }

???? }

???? int sparseArr[][] = newint[sum + 1][3];

???? //給稀疏數(shù)組第一行賦值

???? sparseArr[0][0] = chessArr.length;

???? sparseArr[0][1] = chessArr[0].length;

???? sparseArr[0][2] = sum;

???? //給稀疏數(shù)組其它行賦值

???? int count = 0;//用于記錄是第幾個(gè)非0數(shù)據(jù)

???? for(int i = 0;i < chessArr.length;i++) {

??????? for(int j = 0;j< chessArr[i].length;j++) {

?????????? if(chessArr[i][j] != 0) {

????????????? count++;

????????????? sparseArr[count][0] = i;

????????????? sparseArr[count][1] = j;

????????????? sparseArr[count][2] = chessArr[i][j];

?????????? }

??????? }

???? }

???? System.out.println("-------轉(zhuǎn)換為稀疏數(shù)組為------");

for(int i = 0; i<sparseArr.length;i++) {?????

????System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);

???? }

? }

}

運(yùn)行結(jié)果：

0 0 0 0 0 0 0 0 0 0 0

?0 0 1 0 0 0 0 0 0 0 0

?0 0 0 2 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

?0 0 0 0 0 0 0 0 0 0 0

----------轉(zhuǎn)換為稀疏數(shù)組為---------

11 11 2?

1? 2? 1?

2? 3? 2

稀疏數(shù)組轉(zhuǎn)原始二位數(shù)據(jù)程序過(guò)程：

1、先讀取稀疏數(shù)組第一行創(chuàng)建二維數(shù)組，如上chessArr2 = int[11][11]

2、讀取稀疏數(shù)組后幾行數(shù)據(jù)，并賦值給二位數(shù)據(jù)即可。

隊(duì)列

隊(duì)列是一個(gè)有序列表，可以用數(shù)組或是鏈表來(lái)實(shí)現(xiàn)。

遵循先入先出的原則

示意圖：

maxSize 是該隊(duì)列的最大容量因?yàn)殛?duì)列的輸出、輸入是分別從前后端來(lái)處理，需要兩個(gè)變量front及rear分別記錄隊(duì)列前后端的下標(biāo)，front 會(huì)隨著數(shù)據(jù)輸出而改變，而rear則是隨著數(shù)據(jù)輸入而改變。

數(shù)組模擬隊(duì)列的思路分析：

當(dāng)將數(shù)據(jù)存入隊(duì)列時(shí)稱(chēng)為”addQueue”，addQueue 的處理需要有兩個(gè)步驟：將尾指針往后移：rear+1 , 當(dāng)front == rear【空】。若尾指針rear 小于隊(duì)列的最大下標(biāo)maxSize-1，則將數(shù)據(jù)存入rear所指的數(shù)組元素中，否則無(wú)法存入數(shù)據(jù)。rear == maxSize - 1【隊(duì)列滿】

程序：

class ArrayQueue{

??? private int maxSize;//隊(duì)列容量

??? private int front;//隊(duì)列頭

??? private int rear;//隊(duì)列尾

??? private int[] arr;//模擬隊(duì)列的數(shù)組

??? public ArrayQueue(int size){

??????? maxSize = size;

??????? arr = new int[maxSize];

??????? front = -1;

??????? rear = -1;

??? }

??? //判斷隊(duì)列是否滿

??? public boolean isFull() {

??????? return rear == maxSize - 1;

??? }

??? //判斷隊(duì)列是否空

??? public boolean isEmpty() {

??????? return rear == front;

??? }

??? //加入隊(duì)列

??? public void addQueue(int n) {

??????? if(!isFull()) {

??????????? rear++;

??????????? arr[rear] = n;

??????? }

??? }

??? //取隊(duì)列

??? public int getQueue() {

??????? if(!isEmpty()) {

??????????? front++;

??????????? return arr[front];

??????? }else {

??????????? throw new RuntimeException("---隊(duì)列為空---");

??????? }

??? }

}

以上隊(duì)列只能一次性使用，改進(jìn)成可循環(huán)使用的環(huán)形隊(duì)列(取模方式)

重點(diǎn)考慮取模的應(yīng)用，比如均衡負(fù)載路由中也會(huì)用到取模進(jìn)行路由

思路如下：

1、front隊(duì)頭指針指向隊(duì)列的第一個(gè)元素下標(biāo)，即數(shù)組[front]就是隊(duì)列的第一個(gè)元素

2、rear隊(duì)尾指針指向隊(duì)列的最后一個(gè)元素下標(biāo)的后一個(gè)位置。

3、隊(duì)列滿時(shí)，(rear + 1) % maxSize = fornt時(shí)【隊(duì)列滿】

4、rear == front時(shí)，【空】

分析如上第3步，假如rear=9，front=0，則(9+1)%10=0，所以當(dāng)(rear + 1)% maxSize = fornt時(shí)，代表隊(duì)列已滿。

5、當(dāng)隊(duì)列中有效數(shù)據(jù)的個(gè)數(shù)(rear + maxSize - front) % maxSize

第5步是一個(gè)小算法，需補(bǔ)充學(xué)習(xí)。

程序：

class CircleArray extends ArrayQueue{

?? public CircleArray(int size) {

????? super(size);

????? super.front = 0;

????? super.rear = 0;

?? }

?? //重寫(xiě)父類(lèi)判斷隊(duì)列是否滿

?? public boolean isFull() {

????? return (super.rear + 1) % super.maxSize == super.front;

?? }

?? //重寫(xiě)父類(lèi)加入隊(duì)列的方法

?? public void addQueue(int n) {

????? if(!this.isFull()) {

????????? super.arr[super.rear] = n;

????????? super.rear = (super.rear + 1) % super.maxSize;//將rear后移,這里必須考慮取模(防止越界)

????? }

?? }

?? //重寫(xiě)父類(lèi)取隊(duì)列

?? public int getQueue() {

????? if(!super.isEmpty()) {

????????? //因?yàn)閒ront是指向隊(duì)列的第一個(gè)元素,所以

????????? // 1. 先把 front 對(duì)應(yīng)的值保留到一個(gè)臨時(shí)變量

????????? // 2. 將 front 后移, 考慮取模(防止越界)

????????? // 3. 將臨時(shí)保存的變量返回

????????? int value = super.arr[super.front];

????????? super.front = (super.front + 1) % super.maxSize;

????????? return value;

????? }else {

????????? throw new RuntimeException("---隊(duì)列為空---");

????? }

?? }

}

二、鏈表

鏈表是有序的列表，以節(jié)點(diǎn)的方式來(lái)存儲(chǔ)，每個(gè)節(jié)點(diǎn)包含data域、next域名(指向下一個(gè)節(jié)點(diǎn))，鏈表的各個(gè)節(jié)點(diǎn)不一定是連續(xù)存儲(chǔ)。

鏈表分帶頭節(jié)點(diǎn)鏈表和沒(méi)有頭節(jié)點(diǎn)的鏈表。鏈表是學(xué)樹(shù)結(jié)構(gòu)的基礎(chǔ)，是有一定的實(shí)戰(zhàn)威力的。單列表結(jié)構(gòu)圖：

鏈表最后一個(gè)節(jié)點(diǎn)的next為null。

程序：

public classSingleLinkedListDmo {

??? public static void main(String[] args) {

??????? Nodenode1= newNode(1,"n1");

??????? Nodenode2= newNode(2,"n2");

??????? Nodenode3= newNode(3,"n3");

??????? SingleLinkedListsingleLinkedist= newSingleLinkedList();

??????? singleLinkedist.add(node1);

??????? singleLinkedist.add(node2);

??????? singleLinkedist.add(node3);

??????? singleLinkedist.show();

??? }

}

//鏈表

class SingleLinkedList{

??? //初始化頭節(jié)點(diǎn)

??? NodeheadNode= newNode(0,"");

??? //添加鏈表

??? public void add(Node newNode) {

??????? Nodetemp= headNode;

??????? while(true) {

??????????? if(temp.next == null) {

??????????????? break;

??????????? }

??????????? temp = temp.next;

??????? }

??????? temp.next = newNode;

??? }

??? //展示鏈表

??? public void show() {

??????? Nodetemp= headNode;

??????? if(temp.next == null) {

??????????? System.out.println("這是一個(gè)空鏈表");

??????????? return;

??????? }

??????? while(true) {

??????????? if(temp == null) {//這里用temp.next會(huì)在末尾引發(fā)空指針異常

??????????????? break;

??????????? }

??????????? System.out.println(temp);

??????????? temp = temp.next;

??????? }

??? }

}

//定義表示單鏈表節(jié)點(diǎn)的pojo

class Node{

??? public int no;

??? public String name;

??? public Node next;

??? public Node(int no,String name) {

??????? this.no = no;

??????? this.name = name;

??? }

??? public String toString() {

??????? return "no:"+this.no+",name:"+this.name;

??? }

}

運(yùn)行結(jié)果：

no:0,name:

no:1,name:n1

no:2,name:n2

no:3,name:n3

實(shí)現(xiàn)按no排序插入的邏輯：

1、找到要添加的節(jié)點(diǎn)位置(位置的前一節(jié)點(diǎn)temp)

2、是插入(不是替換)，所以新節(jié)點(diǎn).next = temp.next

3、temp.next = 新節(jié)點(diǎn)

如圖：

程序：

//帶序號(hào)插入

??? public void addByOrder(Node newNode) {

??????? Nodetemp= headNode;

??????? boolean flag = false;//要添加的編號(hào)是否存在

??????? while(true) {

??????????? if(temp.next == null) {

??????????????? break;

??????????? }

??????????? if(temp.next.no > newNode.no) {

??????????????? break;

??????????? }else if(temp.next.no == newNode.no) {

??????????????? flag = true;

??????????????? break;

??????????? }

??????????? temp = temp.next;

??????? }

??????? if(flag) {

??????????? System.out.println("待插入節(jié)點(diǎn)編號(hào)已經(jīng)存在");

??????? }else {

??????????? newNode.next = temp.next;

??????????? temp.next = newNode;

??????? }

??? }

鏈表反轉(zhuǎn)

思路：

1、定義一個(gè)節(jié)點(diǎn)reversetNode

2、遍歷原來(lái)的鏈表，每取出一個(gè)節(jié)點(diǎn)及相鄰的后節(jié)點(diǎn)，將相鄰的后節(jié)點(diǎn)放到reversetNode鏈表的最前端

3、head.next = reversetNode.next

程序：

public staticvoidreversetList(Node headNode)

{

??????? if(headNode.next == null || headNode.next.next == null) {

??????????? return;

??????? }

??????? NodereversetNode= newNode(0,"");//1

??????? NodecurrentNode= headNode.next;

??????? NodenextNode= null;

??????? while(currentNode != null) {

??????????? nextNode = currentNode.next;//記錄一下即將要變動(dòng)的節(jié)點(diǎn)后的next

??????????? currentNode.next = reversetNode.next;//2當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)指向鏈表最前端(reversetNode.next即為鏈表的最前端)

??????????? reversetNode.next = currentNode;//將當(dāng)前節(jié)點(diǎn)連接到新鏈表上

??????????? currentNode = nextNode;//當(dāng)前節(jié)點(diǎn)后移

??????? }

??????? headNode.next = reversetNode.next;//3

??? }

}

從尾向頭打印鏈表，且不改變鏈表結(jié)構(gòu)：

利用棧的原理(后進(jìn)先出)

public staticvoidreversetPrint(Node headNode)

{

??????? Stackstock= newStack<Node>();

??????? NodecurrentNode= headNode.next;

??????? while(currentNode!=null) {

??????????? stock.push(currentNode);

??????????? currentNode = currentNode.next;

??????? }

??????? while(stock.size()>0) {

??????????? System.out.println("彈棧:"+stock.pop());

??????? }

??? }

雙向鏈表:

單向鏈表的缺點(diǎn)分析:

[if !supportLists]1)???[endif]單向鏈表，查找的方向只能是一個(gè)方向，而雙向鏈表可以向前或者向后查找。

[if !supportLists]2)???[endif]單向鏈表不能自我刪除，需要靠輔助節(jié)點(diǎn) ，而雙向鏈表，則可以自我刪除，所以前面我們單鏈表刪除時(shí)節(jié)點(diǎn)，總是找到temp,temp是待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)(認(rèn)真體會(huì)).

所以雙向鏈表:

遍歷\修改:同單向鏈表

添加：

[if !supportLists](1)? [endif]先找到雙向鏈表的最后一個(gè)節(jié)點(diǎn)

[if !supportLists](2)? [endif]temp.next = newNode

newNode.pre = temp

刪除：

(1)? [endif]因?yàn)槭请p向所以可以自我刪除

(2)? [endif]找到要?jiǎng)h除的節(jié)點(diǎn)，比如temp

(3) temp.pre.next = temp.next

temp.next.pre = temp.pre

代碼略。

單向環(huán)形鏈表及約瑟夫問(wèn)題

顧名思義結(jié)構(gòu)圖如下：

約瑟夫問(wèn)題就是環(huán)形單向鏈表的應(yīng)用：

約瑟夫問(wèn)題為，設(shè)編號(hào)為1，2，… n的n個(gè)人圍坐一圈，約定編號(hào)為k（1<=k<=n）的人從1開(kāi)始報(bào)數(shù)，數(shù)到m 的那個(gè)人出列，它的下一位又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列，依次類(lèi)推，直到所有人出列為止，由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列。

思路：

用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來(lái)處理Josephu 問(wèn)題：先構(gòu)成一個(gè)有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，然后由k結(jié)點(diǎn)起從1開(kāi)始計(jì)數(shù)，計(jì)到m時(shí)，對(duì)應(yīng)結(jié)點(diǎn)從鏈表中刪除，然后再?gòu)谋粍h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從1開(kāi)始計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)從鏈表中刪除算法結(jié)束。

步驟：1、創(chuàng)建和遍歷環(huán)形單向鏈表。2、出圈

1、構(gòu)建和遍歷環(huán)形單向鏈表代碼：

public classJosepfu {

??? public static void main(String[] args) {

??????? JosepfuNodeListjosepfuNodeList= newJosepfuNodeList();

??????? josepfuNodeList.add(5);

??????? josepfuNodeList.show();

??? }

}

class JosepfuNodeList{

??? private JosepfuNode first;

??? public void add(int num) {

??????? JosepfuNodecurrentNode= null;

??????? for(int i=1;i<=num;i++) {

??????????? JosepfuNodenode= newJosepfuNode(i);

??????????? if(i == 1) {

??????????????? first = node;

??????????????? first.setNext(first);

??????????????? currentNode = first;

??????????? }else {

??????????????? currentNode.setNext(node);

??????????????? node.setNext(first);

??????????????? currentNode = node;

??????????? }

??????? }

??? }

??? public void show() {

??????? JosepfuNodecurrentNode= first;

??????? while(true) {

??????????? System.out.println("編號(hào)為:"+currentNode.getNo());

??????????? if(currentNode.getNext() == first) {

??????????????? break;

??????????? }

??????????? currentNode = currentNode.getNext();

??????? }

??? }

}

class JosepfuNode{

??? private int no;

??? private JosepfuNode next;

??? public JosepfuNode(int no) {

??????? this.no = no;

??? }

??? public int getNo() {

??????? return no;

??? }

??? public void setNo(int no) {

??????? this.no = no;

??? }

??? public JosepfuNode getNext() {

??????? return next;

??? }

??? public void setNext(JosepfuNode next) {

??????? this.next = next;

??? }

}

2、出圈：假如有5個(gè)人(n=5)，從第一個(gè)人開(kāi)始報(bào)數(shù)(k=1)，數(shù)兩下(m=2)，(1)創(chuàng)建一個(gè)輔助指針helper并指向鏈表的最后一個(gè)節(jié)點(diǎn).(2)報(bào)數(shù)前先讓first和helper移動(dòng)k-次.(3)當(dāng)報(bào)數(shù)時(shí)讓first和helper同時(shí)移動(dòng)m-1次.(4)將first指向的節(jié)點(diǎn)出圈(first=first.next,helper.next=first時(shí)，原來(lái)的first指向的節(jié)點(diǎn)沒(méi)有任何引用，就會(huì)被回收，即出圈)

/**

?????? ?*根據(jù)用戶(hù)的輸入，計(jì)算出小孩出圈的順序

?????? ?*@param startNo表示從第幾個(gè)小孩開(kāi)始數(shù)數(shù)

?????? ?*@param countNum表示數(shù)幾下

?????? ?*@param nums表示最初有多少小孩在圈中

?????? ?*/

?????? public void countBoy(int startNo, intcountNum, int nums) {

????????????? //先對(duì)數(shù)據(jù)進(jìn)行校驗(yàn)

????????????? if (first == null || startNo <1 || startNo > nums) {

???????????????????? System.out.println("參數(shù)輸入有誤， 請(qǐng)重新輸入");

???????????????????? return;

????????????? }

????????????? //創(chuàng)建要給輔助指針,幫助完成小孩出圈

????????????? Boy helper = first;

????????????? //需求創(chuàng)建一個(gè)輔助指針(變量) helper , 事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn)

????????????? while (true) {

???????????????????? if (helper.getNext() ==first) {//helper指向最后小孩節(jié)點(diǎn)

??????????????????????????? break;

???????????????????? }

???????????????????? helper = helper.getNext();

????????????? }

????????????? //小孩報(bào)數(shù)前，先讓 first 和? helper移動(dòng) k - 1次

????????????? for(int j = 0; j < startNo - 1;j++) {

???????????????????? first = first.getNext();

???????????????????? helper = helper.getNext();

????????????? }

//報(bào)數(shù)時(shí)，讓first和helper指針同時(shí)的移動(dòng)m - 1次, 然后出圈

//這里是一個(gè)循環(huán)操作，知道圈中只有一個(gè)節(jié)點(diǎn)

????????????? while(true) {

???????????????????? if(helper == first) { //說(shuō)明圈中只有一個(gè)節(jié)點(diǎn)

??????????????????????????? break;

???????????????????? }

???????????????????? //讓 first 和 helper 指針同時(shí) 的移動(dòng)countNum - 1

???????????????????? for(int j = 0; j

??????????????????????????? first =first.getNext();

?????? ???????????????????? helper= helper.getNext();

???????????????????? }

???????????????????? //這時(shí)first指向的節(jié)點(diǎn)，就是要出圈的小孩節(jié)點(diǎn)

???????????????????? System.out.printf("小孩%d出圈\n", first.getNo());

???????????????????? //這時(shí)將first指向的小孩節(jié)點(diǎn)出圈

???????????????????? first = first.getNext();

???????????????????? helper.setNext(first);

????????????? }

????????????? System.out.printf("最后留在圈中編號(hào)%d \n", first.getNo());

?????? }

}

三、棧

待續(xù)……

? ? ? ? ? ? ? ? ?

? ??????????????II?非線性結(jié)構(gòu)

待續(xù)……