数据结构与算法分析(十四)

您所在的位置:网站首页 字符串处理算法是什么 数据结构与算法分析(十四)

数据结构与算法分析(十四)

2024-07-07 14:12| 来源: 网络整理| 查看: 265

文章目录 一、字符编码与字符类型 1.1 数据类型 1.2 字符类型 二、常见的字符操作 2.1 字符类型识别与大小写转换 2.2 字符格式与数值格式转换 2.3 字符串常用操作 2.3.1 字符串与字符数组的比较操作 2.3.2 字符串与字符数组的插入操作 2.3.3 字符串与字符数组的修改操作 2.3.4 字符串与字符数组的查找操作 2.3.5 字符串的分割操作 更多文章:

计算机诞生之初主要是为了帮助科学家和工程师完成繁琐的数学计算和方程求解,伴随着Web 互联网的普及,计算机处理字符的任务越来越多,在互联网或通信系统中传输的也都是各种字符信息。目前,计算机的两大核心任务就是数值计算和字符处理,分别对应数学语言和自然语言,各种计算机编程语言也分别为数值计算和字符处理提供了丰富的库函数。

一、字符编码与字符类型 1.1 数据类型

计算机寄存器、内存、闪存等存储介质都是以高低电平信号存储数据信息的,高低电平状态分别对应二进制的0 和1,因此计算机存储和处理数据都是以二进制形式进行的。

我们更习惯使用十进制数据进行计算和记录,要表示一个十进制数据需要多个二进制位组合起来,且不同大小的十进制数据需要不同位数的二进制来表示。计算机需要清楚的知道一个数据是由几个二进制位表示的、怎么解释该数据?编程语言为此提供了不同的数据类型,比如使用char、short int、int、long long int 关键字告诉计算机该数据分别需要8、16、32、64位二进制数据来表示整数,下面给出C 语言常用的数据类型(其中bool 类型是C99 新增的,若要使用需包含头文件): C语言常用数据类型 带小数的浮点数为了使用尽可能少的二进制位表示,采用科学计数法的形式编码,比如float、double、long double 分别使用32、64、128 位二进制来表示浮点数(浮点数表示方法可参考博文:IEEE754 浮点数的表示方法)。既然表示浮点数的小数位数有限,自然不能精确表示所有小数,所以两个浮点数不能直接比较大小,我们常假设两个浮点数差的绝对值小于某个精度值EPSINON,这个精度值怎么取呢?主要看表示浮点数的小数位数,比如float 小数部分fraction 能表示的最小数为2-23 = 1.1921 * 10-7(虽然加上指数部分exponent 能表示更小的数,但其小数部分的分辨率大于2-23,并不能精确表示),如果我们自己编写比较浮点数的函数,常将EPSINON 设置为1.0 * 10-6(大于2-23 即可,C语言可在头文件float.h 中查看宏FLT_EPSILON 获得)。

相同类型的数据在不同操作系统上可能会由不同位数的二进制来表示,比如long int 在windows_x64 上使用32 位二进制表示,在linux_x64 上使用64 位二进制表示,为了避免跨平台移植遇到问题,可以使用定宽整数类型(见头文件),比如int8_t、int16_t、int32_t、int64_t 等。

不同位数的二进制能表示的数据范围肯定不一样,比如对于N 位二进制可表示的整数范围是[-2(N-1),2(N-1)-1],如果是使用unsigned 修饰的无符号整数,则其可表示的整数范围是[0, 2N-1]。每种数据类型可表示的数据极限值也可以在头文件和 中通过查询宏常量获知,比如最小和最大的int 类型数据值分别为INT_MIN 和INT_MAX。

值得一提的是,在进行数值计算时,如果计算结果超出该类型可表示范围极限,可能会出现程序错误或计算错误,这一点需要尽量在程序中避免。在进行数据类型转换时,可能会丢失部分数据,是否可接受其对计算结果的影响,需要程序开发者自己判断。

1.2 字符类型

前面介绍的数据类型中有一个char 类型,从字面意思看属于字符类型,也可以表示整数,字符类型跟整数类型有什么区别呢?计算机怎么知道char 表示的是字符还是整数呢?

计算机本身是不识别字符的,要想让计算机可以识别并处理各种字符信息,也需要像二进制表示十进制整数和浮点数那样,按照某个规则表示各种字符。但各种字符不像整数和浮点数那样有规律,对于毫无规律的各种字符,不能单靠某几个规则确定各字符与二进制之间的转换关系,最简单的就是为每个字符赋予一个独一无二的编号(字符码),使用该字符编号来表示该字符,如果要显示该字符,通过该字符编号查询对应的字符表(字符集),就可以获取该字符的显示点阵信息。

字符码跟字符集是配合使用的,二者共同构成一套字符编码方案,同一个字符在不同字符集中的字符码可能是不同的。最常用的字符集是ASCII (American Standard Code for Information Interchange),其中包含了最常用的英文字母、数字、特殊符号、控制字符等共128 个字符,这些字符码可以使用7 个二进制位来表示,早期通讯不是很可靠,字符码加了一个二进制位用于奇偶校验,因此使用8 个二进制位来表示一个ASCII 字符。

八个二进制位正好可以由两个十六进制位来表示,且正好可用来表示一个ASCII 字符,因此常将8 个二进制位组合起来使用,称为八位组Octet 或者字节Byte,前面介绍的各种数据类型使用的二进制位数也都是Octet 或Byte 的整数倍。

我们已经知道计算机通过字符码来存储和处理字符信息(计算机中应存储对应的字符集),字符码实际上是无符号整数,自然也可以使用多位二进制来表示。计算机怎么知道char 表示的是整数还是字符码呢?对一个char 类型变量可以从赋值和输出两个角度看:如果是以单引号括起来的形式赋值(比如char c = ‘1’;),则char 变量存储的是字符1的编码值;如果以%c 格式解释char 变量值,计算机将char 变量值当作字符码,查询ASCII 字符集获得对应的字符点阵信息再输出显示,如果以%d 格式解释char 变量值,则计算机将char 变量值当作整数输出显示。

ASCII 字符集只能表示128 个字符,肯定无法满足我们的使用需求,因此有各种扩展字符集,使用多个字节来表示一个字符(可参考博文:字符编码的设计与演进)。目前国际上使用最广泛的是UTF-8 编码,国内使用比较多的是GB18030 编码:

UTF-8 编码:目前在国际上使用最广泛,UTF-8 使用1 字节表示ASCII 字符,使用2 字节表示欧洲语言字符(比如拉丁文、希腊文等字符),使用3 字节表示亚洲语言字符(比如中日韩文、东南亚文等字符),使用4 字节表示其它不常用字符; GB18030 编码:目前在国内使用比较多,GB18030 使用1 字节表示ASCII 字符,使用2 字节表示亚洲语言字符(比如中日韩文、东南亚文等字符),使用4 字节表示其它不常用字符(比如一些古文字、生僻字等); UTF-16 编码:至少使用16 个二进制位来表示一个字符,也即对常用的Unicode BMP 字符使用2 字节表示,对于不常用的Unicode BMP 以外的字符使用4 字节表示,UTF-16 对于英文字符也需要2 字节表示,因此不兼容ASCII 字符集,且存储和传输英文字符将占用更多资源。UTF-16 分大端和小端两种字节序,也即UTF-16LE 和UTF-16BE,windows 系统默认使用UTF-16LE 编码(Linux 系统默认使用UTF-8 编码)。

在欧美地区,使用UTF-8 编码可以用更少的二进制位来表示常用字符,也就可以节省不少存储资源和传输带宽。在亚洲地区,使用UTF-8 编码表示一个汉字需要 3 Bytes,使用GB18030 编码表示一个汉字只需要2 Bytes,如果汉字比较多,使用GB18030 字符集存储和传输中文字符更高效。

UTF-8 和GB18030 使用多个字节来表示一个字符,属于变长多字节字符编码,在存储和传输字符信息时比较节省资源,因此在磁盘存储和网络传输中应用比较广泛。但变长字节编码不利于计算机处理,计算机每遇到一个字符还要判断该字符由多少个二进制位表示会影响处理效率,因此操作系统在内存中处理字符时,通常先将其转换为定长编码字符(比如UCS-2 或UTF-32)再处理,编程语言也为多于1 字节编码的字符提供了宽字符类型wchar_t,告诉计算机该字符需要多少个二进制位表示。

宽字符类型wchar_t 在不同的操作系统中长度也不同,在windows 系统中使用16 个二进制位表示一个宽字符,在linux 系统中使用32 个二进制位表示一个宽字符。为了避免跨平台移植遇到问题,C11 新提供了char16_t 和char32_t 两种定宽字符类型(见头文件 ),下面给出C 语言支持的字符类型:

类型 描述 char 单字节字符,使用8 个二进制位表示一个字符,比如ASCII 字符集。 wchar_t 宽字节字符,使用16 位(比如windows 系统)或32 位(比如linux 系统)二进制表示一个字符。 char16_t 双字节字符,使用16 个二进制位表示一个字符,比如UTF-16 / UCS-2 字符集。 char32_t 四字节字符,使用32 个二进制位表示一个字符,比如UTF-32 / UCS-4 字符集。

由于这些字符类型变量存储的都是字符编码,字符编码也是整数,这些字符类型实际上是特定宽度的整数类型别名,在windows 和linux 系统中字符类型的定义如下:

//windows系统 typedef unsigned short wchar_t; typedef uint_least16_t char16_t; typedef uint_least32_t char32_t; //linux系统 typedef int wchar_t; typedef unsigned short char16_t; typedef unsigned int char32_t;

计算机一般都是按字节寻址和读写的,对于宽度超过一个字节的数据类型,高字节是存储在高地址还是低地址呢?不同的计算机对此的处理并不一致,这就引出了大端字节序和小端字节序的问题:

大端字节序(BE: Big Endian):高位字节在前,低位字节在后,比较符合人类读写数据的习惯,IETF 规定网络传输都使用大端字节序(网络字节序); 小端字节序(LE: Little Endian):低位字节在前,高位字节在后,计算机进行数值计算先处理低位字节效率更高,常见的x86、ARM 等处理器都默认小端字节序(主机字节序);

前面介绍的宽度超过1 字节的数据类型都存在字节序的问题,对于UTF-16 和UTF-32 这类宽字符编码,如果存储和解析的字节序不一致就会解析出不同的字符导致信息传达错误,因此常在文件开头添加一个BOM(Byte Order Mark),让计算机能正确识别字符编码字节序并正确解释字符信息(比如UTF-16LE BOM为FF FE,UTF-16BE BOM 为FE FF)。不同的计算机通过互联网传输信息时,也需要统一字节序,IETF 规定网络传输统一使用大端字节序,主机借助互联网收发信息都需要进行主机字节序与网络字节序的转换。

二、常见的字符操作

对于整数和浮点数类型,最常用的是各种数学计算,比较基本的是直接通过算术、关系等运算符直接处理,稍微复杂点的是指数函数、幂函数、三角函数、双曲函数等常用数学函数计算,C 标准库在头文件 和 中提供了常用的整数、浮点数、复数的数学计算函数,我们可以直接调用库函数完成常见的数值计算。对于字符类型,并不适合各种数学计算,我们常对其执行哪些处理或操作呢?

2.1 字符类型识别与大小写转换

在跟人交互的文件中存储的信息一般都是字符形式,文件中的数值也需要转换为字符才可以显示出来,计算机如果要处理文件中的数值,需要识别并将其转换为整数或浮点数类型才方便后续计算。因此,识别字符类别、字符格式与数值格式之间的转换,是两种基本的字符操作。

计算机怎么识别字符类别呢?字符型变量内保存的都是字符编码,同一类别的字符编码通常都在一个编码区间范围,我们只需要判断该字符编码在哪个区间范围,就可以识别出该字符类型,C 语言提供的识别字符类型的库函数如下(见头文件):

识别字符类型库函数 功能描述 int isalnum(int c) 若传入字符为字母或数字字符,则返回非零,否则返回 0。 int isalpha(int c) 若传入字符为字母,则返回非零,否则返回 0。 int islower( int ch ) 若传入字符为小写字母,则返回非零,否则返回 0。 int isupper( int ch ) 若传入字符为大写字母,则返回非零,否则返回 0。 int isdigit( int ch ) 若传入字符为十进制数字字符,则返回非零,否则返回 0。 int isxdigit( int ch ) 若传入字符为十六进制数字字符,则返回非零,否则返回 0。 int iscntrl( int ch ) 若传入字符为控制字符,则返回非零,否则返回 0。 int isgraph( int ch ) 若传入字符为可显示字符,则返回非零,否则返回 0。 int isspace( int ch ) 若传入字符为空白字符,则返回非零,否则返回 0。空白字符指的是空格、换行、回车、水平/垂直制表符等。 int isblank( int ch ) 若传入字符为空格符,则返回非零,否则返回 0。 int isprint( int ch ) 若传入字符为可打印字符,则返回非零,否则返回 0。 int ispunct( int ch ) 若传入字符为标点字符,则返回非零,否则返回 0。 int tolower( int ch ) 若传入字符为大写字母,则返回其对应的小写字母,否则不修改传入字符。 int toupper( int ch ) 若传入字符为小写字母,则返回其对应的大写字母,否则不修改传入字符。

宽字符类型只是字符编码占用了更多字节,对宽字符的操作处理跟单字节字符(也称窄字符)类似,重点就是每个字符占用的二进制位数不同了。C 语言也为宽字符操作提供了一系列库函数,详见头文件、 和,本文就不赘述了。

2.2 字符格式与数值格式转换

一般文件中存储的整数或浮点数都是十进制的,且不止一个十进制位,如果将一个十进制整数或浮点数转换为字符格式,通常每一个十进制位都需要一个字符表示,一个完整的十进制数通常需要多个字符或一个字符数组共同表示。如果用字符数组表示一个完整的整数或浮点数,在传参时通常需要数组指针和数组长度两个参数,如果在字符数组尾部添加一个结束标记,程序就可以自动计算字符数组的长度,使用 ‘\0’ 空字符终止的一维字符数组称为字符串。

单字节字符串转换为数值格式的库函数如下(见头文件):

/** 将传入的空终止字符串转换为一个十进制整数值(只转换'+'、'-'、'0'~'9'), * 若转换成功则返回转换后的整数值,若无法转换则返回0, * 若转换后的整数值超出返回类型范围极限则返回未定义的值。*/ int atoi( const char *str ); long atol( const char *str ); long long atoll( const char *str ); /** 将传入的空终止字符串转换为一个十进制浮点值(只转换'+'、'-'、'.'、'e'、'E'、'0'~'9'), * 若转换成功则返回转换后的浮点值,若无法转换则返回0, * 若转换后的浮点值超出返回类型范围极限则返回未定义的值。 */ double atof( const char* str ); /** 将传入的空终止字符串转换为一个整数值,转译哪些字符跟设置的进制有关 * @param str: 指向要被转译的空终止字符串的指针,restrict 用于限定和约束指针,并表明指针是访问一个数据对象的唯一且初始的方式。 * @param str_end: 指向的指针指向最后被转译字符的后一个字符,若未发生转换则指向str,若传入空指针则忽略该参数。 * @param base: 期望转换为整数值的底或进制数,合法范围{0,2,3,...,36},若设为0 则自动检测数值进制,36 进制包含10个数字和26个字母(不区分大小写)。 * @return : 若转换成功则返回转移后的整数值,若无法转换则返回0 并将 *str_end 设为 str ; * 若转换后的整数值超出返回类型范围极限则返回类型极限值,并设 errno 为 ERANGE。 */ long strtol( const char *restrict str, char **restrict str_end, int base ); long long strtoll( const char *restrict str, char **restrict str_end, int base ); unsigned long strtoul( const char *restrict str, char **restrict str_end, int base ); unsigned long long strtoull( const char *restrict str, char **restrict str_end, int base ); /** 将传入的空终止字符串转换为一个浮点值 * @param str: 指向要被转译的空终止字符串的指针,r


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3