标题

Size: px

Start display at page:

Download "标题"

卜煤宗
5 years ago
Views:

1 本章学习导读本章主要介绍串的定义及基本运算, 重点介绍串的存储结构, 基本运算与串的 C# 实现方法读者学习本章后应能掌握串的定义, 串的基本运算, 运用串来实现文本输入和输出串的定义 4.1 串的基本概念字符串在应用程序中的使用非常频繁字符串简称串, 是一种特殊的线性表, 其特殊性在于串中的数据元素是一个个的字符在事务处理程序中, 顾客的信息如姓名地址等及货物的名称产地和规格等, 都被作为字符串来处理另外, 字符串还具有自身的一些特性因此, 把字符串作为一种数据结构来研究串 ( 或字符串 )(String) 是由零个或多个字符组成的有限序列, 一般记作 : S= c0c1 cn-1 (n 0) 其中,S 是串名, 双引号作为串的定界符 ( 不是串的一部分 ), 用双引号引起来的字符序列是串值 ci(0 i n) 可以是字母数字空格或其他字符,n 为串的长度, 当 n=0 时, 称为空串 (EmptyString) 在计算串长时, 空格也应记入串的长度中, 如 S= I m astudent 的长度为主串和子串一个串中任意个连续的字符组成的子序列称为该串的子串 (Substring) 包含子串的串相应地称为主串子串的第一个字符在主串中的位置叫子串的位置如串 s= I mastudent, 它的长度是 13, 串 s1= student 的长度是 7,s1 是 s 的子串,s1 的位置是 7 如果两个串的长度相等并且对应位置的字符都相等, 则称这两个串相等而在 C# 中, 比较两个串是否相等还要看串的语言文化等信息

2 第 4 章串串的存储结构串值的存储串的存储方式取决于我们对串所进行的运算如果在程序设计语言中, 串的运算只是作为输入或输出的常量出现, 则此时只需存储该串的字符序列, 这就是串值的存储此外一个字符序列还可以赋值给一个串变量, 操作时通过串变量名访问串值由于串中的字符都是连续存储的, 而在 C# 中串具有恒定不变的特性, 即字符串一经创建, 就不能将其变长变短或者改变其中任何的字符所以, 这里不讨论串的链式存储, 也不用接口来表示串的操作同样, 把串看作是一个类, 类名为 StringDS 取名为 StringDS 是为了和 C# 自身的字符串类 String 相区别类 StringDS 只有一个字段, 即存放串中字符序列的数组 data 由于串的运算有很多, 在类 StringDS 中只包含部分基本的运算串类 StringDS 的 C# 实现如下所示 : publicclassstringds privatechar[]data; publiccharthis[intindex] get returndata[index]; publicstringds(char[]arr) data=newchar[arr.length]; // 字符数组 // 通过数组下标来访问 // 构造器, 构造一个方法 for(inti=0;i < arr.length;++i) data[i]=arr[i]; publicstringds(stringdss) for(inti=0;i < arr.length;++i) data[i]=s[i]; // 实现字符数组的赋值

3 74 数据结构 (C#) // 构造器 publicstringds(stringdss) for(inti=0;i < arr.length;++i) data[i]=s[i]; // 构造器 publicstringds(intlen) char[]arr=newchar[len]; data=arr; // 求串长 publicintgetlength() // 串比较 publicintcompare(stringdss) // 求子串 publicstringdssubstring(intindex,intlen) // 串连接 publicstringdsconcat(stringdss) // 串插入 publicstringdsinsert(intindex,stringdss) // 串删除 publicstringdsdelete(intindex,intlen) // 串定位 publicintindex(stringdss)

4 第 4 章串 75 说明 : 以上 C# 程序只是部分代码, 主要介绍在 C# 如何在一个类中通过定义一个字符数组来存储字符串, 并通过下标的方法来对该字符数组进行赋值操作具体完整的操作字符串的 C# 程序将在后面的字符串基本运算及实现仔细说明串名的存储映像串名的存储映像就是建立了串名和串值之间的对应关系的一个符号表在这个表中的项目可以依据实际需要来设置, 以能方便地存取串值为原则如 : s1= data s2= structure 假若一个单元仅存放 1 个字符, 则上面两个串的串值顺序存储如图 4-1 所示图 4-1 串 s1 和 s2 的存储状态若符号表中每行包含有串名串值的始地址尾地址, 则如图 4-2(a) 所示, 也可以不设尾地址, 而设置串名串值的始地址和串的长度值则如图 4-2(b) 所示图 4-2 符号表示例 4.3 串的基本运算及其实现串的基本运算有赋值连接求串长求子串求子串在主串中出现的位置判断两个串是否相等删除子串等在本节中, 将使用 C# 程序来介绍这些串运算 ( 串操作 ) 串的基本运算 (1)GetLength(str) 求字符串的长度 : 统计字符串 str 中字符的个数 ( 不包括 '\0 ' ), 返回字符的个数, 若 str 为空串, 则返回值为 0 (2)Compare(StringDSs) 字符串的比较 : 比较两个字符串 str1 str2 若 str1<str2, 则返回负数 ; 若 str1>str2, 则返回正数 ; 若 str1=str2, 则返回 0 (3)SubStr(intindex,intlen) 求子串 : 从主串的 index 位置起找长度为 len 的子串, 若找到, 返回该子串 ; 否则, 返回空值 NULL (4)Str_Concat(StringDSs2) 串的连接 : 把字符串 str2 接到 str1 后面,str1 最后的结尾符

5 76 数据结构 (C#) ' \0 ' 被取消返回 str1 (5)Str_Inst(intindex,StringDSs2) 字符串的插入 : 在字符串 str1 第 index 个位置之前开始, 插入字符串 str2 返回 str1 (6)Delete(intindex,intlen) 字符串的删除 : 在字符串 str 中, 删除从第 index 个字符开始的 len 个长度的子串 (7)Index(StringDSs) 字符串的定位 : 查找子串 s 在主串中首次出现的位置如果找到, 返回子串 s 在主串中首次出现的位置, 否则, 返回串的基本运算实现 1. 求串的长度求串的长度就是求串中字符的个数, 可以通过求数组 str 的长度来求串的长度求串的长度的实现如下 : publicintgetlength(str) returnstr.length; 2. 串的比较 // 通过数组的 Length 属性来返回串的长度如果两个串的长度相等并且对应位置的字符相同, 则串相等, 返回 0; 如果串 s1 对字符大于串 s2 应位置的的字符返回 1, 若小于, 则返回 -1 说明 : 需要注意, 使用 string.equals 来比较两个串是否相等的, 如,s1.Equals(s2) 返回结果为布尔值真或假而使用 string.compare 来比较字符串时, 返回值有三种情况 :<0 小于,=0 等于,>0 大于具体实现程序如下 : publicintcompare(stringdss) intlen=((this.getlength()<=s.getlength())? this.getlength():s.getlength()); inti=0; for(i=0;i < len;++i) if(this[i]! = s[i]) if(i <= len) if(this[i]< s[i]) return -1;

6 第 4 章串 77 elseif(this[i]> s[i]) return1; elseif(this.getlength()==s.getlength()) return0; elseif(this.getlength()< s.getlength()) return -1; return1; 3. 求子串从主串的 index 位置起找长度为 len 的子串, 若找到, 返回该子串, 否则, 返回一个空串具体算法实现如下 : publicstringdssubstr(intindex,intlen) //len 为子串的长度,index 开始取的位置 if((index<0) (index>this.getlength()-1) (len<0) (len>this.getlength() index)) Console.WriteLine("PositionorLengthiserror!"); returnnull; StringDSsubstr=newStringDS(len); for(inti=0;i < len;++i) substr[i]=this[i+index-1]; returnsubstr; 4. 字符串的连接 // 创建一个字符串 substr 用来存储取出的字符串连接的算法实现如下 : publicstringdsstr_concat(stringdss2) StringDSs1=newStringDS(this.GetLength()+ s2.getlength());// 连接后串的长度 for(inti=0;i<this.getlength();++i) s1.data[i]=this[i]; //s1 原来的部分

7 78 数据结构 (C#) for(intj= 0;j<s2.GetLength();++j) s1.data[this.getlength()+j]=s2[j]; // 将 s2 连接到 s1 之后 returns1; 5. 字符串的插入字符串的插入是在一个串 s1 的某个位置如 index 处插入一个串 s2 如果位置符合条件, 则该操作返回一个新串, 新串的长度是串 s1 的长度与串 s2 的长度之和, 新串的第 1 部分是该串的开始字符到第 index 之间的字符, 第 2 部分是串 s2, 第 3 部分是该串从 index 位置字符到该串的结束位置处的字符如果位置不符合条件, 则返回一个空串字符串插入的算法如下 : publicstringdsstr_inst(intindex,stringdss2) intlen=s2.getlength(); intlen2=len+this.getlength();// 插入 s2 后新串的长度 StringDSs1=newStringDS(len2); if(index<0 index>this.getlength()-1) Console.WriteLine("Positioniserror!"); returnnull; for(inti=0;i<index;++i) s1[i]=this[i]; for(inti=index;i<index+len;++i) s1[i]=s2[i-index]; for(inti=index+len;i<len2;++i) // 插入点 index 位置之前的部分 // 将 s2 字符串插入到 s1 中 s1[i]=this[i-len]; // 原字符串中 index 位置之后的部分 returns1; 6. 字符串的删除字符串删除是把一个串中从第 index 位置起连续的 len 长度个字符的子串从主串中删除掉如果位置和长度符合条件, 则该操作返回一个新串, 新串的长度是原串的长度减去 len, 新串的前部分是原串的开始到第 index 个位置之间的字符, 后部分是原串从第 index+len 位置到

8 原串结束的字符如果位置和长度不符合条件, 则返回一个空串串删除的算法实现如下 : publicstringdsdelete(intindex,intlen) 第 4 章串 79 if((index<0) (index>this.getlength()-1) (len<0) (len>this.getlength()-index)) Console.WriteLine("PositionorLengthiserror!"); returnnull; StringDSs=newStringDS(this.GetLength()-len); for(inti =0;i<index;++i) s[i]=this[i]; for(inti =index+len;i<this.getlength();++i) s[i]=this[i]; returns; 7. 字符串的定位串定位的算法实现如下 : publicintindex(stringdss) if(this.getlength()< s.getlength()) Console.WriteLine("Thereisnotstrings!"); return -1; inti=0; intlen =this.getlength()-s.getlength(); while(i<len) if(compare(s)==0) if(i <= len) returni; return -1; 在 C# 中, 一个 String 表示一个恒定不变的字符序列集合 String 类型是封闭类型, 所以,

9 80 数据结构 (C#) 它不能被其他类继承, 而它直接继承自 object 因此,String 是引用类型, 不是值类型, 在托管堆上而不是在线程的堆栈上分配空间 String 类型还继承了 IComparable ICloneable IConvertible IComparable<string> IEnumerable<char> IEnumerable 和 IEquatable< string> 等接口 String 的恒定性指的是一个串一旦被创建, 就不能将其变长变短或者改变其中任何的字符所以, 当我们对一个串进行操作时, 不能改变字符串, 如在本教材定义的 StringDS 类中, 串连接串插入和串删除等操作的结果都是生成了新串而没有改变原串 C# 也提供了 StringBuilder 类型来支持高效地动态创建字符串在 C# 中, 创建串不能用 new 操作符, 而是使用一种称为字符串驻留的机制这是因为 C # 语言将 String 看作是基元类型基元类型是被编译器直接支持的类型, 可以在源代码中用文本常量 (Literal) 来直接表达字符串当 C# 编译器对源代码进行编译时, 将文本常量字符串存放在托管模块的元数据中而当 CLR 初始化时,CLR 创建一个空的散列表, 其中的键是字符串, 值为指向托管堆中字符串对象的引用散列表就是哈希表, 关于散列表的详细介绍见 8. 4 小节当 JIT 编译器编译方法时, 它会在散列表中查找每一个文本字符串常量如果找不到, 就会在托管堆中构造一个新的 String 对象 ( 指向字符串 ), 然后将该字符串和指向该字符串对象的引用添加到散列表中 ; 如果找到了, 不会执行任何操作 C# 提供的 String 类型中的方法很多, 比如构造器有 8 个, 比较两个字符串的方法有 12 个, 连接字符串的方法有 9 个以下列出了该类型中常用的方法, 并对每个方法给出了注释关于 String 更为详细的介绍参考.NET 的有关书籍 publicsealedclassstring:icomparable,icloneable,iconvertible, IComparable<string>,IEnumerable<char>,IEnumerable,IEquatable<string> // 将串初始化为由字符数组指示的值 publicstring(char[]value); // 确定两个指定的 String 对象是否具有不同的值 publicstaticbooloperator! =(stringa,stringb); // 确定两个指定的 String 对象是否具有同一值 publicstaticbooloperator ==(stringa,stringb); // 返回对此串的引用 publicobjectclone(); // 返回与指定的串的排序情况 publicintcompareto(stringstrb); // 连接两个串 publicstaticstringconcat(stringstr0,stringstr1); // 创建一个与指定的串具有相同值的串 publicstaticstringcopy(stringstr); publicboolendswith(stringvalue,stringcomparisoncomparisontype); // 返回指定的串第一个匹配项的索引 publicintindexof(stringvalue); // 在串的指定索引位置插入一个串 publicstringinsert(intstartindex,stringvalue); // 将串的所有匹配项替换为其他指定的串 publicstringreplace(stringoldvalue,stringnewvalue);

10 第 4 章串 81 publicstringsubstring(intstartindex,intlength);// 从指定的字符位置检索子字符串 publicstringtolower();// 将串中的字符转换为小写形式 publicstringtoupper();// 将串中的字符转换为大写形式 4.4 实训项目四学生成绩管理系统实训学生成绩管理系统 1. 实训说明本实训是关于串的应用, 在本实训中主要利用串的链式存储结构, 对学生的各项记录动态的存储, 并且将结果保存在文件中, 可以调用以前的数据从而加深对串的基本存储方法和基本运算的了解, 以及简单的文件操作设计要求 : 可以完成学生数据的输入输出, 并进行简单的管理要求实现以下的基本功能模块 : (1) 输入学生成绩 ;(2) 删除学生成绩 ;(3) 显示所有学生 ;(4) 保存为文本文件 ;(5) 从文件读取完成以上模块后, 有兴趣可以考虑以下功能模块的实现 : (1) 将文件进行复制 ;(2) 进行排序 ;(3) 将学生成绩追加到文本文件 ;(4) 进行分类汇总 2. 程序分析采用链式存储方式, 要定义一个学生类 : publicclassstudent /* 定义数据结构 */ publicintno; publicdoublemath, publicdoubleenglish; publicdoublecsharp, publicdoublenetwork; publicdoubleavg,all; publicstringname; 定义以下方法函数 : (1)publicvoidShowStuInfo(); 显示学生信息 (2)publicvoidAdd(); 添加学生信息 (3)publicvoidDelete(); 删除学生信息

11 82 数据结构 (C#) (4)publicvoidSearch_no(); 查询学生信息 ( 按学号查询 ) (5)publicvoidSearch_name(); 查询学生信息 ( 按姓名查询 ) (6)publicvoidSearch_score(); 查询学生成绩 (7)publicvoidChech(); 选择菜单系统以文本文件保存学生成绩, 输入菜单项前的数组符号进入对应的操作项, 实现对应的功能 3. 程序源代码 usingsystem; // 各种 C# 包 ( 命名空间 ) 的引入 usingsystem.collections.generic; usingsystem.linq; usingsystem.text; namespace 学生信息管理 publicclassstudent publicintno; publicdoublemath,english; publicdoublecsharp,network; publicdoubleavg,all; publicstringname; publicvoidshowstuinfo() // 显示学生信息 Console.WriteLine("\n 学生信息 :"); Console.WriteLine(" 学号 :0",no); Console.WriteLine("\t 姓名 :1",name); Console.WriteLine("\t 数学 :2",math); Console.WriteLine("\t 英语 :3",english); Console.WriteLine("\t C# :4",csharp); Console.WriteLine("\t 计算机网络 :5",network); Console.WriteLine("\t 平均成绩 :6",avg); Console.WriteLine("\t 总成绩 : 7",all); Console.WriteLine(); classstu_manage // 定义学生信息管理类 intx=0;

12 第 4 章串 83 Student[]stud=newStudent[10]; // 声明一个结构体类数组, 数组名 stud publicvoidadd() //Add( ) 方法添加学生信息 Console.WriteLine(" 请输入要添加的学生信息 :"); Console.WriteLine("\n 请输入学号 :"); stud[x].no=int.parse(console.readline()); Console.WriteLine("\n 请输入姓名 :"); stud[x].name=console.readline(); Console.WriteLine("\n 数学成绩 :"); stud[x].math=double.parse(console.readline()); Console.WriteLine("\n 英语成绩 :"); stud[x].english=double.parse(console.readline()); Console.WriteLine("\nC# 成绩 :"); stud[x].csharp=double.parse(console.readline()); Console.WriteLine("\n 计算机网络成绩 :"); stud[x].network=double.parse(console.readline()); double[]inform=newdouble[]stud[x].math,stud[x].english,stud[x].csharp,stud [x].network;// 定义一个数组将输入的成绩存储 for(inti=0;i < inform.length;i++) stud[x].all += inform[i]; stud[x].avg=stud[x].all/4; stud[x].showstuinfo(); x=x+1; publicvoiddelete() intn=-1; // 删除学生信息方法 intno=int.parse(console.readline()); for(inti=0;i < x;i++) if(no==stud[i].no) n=i; for(intc=n+1;c < x;c++) stud[c - 1]=stud[c];// 交换数组索引值, 对指定元素进行删除 x=x - 1;

13 84 数据结构 (C#) publicvoidsearch_no() // 按学号查询学生信息 intn=-1; intno=int.parse(console.readline()); for(inti=0;i < x;i++) if(no==stud[i].no) n=i; stud[i].showstuinfo(); if(n==-1) Console.WriteLine(" 输入学号有误, 请重新输入!"); publicvoidsearch_name() intn=-1; stringname=console.readline(); for(inti=0;i < x;i++) if(name==stud[i].name) n=i; stud[i].showstuinfo(); if(n==-1) // 按姓名查询学生信息 Console.WriteLine(" 输入姓名有误, 请重新输入!"); publicvoidsearch_score() // 查询学生成绩 for(inti=x - 1;i >= 0;i--) // 使用冒泡法对学生成绩排序 for(intj=0;j <= i;j++)

14 if(stud[j].all < stud[j+1].all) stud[x]=stud[j]; stud[j]=stud[j+1]; stud[j+1]=stud[x]; int[]mc=newint[x]; for(inti=0;i < x;i++) mc[i]=i+1; Console.Write(mc[i]+"\t"); Console.Write(stud[i].no+"\t"); Console.Write(stud[i].name+"\t"); Console.Write(stud[i].math+"\t"); Console.Write(stud[i].english+"\t"); Console.Write(stud[i].csharp+"\t"); Console.Write(stud[i].network+"\t"); Console.Write(stud[i].avg+"\t"); Console.Write(stud[i].all+"\t"); Console.WriteLine(); publicvoidchech() // 选择菜单 // 使用循环输出排序后的学生成绩第 4 章串 85 do Console.WriteLine(" 请选择 :\n1 添加学生信息 \n2 删除学生信息 \n3 查询 ( 按学号 )\n4 查询 ( 按姓名 )\n5 查询成绩单 \n6 退出系统 "); intnumber=int.parse(console.readline()); if(number > 6 number < 1) Console.WriteLine(" 输入有误请重新输入!"); switch(number) case1: Add(); case2: Console.WriteLine(" 请输入要删除学生的学号 :");

15 86 数据结构 (C#) while(true); classprogram Delete(); case3: Console.WriteLine(" 请输入学号 :"); Search_no(); case4: Console.WriteLine(" 请输入姓名 :"); Search_name(); case5: Console.WriteLine(" 成绩单 :"); Console.WriteLine(" 名次 \t 学号 \t 姓名 \t 数学 \t 英语 \tc# \t 计算机网络 \t 平均 \t 总成绩 "); Search_score(); case6: Environment.Exit(0); Console.WriteLine("\n 是否要继续!"); staticvoidmain(string[]args) Stu_Managemyuser=newStu_Manage(); myuser.chech(); 本章小结本章主要介绍了如下一些基本概念 : 串 : 串 ( 或字符串 )(String) 是由零个或多个字符组成的有限序列主串和子串 : 一个串的任意个连续的字符组成的子序列称为该串的子串, 包含该子串的串称为主串

16 第 4 章串 87 串的静态存储结构 : 类似于线性表的顺序存储结构, 用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构堆存储结构 : 用一组空间足够大的地址连续的存储单元存放串值字符序列, 但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构串的链式存储结构 : 类似于线性表的链式存储结构, 采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构串名的存储映像 : 串名的存储映像就是建立串名和串值之间的对应关系的一个符号表除上述基本概念以外, 学生还应该了解串的基本运算字符串拷贝 ( 赋值字符串的联接求字符串的长度子串的查询字符串的比较 ) 串的静态存储结构的表示串的链式存储结构的表示串的堆存储结构的表示, 能在各种存储结构方式中求字符串的长度能在各种存储结构方式中利用 C 语言提供的串函数进行操作习题四 (1) 简述空串与空格串串变量与串常量主串与子串串名与串值每对术语的区别? (2) 两个字符串相等的充分条件是什么? (3) 串有哪几种存储结构? (4) 已知两个串 :s1= fgcdbcabcadr,s2= abc, 试求两个串的长度, 判断串 s2 是否是串 s1 的子串, 并指出串 s2 在串 s1 中的位置 (5) 已知 :s1= I mastudent,s2= student,s3= teacher, 试求下列各运算的结果 : strstr(s1,s2); strlen(s1); strcat(s2,s3); delstr(s1,4,10); insstr(str1,7,s3) (6) 设 s1= AB,s2= ABCD,s3= EFGHIJK, 试画出堆存储结构下的存储映像图 (7) 试写出将字符串 s2 中的全部字符拷贝到字符串 s1 中的算法, 不允许利用库函数 strcpy() (8) 设 s1 和 s2 是用结点大小为 1 的单链表表示的串, 试写出找出 s2 中第一个不在 s1 中出现的字符的算法 (9) 设字符串采用块链存储结构, 块链中每个结点存放 m(m=4) 个字符, 试写出实现字符串删除的算法

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,