第5章常用数据结构与算法

1、第 5 章 常用数据结构与算法5.1 字符串字符串 (string) 类型直接从 object 类派生 , 它是被密封的 , 不能再有派生 类。5.1.1 字符串类型定义1. 定义2. 两种字符串 :(1) 规则字符串 :由包含在双引号中的零个或多个字符组成 , 并且可以 包含简单转义序列、十六进制转义序列、 Unicode 转义序列。 如：” hello ”(2) 逐字字符串 : 由 后跟双引号字符、零个或多个字符组成。如：” hello ” 区别：规则字符串要对字符串中的转义序列进行解释 逐字字符串除了对双引号进行解释之外，对其他字符，原样显示。例如： string str1; / 定义字

2、符串类型string str2=”hello,word ” / 规则字符串 hello,wordstring str3= ” hello,word ” / 逐字字符串 hello,wordstring str4= ”hellotword ” / 规则字符串 hello wordstring str5= ” hellotword ”/ 逐字字符串 hellotword5.1.2 字符串类型的应用1判断一个字符串的长度在C#中，字符串类型有一个Length属性，利用它可得到一个字符串变量或一个字符串常量的长度例如：string str= ”abcdefghijk ”; / str 变量中的串由 1

3、1 个字符组成 Console.WriteLine(str.Length); /str 变量的长度为 11Console.WriteLine( ” abcdefghijk ” .Length); / 直接取串的长度为 11 2. 比较两个字符串是否相等C#直接重载了” =”和”匸”两个运算符处理两个字符串是否相等。在C#中，字符串相等的条件：两个字符串都为空串( null )或两个字符串实例长度相同，并且每个字符 位置中的字符都相同。例如：string str1= ” abcdefghijk ” ;string str2= ” abcdefghijk ” ;Console.WriteLine(

4、str1=str2); /str1 和 str2 相等，得到真值 true3. 字符串的连接 直接使用” +”运算符 .string str1= ” abcde” ; str1+= ” fghijk ” ;Console.WriteLine(str1); /str1 的值为” abcdefghijk ”4. 在字符串中插入另一字符串使用字符串类的 Insert 方法。该方法的参数有两个 , 前一个参数是新 字符串要插入的位置 , 后一个参数是要插入的字符串。例如：string str1= ” good morning! ”;string str2=str1.Insert(1,”Hi, ” )C

5、onsole.WriteLine(str2); / str2 的值为” Hi, good morning! ”5. 字符串替换使用字符串类的 Replace 方法。该方法的参数有两个 , 前一个参数是要 被替换的字符串 , 后一个参数是要替换的字符串。例如：string str1= ”Hello, good morning! ” ;string str2=str1.Replace( “ ello ”, ”i, ”); / ”ello ” 被 替 换 为IConsole.WriteLine(str2); / str2 的值为” Hi, good morning! ”6. 提取子串使用字符串类的

6、SubstrIng 方法。该方法的参数有两个 , 前一个参数指 出从第几个位置开始截取 , 后一个参数指出共提取几个字符。 usIng System;class TestpublIc statIc voId MaIn()strIng str1= ”HI,good mornIng! ”;Int I;string str2;for(i=0;istr1.Length;i+) str2=str1.Substring(i,1); / 从 str1 中第 i 个位置开始取一个 字符Console.Write( “ 0 ” ,str2);运行结果 :Hi,good morning!7. 字符串的大小写转换

7、使用字符串类的 ToUpper 方法和 ToLower 方法可以分别把一个字符串 的所有字符都变成大写或小写。例如：using System;class Testpublic static void Main()/ 将 str1 中的所有字符变成大写string str1= ” Hi,good morning! ” ;string str2=str1.ToUpper();Console.WriteLine(str2);str2=str1.ToLower(); / 将 str1 中的所有字符变成小写Console.WriteLine(str2);运行结果 : HI,GOOD MORNING!hi

8、,good morning!8. 去掉字符串两边的空格可使用 Trim 方法去掉前导空格和后缀空格。 但不能去掉字符串第一个非空 格字符和最后一个非空格字符之间的空格。例如：string str1= ” Hello string str2=str1.Trim(); Console.WriteLine(str2);9. 访问字符串中的字符/ 去掉 str1 的前导空格/ str2 的值为” Hello字符串是以“ 0 ”结束的字符序列。从内存的角度看，字符串就是一个字 符数组。可以通过数组的方式访问字符串中的单个字符。例如：string myString= ” String is made of

9、 Character Array.” ;/* 字符变量 chFirst 的内容是字符串 myString 的第一个字符” S” */char chFirst= myString0; / 字符串用字符的数组表示*/* 字符变量 chLast 的内容是字符串 myString 的最后一个字符” char chLast= myStringmyString.Length-1;例题 1(P118) ：using System;class Test public static int Main()string UserName,Password;int i;bool Allow=false; for(i=

10、0;i3;i+) Console.Write(“请输入用户名： ”);UserName=Console.ReadLine(); Console.Write( “请输入口令： ”);Password=Console.ReadLine();if( UserName.Trim().ToLower()=”admin” II Password=”23456” Allow=true;break;elseif(i2)Console.WriteLine( 入。 ”); /for 结束if(Allow=false) Console.WriteLine( return 1; else Console.WriteL

11、ine(return 0;你输入的用户名或密码不正确，请重新输“非法用户，不能进入系统。 ”);你好，欢迎进入系统。 ”);例题 2(P120) ：略52 数组数组类型是从系统抽象类System.Array中派生而来的引用型数据。C#中的数组下标（又称索引）是从 0 开始的。在数组中，每一个成员叫数组元素， 所有数组元素具有相同的数据类型。5.2.1 数组的定义C#中的数组维数被称为秩（Rank）,数组的秩直接决定了数组的下标数。 如果一个数组的秩为 1，则该数组为一维数组，如果一个数组的秩大于 1， 则该数组为多维数组。在数组中数组元素的个数，叫这个维中的数组长度。 无论是一维数组还是多维数

12、组，其下标都从 0 开始，结束于这个维的长度 减 1 。数组定义的格式：数组类型修饰符 数组名 =new 数组类型 数组元素初始化列表 ； 例如：1. int arr=new int3;/* 一维数组 arr 长度为 3， arr0,arr1,arr2各数组元素被初始化为默认值 0 */等价于：int arr;arr=new int3;2. 必须使用常量（可以是直接常量）定义数组的大小。例如：int const ArrayLength =5;int myArray=new int ArrayLength ; / 定义一维数组 myArray 长度为53. 在定义时对 数组元素初始化，这时就不用

13、再指出数组的大小，系统自动 把初始化列表中的元素个数作为数组的长度。例如： string arrLanguages=new string” c”, ”c+”, ”c#”;还可写为：string arrLanguages= ” c”, ” c+”, ”c#”;4.int, arr=new int5,3;/ 定义二维数组 arr, 长度为 155.int, arr=0,1,2,3,4,5;等价于int, arr=new int3,2;arr0,0=0;arr0,1=1;arr1,0=2;arr1,1=3;arr2,0=4;arr2,1=5; 注意：数组越界和类型溢出在运行时才会被发现。5.2.2

14、数组的使用1. 一维数组的使用例如：对用户输入的一个字符串，统计其中每个字母再现的次数。假设不 区分大小写。 (P123)namespace 字母个数class Class1static void Main( string args)int CharNum= new int 26; / 定义数组，用于 26个字母计数 int Other; / 记录除字母之外的任意字符的个数int i; / 循环控制变量 char temp; / 临时变量 string strTest; / 要检测的字符串for (i=0;i26;i+)CharNumi=0; /CharNum 数组元素均赋初值 0 Other

15、=0;Console.WriteLine( 请输入要统计的字符串： ); strTest=Console.ReadLine();strTest=strTest.ToUpper(); / 转成大写字母，便于统计 Console.WriteLine( 字符 出现的次数 );for (i=0;i=A & temp=Z)CharNumtemp-A+; / 相应字母计数加 1elseOther+;for (i=0;i26;i+)if (CharNumi!=0)Console.WriteLine(01,( char )(i+a),CharNumi);Console.WriteLine(Other 0,Ot

16、her);运行结果：请输入要统计的字符串： Madam,Im Adam字符 出现次数a4d2i1m4Other42. 多维数组的使用例如：假设某班有 50人，每名同学一次参加 5 门考试，要求计算每位同学 的总分和每门课的全班平均分。 (P124)namespace 平均分class Class1static void Main( string args)const int Pupil=50; / 定义整型常量 Pupil 为 50个学生const int Class=5; / 定义整型常量 Class 为5门课程int ,Score=78,90,89,85,92 ,89,85,79,100,

17、95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,

18、100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95,78,90,89,85,92,89,85

19、,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95, 78,90,89,85,92,89,85,79,100,95,60,70,80,90,95,95,85,75,65,60,94,86,78,89,95;int i,j; / 循环控制变量int Sum; / 存储总的分变量int Aver=0,0,0,0,0; / 存储各门平均成绩的一维数组Console.WriteLine( 学号 总分 );for (i=0;iPupil;i+)Sum=0;for (j=0;jClass;j+)Sum=Sum+Scorei,j; / 求出第 i

20、个学生 5门课总成绩Averj=Averj+Scorei,j;/ 每门课 50个学生的成绩Console.WriteLine(No. 0 1,i+1,Sum);Console.WriteLine( 科目平均成绩是： );for (j=0;j=MaxLength) / 防止栈溢出 return false ;strCurrentPos=ch; / 字符入栈 CurrentPos+; / 指针上移 return true ;public char Pop() / 出栈操作if (CurrentPos=0) / 栈为空 return 0; / 返回 nullCurrentPos-; / 否则，指针下

21、移return strCurrentPos;class Testpublic static void Main()string Test; / 存放要测试的字符串int i; / 循环控制变量Stack strStack= newStack(); / 声明栈 Console.Write( 输入要测试的字符串： ); Test=Console.ReadLine();for (i=0;iTest.Length;i+ )strStack.Push(Testi); / 调用入栈方法Console.Write( 输入字符串的反序是： );for (i=0;iTest.Length;i+ )Console

22、.Write(strStack.Pop() ); / 调用出栈方法 Console.WriteLine();运行结果： 输入要测试的字符串： Hello,World. 输入字符串的反序是： .dlroW,olleH3. 把数组作为参数 (P127)namespace 用数组作参数class Class1static void PrintArray(string w) / 数组 w作为方法的参数for (int i=0;iw.Length;i+)Console.Write(0,wi);Console.WriteLine();static void Main( string args)string

23、 WeekDays= new string 星期日 , 星期一 , 星期 二 , 星期三 , 星期四 , 星期五 , 星期六 ;PrintArray(WeekDays);/ 调用 PrintArray 方法，WeekDay为参数运行结果 :星期日 星期一 星期二 星期三 星期四 星期五 星期六作业：编写一个控制台应用程序，它接收一个字符串，用“yes ”替换字符串中所有的“ no”。5.3 集 合C#中的数组只是集合类中的一种。集合类一般处理对象列表，其 功能比数组要多， 这些功能是通过执行 System.Collections 名称空间 中的接口而实现的，因此，集合的语法已经标准化了。集合的

24、功能可 以通过接口来实现。集合与数组相似，用来存放彼此相关的内容。区别是，集合可以 通过一个主题词访问其项目，而数组需要用户自己编写查找程序。集 合也可以通过索引访问其元素，这点并不比数组优越。5.3.1 集合的定义如果一个类型满足所有下列条件， 实现 System.Ienumerable 接口或实 现集合模式，就称它是集合类型：(1) 类型包含一个签名 GetEnumerator(), 返回结构类型 (struct) 、类 类型、接口类型的 public 实例方法。(2) 类型包含的 public 实例方法具有签名 MoveNext() 和返回类型 bool 。它递增项计数器并在集合中存在更

25、多项时返回 true 。(3) 类型包含一个名为 Crrent 的 public 实例属性，此属性允许读取 当前值。此属性的类型称为该集合类型的元素类型，读取时返回集合 的当前元素。例：创建 MyCollection 集合/ 集合 MyCollection 的定义 public class MyCollection / 集合名int items;public MyCollection() / 构造函数items=new int5 12,44,33,2,50;/ 上述集合类型的第一条， GetEnumerator() 返回结构类型 public MyEnumerator GetEnumerato

26、r()return new MyEnumerator(this);/ 声明集合类public class MyEnumeratorint nIndex; MyCollection collection;public MyEnumerator (MyCollection coll) collection=coll;nIndex=-1;/* 上述集合类型的第二条， 包含 public 实例方法具有签名 MoveNext() 和返回类型 bool*/public bool MoveNext()nIndex+; return(nIndexcollection.items.GetLengh(0);/*

27、上述集合类型的第三条，名为 Crrent 的 public 实例属性，此属性 允许读取当前值。 */public int Currentget return(collection.items.nIndex);5.3.2 集合的使用利用 foreach 语句遍历集合中的每个元素，并且通过执行循环体对每一个 元素进行操作。语法格式： foreach( 数据类型 变量 in 集合表达式 ) 循环体例如：完整的C#集合范例public class MyCollection / 集合名int items;public MyCollection() / 构造函数items=new int5 12,44,3

28、3,2,50;/ 上述集合类型的第一条， GetEnumerator() 返回结构类型 public MyEnumerator GetEnumerator()return new MyEnumerator(this);/ 声明集合类public class MyEnumeratorint nIndex;MyCollection collection;public MyEnumerator (MyCollection coll)collection=coll;nIndex=-1;/* 上述集合类型的第二条， 包含 public 实例方法具有签名 MoveNext() 和返回类型 bool*/pu

29、blic bool MoveNext()nIndex+; return(nIndexcollection.items.GetLengh(0);/* 上述集合类型的第三条，名为 Crrent 的 public 实例属性，此属性 允许读取当前值。 */public int Currentget return(collection.items.nIndex);public class MainClasspublic static void Main()colMyCollection col=new MyCollection(); / 定义集合类型的一个实例 Console.WriteLine( ”集

30、合中的值有：” );/ 遍历其中成员foreach (int i in col)Console.WriteLine(i); 程序的运行结果为： 集合中的值有：1244332505.4 枚举5.4.1 枚举类型的定义 枚举类型是一种用户自己定义的由一组指定常量集合组成的独特类型，是 从 System.Enum 派生的。定义枚举类型的格式：枚举修饰符 enum 枚举名 枚举符号列表 ； 说明：（ 1）枚举修饰符可以是以下其中之一：new（新建类型）,public,protected,internal,private（2） 枚举符号列表中的每个符号不能有相同的名称，它们之间用“，”分隔，最后一个枚举

31、元素的后面有没有逗号均可。符号列表中的每个枚举元 素均默认为整型常量。例如： enum WeekDay Sun,Mon,Tue,Wed,Thu,Fri,Sat;WeekDay本身就成了类型说明符，枚举符号列表中的每个符号均可作为常量使用。如： WeekDay WeekEnd=WeekDay.Sat,Tomorrow;/ WeekEnd Tomorrow 被定义为 WeekDay类型的变量。（ 3）枚举中的常量符号与整数一一对应，如上例中， 枚举符号从第一个 Sun开始，到最后一个 Sat 依次对应整数 0、1、2、3、4、5、 6, 不直接使用整 数的原因是为了提高程序的可读性。（ 4）可以任

32、意规定其对应关系，如：enum Month January=1,February,March,April,May,June;/January=1,February=2,March=3,April=4,May=5,June=6（ 5）允许给每个 枚举元素赋任意值。如：enum MonthName January=31,February=28,March=31,April=30;例：定义枚举数据（ P139）using System;public class EnumTestenum Days1 Sat,Sun,Mon,Tue,Wed,Thu,Fri ;enum Days2 Sat=5,Sun,M

33、on,Tue,Wed,Thu,Fri ;enum Days3 Sat=31,Sun=1,Mon=0,Tue=7,Wed=3,Thu=0,Fri=0 ;public static void Main()int x=(int)Days1.Sun;/x=1int y=(int)Days1.Fri;/y=6Console.WriteLine(“ Sun=0 Fri=1”,x,y);x=(int)Days2.Sun;/x=6y=(int)Days2.Fri;/y=11Console.WriteLine(“ Sun=0 Fri=1”,x,y);x=(int)Days3.Sun;/x=1y=(int)Days3.Fri;/y=0Console.WriteLine(“ Sun=0 Fri=1”,x,y);运行结果：Sun=1 Fri=6Sun=6 Fri=11Sun=1 Fri=0(6) 程序编译时，编译系统自动把枚举值转换成整数值。因此，枚举类型的值不能打印出来，只能打印出对应的整数。 (如上例) (7)可将枚举的值定义为其它类型 定义枚举类型的格式：枚举修饰符 enum 枚举名：类型 枚举符号列表 ； 这里的类型只能是 lo