XIAOSUO 记录个人学习的足迹

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

摘要：一、概述 FIFO: First In, First Out（先进先出） 受限的线性表，在一端插入，在另一端删除。 二、栈的操作 1.入队列操作EnQueue (T item) ： 将值为item的新数据元素添加到队尾，队列发生变化。 2.出队列操作DeQueue ()： 将对头元素从队列中取出，队列发生变化。 3.取队头元素GetFront () ： 返回队头元素的值，队列不发生变化。 4.求队列的长度GetLength()： 返回队列中数据元素的个数。 5.判断队列是否为空IsEmpty()： 如果队列为空返回true，否则返回false。 6.清空操作Clear()： 使队列为空。 三、队列的顺序表示和实现 用一片连续的存储空间来存储队列中的数据元素，这样的队列称为顺序队列。类似于顺序栈，用一维数组来存放顺序队列中的数据元素。队头设置在最近一个己经离开队列的元素所占的位置，用front表示。队尾设置在最近一个进行入队列的元素的位置，用rear表示。根据循环队列的概念我们很容易知道队列为空的判断条件是rear = front；而队列为满时的判断条件同样也是rear = front。为了解决空队列和满队列的判断问题，我们总是留一个空位置不让起插入数据。当队列为满的条件变成rear + 1 == front。 顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出。假溢出是由于队列“队尾入队队头出队”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列。队尾指示器的加1操作：rear = (rear + 1) % maxsize。队头指示器的加1操作：front = (front + 1) % maxsize。 基本运算在顺序队列上的实现如下： public class SeqQueueT { private int maxsize; //循环顺序队列的容量 private T[] data; //数组，用于存储循环顺序队列中的数据元素 private int front; //指示最近一个己经离开队列的元素所占的位置 private int rear; //指示最近一个进行入队列的元素的位置 public T t…… 阅读全文

摘要：一、数制转换 十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单的算法是基于下列原理： N = (N div d) * d + N mod d。其中：div为整除运算，mod为求余运算。 例：(1348)10 = (2504)8，其运算过程如下： N　　　　N div 8　　　　N mod 8 1348　　　　168　　　　　　 4 168　　　　 21 　　 0 21 　　 2　　　　　　 5 2　　 0　　 　　 2 从上述运算过程可见：①从低位到高位顺序产生八进制数的各个位数；②与打印输出由高位到低位的顺序相反。 因此，将计算过程中得到的八进制数的各位顺序进栈，再按出栈序列打印输出，即可得到与输入对应的八进制数。 二、括号匹配的检验 假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即()或[([][])]等均为正确的格式，[(])或([())均为不正确的格式。 检验括号是否匹配的方法：运用“期待的急迫程度”的概念。 例：考虑下列括号序列 [　　(　　[　　]　　[　　]　　)　　] 1　　2　 3　 4　　5　 6　 7 8 分析：1.计算机接受第1个括号后，期待与之匹配的第8个括号出现。 2.获得第2个括号，此时第1个括号暂时放在一边，而急迫期待与之匹配的第7个括号出现。 3.获取第3个括号，此时又把第2个括号暂时放在一边，而急迫期待与之匹配的第4个括号出现，第3个括号的期待得到满足，消解之后，第2个括号的期待匹配又成为当前最急迫的任务了。 4.以此类推，可见，该处理过程与栈的特点吻合。 算法的思路：1.设置一个栈，顺序读入括号。 2.若是右括号，则或者使置于栈顶的最急迫期待得以消解，或则是不合法的情况。 3.若是左括号，则作为一个新的最急迫的期待压入栈中，自然使原有在栈中所有未消解的期待的急迫性降了一级。 说明：在此算法的开始和结束时，栈都应该是空的。 三、迷宫求解 计算机解迷宫的方法：“穷举求解”法，即从入口出发，顺某一方向向前探索，若能走通，则继续网前走，否则沿原路退回，换一个方向再继续探索，直到所有的通路都探索到为止。如下图为一迷宫 求一条路径算法的基本思想：假设以栈S记录当前路径，则栈顶中存放的是“当前路径上…… 阅读全文

摘要：一、概述 LIFO: Last In, First Out（后进先出） 受限的线性表，它插入和删除只能在表的一端进行 所有插入和删除操作都只能在表的一端进行，这一端叫栈顶。 最后进入栈中的数据最先被拿走。 二、栈的操作 1.初始化栈： 产生一个新的空栈。 2.入栈操作Push(T item)： 将指定类型元素data进到栈中。 3.出栈操作Pop()： 将栈中的栈顶元素取出来，并在栈中删除栈顶元素。 4.取栈顶元素GetTop()： 将栈中的顶元素取出来，栈中元素不变。 5.判断栈空IsEmpty()： 若栈为空，返回true，否则返回false。 6.清空操作Clear()： 从栈中清除所有的数据元素。 三、栈的顺序表示和实现 用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈。类似与顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1。 基本运算在顺序栈上的实现如下： public class SeqStackT { private int maxsize; //顺序栈的容量 private T[] data; //数组，用于存储顺序栈中的数据元素 private int top; //指示顺序栈的栈顶 //索引器 public T this[int index] { get { return data[index]; } set { data[index] = value; } } public int Maxsize { get { return maxsize; } set { maxsize = value; } } public int Top { get { return top; } } public SeqStack(int size) { data = new T[size]; maxsize = size; top = -1; } public void Push(T elem) { if (IsFull()) { throw new Exception(容…… 阅读全文

摘要：一、结点为LinkedListNode对象 该对象的实现如下 //在LinkedListT中LinkedListNodeT相互之间构成双向环状链表 //该双向环状链表通过内部成员next、prev来实现，但对于外部不可见 //对于外部Next、Previous表现为双向链表，首尾不构成环 public sealed class LinkedListNodeT { internal LinkedListT list; internal LinkedListNodeT next; internal LinkedListNodeT prev; internal T item; public LinkedListNode(T value) { this.item = value; } internal LinkedListNode(LinkedListT list, T value) { this.list = list; this.item = value; } public LinkedListT List { get { return list; } } public LinkedListNodeT Next { get { return next == null || next == list.head ? null : next; } } public LinkedListNodeT Previous { get { return prev == null || this == list.head ? null : prev; } } public T Value { get { return item; } set { item = value; } } internal void Invalidate() { list = null; next = null; prev = null; } } 二、外部表现为双向线性链表，内部实现实际为双向环状链表 通过LinkedListNode的实现代码我们可以知道该对象对外通过Next,Previous对next，previous包装实现（Next,Previous均为只读），首尾不相接构成环。而对内next…… 阅读全文