串

在应用程序中使用最频繁的类型是字符串。字符串简称串，是一种特殊的线性表，其特殊性在于串中的数据元素是一个个的字符。字符串在计算机的许多方面应用很广。如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据。在事务处理程序中，顾客的信息如姓名、地址等及货物的名称、产地和规格等，都被作为字符串来处理。另外，字符串还具有自身的一些特性。因此，把字符串作为一种数据结构来研究。

串(String)由 n(n≥0)字符组成的有限序列。一般记为：

S=”c1c2…cn” (n≥0)

其中， S是串名，双引号作为串的定界符，用双引号引起来的字符序列是串值。 ci（ 1≤i≤n）可以是字母、数字或其它字符， n为串的长度，当n=0 时，称为空串(Empty String)。

串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主串。子串的第一个字符在主串中的位置叫子串的位置。如串s1”abcdefg”，它的长度是 7，串s2”cdef”的长度是 4， s2是s1的子串， s2的位置是 3。

如果两个串的长度相等并且对应位置的字符都相等，则称这两个串相等。而在 C#中，比较两个串是否相等还要看串的语言文化等信息。

串的存储和代码实现

由于串中的字符都是连续存储的，而在 C#中串具有恒定不变的特性，即字符串一经创建，就不能将其变长、变短或者改变其中任何的字符。所以，这里不讨论串的链式存储，也不用接口来表示串的操作。同样，把串看作是一个类，类名为 StringDS。取名为 StringDS 是为了和 C#自身的字符串类 String 相区别。类StringDS 只有一个字段，即存放串中字符序列的数组 data。由于串的运算有很多，类 StringDS 中只包含部分基本的运算。串类 StringDS中的方法和属性:

//索引器
public char this[int index]
//求串长
public int GetLength()
//串比较
public int Compare(StringDS s)
//求子串
public StringDS SubString(int index, int len)
//串连接
public StringDS Concat(StringDS s)
//串插入
public StringDS Insert(int index, StringDS s)
//串删除
public StringDS Delete(int index, int len)
//串定位
public int Index(StringDS s)

创建一个自定义的串

using System;

namespace MyStringDS
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            MyString myStr = new MyString (new char[]{'H','e','l','l','o'});

            Console.WriteLine (myStr);

            myStr = myStr.Concat (new char[]{',','M','i','c','h','a','e','l' });

            Console.WriteLine (myStr);
            Console.WriteLine ("长度：" + myStr.GetLength ());

            MyString anotherStr = new MyString (new char[]{ 'H', 'e', 'l', 'l', 'o', ',', 'M', 'i', 'c', 'h', 'a', 'e', 'l' });
            Console.WriteLine (anotherStr);
            Console.WriteLine (myStr.Compare (anotherStr));

            Console.WriteLine (myStr.SubString (3, 5));

            MyString insertStr = new MyString (new char[]{ 'B', 'i', 'b', 'a', 'o' });
            myStr = myStr.Insert (5, insertStr);
            Console.WriteLine (myStr);

            Console.WriteLine (myStr.IndexOf ('B'));
            Console.WriteLine (myStr [3]);

            myStr = myStr.Delete (6, 5);
            Console.WriteLine (myStr);
        }
    }

    class MyString {
        private char[] chars;
        public MyString(char[] chars) {
            this.chars = chars;
        }

        public MyString() {
            this.chars = new char[0];
        }

        public char[] Chars {
            get {
                return chars;
            }
            set {
                chars = value;
            }
        }

        //索引器
        public char this[int index] { 
            get{ 
                for (int i = 0; i < chars.Length; i++) {
                    if (i == index) {
                        return chars [i];
                    }
                }
                return default(char);
            } 
        }
        //求串长
        public int GetLength() {
            return chars.Length;
        }

        //串比较
        public bool Compare(MyString s) {
            if (chars.Length != (s.GetLength())) {
                return false;
            } else {
                for (int i = 0; i < chars.Length; i++) {
                    if (chars [i] != s.Chars [i]) {
                        return false;
                    }
                }
            }
            return true;
        }

        //求子串
        public MyString SubString(int index, int len) {
            if (index + len > chars.Length) {
                Console.Write ("索引或长度越界");
                return null;
            }
            char[] newChars = new char[len];
            for (int i = 0; i < len; i++) {
                newChars [i] = chars [i + index];
            }
            MyString newMyStr = new MyString (newChars);
            return newMyStr;
        }

        //串连接
        public MyString Concat(char[] s) {
            char[] newChars = new char[chars.Length + s.Length];
            for (int i = 0; i < chars.Length; i++) {
                newChars [i] = chars [i];
            }
            for (int i = 0; i < s.Length; i++) {
                newChars [i + chars.Length] = s [i];
            }
            MyString newMyStr = new MyString (newChars);
            return newMyStr;
        }

        //串插入
        public MyString Insert(int index, MyString s) {
            char[] newChars = new char[chars.Length + s.GetLength()];
            for (int i = 0; i <= index; i++) {
                newChars [i] = chars [i];
            }
            for (int i = 0; i < s.GetLength(); i++) {
                newChars [i + index + 1] = s [i];
            }
            for (int i = index + s.GetLength() + 1; i < chars.Length + s.GetLength(); i++) {
                newChars [i] = chars [i - s.GetLength()];
            }
            MyString newMyStr = new MyString (newChars);
            return newMyStr;
        }

        //串删除
        public MyString Delete(int index, int len) {
            if (index + len > chars.Length) {
                Console.Write ("索引或长度越界");
                return null;
            }
            char[] newChars = new char[chars.Length - len];
            for (int i = 0; i <= index; i++) {
                newChars[i] = chars[i];
            }
            for (int i = index + len; i < chars.Length; i++) {
                newChars [i - len] = chars [i];
            }
            MyString newMyStr = new MyString (newChars);
            return newMyStr;
        }

        //串定位
        public int IndexOf(char s) {
            for (int i = 0; i < chars.Length; i++) {
                if(chars[i] == s) {
                    return i;
                }
            }

            return -1;
        }

        public override string ToString ()
        {
            string str = "";
            for (int i = 0; i < chars.Length; i++) {
                str += chars [i].ToString();
            }
            return str;
        }
    }
}

C#中的串

在C#中，一个String表示一个恒定不变的字符序列集合。String类型是封闭类型，所以，它不能被其它类继承，而它直接继承自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创建一个空的散列表，其中的键是字符串，值为指向托管堆中字符串对象的引用。散列表就是哈希表。当JIT编译器编译方法时，它会在散列表中查找每一个文本常量字符串。如果找不到，就会在托管堆中构造一个新的String对象（指向字符串），然后将该字符串和指向该字符串对象的引用添加到散列表中；如果找到了，不会执行任何操作。

c#中的数组

数组是一种常用的数据结构，可以看作是线性表的推广。数组作为一种数据结构，其特点是结构中的数据元素可以是具有某种结构的数据，甚至可以是数组，但属于同一数据类型。数组在许多高级语言里面都被作为固定类型来使用。

数组是n(n≥1)个相同数据类型的数据元素的有限序列。一维数组可以看作是一个线性表，二维数组可以看作是“数据元素是一维数组”的一维数组，三维数组可以看作是“数据元素是二维数组”的一维数组，依次类推。

C#支持一维数组、多维数组及交错数组（数组的数组）。所有的数组类型都隐含继承自System.Array。Array是一个抽象类，本身又继承自System.Object。所以，数组总是在托管堆上分配空间，是引用类型。任何数组变量包含的是一个指向数组的引用，而非数组本身。当数组中的元素的值类型时，该类型所需的内存空间也作为数组的一部分而分配；当数组的元素是引用类型时，数组包含是只是引用。

Array类中的常用方法

using System;
using System.Collections;
public abstract class Array : ICloneable, IList, ICollection, IEnumerable
{
    //判断 Array 是否具有固定大小。
        public bool IsFixedSize { get; }
    //获取 Array 元素的个数。
        public int Length { get; }
    //获取 Array 的秩（维数）。
        public int Rank { get; }
    //实现的 IComparable 接口，在.Array 中搜索特定元素。
        public static int BinarySearch(Array array, object value);
    //实现的 IComparable<T>泛型接口，在 Array 中搜索特定元素。
        public static int BinarySearch<T>(T[] array, T value);
    //实现 IComparable 接口，在 Array 的某个范围中搜索值。
        public static int BinarySearch(Array array, int index,
            int length, object value);
    //实现的 IComparable<T>泛型接口，在 Array 中搜索值。
        public static int BinarySearch<T>(T[] array,
            int index, int length, T value);

    //Array 设置为零、 false 或 null，具体取决于元素类型。
        public static void Clear(Array array, int index, int length);
    //System.Array 的浅表副本。

        public object Clone();
    //从第一个元素开始复制 Array 中的一系列元素
    //到另一 Array 中（从第一个元素开始）。
        public static void Copy(Array sourceArray,
            Array destinationArray, int length);

    //将一维 Array 的所有元素复制到指定的一维 Array 中。
        public void CopyTo(Array array, int index);
    //创建使用从零开始的索引、具有指定 Type 和维长的多维 Array。
        public static Array CreateInstance(Type elementType,
            params int[] lengths);

    //返回 ArrayIEnumerator。
        public IEnumerator GetEnumerator();
    //获取 Array 指定维中的元素数。
        public int GetLength(int dimension);
    //获取一维 Array 中指定位置的值。
        public object GetValue(int index);
    //返回整个一维 Array 中第一个匹配项的索引。
        public static int IndexOf(Array array, object value);
    //返回整个.Array 中第一个匹配项的索引。
        public static int IndexOf<T>(T[] array, T value);
    //返回整个一维 Array 中最后一个匹配项的索引。
        public static int LastIndexOf(Array array, object value);
    //反转整个一维 Array 中元素的顺序。
        public static void Reverse(Array array);
    //设置给一维 Array 中指定位置的元素。
        public void SetValue(object value, int index);
    //对整个一维 Array 中的元素进行排序。
        public static void Sort(Array array);
}