数据结构

丢丢手绢-Scala实现单向循环链表（约瑟夫环）

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)
  }
}

Leave a comment

20 8 月, 2020

by : digitalevers scala, 教程&知识, 数据结构

老鹰变小鸡-Scala实现双向链表（泛型）

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)
  }
}

Leave a comment

20 8 月, 2020

by : digitalevers scala, 教程&知识, 数据结构

老鹰抓小鸡-Scala实现单向链表（泛型）

package com.datacrafts.digitalevers.generic

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


/**
 * 比较粗略实现了泛型版本的单向链表的增删改查操作，代码在scala 2.12.10上编译通过，测试运行通过。有几个点需要注意
 * 1.上下边界 <: >:都没有隐式转换 只有视图边界 % 才有隐式转换
 * 2.在按顺序往链表添加节点时 应将比较器的实例化对象提取到 链表类的属性层 而不应放在方法中  此举是为了解决内存使用
 * 3.编译过程中，实例化比较器需要得知泛型参数的具体类型，之前在这个地方纠结了很久，最终无法通过隐式转换实行自动比较，故只能显式将其转换为Int 或者 Double类型
 * 4.但是由于 scala 在运行过程中会擦除泛型类型，故使用了一个小技巧——加入一个隐式参数TypeTag[T]来保存运行时泛型类型，然后通过模式匹配来决定改转换成哪种对象（Int或者Double)，然后会自动通过隐式转换为 Comparable 子类来进行比较操作
 * 5.感觉还有更好的实现方式，以便可以支持更多的数据类型
 * @param in
 * @tparam T
 */
class genericClass[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
    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
    } else {
      //没有则在该节点前置插入新节点
      newNode.next = curr
      prev.next = newNode
    }
    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
    }
  }

  /**
   * 展示链表的所有数据
   */
  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 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 test{
  def main(args: Array[String]): Unit = {
    val linkTest = new genericClass(0,"")
    val newNode = new node(13,"hello")
    linkTest.addNodeOrder(newNode)
    val newNode2 = new node(15,"scala")
    linkTest.addNodeOrder(newNode2)
    linkTest.updateNode(13,"php")
    //linkTest.delete(15)
    linkTest.show()
    //print(linkTest.length)
  }
}

Leave a comment

19 8 月, 2020

by : digitalevers scala, 实验测试, 数据结构

食堂开饭-Scala实现单向队列（不能重复利用空间，废弃）

package com.datacrafts.digitalevers.queue


object oneWayQueueDemo{
  def main(args: Array[String]): Unit = {

  }
}

/**
 *
 */
class oneWayQueue(maxSize:Int) {
  var front = -1
  var tail = -1

  val length = maxSize
  if(maxSize <= 0){
    throw new Exception("参数错误")
  }
  var oneWayQueue = Array[Int](maxSize)

  /**
   * 队列是否为空
   */
  def isEmpty(): Boolean = {
    if(front == tail) true else false
  }

  /**
   * 队列是否满员
   */
  def isFull():Boolean = {
    if(tail >= length - 1) true else false
  }

  /**
   * 队列弹出数据
   */
  def getData() = {
    if(isEmpty()){
      throw new Exception("队列为空")
    }
    front += 1
    oneWayQueue(front)
  }

  /**
   * 队列添加数据
   * TODO 亦可以直接返回 Exception 类型使其参与逻辑运算
   */
  def addData(inData:Int) = {
    if(isFull()){
      //throw new Exception("队列已满")
      false
    } else {
      tail += 1
      oneWayQueue(tail) = inData
      true
    }
  }
  ////////
}

Leave a comment

18 8 月, 2020

丢丢手绢-Scala实现单向循环链表（约瑟夫环）

老鹰变小鸡-Scala实现双向链表（泛型）

老鹰抓小鸡-Scala实现单向链表（泛型）

食堂开饭-Scala实现单向队列（不能重复利用空间，废弃）

近期文章

近期评论

归档

分类

其他操作