[翻译]C#数据结构与算法 – 第四章 基本查找算法
第4章 基本查找算法
数据查找是一项基本的计算机编程任务而且也已被研究多年。本章仅仅研究查找问题的一个方面 – 在列表(数组)中查找给定的值。
在列表中查找数据有两种基本方式:顺序查找与二分查找。当列表中的项是随机排列时适用顺序查找;二分查找适用于已排好序的列表。
顺序查找
这种最显而易见的查找类型由一个记录集的起始部分开始,遍历每一个记录直到找到你要找的记录或着你来到记录的尾部。这就叫做顺序查找。
顺序查找(又称线性查找)很简单易行。由数组开始部分起比较每一个正访问的数组元素与你要查找的值。如果你找到匹配的元素,查找结束。如果到达数组的末尾也无法得到一个匹配,则表明数组中无此值。
顺序查找的函数如下:
bool SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
if (arr[index] == sValue)
return true;
return false;
}
如果有一个匹配被找到,程序立即返回True并退出。如果到数组的尾部函数仍未返回True,则待查找的值不在数组中且函数返回False。
如下是一个测试我们顺序查找实现的程序:
using System;
using System.IO;
public class Chapter4
{
static void Main()
{
int[] numbers = new int[100];
StreamReader numFile = File.OpenText("c:\numbers.txt");
for (int i = 0; i < numbers.Length - 1; i++)
numbers[i] = Convert.ToInt32(numFile.ReadLine(), 10);
int searchNumber;
Console.Write("Enter a number to search for: ");
searchNumber = Convert.ToInt32(Console.ReadLine(), 10);
bool found;
found = SeqSearch(numbers, searchNumber);
if (found)
Console.WriteLine(searchNumber + " is in the array.");
else
Console.WriteLine(searchNumber + " is not in the array.");
}
static bool SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
if (arr[index] == sValue)
return true;
return false;
}
}
这个程序首先由一个文本文件读取一个数据集。这个数集包含100个整数,以部分随机的顺序存储于一个文件中。然后程序提示用户输入一个待查找的数字,并调用SeqSearch函数来执行查找。
你也可以编写一个这样的顺序查找函数 – 当查找到待查找的值时返回其索引,反之如果找不到返回-1。首先,我们看一下新的函数:
static int SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length - 1; index++)
if (arr[index] == sValue)
return index;
return -1;
}
下面的程序使用了这个函数:
using System;
using System.IO;
public class Chapter4
{
static void Main()
{
int[] numbers = new int[100];
StreamReader numFile = File.OpenText("c:\numbers.txt");
for (int i = 0; i < numbers.Length - 1; i++)
补充:软件开发 , C# ,