XIAOSUO 记录个人学习的足迹

摘要：尽管String类和StringBuilder类提供了一套方法用来处理基于字符串的数据，但是RegEx和它的支持类却为字符串处理任务提供了更强大的功能。字符串的处理主要包括寻找字符串中的模式（模式匹配），以及通过称为正则表达式的特殊语言来执行操作。本问主要介绍正则表达式的方法以及如果利用它们解决普通文本处理任务。 一、正则表达式概述 简单的说，正则表达式是一种可以用于文字模式匹配和替换的强有力的工具。是由一系列普通字符和特殊字符组成的能明确描述文本字符串的文字匹配模式。正则表达式并非一门专用语言，但也可以看作是一种语言，它可以让用户通过使用一系列普通字符和特殊字符构建能明确描述文本字符串的匹配模式。除了简单描述这些模式之外，正则表达式解释引擎通常可用于遍历匹配，并使用模式作为分隔符来将字符串解析为子字符串，或以智能方式替换文本或重新设置文本格式。正则表达式为解决与文本处理有关的许多常见任务提供了有效而简捷的方式。 二、使用正则表达式 为了使用正则表达式需要把RegEx类引入程序。大家可以在System.Text.RegularExpression命名空间中找到这个类。一旦把这个类导入到程序，就需要决定想要用RegEx类来做什么事情了。如果想要进行匹配，就需要使用Match类。如果打算做替换，就需要使用RegEx类的Replace方法。我们先来看一个匹配的操作： Regex reg = new Regex(the); string str = the quick brown fox jumped over the lazy dog; Match matchSet = reg.Match(str); int matchPos; if (matchSet.Success) { matchPos = matchSet.Index; Console.WriteLine(found match at position: + matchPos); } 上面程序中Match类为存储用来与正则表达式进行匹配的数据提供了方法。如果属性Success返回true，那么正则表达式在字符串中至少匹配了一条字串，否则Success返回false。程序还可以有另外一种方法来查看是否匹配成功。通过把正则表达式和目标字符串传递给IsMatch方法可以对正则表达式进行预测试。 如Regex.…… 阅读全文

摘要：一、概述 可变长度的字符串操作类。 以System.String为其数据保存和操作基础。 在字符串操作过程中减少了对象创建次数，但很多情况下仍然会有额外对象创建出来。 二、类的声明 Stringbuilder中有两个非常重要的字段m_currentThread和m_StringValue。前者保存的是Stringbuilder对象拥有者的线程id，用于判断多线程情况下操作Stringbuilder对象是否需要创造副本；后者是以个String类型的对象，用于保存Stringbuilder的实际数据对象，这就说明Stringbuilder是以System.String对象来保存和操作的。 public sealed class StringBuilder : ISerializable { internal IntPtr m_currentThread = Thread.InternalGetCurrentThread(); //对象拥有者的线程id internal volatile String m_StringValue = null; //保存stringbuilder的实际数据的对象 //other code } 三、构造函数 提供7种构造的重载形式用来构建对象，其中有一种是私有重载用于对象的序列化。其他6种重载中主要的代码结构如下 public StringBuilder(String value, int startIndex, int length, int capacity) { if (capacity0) { throw new ArgumentOutOfRangeException(capacity, String.Format(CultureInfo.CurrentCulture, Environment.GetResourceString(ArgumentOutOfRange_MustBePositive), capacity)); } if (length0) { throw new ArgumentOutOfRangeException(length, String.Format(CultureInfo.CurrentCulture, En…… 阅读全文

摘要：一、SubString方法的实现 如果理解了上一篇文章中介绍的FastAllocateString方法与wstrcpy方法，理解SubString方法的实现就会比较容易。此方法的两个重载都会先调用一个参数的校验函数InternalSubStringWithChecks。如果没有发生异常就会继续调用内部实现的核心方法InternalSubString，该方法在内部实现获取[startIndex, startIndex + length]之间的字串。具体代码如下 //返回从startIndex开始到结束的字符串 public String Substring (int startIndex) { return this.Substring (startIndex, Length-startIndex); } public String Substring (int startIndex, int length) { return InternalSubStringWithChecks(startIndex, length, false); } //采用手术室清洁策略来对参数进行检验 internal String InternalSubStringWithChecks (int startIndex, int length, bool fAlwaysCopy) { int thisLength = Length; if (startIndex0) { throw new ArgumentOutOfRangeException(startIndex, Environment.GetResourceString(ArgumentOutOfRange_StartIndex)); } if (startIndex thisLength) { throw new ArgumentOutOfRangeException(startIndex, Environment.GetResourceString(ArgumentOutOfRange_StartIndexLargerThanLength)); } if (length0) { throw new ArgumentOutOfRangeException(length, Envi…… 阅读全文

摘要：一、字符串类的概述 String类继承了IComparable、ICloneable、IConvertible、IEnumerable接口，以便调用者枚举、拷贝、转换容器中的字符。同时还继承了IComparable, IEnumerable, IEquatable，这表示源代码的编写者考虑到了对泛型的支持。如果使用C# 2.0以上标准的编译器编译代码，那么String类还需要继承这三个泛型接口。 String类是.NET Framework中最为重要的类型之一。 不可变对象，提供了多种字符串操作函数。 为StringBuilder类提供基础方法。 为了保证执行效率，String类的性能关键部分采用非托管C++代码编写： - 数据寻址：例如：get_Chars等； - 内存分配：例如：FastAllocateString等； - 内存复制，移动。 二、System.String源代码的组成 String.cs实现主要源代码，其他多个源代码文件实现辅助和基础操作功能。 托管代码部分： – unsafecharbuffer.cs / buffer.cs提供辅助数据操作； – CultureInfo.cs/CompareInfo.cs为字符串比较，大小写处理提供和文化区域相关的代码实现； – Normalization提供规格化处理。 非托管代码部分： – Ecall.cpp / ecall.h实现托管代码到非托管代码映射，FCFuncStart(gStringFuncs)部分； – Object.h实现String类的非托管结构映射和基本取值操作的功能； – Comstring.cpp实现复杂字符串操作； – Comnlsinfo.cpp/.h提供与文化区域相关的复杂字符串操作。 三、类的声明 在String类一开始定义了3个非常重要的私有变量m_arrayLength、m_stringLength和m_firstChar，这3个私有变量在非托管代码中也会拥有同样的声明。以保证托管代码到非托管代码的映射。 public sealed class String : IComparable, ICloneable, IConvertible, IEnumerable, IComparableString, IEnumerablechar, IEquatableString…… 阅读全文

摘要：字符串对大多数计算机程序而言是很普遍的，本篇文章将研究C#语言字符串的方法，分析如何使用String类，在后面的文章中还会介绍String类的具体实现。好了，我们先来看一下如果使用String类把。 一、String类常用的方法 虽然对字符串可以执行许多操作，但是只有几个操作是最常用到的，其中3个最常用方法分别是：找到字符串的字串(Substring)；确定字符串长度(Length)和确定字符在字符串中的位置(IndexOf)。我们先看一段代码，用来实现将一串字符串语句中的单词分割到数组中（C#提供了一个Split方法可以实现该功能），來看看这几个常用方法的使用。 static void Main() { string str = now is the time for all good people; Liststring words = SplitWords(str); foreach (string word in words) Console.Write(word + ); Console.ReadLine(); } public static Liststring SplitWords(string str) { string[] ws = new string[str.Length - 1]; Liststring result = new Liststring(); int pos; string word; pos = str.IndexOf( ); while (pos 0) { word = str.Substring(0, pos); result.Add(word); str = str.Substring(pos + 1, str.Length - (pos + 1)); if (pos == 1) { word = str.Substring(0, str.Length); result.Add(word); } pos = str.IndexOf( ); } return result; } 除了IndexOf为C#还提供LastIndexOf方法。IndexOf是从左向右查，LastIndexOf是从右向左查，不管是IndexOf还是LastIndexO…… 阅读全文

摘要：一、串概述 串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表，其特殊性在于串中的数据元素是一个个的字符。 串中字符的个数，称为串的长度。 不含任何字符的串称为空串，它的长度n=0，记为s=。 串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主串。 子串的第一个字符在主串中的位置叫子串的位置。例如: 串s1=David Ruff，它的长度是10，串s2=Ruff的长度是4，s2是s1的子串，s2的位置是6。 二、串的操作 1.串比较：Compare（s） 2.求子串：SubString(int index, int len) 3.求串的长度：GetLength() 4.串连接：Concat(s) 5.串定位：IndexOf(s,startpos) 6.串插入：Insert(index, s) 7.串删除：Delete(index, len) 三、串的顺序表示 串的静态存储结构即顺序存储结构是用一组地址连续的存储单元存储串的字符序列。可用高级语言的字符数组来实现。 不同的语言在用数组存放字符串时，其处理方式可能有所不同。 对串进行操作： 1.创建顺序串 步骤： a.如果给定的参数是字符数组的话，将创建一个一样大的数组，并将参数数组中的每个字符拷贝到字符串的存储空间里，即新创建的数组里。 b.如果给定的参数是SeqString类的实例的话，就将参数串所在存储空间的每个字符拷贝到新创建字符串的数组空间中。 2.求子串：SubString(int index, int len) 步骤： a.首先确定index和len的合法性，index应限定在0≤index≤主串长度-1的范围内，len应限定在0len≤主串长度-index的范围内,如果不合法的，将null返回主调程序。 b.创建一个新的字符串，并为新字符串申请的数组空间，空间大小为子串的长度len一样的大小。 c.在主串的index位置开始，将主串len个字符拷贝到子串的数组空间中。 d.将子串返回主调程序。 3.串比较：Compare(SeqString s) 步骤： a.依次将较短字符串中的每个字符与较长字串的每个字符比较，当被比较的两个字符不相等时，终止比较。 b.如果比较在中途退出，需进一步判断主串与字符串S在退出比较时所比较字符的大小…… 阅读全文

摘要：一、通过数组和首尾下标指针组成环形队列 私有部分成员如下： public class QueueT : IEnumerableT, System.Collections.ICollection { private T[] _array; private int _head; //头引用 private int _tail; //尾引用 private int _size; //元素个数 private int _version; private const int _MinimumGrow = 4; //队列能容纳元素的最低下限 private const int _GrowFactor = 200; //扩展因子，_GrowFactor/100的结果为扩展的倍数 private const int _DefaultCapacity = 4; //默认数据项容量 static T[] _emptyArray = new T[0]; //................其他部分 ｝ 二、当空间不够时，根据扩张因子决定新缓冲区大小 当数据复制到新缓冲区，带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费。 //会涉及到数据项到新缓冲区的复杂开销 //在数据写入到新缓冲区后队列会被设置成0 //原有缓冲区会被丢失 private void SetCapacity(int capacity) { Object[] newarray = new Object[capacity]; if (_size 0) { if (_head _tail) { Array.Copy(_array, _head, newarray, 0, _size); } else { Array.Copy(_array, _head, newarray, 0, _array.Length - _head); Array.Copy(_array, 0, newarray, _array.Length - _head, _tail); } } _array = newarray; _head = 0; _tail = (_size == …… 阅读全文

摘要：一、采用数组保存数据 部分私有成员如下： public class StackT : IEnumerableT, System.Collections.ICollection { private T[] _array; 　　　　　　　　　　 //stack数据项保存的数组 private int _size; 　　　　　　　　　　 //数据项的实际个数 private int _version; 　　　　　　　　　　//数据项被修改过的次数,主要用户枚举过程中对于数据的修改 private const int _defaultCapacity = 4;　 //初始stack大小 static T[] _emptyArray = new T[0]; //................其他部分 ｝ 二、当数据空间不够时，扩大1倍空间 同List类，带来O(n)的数据复制开销。最坏可能带来sizeof(T)*(n-1)的空间浪费（可以使用TrimExcess来缩紧）。 三、数据Push/Pop的复杂度均为O(1) //只有当数据项的个数小于数据实际长度的0.9倍时,系统才会收索数组 //在收索过程中会创建新的缓冲区数据,涉及到_size个数据项的复制,以及可能会引起cc启动的开销 public void TrimExcess() { int threshold = (int)(((double)_array.Length) * 0.9); if( _size threshold ) { T[] newarray = new T[_size]; Array.Copy(_array, 0, newarray, 0, _size); _array = newarray; _version++; } } public T Peek() { if (_size==0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack); return _array[_size-1]; } public T Pop() { if (_size == 0) ThrowHelper.…… 阅读全文

摘要：这篇文章是一些与栈和队列相关的算法 1.栈的push、pop序列是否一致 2.如何用一个数组实现两个栈 3.用两个栈实现队列 4.如果用一个循环数组q[num]表示队列时，该队列只有一个头引用front，不设尾引用rear，而改置计数器count用以记录队列中节点的个数。请实现出该队列的基本运算并回答此队列中能容纳的元素个数是count-1吗 1.栈的push、pop序列是否一致 输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。 比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。 解决方法：先for循环把arr1中的元素入栈，并在每次遍历时，检索arr2中可以pop的元素。如果循环结束，而stack中还有元素，就说明arr2序列不是pop序列。 static bool SequenceIsPossible(int[] arr1, int[] arr2) { Stack stack = new Stack(); for(inti = 0, j = 0; i arr1.Length; i++) { stack.Push(arr1[i]); while(stack.Count 0 (int)stack.Peek() == arr2[j]) { stack.Pop(); j++; } } return stack.Count == 0; } 2.如何用一个数组实现两个栈 网上流传着两种方法： 方法1 采用交叉索引的方法 一号栈所占数组索引为0, 2, 4, 6, 8......(K2) 二号栈所占数组索引为1，3，5，7，9 ......(K2 + 1) 算法实现…… 阅读全文

摘要：一、CPU资源的竞争问题 在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。 二、主机与外部设备之间速度不匹配的问题 以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。 三、舞伴问题 假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 分析：先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。代码如下： 四、用队列排序数据 队列也可以用来对数据进行排序。回顾计算的早期时代，那时的程序都是通过穿孔卡片录入到大型计算机内，其中每张卡片上存有单独一条程序语句。卡片用机械排序器进行排序，这种排序器采用类似箱子的结构。而我们可以用队列排序数据的方式来模拟此过程，这种排序技术被称为基数排序。基数排序在编程的指令系统中不是最快的排序方法。但是它却能说明队列的一种有趣的应用。 具体的过程与实现我会在讲排序的时候再详细介绍，现在只要知道基数排序是通过队列来实现的就行了。 五、优先队列 大…… 阅读全文