日期: 2020 年 8 月 20 日

package com.datacrafts.digitalevers.link

/**
 * 经典的约瑟夫环问题
 * 本质就是一个单向循环链表的实现
 * @param n 链表中初始节点个数
 */
class Josephus(n:Int) {
    var length = 0
    var head:node = null
    var curr:node = null
    var prev:node = null
    for(index <- 1 to n){
      if(length == 0){
        curr  = new node(index)
        prev = curr
        head = curr
        curr.next = curr
      } else {
        val temp  = new node(index)
        temp.next = head
        curr.next = temp
        prev = curr
        curr = temp
      }
      length += 1
    }
    //初始化完成后复位
    curr = head
    prev = head

  /**
   * 移动到第k个人
   * 1 <= k <= length
   */
  def moveToK(k:Int): Unit ={
      for(index <- 1 until k){
          prev = curr
          curr = curr.next
      }
  }

  /**
   * 开始丢手绢过程
   * 丢到第 m 个人则退出
   * 若curr 与 prev相等 说明循环链表中只剩一个节点 则结束循环
   */
  def circle(m:Int): Unit ={
    while(curr != prev){
      for(index <- 1 until m){
        prev = curr
        curr = curr.next
      }
      //循环结束 删除当前节点
      println(curr.id)
      prev.next = curr.next
      curr = curr.next
      length -= 1
    }
    println(curr.id)
  }

  /**
   * 展示约瑟夫环上所有节点数据
   */
  def show(): Unit = {
    var curr = head
    for(index <- 1 to length){
      println(curr.id)
      curr = curr.next
    }
  }
}

/**
 * 节点类型
 * @param _id
 */
class node(_id:Int){
  var id:Int = _id
  var next:node = null
}

object Josephus{
  def main(args: Array[String]): Unit = {
    var josephus = new Josephus(7)
    //josephus.show()
    josephus.moveToK(4)
    //println(josephus.curr.id)
    //println(josephus.prev.id)
    josephus.circle(3)
    //println(josephus.length)
  }
}

package com.datacrafts.digitalevers.generic

import util.control.Breaks._
import scala.reflect.runtime.universe._


class twoWay[T,U](in:T,v:U) {
  private var size = 0
  var head:node[T,U] = new node[T,U](in,v)

  //比较器
  val cc = new commonCompare

  /**
   * 链表尾部添加节点
   * @param newNode
   */
  def addNode(newNode:node[T,U]): Unit = {
    var temp = head
    while(temp.next != null){
      temp = temp.next
    }
    temp.next = newNode
    newNode.prev = temp
    size += 1
  }

  /**
   * 按顺序插入节点
   */
  def addNodeOrder(newNode:node[T,U])(implicit t:TypeTag[T]): Unit = {
    var curr = head
    var prev = head

    t.tpe match {
      case tpe if tpe == typeOf[Int]=>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Int], newNode.id.asInstanceOf[Int]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
      case tpe if tpe == typeOf[Double] =>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Double], newNode.id.asInstanceOf[Double]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
    }
    /////match

    if(curr == null){
      //没有找到该节点则在链表尾部插入新节点
      prev.next = newNode
      newNode.prev = prev
    } else {
      //没有则在该节点前置插入新节点
      newNode.next = curr
      prev.next = newNode

      curr.prev = newNode
      newNode.prev = prev
    }
    size += 1
  }

  /**
   * 更新节点数据域
   */
  def updateNode(id:T,data:U){
    var curr = head
    while (curr != null && curr.id != id) {
      curr = curr.next
    }
    if(curr != null){
      curr.data = data
    }
  }

  /**
   * 删除节点（自我删除）
   */
  def delete(id:T): Unit = {
    /*var curr = head
    var prev = head
    while (curr != null && curr.id != id){
      prev = curr
      curr = curr.next
    }
    if(curr != null){
      prev.next = curr.next
      curr.next.prev = prev
      curr.next = null
      curr.prev = null
    }*/
    var curr = head
    while (curr != null && curr.id != id){
      curr = curr.next
    }
    if(curr != null){
      curr.prev.next = curr.next
      if(curr.next != null) {
        curr.next.prev = curr.prev
      }
      //清除待删除节点自身与其他节点的关系
      curr.next = null
      curr.prev = null
    }
  }

  /**
   * 展示链表的所有数据
   */
  def show(): Unit ={
    var temp = head
    while(temp.next != null){
      temp = temp.next
      println(temp)
    }
  }

  def length = {
    size
  }
}

class node[T,U](in:T,v:U){
  var id:T = in
  var data:U = v
  var prev:node[T,U] = null
  var next:node[T,U] = null

  override def toString: String = {
    id + " "+data.toString
  }
}

/**
 * 泛型的通用比较类
 */
class commonCompare{
  def greater[T<% Comparable[T]](t1:T,t2:T) =
    if(t1.compareTo(t2) > 0) true else false
}



object testTwoWay{
  def main(args: Array[String]): Unit = {
    val linkTest = new twoWay(0,"")
    val newNode = new node(13,"hello")
    linkTest.addNodeOrder(newNode)
    val newNode2 = new node(15,"scala")
    linkTest.addNodeOrder(newNode2)
    val newNode3 = new node(20,"java")
    linkTest.addNodeOrder(newNode3)
    //linkTest.updateNode(13,"php")
    linkTest.delete(15)
    linkTest.delete(13)

    linkTest.addNodeOrder(newNode2)
    linkTest.show()
    //print(linkTest.length)
  }
}