13 字符串与整数集合

知识点：

1. 字符串

我们古人没有电影电视，没有游戏网络，所以文人们就会想出一些文字游戏来娱乐。比如宋代的李禺写了这样一首诗：“枯眼望遥山隔水，往来曾见几心知？壶空怕酌一杯酒，笔下难成和韵诗。途路阻人离别久，讯音无雁寄回迟。孤灯守夜长寥寂，夫忆妻兮父忆儿。”显然这是老公想念老婆和儿子的诗句。曾经和妻儿在一起，享受天伦之乐，现在一个人长久没有回家，也不见书信返回，望着油灯想念亲人，能不伤感吗？

可仔细一读发现，这首诗竟然可以倒过来读：“儿忆父兮妻忆夫，寂寥长夜守灯孤。迟回寄雁无音讯，久别离人阻路途。诗韵和成难下笔，酒杯一酌怕空壶。知心几见曾来往，水隔山遥望眼枯。”这表达了妻子对丈夫的思念。老公离开好久，路途遥远，难以相见。写信不知道写什么，独自喝酒也没什么兴致。只能和儿子夜夜守在家里一盏孤灯下，苦等老公的归来。

这种诗叫做回文诗。它是一种可以倒读或反复回旋阅读的诗体。刚才这首就是正读是丈夫思念妻子，倒读是妻子思念丈夫的古诗。是不是感觉很奇妙呢？
在英文单词中，同样有神奇的地方。“即使是 lover 也有个 over，即使是 friend 也有个 end，即使是 believe 也有个 lie。”你会发现，本来不相干，甚至对立的两个词，却有某种神奇的联系。这可能是创造这几个单词的智者们也没有想到的问题。

今天我们就要来谈谈这些单词或句子组成字符串的相关问题。

1.1 串的定义与操作

（1）串的相关定义

• 串（string）：由零个或多个字符组成的有限序列，又名字符串，记为S=“c1c2...cn”。
• 串的长度：串中包含字符的个数。
• 空串（null string）：长度为零的串。直接用双引号""表示，在C#中也可用string.Empty来表示。

还有一些概念需要解释：

• 空白串：由一个或多个空格组成的串。
• 子串与主串：串中任意连续字符组成的子序列，称为该串的子串。相应的包含子串的串称为主串，即子串是主串的一部分。
• 子串在主串中的位置：子串在主串中第一次出现时，子串第一个字符在主串中的序号。

例如：

A = “this is a string”; 
B = “is”;
// B在A中的位置为2。

• 串相等：长度相等且对应位字符相同。

（2）串的操作

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，也就是串中的元素都是字符。因此，对于串的基本操作与线性表是有很大差别的。

• 线性表关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素。
• 串关注的是它子串的应用问题，如查找子串位置，得到指定位置的子串、替换子串等操作。

关于串的基本操作如下：

• 获取串的长度
• 获取或设置指定索引处的字符
• 在指定位置插入子串
• 在指定位置移除给定长度的子串
• 在指定位置取子串
• 当前串的拷贝
• 串连接
• 串的匹配
• 填充字符串
• 去除两边空格

比如 C# 中，字符串操作还有ToLower()转小写、ToUpper()转大写等比较方便的操作，它们其实就是前面这些基本操作的扩展函数。

namespace LinearStruct
{/// <summary>/// 串的抽象数据类型/// </summary>public interface IString{/// <summary>/// 获取串的长度/// </summary>int Length { get; }/// <summary>/// 获取或设置指定索引处的字符/// </summary>/// <param name="index">要获取或设置的字符从零开始的索引</param>/// <returns>指定索引处的字符</returns>char this[int index] { get; set; }/// <summary>/// 在指定位置插入子串/// </summary>/// <param name="startIndex">插入的位置</param>/// <param name="s">插入的子串</param>/// <returns>插入串后得到的新串</returns>IString Insert(int startIndex, IString s);/// <summary>/// 在指定位置移除子串/// </summary>/// <param name="startIndex">移除的位置</param>/// <param name="count">移除的长度</param>/// <returns>移除后得到的新串</returns>IString Remove(int startIndex, int count);/// <summary>/// 在指定位置取子串/// </summary>/// <param name="startIndex">取子串的位置</param>/// <param name="count">子串的长度</param>/// <returns>取得的子串</returns>IString SubString(int startIndex, int count);/// <summary>/// 当前串的拷贝/// </summary>/// <returns>当前串的拷贝</returns>IString Clone();/// <summary>/// 串连接/// </summary>/// <param name="s">在尾部要连接的串</param>/// <returns>连接后得到的新串</returns>IString Concat(IString s);/// <summary>/// 串的匹配/// </summary>/// <param name="value">要匹配的子串</param>/// <param name="startIndex">串匹配的开始位置</param>/// <returns>子串在主串中的位置,不存在返回-1.</returns>int IndexOf(IString value, int startIndex = 0);/// <summary>/// 填充字符串/// </summary>/// <param name="totalWidth">结果字符串中的字符数</param>/// <param name="paddingChar">填充字符</param>/// <returns>如果totalWidth小于此实例的长度，则为与此实例相同的新IString。</returns>IString PadLeft(int totalWidth, char paddingChar);/// <summary>/// 去掉两端的空格/// </summary>/// <returns>从当前对象的开始和末尾移除所有空白字符后保留的字符串。</returns>IString Trim();}
}

1.2 串的存储与实现

串的存储结构与线性表相同，分为两种：

• 顺序存储：char类型的数组。由于数组是定长的，就存在一个预定义的最大串长度，它规定在串值后面加一个不计入串长度的结束符，比如’\0’来表示串值的终结。
• 链式存储：SlinkList<char> （浪费存储空间）

using System;namespace LinearStruct
{/// <summary>/// 串抽象数据类型的实现--顺序串/// </summary>public class SeqString : IString{protected readonly char[] CStr; //字符串以'\0'结束/// <summary>/// 初始化SeqString类的新实例/// </summary>public SeqString(){CStr = new char[] { '\0' };}/// <summary>/// 初始化SeqString类的新实例/// </summary>/// <param name="s">初始字符串</param>public SeqString(string s){if (s == null)throw new ArgumentNullException();int len = s.Length;CStr = new char[len + 1];for (int i = 0; i < len; i++){CStr[i] = s[i];}CStr[len] = '\0';}/// <summary>/// 初始化SeqString类的新实例(只能在类的内部使用)/// </summary>/// <param name="length">串的长度</param>protected SeqString(int length){if (length < 0)throw new ArgumentOutOfRangeException();CStr = new char[length + 1];CStr[length] = '\0';}/// <summary>/// 获取串的长度/// </summary>public int Length{get{int i = 0;while (CStr[i] != '\0')i++;return i;}}/// <summary>/// 获取或设置指定索引处的字符/// </summary>/// <param name="index">要获取或设置的字符从零开始的索引</param>/// <returns>指定索引处的字符</returns>public char this[int index]{get{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();return CStr[index];}set{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();CStr[index] = value;}}/// <summary>/// 在指定位置插入子串/// </summary>/// <param name="startIndex">插入的位置</param>/// <param name="s">插入的子串</param>/// <returns>插入串后得到的新串</returns>public IString Insert(int startIndex, IString s){if (s == null)throw new ArgumentNullException();if (startIndex < 0 || startIndex > Length)throw new ArgumentOutOfRangeException();int len1 = Length;int len2 = s.Length;SeqString str = new SeqString(len1 + len2);for (int i = 0; i < startIndex; i++){str.CStr[i] = CStr[i]; //注意str[i]直接使用是错误的}for (int i = 0; i < len2; i++){str.CStr[i + startIndex] = s[i];}for (int i = startIndex; i < len1; i++){str.CStr[i + len2] = CStr[i];}return str;}/// <summary>/// 串连接/// </summary>/// <param name="s">在尾部要连接的串</param>/// <returns>连接后得到的新串</returns>public IString Concat(IString s){if (s == null)throw new ArgumentNullException();return Insert(Length, s);}/// <summary>/// 串连接运算符的重载/// </summary>/// <param name="s1">第一个串</param>/// <param name="s2">第二个串</param>/// <returns>连接后得到的新串</returns>public static SeqString operator +(SeqString s1, SeqString s2){if (s1 == null || s2 == null)throw new ArgumentNullException();return s1.Concat(s2) as SeqString;}/// <summary>/// 在指定位置移除子串/// </summary>/// <param name="startIndex">移除的位置</param>/// <param name="count">移除的长度</param>/// <returns>移除后得到的新串</returns>public IString Remove(int startIndex, int count){if (startIndex < 0 || startIndex > Length - 1)throw new ArgumentOutOfRangeException();if (count < 0)throw new ArgumentOutOfRangeException();int len = Length;int left = len - startIndex; //最多移除字符个数count = (left < count) ? left : count; //实际移除字符个数SeqString str = new SeqString(len - count);for (int i = 0; i < startIndex; i++){str.CStr[i] = CStr[i];}for (int i = startIndex + count; i < len; i++){str.CStr[i - count] = CStr[i];}return str;}/// <summary>/// 在指定位置取子串/// </summary>/// <param name="startIndex">取子串的位置</param>/// <param name="count">子串的长度</param>/// <returns>取得的子串</returns>public IString SubString(int startIndex, int count){if (startIndex < 0 || startIndex > Length - 1)throw new ArgumentOutOfRangeException();if (count < 0)throw new ArgumentOutOfRangeException();int left = Length - startIndex; //取子串最大长度count = (left < count) ? left : count; //子串实际长度SeqString str = new SeqString(count);for (int i = 0; i < count; i++)str.CStr[i] = CStr[i + startIndex];return str;}/// <summary>/// 当前串的拷贝/// </summary>/// <returns>当前串的拷贝</returns>public IString Clone(){int len = Length;SeqString str = new SeqString(len);for (int i = 0; i < len; i++)str.CStr[i] = CStr[i];return str;}/// <summary>/// 填充字符串/// </summary>/// <param name="totalWidth">结果字符串中的字符数</param>/// <param name="paddingChar">填充字符</param>/// <returns>/// 如果totalWidth小于此实例的长度，则为与此实例相同的新IString。/// </returns>/// <remarks>/// 异常:/// System.ArgumentOutOfRangeException:totalWidth 小于零。/// </remarks>public IString PadLeft(int totalWidth, char paddingChar){if (totalWidth < 0)throw new ArgumentOutOfRangeException();int len = Length;if (len >= totalWidth)return Clone();SeqString result = new SeqString(totalWidth);int left = totalWidth - len;for (int i = 0; i < left; i++){result.CStr[i] = paddingChar;}for (int i = 0; i < len; i++){result.CStr[i + left] = CStr[i];}return result;}/// <summary>/// SeqString类的输出字符串/// </summary>/// <returns>SeqString类的输出字符串</returns>public override string ToString(){string str = string.Empty;for (int i = 0, len = Length; i < len; i++)str += CStr[i];return str;}/// <summary>/// 串的匹配/// </summary>/// <param name="value">要匹配的子串</param>/// <param name="startIndex">匹配的起始位置</param>/// <returns>子串在主串中的位置,不存在返回-1.</returns>public int IndexOf(IString value, int startIndex = 0){if (value == null || value.Length == 0)throw new Exception("匹配字符串为null或空.");if (startIndex < 0 || startIndex > value.Length - 1)throw new ArgumentOutOfRangeException();int len1 = Length;int len2 = value.Length;for (int i = startIndex; i <= len1 - len2; i++){if (CStr[i] == value[0]){int j;for (j = 1; j < len2; j++){if (CStr[j + i] != value[j])break;}if (j == len2)return i;}}return -1;}/// <summary>/// 移除所有前导空白字符和尾部空白字符。/// </summary>/// <returns>从当前对象的开始和末尾移除所有空白字符后保留的字符串。</returns>public IString Trim(){//返回移除所有前导空白字符和尾部空白字符后保留的字符串.int left, right;int len = Length;for (left = 0; left < len; left++){if (CStr[left] != ' ')break;}if (left == len)return new SeqString();for (right = len - 1; right >= 0; right--){if (CStr[right] != ' ')break;}return SubString(left, right - left + 1);}}
}

例子：

class Program
{static void Main(string[] args){string S = "teacher and student all like tea.";IString str = new SeqString(S);Console.WriteLine("原字符串:{0}", str);// 原字符串: teacher and student all like tea.IString str2 = str;IString str3 = str.Clone();str2[0] = 'm';Console.WriteLine("没调用Clone方法:{0}", str);// 没调用Clone方法: meacher and student all like tea.Console.WriteLine("调用Clone方法:{0}", str3);// 调用Clone方法: teacher and student all like tea.str = new SeqString(S);IString str4 = new SeqString("mother ");Console.WriteLine(str.Insert(0, str4));// mother teacher and student all like tea.Console.WriteLine(str.Insert(3, str4));// teamother cher and student all like tea.Console.WriteLine(str.Remove(3, 2));// teaer and student all like tea.Console.WriteLine(str.Remove(3, 10));// teatudent all like tea.Console.WriteLine(str.Concat(str4));// teacher and student all like tea.motherConsole.WriteLine((SeqString) str4 + (SeqString) str);// mother teacher and student all like tea.Console.WriteLine(str.SubString(3, 0));//Console.WriteLine(str.SubString(3, 4));// cherConsole.WriteLine(str.SubString(3, 10));// cher and sIString parS1 = new SeqString("ea");IString parS2 = new SeqString("hk");Console.WriteLine(str.IndexOf(parS1));// 1Console.WriteLine(str.IndexOf(parS2));// -1IString str5 = new SeqString("   a  ");Console.WriteLine(str5.Length);// 6Console.WriteLine(str5.Trim().Length);// 1}

1.3 C# 中的字符串

字符串为C#语言中一种默认的数据类型，该种类型提供了大量的方法以供程序员使用。

C# 中存在两种字符串，一种是不可变字符的字符串（string）、另一种是可变字符的字符串（StringBuilder）。

例子：不可变字符串

class Program
{static void Main(string[] args){string str = "This is a string";string substr = str.Substring(0, 3);Console.WriteLine(substr);// Thistring insertstr = str.Insert(3, "InsertString");Console.WriteLine(insertstr);// ThiInsertStrings is a stringstring removestr = str.Remove(3, 4);Console.WriteLine(removestr);// Thi a stringint length = str.Length;Console.WriteLine(length);// 16bool flag1 = (str == "This is a String") ? true : false;Console.WriteLine(flag1);// Falsebool flag2 = (str != "This is a String") ? true : false;Console.WriteLine(flag2);// Truestring catstr = str + "and other string";Console.WriteLine(catstr);// This is a stringand other stringint index = str.IndexOf("is");Console.WriteLine(index);// 2string replacestr = str.Replace("is", "IS");Console.WriteLine(replacestr);// ThIS IS a stringchar c = str[3];Console.WriteLine(c);// s// str[3] = 'c';// 错误  CS0200 无法为属性或索引器“string.this[int]”赋值 - 它是只读的}
}

例子：可变字符串

class Program
{static void Main(string[] args){StringBuilder strb = new StringBuilder("abcdef");strb[0] = 'M';Console.WriteLine(strb);// Mbcdef}
}

2. 整数集合

2.1 整数集合的定义与操作

（1）整数集合的定义

由若干互不相同的正整数组成的集合，其中全集为 0 至 MaxRange，MaxRange 为构成该集合元素的最大值。

（2）整数集合的操作

• 向集合中添加元素
• 删除集合中的元素
• 判断元素是否属于该集合
• 得到集合中的所有元素
• 求两个集合的并集
• 求两个集合的交集
• 求两个集合的差集
• 求集合的补集

namespace LinearStruct
{/// <summary>/// 集合的抽象数据类型/// </summary>/// <typeparam name="T">集合元素的类型</typeparam>public interface ISet<T>{/// <summary>/// 向集合中添加元素/// </summary>/// <param name="elt">要插入到集合的元素</param>void Insert(T elt);/// <summary>/// 删除集合中的元素/// </summary>/// <param name="elt">要删除的集合元素</param>void Remove(T elt);/// <summary>/// 判断元素是否属于该集合/// </summary>/// <param name="elt">要判断的集合元素</param>/// <returns>若属于该集合返回true,否则返回false.</returns>bool IsMember(T elt);/// <summary>/// 得到集合中的所有元素/// </summary>/// <returns>表示集合中所有元素的字符串.</returns>string GetElements();/// <summary>/// 求两个集合的并集/// </summary>/// <param name="b">与其求并的集合</param>/// <returns>两个集合的并集</returns>ISet<T> Union(ISet<T> b);/// <summary>/// 求两个集合的交集/// </summary>/// <param name="b">与其求交的集合</param>/// <returns>两个集合的交集</returns>ISet<T> Intersect(ISet<T> b);/// <summary>/// 求两个集合的差集/// </summary>/// <param name="b">与其求差的集合</param>/// <returns>两个集合的差集</returns>ISet<T> DiffSet(ISet<T> b);/// <summary>/// 求集合的补集/// </summary>/// <returns>集合的补集</returns>ISet<T> Complement();}
}

2.2 整数集合的存储与实现

（1）利用数组进行实现

若整数集合为$A_n=\{0,1,2,\cdots ,n-1\}$，则其子集也必须存放在长度为$n$的数组中。

• 全集：uint[] A = new uint[n]; 元素全部赋值1。
• 空集为：uint[] A = new uint[n]; 元素全部赋值0。

例子：

$MaxRange=7$

$I=\{0,1,2,3,4,5,6,7\},A=\{0,5,7\},B=\{2,5,6\}$

（2）利用位运算进行实现

例子：

$MaxRange=7$

$I=\{0,1,2,3,4,5,6,7\},A=\{0,5,7\},B=\{2,5,6\}$

using System;namespace LinearStruct
{/// <summary>/// 用整数集合实现集合的抽象数据类型/// </summary>public class IntSet : ISet<uint> //uint 32位无符号整数{private readonly uint[] _bitSet;//位数组/// <summary>/// 获取整数集合中的最大元素,全集为0至MaxRange/// </summary>public uint MaxRange { get; }/// <summary>/// 初始化IntSet类的新实例/// </summary>/// <param name="maxRge">整数集合中的最大元素</param>public IntSet(uint maxRge){MaxRange = maxRge;_bitSet = new uint[MaxRange / 32 + 1];for (int i = 0; i < _bitSet.Length; i++){_bitSet[i] = 0;//当前集合为空集}}/// <summary>/// 获取元素在位数组中的索引号/// </summary>/// <param name="elt">获取在位数组中索引号的元素</param>/// <returns>元素在位数组中的索引号</returns>private uint ArrayIndex(uint elt){if (elt > MaxRange)throw new ArgumentOutOfRangeException();return elt / 32;}/// <summary>/// 获取元素对应位置的整数/// </summary>/// <param name="elt">获取对应位置整数的元素</param>/// <returns>元素对应位置的整数</returns>private uint BitMask(uint elt){if (elt > MaxRange)throw new ArgumentOutOfRangeException();return (uint)Math.Pow(2, elt % 32);}/// <summary>/// 向集合中添加元素/// </summary>/// <param name="elt">要插入到集合的元素</param>public void Insert(uint elt){if (elt > MaxRange)throw new ArgumentOutOfRangeException();_bitSet[ArrayIndex(elt)] |= BitMask(elt);}/// <summary>/// 删除集合中的元素/// </summary>/// <param name="elt">要删除的集合元素</param>public void Remove(uint elt){if (elt > MaxRange)throw new ArgumentOutOfRangeException();_bitSet[ArrayIndex(elt)] &= ~BitMask(elt);}/// <summary>/// 判断元素是否属于该集合/// </summary>/// <param name="elt">要判断的集合元素</param>/// <returns>若属于该集合返回true,否则返回false.</returns>public bool IsMember(uint elt){if (elt > MaxRange)return false;uint i = _bitSet[ArrayIndex(elt)] & BitMask(elt);return i != 0;}/// <summary>/// 获取对应二进制字符串/// </summary>/// <returns>对应二进制字符串</returns>public string GetBitString(){string temp = string.Empty;for (int i = 0; i < _bitSet.Length; i++){temp = Convert.ToString(_bitSet[i], 2).PadLeft(32, '0') + temp;}return temp.Remove(0, 32 - (int)(MaxRange % 32 + 1));}/// <summary>/// 得到集合中的所有元素/// </summary>/// <returns>表示集合中所有元素的字符串.</returns>public string GetElements(){string s = GetBitString();string temp = string.Empty;int j = 0;for (int i = s.Length - 1; i >= 0; i--){if (s[i] == '1')temp += j + " ";j++;}return temp.Trim();}/// <summary>/// 求两个集合的并集/// </summary>/// <param name="b">与其求并的集合</param>/// <returns>两个集合的并集</returns>public IntSet Union(IntSet b){if (b == null)throw new ArgumentNullException();if (b.MaxRange != MaxRange)throw new Exception("两个集合范围不同.");IntSet temp = new IntSet(MaxRange);for (int i = 0; i < _bitSet.Length; i++){temp._bitSet[i] = _bitSet[i] | b._bitSet[i];}return temp;}/// <summary>/// 求两个集合的交集/// </summary>/// <param name="b">与其求交的集合</param>/// <returns>两个集合的交集</returns>public IntSet Intersect(IntSet b){if (b == null)throw new ArgumentNullException();if (MaxRange != b.MaxRange)throw new Exception("两个集合范围不同.");IntSet temp = new IntSet(MaxRange);for (int i = 0; i < _bitSet.Length; i++){temp._bitSet[i] = _bitSet[i] & b._bitSet[i];}return temp;}/// <summary>/// 求两个集合的差集/// </summary>/// <param name="b">与其求差的集合</param>/// <returns>两个集合的差集</returns>public IntSet DiffSet(IntSet b){if (b == null)throw new ArgumentNullException();if (MaxRange != b.MaxRange)throw new Exception("两集合范围不同.");IntSet temp = new IntSet(MaxRange);for (int i = 0; i < _bitSet.Length; i++){temp._bitSet[i] = _bitSet[i] & (~b._bitSet[i]);}return temp;}/// <summary>/// 求集合的补集/// </summary>/// <returns>集合的补集</returns>public IntSet Complement(){IntSet temp = new IntSet(MaxRange);for (int i = 0; i < _bitSet.Length; i++){temp._bitSet[i] = ~_bitSet[i];}return temp;}ISet<uint> ISet<uint>.Union(ISet<uint> b){return Union(b as IntSet);}ISet<uint> ISet<uint>.Intersect(ISet<uint> b){return Intersect(b as IntSet);}ISet<uint> ISet<uint>.DiffSet(ISet<uint> b){return DiffSet(b as IntSet);}ISet<uint> ISet<uint>.Complement(){return Complement();}}
}

例子：

class Program
{static void Main(string[] args){IntSet setA = new IntSet(33);IntSet setB = new IntSet(33);setA.Insert(5);setA.Insert(30);setA.Insert(23);setB.Insert(5);setB.Insert(24);setB.Insert(9);Console.WriteLine("A集合:{0};{1}", setA.GetBitString(), setA.GetElements());//A集合: 0001000000100000000000000000100000; 5 23 30Console.WriteLine("B集合:{0};{1}", setB.GetBitString(), setB.GetElements());// B集合: 0000000001000000000000001000100000; 5 9 24IntSet setC = setA.Union(setB);Console.WriteLine("A并B :{0}:{1}", setC.GetBitString(), setC.GetElements());// A并B: 0001000001100000000000001000100000:5 9 23 24 30setC = setA.Intersect(setB);Console.WriteLine("A交B :{0}:{1}", setC.GetBitString(), setC.GetElements());// A交B: 0000000000000000000000000000100000:5setC = setA.DiffSet(setB);Console.WriteLine("A差B :{0}:{1}", setC.GetBitString(), setC.GetElements());// A差B: 0001000000100000000000000000000000:23 30setC = setA.Complement();Console.WriteLine("A的补:{0}:{1}", setC.GetBitString(), setC.GetElements());// A的补: 1110111111011111111111111111011111:0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16// 17 18 19 20 21 22 24 25 26 27 28 29 31 32 33}
}

2.3 C# 中整数集合的应用

namespace System.Drawing
{//指定应用到文本的字形信息。public enum FontStyle{Regular = 0, // 普通文本。Bold = 1, // 加粗文本。 Italic = 2, // 倾斜文本。Underline = 4, // 带下划线的文本。Strikeout = 8, // 中间有直线通过的文本。}
}

例子：

FontStyle fs = FontStyle.Bold | FontStyle.Strikeout;
Font fnt = new Font("宋体", 12f, fs);
this.label1.Font = fnt;