LINQ 链接及二叉搜索树解析

• 下载源代码 - 26.59 KB

摘要

在数据查询方面，本文将介绍 LINQ 这一强大的数据查询功能。它将展示如何使用 LINQ 的 where 子句筛选数组或集合，如何使用 orderby 子句对查询结果进行排序，以及如何使用 select 子句选择对象的特定属性。语言集成查询 (LINQ) 允许您编写查询表达式，从某些数据源中检索信息。本文将重点介绍如何使用 LINQ to objects 查询数组和列表，选择满足一组条件的元素——这被称为筛选。请注意，在 LINQ 中，数据的两个主要单元是元素和序列。本文的后半部分将改变方向，介绍二叉搜索树数据结构。虽然这种数据结构与查询存储在硬盘上的数据库中的数据无关，但它体现了数据遍历的过程。如果您是高级开发人员，将这两个主题混合在一起可能没有太大意义——这仅仅是为了鼓励初学者学习数据访问。话虽如此，LINQ 查询以 from 子句开始，该子句指定一个范围变量（值）和要查询的数据源（值）。范围变量代表数据源中的每一项（类似于 foreach 语句中的控制变量）。查询表达式以 select 或 group 子句结束，您可以将其视为遍历输入序列。

using System;
using System.Collections.Generic;
using System.Linq;
class LinqDemo
{
static void Main()
{
   string[] names = { "Tom", "Dick", "Harry", "Mary", "Jay" };
   IEnumerable query =
   from n in names
   where n.Contains ("a") // Filter elements
   orderby n.Length // Sort elements
   select n.ToUpper(); // Translate each element (project)
     foreach (string name in query) 
     Console.WriteLine (name);
 }
}

输出

JAY
MARY
HARRY

下面的代码示例演示了如何使用 LINQ 查询整数数组。筛选数组的重复语句侧重于获取结果的过程——迭代元素并检查它们是否满足所需条件。

using System;
using System.Collections.Generic;
using System.Linq;
class LinqDemo
 {
  public static void Main(string[]  args)
   {
    
     int[]  values = { 2, 9, 5, 0, 3, 7, 1, 4, 8, 5 };
     Display(values, "Original array:");

     var filtered = 
      from value in values
      where value > 4
      select value;
     
     Display(filtered, "Array values greater than 4:");

      var sorted = 
       from value in values
       orderby value
       select value;

     Display(sorted, "Original array, sorted:");

      var sortFilteredResults =
        from value in filtered
        orderby value descending
        select value;

      Display( sortFilteredResults, "Values greater than 4, 
			descending order (separately):");

       var sortAndFilter =
          from value in values
          where value > 4
          orderby value descending
          select value;

      Display( sortAndFilter, "Values greater than 4, descending order (one query):");
      }
      public static void Display(
       IEnumerable results, string header)
       {
         Console.Write(  "{0}", header );
         foreach (var element in results)
         Console.Write(  "{0}", element);
         Console.WriteLine();
       }
  }

输出

Original array:2950371485
Array values greater than 4:95785
Original array, sorted:0123455789
Values greater than 4, descending order (separately):98755
Values greater than 4, descending order (one query):98755

数组和集合已经实现了 IEnumerable<t> 接口——它们定义了其所描述的方法。您可以在数组或集合上调用 IEnumerable<t> 定义的任何方法来遍历其元素。如果您熟悉泛型集合和迭代器，这应该很好理解：foreach 语句使用 IEnumerable<t> 方法来遍历集合的每个元素。LINQ 查询返回一个具有整数等类型的对象。它也可以用于大多数数据类型，包括字符串和用户定义的类。

使用 LINQ 查询 Employee 对象数组

要使用 LINQ 查询 Employee 对象数组，我们首先必须编写一个用户定义的类。这是一个具有 FirstName、LastName 和 MonthlySalary 属性的 Employee 类。

using System;
public class Employee
 {
   private decimal monthlySalaryValue;

   public string FirstName { get;   set;  }
   public string LastName  { get;   set;  }

   public Employee(string first, string last, decimal salary)
     {
        FirstName = first;
        LastName = last;
        MonthlySalary = salary;
     }

   public decimal MonthlySalary
     {
        get
         {
            return monthlySalaryValue;
         }
        set
         {
             if ( value >= 0M )
              {
                monthlySalaryValue = value;
              }
          }
      }

    public override string ToString()
     {
       return string.Format("{0, -10} {1, -10} {2, 10:C}",
       FirstName, LastName, MonthlySalary);
     }
  }

我们将其编译为类库。

csc.exe /target:library Employee.cs. 

using System;
using System.Collections.Generic;
using System.Linq;
class LinqDemo
 {
  public static void Main(string[]  args)
   {
     Employee[]  employees = {
       new Employee("Jason", "Red", 5000M),
       new Employee("Ashley", "Green", 7600M),
       new Employee("Mathew", "Indigo", 3587.5M),
       new Employee("James", "Indigo", 4700.77M),
       new Employee("Luke", "Indigo", 6200M),
       new Employee("Jason", "Blue", 3200M),
       new Employee( "Wendy", "Brown", 4236.4M) };

       Display( employees, "Original array" );

       var between4K6K =
        from e in employees
        where e.MonthlySalary >= 4000M && e.MonthlySalary <= 6000M
        select e;

        Display( between4K6K, string.Format
	("Employees earning in the range {0:C}-{1:C} per month", 4000, 6000) );


        var nameSorted = 
         from e in employees
         orderby e.LastName, e.FirstName
         select e;
       
        Console.WriteLine("First employee when sorted by name:");

         if (nameSorted.Any() )
           Console.WriteLine( nameSorted.First().ToString() + "\n" );
         else
           Console.WriteLine( "not found\n" );

         var lastNames = 
            from e in employees
            select e.LastName;

         Display(lastNames.Distinct(), "Unique employees last names");

         var names = 
         from e in employees
         select new { e.FirstName, Last = e.LastName };

         Display(names, "Names only");
       }
  
     public static void Display<t>(
     IEnumerable<t> results, string header)
      {
          Console.WriteLine( "{0}:", header );

          foreach (T element in results)
          Console.WriteLine( element );
          Console.WriteLine();
      }
  }

我们通过如下方式编译主文件来外部引用 Employee 类。

csc.exe /reference:Employee.dll Program.cs 

输出

Original array:
Jason      Red         $5,000.00
Ashley     Green       $7,600.00
Mathew     Indigo      $3,587.50
James      Indigo      $4,700.77
Luke       Indigo      $6,200.00
Jason      Blue        $3,200.00
Wendy      Brown       $4,236.40

Employees earning in the range $4,000.00-$6,000.00 per month:
Jason      Red         $5,000.00
James      Indigo      $4,700.77
Wendy      Brown       $4,236.40

First employee when sorted by name:
Jason      Blue        $3,200.00

Unique employees last names:
Red
Green
Indigo
Blue
Brown

Names only:
{ FirstName = Jason, Last = Red }
{ FirstName = Ashley, Last = Green }
{ FirstName = Mathew, Last = Indigo }
{ FirstName = James, Last = Indigo }
{ FirstName = Luke, Last = Indigo }
{ FirstName = Jason, Last = Blue }
{ FirstName = Wendy, Last = Brown }

我们看到了一个 orderby 子句，用于根据多个属性（在逗号分隔的列表中指定）对结果进行排序。在此查询中，员工按姓氏的字母顺序排序。查询结果的 Any 方法在至少有一个元素时返回 true；如果没有元素则返回 false。查询结果的 First 方法返回结果中的第一个元素。请注意，我们没有指定定义 First 和 Any 方法的类。这些方法没有在 IEnumerable<t> 接口中声明。它们是扩展方法，但可以像 IEnumerable<t> 的方法一样使用。select 子句用于选择范围变量的 LastName 属性，而不是范围变量本身。这使得查询结果仅包含姓氏（作为字符串），而不是完整的 Employee 对象。LINQ 查询选择了 FirstName 和 LastName 属性，语法 ** new { e.FirstName, Last = e.LastName } ** 创建了一个匿名类型（没有名称的类型）的新对象，编译器会根据花括号中列出的属性为您生成该对象。在我们的例子中，匿名类型包含所选 Employee 对象的姓和名属性。这演示了如何为所选属性指定新名称。

使用 LINQ 查询泛型集合

using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
public static void Main() {
     List items = new List();
     items.Add("aQua");
     items.Add("RusT");
     items.Add("yElLow");
     items.Add("rEd");

    var startsWithR =
      from item in items
     let uppercasedString = item.ToUpper()
    where uppercasedString.StartsWith("R")
    orderby uppercasedString
    select  uppercasedString;

      foreach (var item in startsWithR)
      Console.Write( "{0} ", item);
      Console.WriteLine();

       items.Add("rUbY");
       items.Add("SaFfRon");

         foreach ( var item in startsWithR)
         Console.Write(  "{0} ", item);
         Console.WriteLine();
  }
}

输出

RED RUST
RED RUBY RUST

我们使用 LINQ 的 let 子句来创建一个新的范围变量。我们使用 string 的 ToUpper 方法将每个项目转换为大写，然后将结果存储在新的范围变量 uppercasedString 中。接下来，我们在 where、orderby 和 select 子句中使用新的范围变量 uppercasedString。请注意，查询只创建一次。

var startsWithR =
      from item in items
      let uppercasedString = item.ToUpper()
      where uppercasedString.StartsWith("R")
      orderby uppercasedString
      select  uppercasedString;

多次迭代结果会得到两个不同的颜色列表。这展示了 LINQ 的延迟执行特性——查询仅在您访问结果时（例如，对其进行迭代或使用 Count 方法时）执行，而不是在您定义查询时执行。这允许您创建一次查询并多次执行它。每次查询执行时，对数据源的任何更改都会反映在结果中。

二叉搜索数据结构：与 LINQ 并非真有关联，但同样强大

像链表、栈和队列这样的数据结构是线性数据结构。它们在内存中是连续存储的。树是一种具有特殊属性的非线性、二维数据结构。然而，二叉树在内存中不是连续存储的（可以把内存想象成一个字节数组）。BinaryTree 类的实例有一个对根 Node 类实例的引用。根 Node 类实例有对其左右子 Node 实例的引用；这些子实例又有对其子实例的引用，依此类推。关键在于，构成二叉树的各种 Node 实例可以分散在整个 CLR 托管堆中。它们不一定是连续的，不像数组的元素。对于二叉树，每个树节点有两个链接。根节点是树中的第一个节点。根节点中的每个链接都指向一个子节点。左子节点是左子树中的第一个节点，右子节点是右子树中的第一个节点。假设我们想访问二叉树中的某个特定节点。要完成这个任务，我们需要搜索二叉树的节点集，寻找那个特定的节点。与数组不同，这里没有对给定节点的直接访问。搜索二叉树需要线性时间，因为可能需要检查所有节点。也就是说，随着二叉树中节点数量的增加，找到任意一个节点的步骤数也会增加。

为了说明这种数据结构，我们将编写一个应用程序，它创建一个整数的二叉搜索树，并以三种方式遍历它（或走遍它的所有节点）——使用递归的中序、前序和后序遍历。可以说，最简单的方法是编写一个定义这三种算法的类库，然后编写一个测试应用程序来检验结果。这里的遍历是我们的应用程序将要测试的可重用库。

using System;

 namespace BinaryTreeLibrary
  {
    class TreeNode
    {
     public TreeNode LeftNode {  get;  set; }

     public int Data {  get;  set; }
     public TreeNode RightNode  {  get;  set; }
     public TreeNode ( int nodeData )
      {
         Data = nodeData;
         LeftNode = RightNode = null;
      }

    public void Insert ( int insertValue )
     {
        if ( insertValue < Data )
         {
           if ( LeftNode == null )
           
            LeftNode = new TreeNode(insertValue);
            else
            LeftNode.Insert(insertValue);
         }

        else if (insertValue > Data )
        {

         if ( RightNode == null )
          RightNode = new TreeNode (insertValue);

       else
          RightNode.Insert(insertValue);
      }
    }
  }

 public class Tree
  {
    private TreeNode root;
    public Tree()
     {
       root = null;
     }
    public void insertNode( int insertValue)
     {
       if ( root == null )
        root = new TreeNode(insertValue);
       else
        root.Insert(insertValue);
     }

  public void PreorderTraversal()
    {
      PreorderHelper (root);
    }

private void PreorderHelper(TreeNode node )
    {
       if (node != null )
    {
    Console.Write( node.Data + " " );
    PreorderHelper(node.LeftNode);
    PreorderHelper(node.RightNode);

     }
  }

   public void InorderTraversal()
    {
       InorderHelper( root );
    }

   private void InorderHelper( TreeNode  node )
    {
      if ( node != null )
      {
       InorderHelper(node.LeftNode);
       Console.Write(node.Data + " " );
       InorderHelper(node.RightNode );
      }
   }

   public void PostorderTraversal()
     {
      PostorderHelper( root );
     }

    private void PostorderHelper(TreeNode  node)
      {
         if (node != null)
          {
            PostorderHelper(node.LeftNode);
            PostorderHelper(node.RightNode);
            Console.Write(node.Data + " " );
          }
        }
     }
  }

算法并不像人们说的那么难。它们只是计算模型。这个文件可以编译成 C# 类库，也可以在命令行上使用 /target:library 开关来编译。如果将其编译为类库，您只需添加一个 C# 控制台应用程序解决方案并引用该 DLL。下面是测试这个库的应用程序。

using System;
using BinaryTreeLibrary;

public class TreeTest
 {
   public static void Main(string[]  args)
    {
      Tree tree = new Tree();
      int insertValue;

      Console.WriteLine("Inserting Values:  ");
      Random random = new Random();
      for (int i  = 1; i <= 10; i++)
      {
      insertValue = random.Next(100);
      Console.Write(insertValue + " ");
      tree.insertNode(insertValue);
     }

    Console.WriteLine("\n\nPreorder traversal");
    tree.PreorderTraversal();

    Console.WriteLine("\n\nInorder traversal");
    tree.InorderTraversal();

    Console.WriteLine("\n\nPostorder traversal");
    tree.PostorderTraversal();
    Console.WriteLine();
     }
   }

输出如下

Inserting Values:
52 62 69 30 45 94 71 45 91 50

Preorder traversal
52 30 45 50 62 69 94 71 91

Inorder traversal
30 45 50 52 62 69 71 91 94

Postorder traversal
50 45 30 91 71 94 69 62 52

参考文献

• MSDN 库
• Paul Deitel 和 Harvey Deitel 的 C# 系列丛书