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

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

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

3、.WriteLine(”abcdefghijk”.Length);/直接取串的长度为112.比较两个字符串是否相等C#直接重载了”=”和”!=”两个运算符处理两个字符串是否相等。在C#中，字符串相等的条件：两个字符串都为空串（null）或两个字符串实例长度相同，并且每个字符位置中的字符都相同。例如：string str1=”abcdefghijk”;string str2=”abcdefghijk”;Console.WriteLine(str1=str2); /str1和str2相等，得到真值true3.字符串的连接直接使用”+”运算符.string str1=”abcde”;str1+=”f

4、ghijk”;Console.WriteLine(str1); /str1的值为”abcdefghijk”4.在字符串中插入另一字符串使用字符串类的Insert方法。该方法的参数有两个,前一个参数是新字符串要插入的位置,后一个参数是要插入的字符串。例如：string str1=”good morning!”;string str2=str1.Insert(1,”Hi,”)Console.WriteLine(str2); / str2的值为” Hi, good morning!”5.字符串替换使用字符串类的Replace方法。该方法的参数有两个,前一个参数是要被替换的字符串,后一个参数是要替换的

5、字符串。例如：string str1=”Hello, good morning!”;string str2=str1.Replace(“ello”,”i,”);/”ello”被替换为”i”Console.WriteLine(str2); / str2的值为” Hi, good morning!”6.提取子串使用字符串类的Substring方法。该方法的参数有两个,前一个参数指出从第几个位置开始截取,后一个参数指出共提取几个字符。using System;class Test public static void Main() string str1=”Hi,good morning!”;int

6、 i;string str2;for(i=0;istr1.Length;i+)str2=str1.Substring(i,1);/从str1中第i个位置开始取一个字符Console.Write(“0”,str2);运行结果:Hi,good morning!7. 字符串的大小写转换使用字符串类的ToUpper方法和ToLower方法可以分别把一个字符串的所有字符都变成大写或小写。例如：using System;class Test public static void Main() string str1=” Hi,good morning!”;string str2=str1.ToUpper(

7、);/将str1中的所有字符变成大写Console.WriteLine(str2); str2=str1.ToLower(); /将str1中的所有字符变成小写Console.WriteLine(str2);运行结果: HI,GOOD MORNING!hi,good morning!8.去掉字符串两边的空格可使用Trim方法去掉前导空格和后缀空格。但不能去掉字符串第一个非空格字符和最后一个非空格字符之间的空格。例如：string str1=” Hello”;string str2=str1.Trim(); /去掉str1的前导空格Console.WriteLine(str2); / str2的

8、值为”Hello”9.访问字符串中的字符字符串是以“0”结束的字符序列。从内存的角度看，字符串就是一个字符数组。可以通过数组的方式访问字符串中的单个字符。例如：string myString=”String is made of Character Array.”; /*字符变量chFirst的内容是字符串myString的第一个字符”S”*/char chFirst= myString0; /字符串用字符的数组表示/*字符变量chLast的内容是字符串myString的最后一个字符”.”*/char chLast= myStringmyString.Length-1;例题1(P118)：us

9、ing System;class Test public static int Main() string UserName,Password; int i; bool Allow=false; for(i=0;i3;i+) Console.Write(“请输入用户名： ”); UserName=Console.ReadLine(); Console.Write(“请输入口令： ”); Password=Console.ReadLine(); if( UserName.Trim().ToLower()=”admin”Password=”) Allow=true; break;elseif(i2

10、) Console.WriteLine(“你输入的用户名或密码不正确，请重新输入。 ”); /for结束if(Allow=false) Console.WriteLine(“非法用户，不能进入系统。 ”); return 1;else Console.WriteLine(“你好，欢迎进入系统。 ”); return 0;例题2(P120)：略 52 数组数组类型是从系统抽象类System.Array中派生而来的引用型数据。C#中的数组下标（又称索引）是从0开始的。在数组中，每一个成员叫数组元素，所有数组元素具有相同的数据类型。5.2.1数组的定义C#中的数组维数被称为秩（Rank），数组的秩直

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

12、nt myArray=new intArrayLength;/ 定义一维数组myArray长度为53.在定义时对数组元素初始化，这时就不用再指出数组的大小，系统自动把初始化列表中的元素个数作为数组的长度。例如：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

13、=2;arr1,1=3;arr2,0=4;arr2,1=5;注意：数组越界和类型溢出在运行时才会被发现。5.2.2 数组的使用1.一维数组的使用例如：对用户输入的一个字符串，统计其中每个字母再现的次数。假设不区分大小写。(P123)namespace 字母个数class Class1static void Main(string args)int CharNum=new int26;/定义数组，用于26个字母计数int Other;/记录除字母之外的任意字符的个数int i;/循环控制变量char temp;/临时变量string strTest;/要检测的字符串for(i=0;i26;i+)

14、CharNumi=0; /CharNum数组元素均赋初值0Other=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.W

15、riteLine(Other 0,Other); 运行结果：请输入要统计的字符串：Madam,Im Adam字符 出现次数a 4d2i1m4Other42.多维数组的使用例如：假设某班有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,10

16、0,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,7

17、9,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,

18、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;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个学生5门课总成绩Aver

19、j=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-;/否则，指针下移return strCurrentPos;class Testpublic s

20、tatic void Main()string Test;/存放要测试的字符串int i;/循环控制变量Stack strStack=new Stack();/声明栈Console.Write(输入要测试的字符串：);Test=Console.ReadLine();for(i=0;iTest.Length;i+ )strStack.Push(Testi);/调用入栈方法Console.Write(输入字符串的反序是：);for(i=0;iTest.Length;i+ )Console.Write(strStack.Pop() ); /调用出栈方法Console.WriteLine(); 运行结

21、果：输入要测试的字符串：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 WeekDays=new string星期日 ,星期一 ,星期二 ,星期三 ,星期四 ,星期五 ,星期六 ;PrintArray(

22、WeekDays);/调用PrintArray方法，WeekDays为参数运行结果:星期日 星期一 星期二 星期三 星期四 星期五 星期六 作业：编写一个控制台应用程序，它接收一个字符串，用“yes”替换字符串中所有的“no”。5.3 集 合C#中的数组只是集合类中的一种。集合类一般处理对象列表，其功能比数组要多，这些功能是通过执行System.Collections名称空间中的接口而实现的，因此，集合的语法已经标准化了。集合的功能可以通过接口来实现。集合与数组相似，用来存放彼此相关的内容。区别是，集合可以通过一个主题词访问其项目，而数组需要用户自己编写查找程序。集合也可以通过索引访问其元素，

23、这点并不比数组优越。5.3.1 集合的定义如果一个类型满足所有下列条件，实现System.Ienumerable接口或实现集合模式，就称它是集合类型：(1)类型包含一个签名GetEnumerator(),返回结构类型(struct)、类类型、接口类型的public实例方法。(2) 类型包含的public实例方法具有签名MoveNext()和返回类型bool。它递增项计数器并在集合中存在更多项时返回true。(3) 类型包含一个名为Crrent的public实例属性，此属性允许读取当前值。此属性的类型称为该集合类型的元素类型，读取时返回集合的当前元素。例：创建MyCollection集合/集合M

24、yCollection的定义 public class MyCollection/集合名 int items; public MyCollection()/构造函数 items=new int5 12,44,33,2,50;/上述集合类型的第一条，GetEnumerator()返回结构类型public MyEnumerator GetEnumerator() return new MyEnumerator(this);/声明集合类public class MyEnumerator int nIndex; MyCollection collection; public MyEnumerator

25、(MyCollection coll) collection=coll; nIndex=-1;/*上述集合类型的第二条，包含public实例方法具有签名MoveNext()和返回类型bool*/public bool MoveNext() nIndex+; return(nIndexcollection.items.GetLengh(0);/*上述集合类型的第三条，名为Crrent的public实例属性，此属性允许读取当前值。*/public int Current get return(collection.items.nIndex);5.3.2 集合的使用利用foreach 语句遍历集合中

26、的每个元素，并且通过执行循环体对每一个元素进行操作。语法格式：foreach(数据类型 变量 in 集合表达式) 循环体例如：完整的C#集合范例public class MyCollection/集合名 int items; public MyCollection()/构造函数 items=new int5 12,44,33,2,50;/上述集合类型的第一条，GetEnumerator()返回结构类型public MyEnumerator GetEnumerator() return new MyEnumerator(this);/声明集合类public class MyEnumerator

27、int nIndex; MyCollection collection; public MyEnumerator (MyCollection coll) collection=coll; nIndex=-1;/*上述集合类型的第二条，包含public实例方法具有签名MoveNext()和返回类型bool*/public bool MoveNext() nIndex+; return(nIndexcollection.items.GetLengh(0);/*上述集合类型的第三条，名为Crrent的public实例属性，此属性允许读取当前值。*/public int Current get ret

28、urn(collection.items.nIndex);public class MainClass public static void Main() MyCollection col=new MyCollection();/定义集合类型的一个实例col Console.WriteLine(”集合中的值有：”); /遍历其中成员 foreach (int i in col) Console.WriteLine(i); 程序的运行结果为：集合中的值有：1244332505.4 枚举5.4.1 枚举类型的定义枚举类型是一种用户自己定义的由一组指定常量集合组成的独特类型，是从System.Enu

29、m派生的。定义枚举类型的格式：枚举修饰符 enum枚举名 枚举符号列表；说明：（1）枚举修饰符可以是以下其中之一：new(新建类型),public,protected,internal,private（2）枚举符号列表中的每个符号不能有相同的名称，它们之间用“，”分隔，最后一个枚举元素的后面有没有逗号均可。符号列表中的每个枚举元素均默认为整型常量。例如：enum WeekDay Sun,Mon,Tue,Wed,Thu,Fri,Sat;WeekDay本身就成了类型说明符，枚举符号列表中的每个符号均可作为常量使用。如：WeekDay WeekEnd=WeekDay.Sat,Tomorrow;/ W

30、eekEnd ,Tomorrow被定义为WeekDay类型的变量。（3）枚举中的常量符号与整数一一对应，如上例中，枚举符号从第一个Sun 开始，到最后一个Sat依次对应整数0、1、2、3、4、5、6,不直接使用整数的原因是为了提高程序的可读性。（4）可以任意规定其对应关系，如：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,Mar

31、ch=31,April=30;例：定义枚举数据（P139）using System;public class EnumTest enum Days1 Sat,Sun,Mon,Tue,Wed,Thu,Fri ;enum Days2 Sat=5,Sun,Mon,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=

32、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枚举名：类型 枚举符号列表；