解决串的编程问题.ppt

解决串的编程问题,数据结构(C#语言版),目标,在本章中,你将学到: 识别串的特性 串的基本操作 串的存储结构 串的算法实现,学习情境用串解决以一敌百游戏的编程,问题描述 湖南卫视2008年力推的益智型节目以一敌百深受大家的欢迎。以一敌百的节目核心就是集中凸显一个人对垒一百人的智力对抗。其中，每道题由问题回答人与台下的100位来自各行各业的挑战者（也称为“快乐答人”）分别作答，回答人胜利将继续作答，而台下回答错误的挑战者将出局，由剩下的人继续比赛。回答人一路闯关胜利将抱得奖金归，如果中途落败，奖金将由剩下的挑战者们瓜分。,编写程序模拟上面的工作过程，主要要求如下： 出题，题目巳存在一个文件名为question.txt的文件中 。 依次显示题库中的每一道题目的编号、题目内容、选项，然后先由挑战者开始做答，但不显示结果。接着由问题回答人做答 。 问题回答人和挑战者都回答完毕后，显示题目正确答案，然后给出问题回答人的得分，每答对1题得100金球，答对将和剩下的挑战者继续比赛，答错所得金球将由剩下挑战者刮分。,串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表 。 串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主串。 子串的第一个字符在主串中的位置叫子串的位置。 例如: 串s1=“David Ruff“，它的长度是10，串s2=“Ruff“的长度是4，s2是s1的子串，s2的位置是6。,认识串分析串的逻辑结构,1. 串的定义,2. 串的特征,串从数据结构上来说是一种特殊的线性表，其特殊性在于串中的数据元素是一个个的字符 。,串比较：Compare（s） 求子串：SubString(int index, int len) 求串的长度：GetLength() 串连接：Concat(s) 串定位：IndexOf(s,startpos) 串插入：Insert(index, s) 串删除：Delete(index, len),认识串识别串的基本操作,串的基本操作有以下几种：,串的静态存储结构即顺序存储结构是用一组地址连续的存储单元存储串的字符序列 。可用高级语言的字符数组来实现。 不同的语言在用数组存放字符串时，其处理方式可能有所不同。,用顺序存储结构解决串的编程问题用顺序存储结构表示串,创建顺序串就是利用给定的字符数组、己有的一个字符串或者给定的长度，调用SeqString类的构造函数，在构造函数中执行下面的操作：,1. 创建顺序串,用顺序存储结构解决串的编程问题对顺序串进行操作,从主串的index位置起找长度为len的子串，要寻找子串，需要执行下面的步骤：,2.求子串：SubString(int index, int len),用顺序存储结构解决串的编程问题对顺序串进行操作,将主串中的每个字符与s中的每个字符进行比较，需要执行下面的步骤：,3.串比较：Compare(SeqString s),用顺序存储结构解决串的编程问题对顺序串进行操作,串连接就是将主串和字符串s连接生成一个新的字符串，要进行串连接，需要执行下面的步骤,4.串连接：Concat(s),用顺序存储结构解决串的编程问题对顺序串进行操作,在主串的startpos位置开始，查找子串s在主串中首次出现的位置。这里使用的是Brute-Force算法，在这个算法中，s称为模式串。具体需执行下面的步骤：,.串定位：IndexOf(SeqString s, int startpos),用顺序存储结构解决串的编程问题对顺序串进行操作,在主串的startpos位置开始，查找子串s在主串中首次出现的位置。这里使用的是Brute-Force算法，在这个算法中，s称为模式串。具体需执行下面的步骤：,.串定位：IndexOf(SeqString s, int startpos),用顺序存储结构解决串的编程问题对顺序串进行操作,串插入是指在主串的位置index处插入一个串s。如果位置符合条件，则该操作返回一个新串，新串的长度是主串的长度与串s的长度之和，新串的第1部分是该串的开始字符到第index之间的字符，第2部分是串s,第3部分是主串从index位置字符到串串的结束位置处的字符。如果位置不符合条件，则返回一个空串。,.串插入：Insert(int index, SeqString s),用顺序存储结构解决串的编程问题对顺序串进行操作,串删除是从串的第index位置起连续的len个字符的子串从主串中删除掉。如果位置和长度符合条件，则该操作返回一个新串，新串的长度是原串的长度减去len，新串的前部分是原串的开始到第index个位置之间的字符，后部分是原串从第index+len位置到原串结束的字符。如果位置和长度不符合条件，则返回一个空串。,.串删除：Delete(int index, int len),用顺序存储结构解决串的编程问题对顺序串进行操作,小结,在本章中，你已经学到： 字符串是在应用程序中使用最频繁的数据类型之一。字符串简称串，是一种特殊的线性表，其特殊性在于串的数据元素是一个个的字 ； 长度为零的串称为空串（Empty String），它不包含任何字符。仅由一个或多个空格组成的串称为空白串（Blank String）； 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号定义为子串在主串