解决串的编程问题.ppt

《解决串的编程问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、解决串的编程问题数据结构(C#语言版)目标在本章中,你将学到:识别串的特性串的基本操作串的存储结构串的算法实现学习情境——用串解决以一敌百游戏的编程[问题描述]湖南卫视2008年力推的益智型节目《以一敌百》深受大家的欢迎。《以一敌百》的节目核心就是集中凸显一个人对垒一百人的智力对抗。其中，每道题由问题回答人与台下的100位来自各行各业的挑战者（也称为“快乐答人”）分别作答，回答人胜利将继续作答，而台下回答错误的挑战者将出局，由剩下的人继续比赛。回答人一路闯关胜利将抱得奖金归，如果中途落败，奖金将由剩下的挑战者们瓜分。编写程序模拟上

2、面的工作过程，主要要求如下：出题，题目巳存在一个文件名为question.txt的文件中。依次显示题库中的每一道题目的编号、题目内容、选项，然后先由挑战者开始做答，但不显示结果。接着由问题回答人做答。问题回答人和挑战者都回答完毕后，显示题目正确答案，然后给出问题回答人的得分，每答对1题得100金球，答对将和剩下的挑战者继续比赛，答错所得金球将由剩下挑战者刮分。串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主

3、串。子串的第一个字符在主串中的位置叫子串的位置。例如:串s1="DavidRuff"，它的长度是10，串s2="Ruff"的长度是4，s2是s1的子串，s2的位置是6。认识串——分析串的逻辑结构1.串的定义2.串的特征串从数据结构上来说是一种特殊的线性表，其特殊性在于串中的数据元素是一个个的字符。串比较：Compare（s）求子串：SubString(intindex,intlen)求串的长度：GetLength()串连接：Concat(s)串定位：IndexOf(s,startpos)串插入：Insert(index,s)串删除

4、：Delete(index,len)认识串——识别串的基本操作串的基本操作有以下几种：串的静态存储结构即顺序存储结构是用一组地址连续的存储单元存储串的字符序列。可用高级语言的字符数组来实现。不同的语言在用数组存放字符串时，其处理方式可能有所不同。用顺序存储结构解决串的编程问题——用顺序存储结构表示串创建顺序串就是利用给定的字符数组、己有的一个字符串或者给定的长度，调用SeqString类的构造函数，在构造函数中执行下面的操作：1.创建顺序串用顺序存储结构解决串的编程问题——对顺序串进行操作步骤操作1如果给定的参数是字符数组的话，将

5、创建一个一样大的数组，并将参数数组中的每个字符拷贝到字符串的存储空间里，即新创建的数组里。2如果给定的参数是SeqString类的实例的话，就将参数串所在存储空间的每个字符拷贝到新创建字符串的数组空间中。从主串的index位置起找长度为len的子串，要寻找子串，需要执行下面的步骤：2.求子串：SubString(intindex,intlen)用顺序存储结构解决串的编程问题——对顺序串进行操作步骤操作1首先确定index和len的合法性，index应限定在0≤index≤主串长度-1的范围内，len应限定在0

6、ndex的范围内,如果不合法的，将null返回主调程序。2创建一个新的字符串，并为新字符串申请的数组空间，空间大小为子串的长度len一样的大小3在主串的index位置开始，将主串len个字符拷贝到子串的数组空间中4将子串返回主调程序将主串中的每个字符与s中的每个字符进行比较，需要执行下面的步骤：3.串比较：Compare(SeqStrings)用顺序存储结构解决串的编程问题——对顺序串进行操作步骤操作1依次将较短字符串中的每个字符与较长字串的每个字符比较，当被比较的两个字符不相等时，终止比较2如果比较在中途退出，需进一步判断主串与

7、字符串S在退出比较时所比较字符的大小，如果主串的字符小，返回-1，否则返回13如果比较是正常退出，则需进一步判断两个字符串的长度是否相等，如相等，返回0，否则如果主串的长度大于S的长度，返回1，否则返回-1。串连接就是将主串和字符串s连接生成一个新的字符串，要进行串连接，需要执行下面的步骤4.串连接：Concat(s)用顺序存储结构解决串的编程问题——对顺序串进行操作步骤操作1申请一块连续的可以存储两个字符串的空间2将主串中的每个字符逐个拷贝到连续空间的前部分3将字符串s逐个拷贝到主串的后面4将新生成的字符串返回给使用者在主串的s

8、tartpos位置开始，查找子串s在主串中首次出现的位置。这里使用的是Brute-Force算法，在这个算法中，s称为模式串。具体需执行下面的步骤：５.串定位：IndexOf(SeqStrings,intstartpos)用顺序存储结构解决串的编程