`
hideto
  • 浏览: 2683157 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

每天一条Ruby小道之高级数据结构

    博客分类:
  • Ruby
阅读更多
Set

初始化
require 'set'
s1 = Set[3,4,5]
arr = [3,4,5]
s2 = Set.new(arr)
s3 = Set.new(arr) {|x| x.to_s}

简单操作
x = Set[1,2,3]
y = Set[3,4,5]

a = x.union(y)   # Set[1,2,3,4,5]
b = x | y        # Set[1,2,3,4,5]
c = x + y        # Set[1,2,3,4,5]

d = x.intersection(y)   # Set[3]
e = x & y               # Set[3]

diff = x - y     # Set[1,2]

x.include?(2)    # true
x.include?(4)    # false
x.member?(2)     # true
x.member?(4)     # false

x.empty?         # false
x.clear
x.empty?         # true

x = Set[3,4,5]
y = Set[3,4]

x.subset?(y)         # false
y.subset?(x)         # true
y.proper_subset?(x)  # true
x.subset?(x)         # true
x.proper_subset?(x)  # false
x.superset?(y)       # true
x << 6               # Set: {3,4,5,6}
Set[3,4,5] == Set[5,4,3]  # true

高级操作
s = Set[1,2,3,4,5]
s.each {|x| puts x; break}  # Output: 5

files = Set.new(Dir["*"])
hash = files.classify do |f|
  if File.size(f) <= 10_000
    :small
  elsif File.size(f) <= 10_000_000
    :medium
  else
    :large
  end
end

small_files = hash[:small]
medium_files = hash[:medium]
large_files = hash[:large]

numbers = Set[1,2,3,4,5,6,7,8,9,0]
set = numbers.divide{|i| i % 2}
p set #<Set: {#<Set: {5, 1, 7, 3, 9}>,  #<Set: {0, 6, 2, 8, 4}>}>

Stack&Queue

Ruby没有实现Stack(LIFO)和Queue(FIFO)
Stack实现
class Stack

  def initialize
    @store = []
  end

  def push(x)
    @store.push x
  end

  def pop
    @store.pop
  end

  def peek
    @store.last
  end

  def empty?
    @store.empty?
  end

end

Queue实现
class Queue

  def initialize
    @store = []
  end

  def enqueue(x)
    @store << x
  end

  def dequeue
    @store.shift
  end

  def peek
    @store.first
  end

  def length
    @store.length
  end

  def empty?
    @store.empty?
  end

end

Tree

宽度优先插入和遍历的二插树实现
class Tree

  attr_accessor :left
  attr_accessor :right
  attr_accessor :data

  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end

  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end

  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
end

可搜索的二叉树实现
class Tree

  attr_accessor :left
  attr_accessor :right
  attr_accessor :data

  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end

  def insert(x)
    if @data == nil
      @data = x
    elsif x <= @data
      if left == nil
        @left = Tree.new x
      else
        @left.insert x
      end
    else
      if @right == nil
        @right = Tree.new x
      else
        @right.insert x
      end
    end
  end

  def inorder()
    @left.inorder {|y| yield y} if @left != nil
    yield @data
    @right.preorder {|y| yield y} if @right != nil
  end

  def preorder()
    yield @data
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
  end

  def postorder()
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
    yield @data
  end

end

Graph

class LowerMatrix < TriMatrix

  def initialize
    @store = ZArray.new
  end

end

class Graph

  def initialize(*edges)
    @store = LowerMatirx.new
    @max = 0
    for e in edges
      e[0], e[1] = e[1], e[0] if e[1] > e[0]
      @store[e[0], e[1]] = 1
      @max = [@max, e[0], e[1]].max
    end
  end

  def [](x,y)
    if x > y
      @store[x,y]
    elsif x < y
      @store[y,x]
    else
      0
    end
  end

  def []=(x,y,v)
    if x > y
      @store[x,y] = v
    elsif x < y
      @store[y,x] = v
    else
      0
    end
  end

  def edge? x,y
    x,y = y,x if x < y
    @store[x,y] == 1
  end

  def add x,y
    @store[x,y] = 1
  end

  def remove x,y
    x,y = y,x if x < y
    @store[x,y] = 0
    if (degree @max) == 0
      @max -= 1
    end
  end

  def vmax
    @max
  end

  def degree x
    sum = 0
    0.upto @max do |i|
      sum += self[x,i]
    end
    sum
  end

  def each_vertex
    (0..@max).each {|v| yield v}
  end

  def each_edge
    for v0 in 0..@max
      for v1 in 0..v0-1
        yield v0,v1 if self[v0,v1] == 1
      end
    end
  end

end

另外RAA和Rubyforge上有RubyGraph,RGraph和GraphR等Ruby的Graph Tools
分享到:
评论
3 楼 jim.jin 2008-08-08  
请问怎么安装 TriMatrix 库,或哪里可以下载?
2 楼 hideto 2008-01-24  
确实实现了Queue,可能我看的书old了
1 楼 linkerlin 2008-01-24  
thread库不是有一个线程安全的Queue吗?

相关推荐

    Ruby数据结构简介 word文档

    Ruby数据结构简介 word文档

    algorithms, ruby 算法和数据结构 C 扩展.zip

    algorithms, ruby 算法和数据结构 C 扩展 算法 API文档描述:开始作为一个 Google的代码 2008项目由 。com 。Li编写,由奥斯汀 Ziegler原始建议:对场景使用正确的数据结构或者算法是编程的一个重要方面。 在计算机...

    探索Ruby中的元组:数据结构的奥秘

    而在 Ruby 这种灵活而强大的语言中,元组(Tuple)是一种经常被忽视但极其有用的数据结构。本文将深入探讨 Ruby 中的元组,解释其概念、用途,并展示如何通过代码实现和使用它。 #### 什么是元组? 在计算机科学中...

    Ruby算法和数据结构。C扩展_Ruby_C_下载.zip

    在这个压缩包中,"algorithms-master"可能是一个包含Ruby实现的算法和数据结构的代码库。它可能包括以下内容: 1. **排序算法**:如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,这些都是处理大量...

    Ruby-chewy高级ElasticsearchRuby框架

    Ruby-chewy是一个高级的Elasticsearch Ruby框架,它构建在官方的elasticsearch-ruby客户端之上,为开发者提供了更简洁、强大的接口来操作Elasticsearch。这篇文章将深入探讨chewy框架的核心特性、如何安装与配置,...

    流行数据结构和算法的实现_Erlang_Ruby_下载.zip

    《流行数据结构与算法的实现:Erlang与Ruby篇》 在计算机科学中,数据结构和算法是核心部分,它们决定了程序的效率和可扩展性。本资源包聚焦于两种编程语言——Erlang和Ruby,分别探讨如何实现常见且重要的数据结构...

    Ruby基础语法+Ruby变量与数据类型+Ruby控制结构+Ruby函数与方法+Ruby面向对象编程等全套教程

    Ruby变量与数据类型 Ruby控制结构 Ruby函数与方法 Ruby面向对象编程 Ruby模块与包 Ruby错误处理 Ruby文件与I/O操作 Ruby正则表达式 Ruby网络编程 Ruby数据库交互 Ruby测试框架 RubyWeb框架Rails入门 Ruby高级特性 ...

    Ruby-RGL在Ruby中图形数据结构和算法的框架

    Ruby-RGL是一个强大的开源库,专门用于在Ruby编程语言中实现图形数据结构和算法。这个框架为Ruby开发者提供了一系列工具,使他们能够处理复杂的图论问题,进行网络分析,以及进行科学计算和分析。RGL全称为“Ruby ...

    R和Ruby数据分析之旅

    R和Ruby数据分析之旅 数据分析 数据挖掘

    Ruby-SycamoreRuby的无序树的数据结构

    Ruby-Sycamore是一种在Ruby编程语言中实现的无序树数据结构。Sycamore树是一种灵活且高效的工具,适用于处理需要树形结构的数据。它不仅提供了基本的树操作,如插入、删除和查找,还支持一些高级功能,如迭代、深度...

    Ruby编程语言中基础和高级控制结构详解

    内容概要:本文详细介绍了Ruby编程语言中的基础和高级控制结构,包括条件语句(if、unless)、循环语句(while、until、for)、迭代器(each、map、select),以及模式匹配(case)、跳转控制(next、retry、break、...

    Ruby Data-Processing ruby数据处理

    Ruby是一种强大的动态编程语言,尤其在数据处理方面表现出色。Map、Reduce和Select是Ruby中用于操作和处理数据的关键概念,它们在数据科学、分析和软件工程领域中扮演着重要角色。 1. **Ruby Map**: Map函数允许...

    Ruby-HappyMapper允许您快速轻松地解析XML数据并将其转换成ruby的数据结构

    Ruby-HappyMapper是一个强大的库,专门用于处理XML数据,它为开发者提供了一种简洁、高效的途径,将XML文档转换为Ruby对象。这个库的核心理念是让解析和操作XML变得如同处理Ruby中的普通数据结构一样简单。在Ruby...

    Ruby-RubyGraphVizGraphViz绘图工具的Ruby接口

    对于复杂的数据结构,例如树或图,RubyGraphViz提供了一种直观的方式来表示它们。 在处理大量数据时,RubyGraphViz可以与数据库、CSV文件或其他数据源结合,动态生成图形。例如,你可以从数据库查询中获取数据,...

    Ruby-一个Ruby的例子

    在压缩包`RubyDemo_First-master`中,我们可以假设这是一个简单的Ruby项目,可能包含一个或多个Ruby文件(`.rb`),这些文件可能包含各种示例代码,比如控制台应用、基础的数据结构操作、面向对象编程示例等。...

    Ruby-MongoidTreeMongoid文档树结构使用物化路径模式

    Ruby-MongoidTree是一个用于Mongoid ORM的插件,它允许你在MongoDB数据库中创建和操作树形结构的数据。Mongoid Tree是基于物化路径模式实现的,这是一种在非关系型数据库中构建层级数据的方法。在此模式下,每个文档...

    R和Ruby数据分析之旅,中文完整扫描版

    如果你对万事万物的运行方式充满好奇,这本有趣的《R和Ruby数据分析之旅》会帮你找到日常生活中某些问题的真正答案。借助基本的数学方法,并使用Ruby和R语言做一些简单的编程工作,你就能学会如何对问题建模,并找出...

    《Ruby Programming—向Ruby之父学程序设计(第2版)》电子书

    书中的第一章通常会介绍Ruby的基本语法,包括变量声明、数据类型(如整型、浮点型、字符串、布尔型、数组和哈希)以及控制结构(如条件语句if/else和循环for/while)。 接下来,书中的核心内容会深入到Ruby的面向...

Global site tag (gtag.js) - Google Analytics