2019-08-08 15:01:38 qq_42453117 阅读数 3106
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4965 人正在学习 去看看 佟刚

本篇文章介绍数据结构中的环形链表。

介绍

环形链表,类似于单链表,也是一种链式存储结构,环形链表由单链表演化过来。单链表的最后一个结点的链域指向NULL,而环形链表的建立,不要专门的头结点,让最后一个结点的链域指向链表结点。 简单点说链表首位相连,组成环状数据结构。如下图结构:
在这里插入图片描述
而在环形链表中,最为著名的即是约瑟夫环问题。

约瑟夫环问题

问题介绍:
设编号为1、2、3、… 、n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列。依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
我们可以举个例子来分析一下:
假设一共有5个人,即n = 5;从第一个人开始报数,即k = 1;数到2的人出列,即m = 2。
示意图如下:
在这里插入图片描述
出队列的顺序即为:2 -> 4 -> 1 -> 5 -> 3

那么我们首先得构建出一个单向的环形链表。
在这里插入图片描述
实现分析:

  1. 先创建第一个节点,让first指向该节点,并形成环状
  2. 每创建一个新的节点就将该节点加入到已有的环形链表中

分析完毕,我们用代码实现一下:

//创建一个环形的单向链表
class CircleSingleLinkedList {
	// 创建一个first节点,当前没有编号
	private Boy first = null;

	// 添加节点,构建成一个环形链表
	public void addBoy(int nums) {
		// 对nums做一个校验
		if (nums < 1) {
			System.out.println("数据错误");
			return;
		}

		// 定义辅助节点
		Boy curBoy = null;

		// 使用循环创建环形链表
		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;// curBoy后移
			}
		}
	}

	// 遍历当前环形链表
	public void list() {
		// 判断链表是否空
		if (first == null) {
			System.out.println("链表为空");
			return;
		}
		// 定义辅助节点
		Boy curBoy = first;
		while (true) {
			System.out.println("节点编号:" + curBoy.getNo());
			if (curBoy.getNext() == first) {
				// 此时说明遍历完毕
				break;
			}
			curBoy = curBoy.getNext();// curBoy后移
		}
	}
}

//创建一个Boy类,表示一个节点
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;
	}
}

这样就实现了一个环形链表,接下来测试一下:

public static void main(String[] args) {
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);
		circleSingleLinkedList.list();
}

运行结果:

节点编号:1
节点编号:2
节点编号:3
节点编号:4
节点编号:5

运行结果也是没有问题的,接下来便是生成出圈序列。
问题分析:

  1. 先创建一个辅助节点helper,事先应该指向环形链表的最后一个节点
  2. 报数前,先让first和helper移动k - 1次
  3. 开始报数时,让first和helper节点同时移动,移动m - 1次
  4. 此时可以将first指向的节点出圈
  5. 如何出圈呢?
    使first = first.next,即:将first节点往前移动一下
    使helper.next = 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;
		// helper事先应该指向环形链表的最后一个节点
		while (true) {
			if (helper.getNext() == first) {
				break;
			}
			helper = helper.getNext();// helper后移
		}
		// 报数前,先让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.println("节点" + first.getNo() + "出圈");
			// 将该节点出圈
			first = first.getNext();
			helper.setNext(first);
		}
		System.out.println("最后留在圈中的节点编号:" + first.getNo());
	}

这个实现的逻辑相对来说还是比较复杂和难以理解的,接下来编写测试代码:

	public static void main(String[] args) {
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);
		circleSingleLinkedList.list();

		System.out.println("--------------");

		// 测试出圈序列
		circleSingleLinkedList.countBoy(1, 2, 5);
	}

运行结果:

节点编号:1
节点编号:2
节点编号:3
节点编号:4
节点编号:5
--------------
节点2出圈
节点4出圈
节点1出圈
节点5出圈
最后留在圈中的节点编号:3

和开始计算的结果相吻合。
到此,关于约瑟夫环的问题就成功解决了。

推荐阅读

1.图解Java数据结构之稀疏数组

2.图解Java数据结构之队列

3.图解Java数据结构之单链表

4.图解Java数据结构之双向链表

2019-08-14 10:52:48 money_yao 阅读数 82
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4965 人正在学习 去看看 佟刚

1.背景描述:

  • Josephu问题:设编号为1,2,3,...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,以此类推,直到所有人都出列为止,由此产生一个出队编号的序列。
  • 用一个不带头节点的循环链表来处理Josphu问题:先构成一个有n个节点的单循环链表,然后由k节点从1开始计数,计到m时,对应节点从链表中删除,然后再从被删除的节点的下一个节点又从1开始计数,直到最有一个节点从链表中删除,算法结束。
  • 构建一个单向的环形链表,先创建第一个节点,让first指向该节点,并形成环形;后面当每创建一个新的节点,就把该节点加入已有的环形链表中;
  • 遍历环形链表,让辅助指针curNode指向first节点,然后通过while循环遍历该链表,直到curNode.next==first结束;
  • 节点出圈,创建一个辅助指针helper,事先指向环形链表的最后一个节点,
  • 开始报数前,先让first和helper先移动k-1次,到达开始报数的位置;
  • 当报数时,让first和helper指针同时移动m-1次;
  • 将first指向的节点出圈,first=first.next;helper.next=first;原来first指向的节点没有任何引用,会被回收。

2.代码实现:

package linkedlist;

public class Josephu {

	public static void main(String[] args) {
		//测试环形链表构建和遍历
		CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(125);
		circleSingleLinkedList.showNode();
		//测试出圈
		circleSingleLinkedList.countNode(10, 20, 125);
	}
}
//创建环形单向链表
class CircleSingleLinkedList{
	//创建first节点,当前不初始化
	private Boy first=null;
	//添加节点,构建成环形的链表
	public void addBoy(int nums) {
		if(nums<1) {
			System.out.println("nums的值不正确,至少大于1");
			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 showNode() {
		if(first==null) {
			System.out.println("链表为空");
			return;
		}
		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 countNode(int startNo,int countNum,int nums) {
		if(first==null || startNo<1 || startNo>nums) {
			System.out.println("参数输入有误,重新输入");
			return;
		}
		//创建辅助指针,帮助完成node出圈,helper指针需要指向最后的节点
		Boy helper=first;
		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();
		}
		//报数时,让helper和first指针同时移动countNum次,然后出圈;循环直到圈中只有一个节点
		while(true) {
			if(helper==first) {//说明圈中只有一个节点
				break;
			}
			for(int j=0;j<countNum-1;j++) {
				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());
	}
}
//定义节点
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;
	}
	@Override
	public String toString() {
		return "Boy [no=" + no + ", next=" + next + "]";
	}	
}

 

2019-07-18 21:10:15 weixin_45303050 阅读数 44
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4965 人正在学习 去看看 佟刚
//循环链表有头节点,头节点为空,尾部指向头节点 
#define Elemtype int 
#include<iostream>
#include<malloc.h>
using namespace std;

typedef struct Node
{
	Elemtype data;
	struct Node* next;
}Node,*Circlelist;
Circlelist InitCirclelist()//创建循环链表 
{
Circlelist L, p,q;
 	L=(Circlelist)malloc(sizeof(Node));
 p=L;
 int n;
 cout<<"请输入循环链表结点数目:"; 
 cin>>n;
 int num; 
 for(int i=1;i<=n;i++)
 {
 	
 	cout<<"请输入结点:";
	 cin>>num; 
 	q=(Circlelist)malloc(sizeof(Node));
 	q->data=num;
 	p->next=q;
 	p=q;
 	
 }
 p->next=L;
 cout<<"输入完毕"<<endl; 
 return L;
}
void Printlist(Circlelist L)//打印循环链表 
{
	Circlelist p,q;

		p=L;
		int i=1;
		while(p->next!=L)
		{
			p=p->next;
		cout<<"第"<<i<<"个结点数据为"<<p->data<<endl;
		
		i++;	
		}
	
	cout<<"打印完毕"<<endl; 
}
int  Lengthlist(Circlelist L)//计算循环链表节点数,加入到killNode中作为比较条件 
{
	Circlelist p,q;

		p=L;
		int i=0;
		while(p->next!=L)
		{
			p=p->next;
		
		
		i++;	
		}
//		cout<<"长度为:"<<i<<endl; 
        return i;
}
int  CountLengthlist(Circlelist L)//计算循环链表节点数并输出长度 
{
	Circlelist p,q;

		p=L;
		int i=0;
		while(p->next!=L)
		{
			p=p->next;
		
		
		i++;	
		}
		cout<<"链表长度为:"<<i<<endl; 
        return i;
}
void KillNode(Circlelist L)//约瑟夫环的部分 
{
	Circlelist p,q;
	p=L;
	int lengthlist=Lengthlist(L);
   for(int i=1;i<=lengthlist-1;i++)//这里一开始把Lengthlist(L)当作与i的比较条件,殊不知在每一轮for循环中,L的长度是不断减小的,呜呜呜呜!!以后涉及到比较的条件,都用常量来表示!!! 
    {
    	cout<<"第"<<i<<"轮开始"<<endl; 
    	CountLengthlist(L);
    	cout<<"****************************"<<endl; 
       for(int j=1;j<3;j++)
       {
    
       	if(p->next==L)
       	{
       	  p=p->next->next;
		cout<<p->data<<endl; 
//		   
	}
	else{
//		cout<<p->next->data<<"我是L"<<endl; 
	       p=p->next;
		   cout<<p->data<<endl; 
//		   if(p->next==L)
//       	{
//       	  p=p->next->next;
//		cout<<p->data<<"ccccccc"<<endl; 
//		   
//	}
	}
	   }
	  if(p->next!=L )
	   {
	   cout<<p->next->data<<"死亡结点"<<endl;
	   q=p->next;
	   p->next=p->next->next;
	   free(q);
//	   cout<<q->data;
}
else{
	p=p->next;
	cout<<p->next->data<<"死亡结点"<<endl;
	   q=p->next;
	   
	   p->next=p->next->next;
	 
	   free(q);
}
	}
	if(p!=L) //判断最后的存活结点时需要注意结点必须是有效的 
	{
	cout<<"存活结点:"<<p->data<<endl;
}
else{
	cout<<"存活结点"<<p->next->data; 
}
	
	
}
int main()
{
	Circlelist S;
   S=InitCirclelist();
	Printlist(S); 
//	Lengthlist(S); 
	KillNode(S);
}

 

2019-12-15 12:54:24 qq_38620956 阅读数 63
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4965 人正在学习 去看看 佟刚

约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.)

N个人围成一圈,从第X个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。

 例如N=5,X=1,  M=2,被杀掉的顺序是:2 , 4 , 1 , 5 , 3

Java环形链表实现

   1.模拟链表的 单个节点的数据结构

class Boy {

    private int number;       小孩编号
    private Boy next;        小孩下一位 

    public Boy(int number) {
        this.number = number;}

    public Boy getNext() {
        return next;}

    public void setNext(Boy next) {
        this.next = next;        }
}

 2. 添加小孩并形成环

    1 .定一个辅助 cur 指针   始终指向最新添加进来的小孩          2.当第一个小孩时,自己指向自己         

    3.当不是第一个时,  将 cur 的下一位指向新添加进来的 ,将新添加进来的 指向第一个形成环  ,   将cur后移指向自己

  public void add(int num) {
        if (num < 1) {
            System.out.println("数量太小!");
            return;
        }

        Boy cur = null;     //定一个辅助指针变量

        for (int i = 1; i <= num; i++) {
            if (i == 1) {
                first = new Boy(1);          //如果是第一个 就定义第一个小孩
                first.setNext(first);         //将自己指向自己
                cur = first;                  //将当前指向first , 后面继续使用
            } else {
                Boy boy = new Boy(i);      //不是第一个,根据编号创建
                cur.setNext(boy);          //将当前指针的下一位指向,新来的
                boy.setNext(first);         //将新来的指向第一个,形成环
                cur = boy;                   //将当前指向新来的 , 后面继续使用
}}}

3.实现约瑟夫问题

    1. 因为是单向的环形链表,所以定一个辅助指针 helper 始终指向  cur 后面的一位

    2.先让  helper cur 同时移动   startNumber-1个      因为数数自己也算一个

    3.开始剔除时,结束条件 :  cur== helper         

    4.数数时    helper cur同时移动 countNumber - 1 个 后         cur就是需要出圈的小孩

            cur=cur.getNext();          让cur后移一位, 即下一位开始报数的人
            helper.setNext(cur);        让helper指向 出圈的小孩的下一个, 即下一位开始报数的人,就是让当前first小孩出圈

 

    5.first为第一个加入的小孩  

       1.第一循环将helper 放在first 后面去             2.for循环将first, helper  同时移动 startnumber-1个,即从第几个开始数

       3.开始数数,  如果first==helper 说明到了最后一个结束循环  将first, helper  同时移动 countnumber-1个 ,first指向的为出圈的

       4.将first后移,将helper 指向新的first,即将旧的first出圈

    public void ShowJosephProblem(int startNumber, int countNumber, int BoyNumbers) {
        this.add(BoyNumbers);
        if (startNumber < 1 || startNumber > BoyNumbers) {
            System.out.println("参数非法");
            return;
        }

        Boy helper = first;    //先让helper指向first  再循环使他指向最后一个

        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }

        //让first 指向 第一个开始数数的小孩
        for (int i = 0; i < startNumber - 1; i++) {   //因为自己数算一个,所以是移动 countNumber-1个
            helper = helper.getNext();
            first = first.getNext();
        }

        //开始数数,
        while (true){

            if (first ==helper){   //因为 helper 跟在后面  当最后一个小孩时他们相等
                break;
            }

            //让first,helper同时移动countNumber- 1个后  ,现在first 指向需要出圈的小孩,helper指向它的前一个
            for (int i = 0; i < countNumber - 1; i++) {
                first = first.getNext();
                helper=helper.getNext();
            }

            System.out.printf("当前出圈小孩编号: %d \n", first.getNumber());

            first = first.getNext();   //让first后移一位, 即下一位开始报数的人
            helper.setNext(first);  //让helper指向 出圈的小孩的下一个, 即下一位开始报数的人,就是让当前first小孩出圈
        }
        System.out.printf("最后小孩编号: %d", first.getNumber());        }}

 

2017-04-04 15:22:17 u011376293 阅读数 410
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    4965 人正在学习 去看看 佟刚

在很多编程语言中,数组的长度是固定的;在数组中添加和删除元素很麻烦。而Javascript数组并不存在上述问题,因为Javascript中,数组被实现为对象,而且拥有自己的一系列方法,例如push(),shift(),splice()。然而,Javascript中,数组的主要问题也是被实现成对象导致的效率低下。

链表是由一组节点组成,每个节点除了包括一个数据,还包括使用一个对象的引用指向它的后继。指向另一个节点的引用叫做。链表最前面有一个特殊的节点,叫做头节点。链表最后的节点指向一个null节点。遍历链表,就是跟着链,从链表的首元素走到尾元素。

  • 链表的JS实现
  • 解决实际问题

链表的JS实现

链表包含两个类。Node类用来表示节点。LList类提供了插入节点,删除节点,查找节点,显示链表元素等辅助方法。

//llist.js
//Node对象定义
function Node(element){
    this.element = element;
    this.next = null;
}
//LList对象定义
function LList(){
    this.head = new Node("head");
    this.find = find;
    this.insert = insert;
    this.remove = remove;
    this.findPrevious = findPrevious;
    this.display = display;
}

function find(item){
    var currNode = this.head;
    while(currNode.element != item)
    {
        currNode = currNode.next;
    }
    return currNode;
}

function insert(element, item){
    var newNode = new Node(element);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

function findPrevious(item){
    var current = this.head;
    while(current.next.element != item && current.next != null)
    {
        current = current.next;
    }
    return current;
}

function remove(item){
    var prevNode = this.findPrevious(item);
    if(prevNode.next != null)
        prevNode.next = prevNode.next.next;
}

function display(){
    var str = "";
    var current = this.head;
    while(current.next != null)
    {
        str += current.next.element + "\n";
        current = current.next;
    }
    return str;
}
//实例化一个链表
var oneLList = new LList();

链表的实际应用

问题描述:传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围。犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案。他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人。约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存。请问哪两个位置?

(一)网页展示

这里写图片描述

(二)html代码

<!DOCTYPE html>
<html>
<head>
    <title>Linked List</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <script src="circlelinklist.js" type="text/javascript"></script>
</head>
<style>
div {
    width: 60%;
    margin: 30px auto;
    padding: 10px;
    border: 1px solid #333;
}
</style>
<body>
    <div>
        <h2>约瑟夫环</h2>
        <input type="button" value="新建数组:" onclick="waitKilled()" />
        <textarea id="waiting_people"></textarea>
        <input type="button" value="杀人顺序:" onclick="getKilled()" />
        <textarea id="dying_people"></textarea>
    </div>
</body>
</html>

(三)Javascript方法

循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点指向本身:head.next = head。这样便形成了循环链表。

//circleList.js
//直接构建1-41编号的循环链表,无需定义插入和删除操作。
function Node(element){
    this.element = element;
    this.next = null;
}

function LList(num){
    var head = new Node(1);
    var p = head;
    for(var i=2; i<=num; i++)
    {
        var temp = new Node(i);
        p.next = temp;
        p = temp;
    }
    p.next = head;
    return head;
}

var cirLinkList = new LList(41);

function getKilled(){
    var current = cirLinkList;
    var str = "";
    while(current.next.element != current.element)
    {
        for(var i=1; i<3; i++)
        {
            var temp = current;
            current = current.next;     
        }
        //删除节点的本质即改变其前一个元素的后继
        temp.next = current.next;
        str += current.element + " ";
        current = temp.next;
    }
    str += current.element;
    //将杀人顺序显示在网页上
    var dresult = document.getElementById("dying_people");
    dresult.innerHTML = str;
}
没有更多推荐了,返回首页