常用数据结构与算法(数组)

第 7章 常用数据结构与算法 数据结构和算法是程序设计的基石。 本章重点讲述 C#中的几个主要的数据结构类型： 字符串、 数组 和枚举。 本章还将介绍一些常用算法，如几种典型排序算法的 C#实现。27.2 数组 数组 的作用非常强大，数据也是基本数据结构之一，是编程实现过程中必不可少的要素之一。37.2.1 数组的概念 数组（ Array）是一种数据结构，一个数组由若干个类型相同的数组元素的变量。 C#中，数组中的所有变量都具有相同的类型，而且数组具有一定的长度。 在数组中，每一个成员叫做数组元素，数组元素的类型称为数组类型，数组类型可以是 C#中定义的任意类型，其中也包括数组类型本身。4 如果一个数组的类型不是数组类型，称之为一维数组。如果数组元素的类型是数组类型，就称之为多维数组，也就是说，数组定义可以嵌套。 这些变量可以通过一个数组名和数组下标（或者称为索引）来访问，数组元素的下标是 从零开始，结束于长度从零开始，结束于长度减一。减一。57.2.1 数组的概念 数组被用于各种目的，因为它提供了一种高效、方便的手段将相同类型的变量合成一组。 例如，可以用数组保存一个月中每天的温度记录，货物平均价格的记录。 数组的主要优点是，通过这样的一种方式组织数据使得数据容易 被操纵 静态操作 。 例如，有一个数组，它包括选定的一组学生的数学成绩，操作该数组，很容易计算其平均数学成绩。而且以这样的方式组织数据，会很容易实现对数据的排序。67.2.1 数组的概念 在实际使用数据的过程中，一般是 先确定数据类型 ，然后根据实际情况 确定数组的长度 。 C#中的数组是由 System.Array类派生而来 的引用对象，因此可使用 Array类的方法和成员进行各种操作。 比如： Length属性 GetLength()方法 Sort()方法 。77.2.2 System.Array类 System.Array类是 C#中各种数组的基类，其常用属性和方法的简单说明如表 7-1所示。87.2.3 一维数组 由具有一个下标的数组元素所构成的数组就是一维数组，一维数组是简单的数组。 例如：为了记录 50个银行储蓄用户的账号，就可以使用一个长度为 50的一维数组来处理。 一维数组比较直观，使用起来相对容易。97.2.3 一维数组1. 一维数组的定义 数据在使用前先进行定义。定义一维数组的格式如下：数据类型数据类型 数组名； 其中数组类型为各种数据类型，它表示数据元素的类型；在数组名与数据类型之间是一组空的方括号。 例如：int intArr; /定义了一个整型一维数组string strArr; /定义了一个字符串类型一维数组 注意：数组是引用类型，这里只是定义了一个存储 该数组首地址值的空间 ！ 在定义数组后， 必须必须 对其进行初始化才能使用 ，即动态初始化和静态初始化。107.2.3 一维数组2. 动态初始化 动态初始化需要借助 new运算符，为数组元素分配内运算符，为数组元素分配内存空间，并为数据元素赋初始值。存空间，并为数据元素赋初始值。 动态初始化数组的格式如下：数组名 = new 数据类型 数组长度 ；例如：char chArr; /定义数组引用chArr=new char10; /动态申请数组元素空间，/并默认初始化 10个元素值均为 011 在 C#中，可以将数组定义与动态初始化合在一起，格式如下：数据类型 数组名 =new 数据类型 数组长度 ； 例如：int intArr=new int5; 上面的语句定义了一个整型数组，它包含从intArr0到 intArr4这 5个元素。 new运算符用于创建数组实例，并用默认值对数据元素进行初始化。在本例中，所有数组元素的值都被初始化为 0。127.2.3 一维数组 定义其他类型的数组的方法是一样的，如下面的语句用于定义一个存储 3个字符串元素的数组，并对其进行初始化：string strArr=new string3; strArr数组中所有数组元素的初始值都为 “”。137.2.3 一维数组注意： C#中动态分配空间，数组长度是可以为变量的！ 数组的动态初始化，能够在程序的运行过程中分配长度。 int a; int j; j=int.Parse(Console.ReadLine(); a = new intj;/ 可以使用变量147.2.3 一维数组 当用 new创建数组实例，其长度为常量时： 用户可以在创建数组实例的同时，自行赋予其初始化值，程序代码如下：int intArr=new int53,6,9,2,10; 此时数组元素的初始化值就是大括号中列出的元素值。string strArr=new string3“1”,”2”,”3”;要求：初始化列表中元素个数与长度描述一致！ C#中，不允许部分初始化数组元素，要么不给，要么全部给出初始值。 157.2.3 一维数组3. 静态初始化 静态初始化数组时， 必须与数组定义结合在一起 ，否则程序就会报错。静态初始化数组的格式如下：数据类型 数据名 =元素 1,元素 2; 用这种方法对数组进行初始化时，无须说明数组元素的个数，只需按顺序列出数组中的全部元素即可，系统会自动计算并分配数组所需的内存空间。 例如：int intArr=3,6,9,2,10;string strArr=“English”,”Maths”,”Computer”;167.2.3 一维数组4. 关于一维数据初始化的几点说明（ 1） 动态初始化数组时，可以把定义与初始化分开在不同的语句中者，例如：int intArr; /定义数组intArr=new int5; /动态初始化，初始化元素的值均为 0或者intArr=new int5 3,6,9,2,10; 此时，在 new int53,6,9,2,10这条语句中，方括号中表示数组元素个数的 “ ”可以省略，因为后面大括号中已列出了数组中的全部元素。177.2.3 一维数组4. 关于一维数据初始化的几点说明（ 2） 静态初始化数组必须与数组结合在一条语句中，否则程序就会出错。（ 3） 在数组初始化语句中，如果大括号中已明确列出了数组中的元素，即确定了元素个数，则表示数组元素个数的数值（即方括号中的数值）必须是常量，并且该数值必须与数组元素个数一致。187.2.3 一维数组5. 访问一维数组中的元素 在 C#中是通过数组名和下标值来访问数组元素的。 在访问数组元素时，其下标可以是一个整型常量或整型表达式。例如，下面的数组元素的下标都是合法的：intArr3， strArr0， intArrj， strArr2*i-1 在实际的程序设计中，也可能导致下标值超越正常取值范围。如果下标越界，将会抛出一个System.IndexOutOfRangeException的异常。19static void Main(string args)int count;Console.WriteLine(“请输入您要登记的学生人数 “);count=int.Parse(Console.ReadLine();/ 声明一个存放姓名的字符串数组 ，其长度等于提供的学生人数 string names = new stringcount;/ 用一个 for 循环来接受姓名 for(int i=0; i“,QueArrayi);Console.WriteLine();/进行换行Array.Sort(QueArray); /对数组升序排序/输出排序后的数组Console.WriteLine(“排序以后的数组： “);for (int i = 0; i “, QueArrayi);247.2.3 一维数组6. 查找元素 在数组中查找元素，一是寻找到与给定值相同的元素，可以使用 Array类的 BinarySearch方法。二是判定数组中是否含有一个特定的元素，可以用 Contains方法来实现。（ 1） BinarySearch方法 BinarySearch使用二进制搜索算法在一维的排序 Array中搜索算法， 注意必须是已经排序的数组。注意必须是已经排序的数组。 如果找到给定的值，则返回其下标；否则，返回一个负整数。常用形式如下：public static int BinarySearch(Array array,object value); 其中，参数 array为待搜索的数组， value为待寻找的元素值。257.2.3 一维数组【 例 7-2】 给定 8个数： 8、 7、 6、 5、 4、 3、 2、 1，将这些数存在数组中，利用 Array类的 BinarySearch方法返回其中的元素 5的下标。using System; namespace BinarySearchclass BinarySearchstatic void Main()/定义数组int myArr=8,7,6,5,4,3,2,1;/对数组排序Array.Sort(myArr); 267.2.3 一维数组/搜索int target=5;int result=Array.BinarySearch(myArr,target); Console.WriteLine(“0的下标为 1“,target,result);Console.ReadLine();277.2.3 一维数组（ 2） Contains方法 Contains方法可以确定某个特定值是否包含在数组中，返回一个 bool值（ True或 False）。 Array类的这个方法实际上是对 IList接口中方法的实现，常用形式如下：bool IList对象 .Contains(object value); 其中，参数 value代表所要验证的元素值。287.2.3 一维数组【 例 7-4】 判定学生数组 arrSname中是否包含 “赵六 ”。using System;namespace Containsclass Containsstatic void Main()/定义数组st