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

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

《第5章 常用数据结构与算法.docx》由会员分享，可在线阅读，更多相关《第5章 常用数据结构与算法.docx（23页珍藏版）》请在冰点文库上搜索。

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

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

5.1字符串

字符串（string）类型直接从object类派生,它是被密封的,不能再有派生类。

5.1.1字符串类型定义

1.定义

2.两种字符串:

（1）规则字符串:

由包含在双引号中的零个或多个字符组成,并且可以包含简单转义序列、十六进制转义序列、Unicode转义序列。

如：

”hello”

（2）逐字字符串:

由@后跟双引号字符、零个或多个字符组成。

如：

@”hello”

区别：

规则字符串要对字符串中的转义序列进行解释

逐字字符串除了对双引号进行解释之外，对其他字符，原样显示。

例如：

stringstr1;//定义字符串类型

stringstr2=”hello,word”//规则字符串hello,word

stringstr3=@”hello,word”//逐字字符串hello,word

stringstr4=”hello\tword”//规则字符串helloword

stringstr5=@”hello\tword”//逐字字符串hello\tword

5.1.2字符串类型的应用

1．判断一个字符串的长度

在C#中，字符串类型有一个Length属性，利用它可得到一个字符串变量或一个字符串常量的长度。

例如：

stringstr=”abcdefghijk”;//str变量中的串由11个字符组成

Console.WriteLine（str.Length）;//str变量的长度为11

Console.WriteLine（”abcdefghijk”.Length）;//直接取串的长度为11

2.比较两个字符串是否相等

C#直接重载了”==”和”!

=”两个运算符处理两个字符串是否相等。

在C#中，字符串相等的条件：

两个字符串都为空串（null）或两个字符串实例长度相同，并且每个字符位置中的字符都相同。

例如：

stringstr1=”abcdefghijk”;

stringstr2=”abcdefghijk”;

Console.WriteLine（str1==str2）;//str1和str2相等，得到真值true

3.字符串的连接

直接使用”+”运算符.

stringstr1=”abcde”;

str1+=”fghijk”;

Console.WriteLine（str1）;//str1的值为”abcdefghijk”

4.在字符串中插入另一字符串

使用字符串类的Insert方法。

该方法的参数有两个,前一个参数是新字符串要插入的位置,后一个参数是要插入的字符串。

例如：

stringstr1=”goodmorning!

”;

stringstr2=str1.Insert（1,”Hi,”）

Console.WriteLine（str2）;//str2的值为”Hi,goodmorning!

”

5.字符串替换

使用字符串类的Replace方法。

该方法的参数有两个,前一个参数是要被替换的字符串,后一个参数是要替换的字符串。

例如：

stringstr1=”Hello,goodmorning!

”;

stringstr2=str1.Replace（“ello”,”i,”）;//”ello”被替换为”i”

Console.WriteLine（str2）;//str2的值为”Hi,goodmorning!

”

6.提取子串

使用字符串类的Substring方法。

该方法的参数有两个,前一个参数指出从第几个位置开始截取,后一个参数指出共提取几个字符。

usingSystem;

classTest

{

publicstaticvoidMain（）

{

stringstr1=”Hi,goodmorning!

”;

inti;

stringstr2;

for（i=0;i

{str2=str1.Substring（i,1）;//从str1中第i个位置开始取一个字符

Console.Write（“{0}”,str2）;

}

}

}

运行结果:

Hi,goodmorning!

7.字符串的大小写转换

使用字符串类的ToUpper方法和ToLower方法可以分别把一个字符串的所有字符都变成大写或小写。

例如：

usingSystem;

classTest

{

publicstaticvoidMain（）

{

stringstr1=”Hi,goodmorning!

”;

stringstr2=str1.ToUpper（）;//将str1中的所有字符变成大写

Console.WriteLine（str2）;

str2=str1.ToLower（）;//将str1中的所有字符变成小写

Console.WriteLine（str2）;

}

}

运行结果:

HI,GOODMORNING!

hi,goodmorning!

8.去掉字符串两边的空格

可使用Trim方法去掉前导空格和后缀空格。

但不能去掉字符串第一个非空格字符和最后一个非空格字符之间的空格。

例如：

stringstr1=”Hello”;

stringstr2=str1.Trim（）;//去掉str1的前导空格

Console.WriteLine（str2）;//str2的值为”Hello”

9.访问字符串中的字符

字符串是以“\0”结束的字符序列。

从内存的角度看，字符串就是一个字符数组。

可以通过数组的方式访问字符串中的单个字符。

例如：

stringmyString=”StringismadeofCharacterArray.”;

/*字符变量chFirst的内容是字符串myString的第一个字符”S”*/

charchFirst=myString[0];//字符串用字符的数组表示

/*字符变量chLast的内容是字符串myString的最后一个字符”.”*/

charchLast=myString[myString.Length-1];

例题1（P118）：

usingSystem;

classTest

{publicstaticintMain（）

{stringUserName,Password;

inti;

boolAllow=false;

for（i=0;i<3;i++）

{Console.Write（“请输入用户名：

”）;

UserName=Console.ReadLine（）;

Console.Write（“请输入口令：

”）;

Password=Console.ReadLine（）;

if（UserName.Trim（）.ToLower（）==”admin”‖Password==””）

{Allow=true;

break;}

else

{if（i<2）

Console.WriteLine（“你输入的用户名或密码不正确，请重新输入。

”）;}

}//for结束

if（Allow==false）

{Console.WriteLine（“非法用户，不能进入系统。

”）;

return1;}

else

{Console.WriteLine（“你好，欢迎进入系统。

”）;

return0;}

}

}

例题2（P120）：

略

5．2数组

数组类型是从系统抽象类System.Array中派生而来的引用型数据。

C#中的数组下标（又称索引）是从0开始的。

在数组中，每一个成员叫数组元素，所有数组元素具有相同的数据类型。

5.2.1数组的定义

C#中的数组维数被称为秩（Rank），数组的秩直接决定了数组的下标数。

如果一个数组的秩为1，则该数组为一维数组，如果一个数组的秩大于1，则该数组为多维数组。

在数组中数组元素的个数，叫这个维中的数组长度。

无论是一维数组还是多维数组，其下标都从0开始，结束于这个维的长度减1。

数组定义的格式：

数组类型修饰符[]数组名=new数组类型[]{数组元素初始化列表}；

例如：

1.int[]arr=newint[3];/*一维数组arr长度为3，arr[0],arr[1],arr[2]各数组元素被初始化为默认值0*/

等价于：

int[]arr;

arr=newint[3];

2.必须使用常量（可以是直接常量）定义数组的大小。

例如：

intconstArrayLength=5;

int[]myArray=newint[ArrayLength];//定义一维数组myArray长度为5

3.在定义时对数组元素初始化，这时就不用再指出数组的大小，系统自动把初始化列表中的元素个数作为数组的长度。

例如：

string[]arrLanguages=newstring[]{”c”,”c++”,”c#”};

还可写为：

string[]arrLanguages={”c”,”c++”,”c#”};

4.int[,]arr=newint[5,3];//定义二维数组arr,长度为15

5.int[,]arr={{0,1},{2,3},{4,5}};

等价于

int[,]arr=newint[3,2];

arr[0,0]=0;

arr[0,1]=1;

arr[1,0]=2;

arr[1,1]=3;

arr[2,0]=4;

arr[2,1]=5;

注意：

数组越界和类型溢出在运行时才会被发现。

5.2.2数组的使用

1.一维数组的使用

例如：

对用户输入的一个字符串，统计其中每个字母再现的次数。

假设不区分大小写。

（P123）

namespace字母个数

{

classClass1

{

staticvoidMain（string[]args）

{

int[]CharNum=newint[26];//定义数组，用于26个字母计数

intOther;//记录除字母之外的任意字符的个数

inti;//循环控制变量

chartemp;//临时变量

stringstrTest;//要检测的字符串

for（i=0;i<26;i++）

CharNum[i]=0;//CharNum数组元素均赋初值0

Other=0;

Console.WriteLine（"请输入要统计的字符串：

"）;

strTest=Console.ReadLine（）;

strTest=strTest.ToUpper（）;//转成大写字母，便于统计

Console.WriteLine（"字符出现的次数"）;

for（i=0;i

{

temp=strTest[i];//取strTest中第i个字母

if（temp>='A'&&temp<='Z'）

CharNum[temp-'A']++;//相应字母计数加1

else

Other++;

}

for（i=0;i<26;i++）

if（CharNum[i]!

=0）

Console.WriteLine（"{0}{1}",（char）（i+'a'）,CharNum[i]）;

Console.WriteLine（"Other{0}",Other）;

}

}

}

运行结果：

请输入要统计的字符串：

Madam,I’mAdam

字符出现次数

a4

d2

i1

m4

Other4

2.多维数组的使用

例如：

假设某班有50人，每名同学一次参加5门考试，要求计算每位同学的总分和每门课的全班平均分。

（P124）

namespace平均分

{

classClass1

{

staticvoidMain（string[]args）

{

constintPupil=50;//定义整型常量Pupil为50个学生

constintClass=5;//定义整型常量Class为5门课程int[,]Score={{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,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,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}};

inti,j;//循环控制变量

intSum;//存储总的分变量

int[]Aver={0,0,0,0,0};//存储各门平均成绩的一维数组

Console.WriteLine（"学号总分"）;

for（i=0;i

{

Sum=0;

for（j=0;j

{

Sum=Sum+Score[i,j];//求出第i个学生5门课总成绩

Aver[j]=Aver[j]+Score[i,j];//每门课50个学生的成绩和

}

Console.WriteLine（"No.{0}{1}",i+1,Sum）;

}

Console.WriteLine（"科目平均成绩是：

"）;

for（j=0;j

{

Aver[j]/=Pupil;//每门课的平均成绩

Console.WriteLine（"{0}",Aver[j]）;

}

}

}

}

3.用数组模拟栈操作（P125）

usingSystem;

namespace用数组模拟栈操作

{

classStack

{

privateconstintMaxLength=50;

char[]str=newchar[MaxLength];//定义字符数组，用于存储站的数据

intCurrentPos;//栈顶指针

publicStack（）//栈类构造函数

{

CurrentPos=0;//清栈

}

publicboolPush（charch）//入栈操作

{

if（CurrentPos>=MaxLength）//防止栈溢出

returnfalse;

str[CurrentPos]=ch;//字符入栈

CurrentPos++;//指针上移

returntrue;

}

publiccharPop（）//出栈操作

{

if（CurrentPos<=0）//栈为空

return'\0';//返回null

CurrentPos--;//否则，指针下移

returnstr[CurrentPos];

}

}

classTest

{

publicstaticvoidMain（）

{

stringTest;//存放要测试的字符串

inti;//循环控制变量

StackstrStack=newStack（）;//声明栈

Console.Write（"输入要测试的字符串：

"）;

Test=Console.ReadLine（）;

for（i=0;i

strStack.Push（Test[i]）;//调用入栈方法Console.Write（"输入字符串的反序是：

"）;

for（i=0;i

Console.Write（strStack.Pop（））;//调用出栈方法

Console.WriteLine（）;

}

}

}

运行结果：

输入要测试的字符串：

Hello,World.

输入字符串的反序是：

.dlroW,olleH

3.把数组作为参数（P127）

namespace用数组作参数

{

classClass1

{

staticvoidPrintArray（string[]w）//数组w作为方法的参数

{

for（inti=0;i

Console.Write（"{0}",w[i]）;

Console.WriteLine（）;

}

staticvoidMain（string[]args）

{

string[]WeekDays=newstring[]{"星期日","星期一","星期二","星期三","星期四","星期五","星期六"};

PrintArray（WeekDays）;//调用PrintArray方法，WeekDays为参数

}

}

}

运行结果:

星期日星期一星期二星期三星期四星期五星期六

作业：

编写一个控制台应用程序，它接收一个字符串，用“yes”替换字符串中所有的“no”。

5.3集合

C#中的数组只是集合类中的一种。

集合类一般处理对象列表，其功能比数组要多，这些功能是通过执行System.Collections名称空间中的接口而实现的，因此，集合的语法已经标准化了。

集合的功能可以通过接口来实现。

集合与数组相似，用来存放彼此相关的内容。

区别是，集合可以通过一个主题词访问其项目，而数组需要用户自己编写查找程序。

集合也可以通过索引访问其元素，这点并不比数组优越。

5.3.1集合的定义

如果一个类型满足所有下列条件，实现System.Ienumerable接口或实现集合模式，就称它是集合类型：

（1）类型包含一个签名GetEnumerator（）,返回结构类型（struct）、类类型、接口类型的public实例方法。

（2）类型包含的public实例方法具有签名MoveNext（）和返回类型bool。

它递增项计数器并在集合中存在更多项时返回true。

（3）类型包含一个名为Crrent的public实例属性，此属性允许读取当前值。

此属性的类型称为该集合类型的元素类型，读取时返回集合的当前元素。

例：

创建MyCollection集合

//集合MyCollection的定义

publicclassMyCollection//集合名

{

int[]items;

publicMyCollection（）//构造函数

{

items=newint[5]{12,44,33,2,50};

}

//上述集合类型的第一条，GetEnumerator（）返回结构类型

publicMyEnumeratorGetEnumerator（）

{

returnnewMyEnumerator（this）;

}

//声明集合类

publicclassMyEnumerator

{

intnIndex;

MyCollectioncollection;

publicMyEnumerator（MyCollectioncoll）

{

collection=coll;

nIndex=-1;

}

/*上述集合类型的第二条，包含public实例方法具有签名MoveNext（）和返回类型bool*/

publicboolMoveNext（）

{

nIndex++;

return（nIndex

}

/*上述集合类型的第三条，名为Crrent的public实例属性，此属性允许读取当前值。

*/

publicintCurrent

{

get

{

return（collection.items.[nIndex]）;

}

}

}

}

5.3.2集合的使用

利用foreach语句遍历集合中的每个元素，并且通过执行循环体对每一个元素进行操作。

语法格式：

foreach（数据类型变量in集合表达式）循环体

例如：

完整的C#集合范例

publicclassMyCollection//集合名

{

int[]items;

publicMyCollection（）//构造函数

{

items=newint[5]{12,44,33,2,50};

}

//上述集合类型的第一条，GetEnumerator（）返回结构类型

publicMyEnumeratorGetEnumerator（）

{

returnnewMyEnumerator（this）;

}

//声明集合类

publicclassMyEnumerator

{

intnIndex;

MyCollectioncollection;

publicMyEnumerator（MyCollectioncoll）

{

collection=coll;

nIndex=-1;

}

/*上述集合类型的第二条，包含public实例方法具有签名MoveNext（）和返回类型bool*/

publicboolMoveNext（）

{

nIndex++;