数据结构（C#版）串和数组

痛定思痛。 2022-03-09 09:10 199阅读 0赞

**串**

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

**串的基本概念**

串(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中的方法和属性:

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace _005_串
    {
        class StringDS
        {
            private char[] data;//用来存放字符串中的字符
    
            public StringDS(char[] array)
            {
                data = new char[array.Length];
                for(int i = 0; i < array.Length; i++)
                {
                    data[i] = array[i];
                }
            }
    
            public StringDS(string str)
            {
                data = new char[str.Length];
                for (int i = 0; i < str.Length; i++)
                {
                    data[i] = str[i];
                }
            }
    
            //根据索引访问字符的索引器
            public char this[int index]
            {
                get
                {
                    return data[index];
                }
            }
    
            public int GetLength()
            {
                return data.Length;
            }
    
            /// <summary>
            /// 如果两个字符串一样 返回0
            /// 如果当前字符串小于s 返回-1
            /// 如果当前字符串大于s 返回1
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public int Compare(StringDS s)
            {
                //取得长度更小的字符串的长度
                int len = this.GetLength() < s.GetLength() ? this.GetLength() : s.GetLength();
                int index = -1;//存储不相等的字符串的索引位置
                for(int i = 0; i < len; i++)
                {
                    if (this[i] != s[i])
                    {
                        index = i;
                        break;
                    }
                }
                if (index != -1)
                {
                    if (this[index] > s[index])
                    {
                        return 1;
                    }
                    else
                    {
                        return -1;
                    }
                }
                else
                {
                    if(this.GetLength() == s.GetLength())
                    {
                        return 0;
                    }
                    else if(this.GetLength() > s.GetLength())
                    {
                        return 1;
                    }
                    else
                    {
                        return -1;
                    }
                }
            }
    
            /// <summary>
            /// 建立一个子字符串
            /// </summary>
            /// <param name="index"></param>
            /// <param name="length"></param>
            /// <returns></returns>
            public StringDS SubString(int index, int length)
            {
                char[] newData = new char[length];
                for(int i = index; i < index + length; i++)
                {
                    newData[i - index] = data[i];
                }
                return new StringDS(newData);
            }
    
            /// <summary>
            /// 将两个字符串合并为一个字符串
            /// </summary>
            /// <param name="s1"></param>
            /// <param name="s2"></param>
            /// <returns></returns>
            public static StringDS Concat(StringDS s1,StringDS s2)
            {
                char[] newData = new char[s1.GetLength() + s2.GetLength()];
                for(int i = 0; i < s1.GetLength(); i++)
                {
                    newData[i] = s1[i];
                }
                for(int i = s1.GetLength(); i < newData.Length; i++)
                {
                    newData[i] = s2[i - s1.GetLength()];
                }
                return new StringDS(newData);
            }
    
            /// <summary>
            /// 查找子字符串在字符串中的位置
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public int IndexOf(StringDS s)
            {
                for (int i = 0; i <= this.GetLength() - s.GetLength(); i++)
                {
                    bool isEqual = true;
                    for (int j = i; j < i + s.GetLength(); j++)
                    {
                        if (this[j] != s[j - i])
                        {
                            isEqual = false;
                        }
                    }
                    if (isEqual)
                    {
                        return i;
                    }
                    else
                    {
                        continue;
                    }
                }
                return -1;
            }
        }
    }

**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);
    
    }

**练习题**

1 设 s=”I am a teacher”,i=”excellent”,r=”student”。用 StringDs类中的方法求：
    （ 1） 串 s、i、r 的长度；    14    9    7
    （ 2） S.SubString(8, 4)、i.SubString(2, 1)；    each    c
    （ 3） S.IndexOf(“tea”)、i.IndexOf(“cell”)、r.IndexOf(“den”)。    7    2    3
    
    2 串的替换操作是指：已知串 s、t、r，用 r 替换 s 中出现的所有与 t 相等的子串。写出算法，方法名为 Replace。
    
    3 已知下列字符串：
    a=”THIS”,f=”A SMPLE” c=”GOOD”,d=”NE”,b=”︼”,g=”IS”,
    s=a.Concat(b.Concat(a.SubString(3,2)).(f.SubString(2,7))),
    t=f.Replace(f.SubString(3,6),c),
    u=c.SubString(3,1).Concat(d),
    v=s.Concat(b.Concat(t.ConCat(b.Concat(u))))。
    问 s,t,v,GetLength(s),v.IndexOf(g),u.IndexOf(g)各是什么。
    
    4 设已知两个串为：
    S1=”bc cad cabcadf”,S2=”abc”。试求两个串的长度，并判断 S2 串是否是 S1 串的子串，如果 S2 是 S1 的子串，指出 S2 在 S1 中的起始位置。    
    是，起始位置为8
    
    5 已知：s=”(XYZ)+*”，t=”(X+Z)*Y”，试利用连接、求子串和替换等基本运算，将 s 转化为 t。

**练习题的答案**

**1**

StringDS s = new StringDS("I am a teacher");
                StringDS i = new StringDS("excellent");
                StringDS r = new StringDS("student");
                Console.WriteLine("s的长度为" + s.GetLength());
                Console.WriteLine("i的长度为" + i.GetLength());
                Console.WriteLine("r的长度为" + r.GetLength());
    
                StringDS s1 = s.SubString(8, 4);
                Console.WriteLine(s1.ToString());
    
                StringDS i1 = i.SubString(2, 1);
                Console.WriteLine(i1.ToString());
    
                Console.WriteLine(s.IndexOf(new StringDS("tea")));
                Console.WriteLine(i.IndexOf(new StringDS("cell")));
                Console.WriteLine(r.IndexOf(new StringDS("den")));

![20190316173404285.png][]

**2**

public StringDS Replace(StringDS s, StringDS t, StringDS r)
            {
                int temp = s.IndexOf(t); //查找t字符串在s中的位置 
                if (temp != -1)  //s中有与t相似的字串
                {
                    StringDS s1 = s.SubString(0, temp);
                    StringDS s2 = s.SubString(temp + t.GetLength(), s.GetLength() - (temp + t.GetLength()));
                    s1 = s1.Concat(s1, r);
                    s1 = s1.Concat(s1, s2);
                    return (s1.Replace(s1, t, r));
                }
                return s;
            }

验证结果

StringDS s = new StringDS("ababa");
                StringDS t = new StringDS("aba");
                StringDS r = new StringDS("d");
    
                StringDS temp = new StringDS("");
                temp = temp.Replace(s, t, r);
                Console.WriteLine(temp.ToString());

![20190316173631842.png][]

StringDS s = new StringDS("abababbaba");
                StringDS t = new StringDS("aba");
                StringDS r = new StringDS("d");
    
                StringDS temp = new StringDS("");
                temp = temp.Replace(s, t, r);
                Console.WriteLine(temp.ToString());

![20190316173724635.png][]

[20190316173404285.png]: /images/20220309/be79e184f71b40f5a7022bc77ed9b7e0.png
[20190316173631842.png]: /images/20220309/5a2659e38e3345d489b08bf19e5ff284.png
[20190316173724635.png]: /images/20220309/37308be7a1584c538849cbcf388273ed.png