阅读 72

数据结构和算法 <字符串>(一、介绍字符串)

个人比较喜欢系统学习一个知识,竟然是一个系统学习过程,前面的介绍部分自然不能少,总不能一上来就高潮吧,先来点过渡,也好好整理一个概念。

1.1  串的定义

我们现在常用的搜索引擎,当我们在文本框中输入“数据”时,它已经把我们想要的“数据结构”列在下面了,这个显然就是一个字符串查找匹配的工作。

所以我们就要好好分析字符串这样的数据结构,来看看《大话数据结构》是怎么定义的: 串是由零个或多个字符组成的有限序列,又名叫字符串

一般记为s="a1a2......an" (n≥0)

a就是一个一个的字符,然后把n个字符拼接起来就是字符串,n是字符串的长度,是有限长度的,n也可能为0,为0是就是空串,可以用“”这个表示。

特别注意的是,有一种字符串叫空格串,空格串是有内容的,里面包含着空格,可能不止一个空格。

1.2  串的比较

两个数字,很容易比较大小。2比1大,这完全正确,可是两个字符串如何比较?比如“silly”、“stupid”这样的同样表达“愚蠢的”的单词字符串,它们在计算机中的大小其实取决于它们挨个字母的前后顺序。它们的第一个字母都是“s”,我们认为不存在大小差异,而第二个字母,i<t,我们排序都是按字典序,所以说“silly” < "stupid"。(明确的说应该是按ASCII码表编码的顺序,不过ASCII码表在编码的时候本来就是按字典序的)

1.3  串的存储结构

字符串一般都是用一组地址连续的存储单元来存储的,按照字符串的长度,为字符串变量分配一个固定的存储区。一般我们都是用定长的数组来定义。 既然是定长数组,就存在一个最大串的长度,但是实际字符串的长度不会是最大长度的,所以我们需要把实际的串长度值保存在数组的0下标位置,有的保存在最后一个下标位置(感觉没看到这么用的)。但是c语言就不这么干,c语言在字符串的最后添加一个"\0"表示字符串的结束,我们要想知道字符串的长度,就遍历一次字符串,就知道了长度,确实有点麻烦。

像c语言我们比较喜欢用结构体来封装一个字符串,一个是字符数组,存储字符串,一个是长度,为什么这样呢?是因为如果字符串后面忘记了“\0”,就会出现指针越界,是一个非常危险的事情,所以一般都是封装成一个结构体。

又比如高级语言c++、Java,语言级别就支持了string类型,这个就不用我们操心了,不过底层的封装其实跟c语言是差不多的。

1.4  字母表

一些应用程序可能会对字符串的字母表做出限制,在Java中,会封装一个Alphabet类描述字母表

字母表的API

public class Alphabet
More ActionsAlphabet(String s)根据S中的字符创建一个字母表
char toChar(int index)获取字母表中索引位置的字符
int toIndex(char c)获取c字符的索引,在0到R-1之间
boolean  contains(char c)c在字母表之中么
int R()基数(在字母表中的字符数量)
int lgR()表示一个索引所需的比特数
int[] toIndices(String s)将s转换为R进制的整数
String toChars(int[] indices)将R进制的整数转换为基于该字母表的字符串

是不是有点懵逼,我为什么写这个,下面我们来看看一个经典的例子就明白了:

public class Count { public static void main(String[] args)     {         Alphabet alpha = new Alphabet(argc[0]);  //生成一个字母表         int R = alpha.R();     //获取字母表的字符数量         int[] count = new int[R]; //申请一个统计字符频率的数组                  String S = StdIn.readAll();   //读取字符串         int N = S.length(); //计算字符串         for (int i=0; i<N; i++)          {             if (alpha.contains(s.charAt(i))) //判断字符是否在字母表中                 count[alpha.toIndex(s,charAt(i))]++; //如果在的话,获取下标,然后进行统计         }                  for (int c=0; c<R; c++)         {             StdOut.println(alpha.toChar(c) + " " + count[c]);  //输出         }     } }


作者:善良的小油条
链接:https://juejin.cn/post/7028855944251441166


文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐