用顺序存储解决串的编程问题

落日映苍穹つ 2021-09-18 09:22 279阅读 0赞

用顺序存储解决串的编程问题:

串即字符串，是由0个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。一般记为：s="a1,a2,...,an" (n>=0)

n为串的长度，当n=0时，称为空串。

串中任意个连续的字符组成的子序列，称为该串的子串（substring），包含子串的串，相应的称为主串，串的第1个字符，在主串中的位置，叫子串的位置。

串从数据结构上来说是一种特殊的线性表，其特殊性在于串中的数据元素是一个个的字符，但是串的基本操作和线性表的基本操作相比却有很大的不同，线性表上的操作主要是针对线性表中的某个数据元素进行的，而串上的操作主要是针对串的整体或串的某一部分子串上进行的。

串是一种特殊的线性表，所以线性表的两种存储结构，顺序存储结构和链式存储结构也同样适用于串。

**重难点：串定位，串插入**

using System;
    
    namespace 用顺序存储解决串的编程问题
    {
        class Program
        {
            static void Main(string[] args)
            {
            }
        }
    
        interface IString<T>
        {
            int Compare(T s);//串比较
            T SubString(int index, int len);//求子串
            int GetLength();//求串的长度
            T Concat(T s);//串连接
            int IndexOf(T s, int startpos);//串定位
            T Insert(int index, T s);//串插入
            T Delete(int index, int len);//串删除
        }
    
        class SeqString : IString<SeqString>
        {
            private char[] data;//字符数组
    
            public char this[int index]//索引器。必须是这种索引器，否则构造函数中的s[i]会报错
            {
                get { return data[index]; }
                set { data[index] = value; }
            }
    
            //构造函数
            public SeqString (int len)
            {
                data = new char[len];
            }
            public SeqString (SeqString s)
            {
                data = new char[s.GetLength()];
                for (int i = 0; i < s.GetLength (); i++)
                {
                    data[i] = s[i];
                }
            }
            public SeqString (char[] arr)
            {
                data = new char[arr.Length];
                for (int i = 0; i < arr .Length ; i++)
                {
                    data[i] = arr[i];
                }
            }
    
            /// <summary>
            /// 求串长。返回串中字符的个数
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return data.Length;
            }
    
            /// <summary>
            /// 求子串。从主串的index位置起找长度为len的子串。0<=index<=主串长度-1。0<len<=主串长度-index
            /// </summary>
            /// <param name="index"></param>
            /// <param name="len"></param>
            /// <returns></returns>
            public SeqString SubString(int index, int len)
            {
                if((index <0)||(index >this .GetLength ()-1)||(len <=0)||(len>this .GetLength() -index))
                {
                    Console.WriteLine("Position or length is error");
                    return null;
                }
                SeqString s = new SeqString(len);
                for (int i = 0; i < len ; i++)
                {
                    s[i] = this[i + index];
                }
                return s;
            }
    
            /// <summary>
            /// 串连接。将一个串和另外一个串连接成一个串，其结果返回一个新串，新串的长度是两个串的长度之和，新串的前部分是原串，长度为原串的长度，新串的后部分是串S,长度为串S的长度
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public SeqString Concat(SeqString s)
            {
                SeqString s1 = new SeqString(this.GetLength() + s.GetLength());
                for (int i = 0; i < this .GetLength (); i++)
                {
                    s1.data[i] = this.data[i];
                }
                for (int j = 0; j < s.GetLength (); j++)
                {
                    s1.data[this.GetLength() + j] = s[j];
                }
                return s1;
            }
    
            /// <summary>
            /// 串删除。串删除是从串的第index位置起连续的len个字符的子串从主串中删除掉
            /// </summary>
            /// <param name="index"></param>
            /// <param name="len"></param>
            /// <returns></returns>
            public SeqString Delete(int index, int len)
            {
                if ((index < 0) || (index > this.GetLength() - 1) || (len <= 0) || (len > this.GetLength() - index))
                {
                    Console.WriteLine("Position or length is error");
                    return null;
                }
                SeqString s = new SeqString(this.GetLength() - len);
                int j = 0;
                for (int i = 0; i < index ; i++)
                {
                    s[j++] = this[i];//重难点。注意：这里不是++j。画个图就能理解
                }
                for (int i = index +len ; i < this .GetLength (); i++)
                {
                    s[j++] = this[i];//重难点。注意:这里不是++j。
                }
                return s;
            }
    
            /// <summary>
            /// 串比较。
            /// 依次将较短字符串中的每个字符与较长字符串的每个字符比较，当被比较的两个字符不相等时，终止比较。
            /// 如果比较在中途退出，需进一步判断主串与字符串s在退出比较时所比较字符的大小，如果主串的字符串小，返回-1，否则返回1。
            /// 如果比较是正常退出，则需进一步判断两个字符串的长度是否相等，如相等返回0，否则如果主串的长度大于s的长度，返回1，否则返回-1
            /// </summary>
            /// <param name="s"></param>
            /// <returns></returns>
            public int Compare(SeqString s)
            {
                int len = ((this.GetLength() <= s.GetLength() ? this.GetLength() : s.GetLength()));
                int i = 0;
                for (i = 0; i < len ; i++)
                {
                    if(this[i] != s[i])
                    {
                        break;
                    }
                }
                if (i < len)
                {
                    if(this[i] < s[i])
                    {
                        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>
            /// 串定位。从主串的startpos位置开始，查找子串S在主串中首次出现的位置
            /// </summary>
            /// <param name="s"></param>
            /// <param name="startpos"></param>
            /// <returns></returns>
            public int IndexOf(SeqString s, int startpos) //理解不了！
            {
                SeqString sub;
                sub = this.SubString(startpos, this.GetLength() - startpos);
                if(sub .GetLength ()<s.GetLength())
                {
                    Console.WriteLine("There is not string s");
                    return -1;
                }
    
                int i = 0;
                int j = 0;
                int v;
                while (i<sub .GetLength ()&&j<s.GetLength())
                {
                    if(sub .data [i]==s.data[j])
                    {
                        j++;
                        i++;
                    }else
                    {
                        i = i - j + 1;
                        j = 0;
                    }
                }
                if(j==s.GetLength())
                {
                    v = i - s.GetLength() + startpos;
                }else
                {
                    return v = -1;
                }
                return v;
            }
    
            /// <summary>
            /// 串插入。指在主串的位置index处插入一个串S。如果位置符合条件，则该操作返回一个新串，新串的长度是主串的长度与串s的长度之和。
            /// </summary>
            /// <param name="index"></param>
            /// <param name="s"></param>
            /// <returns></returns>
            public SeqString Insert(int index, SeqString s)
            {
                int len = s.GetLength();
                int len2 = this.GetLength() + len;
                SeqString s1 = new SeqString(len2);
    
                if(index <0||index >this .GetLength() - 1)
                {
                    Console.WriteLine("Position is error");
                    return null;
                }
                for (int i = 0; i < index ; i++)
                {
                    s1[i] = this[i];
                }
    
                //太难理解了
                for (int i = index ; i < index +len ; i++)
                {
                    s1[i] = s[i - index];
                }
                for (int i = index +len ; i <  len2 ; i++)
                {
                    s1[i] = this[i - len];
                }
    
                return s1;
            }
    
            /// <summary>
            /// 取字符串的值
            /// </summary>
            /// <returns></returns>
            public override string ToString()
            {
                return new String(data);
            }
        }
    }