大众点评网站模板舆情报告分析案例

当前位置： 首页 > news >正文

大众点评网站模板,舆情报告分析案例,网站技能培训,国内知名展示设计公司本文参考网课为 数据结构与算法 1 第四章字符串#xff0c;主讲人 张铭 、王腾蛟 、赵海燕 、宋国杰 、邹磊 、黄群。 本文使用IDE为 Clion#xff0c;开发环境 C14。 更新#xff1a;2023 / 11 / 12 数据结构与算法 | 第四章#xff1a;字符串 字符串概念字符串字符字符…本文参考网课为 数据结构与算法 1 第四章字符串主讲人 张铭 、王腾蛟 、赵海燕 、宋国杰 、邹磊 、黄群。 本文使用IDE为 Clion开发环境 C14。 更新2023 / 11 / 12 数据结构与算法 | 第四章字符串 字符串概念字符串字符字符编码子串 抽象数据类型存储与实现顺序存储C / C的标准字符串标准串运算字符串长度字符串寻找字符 C的字符串类 String字符串类运算构造算子赋值算子提取子串 模式匹配概念应用分类精确匹配单选模式朴素匹配算法KMP 算法 近似匹配 参考链接 字符串 概念 字符串 字符串 是一类简单的由 字符 char构成的线性结构的 线性表。 字符串 简称 串为零个或多个 字符 / 符号 构成的有限序列。 n (0) 个 字符 的有限序列一般记作 S C0C1…Cn-1。 S 为串名C0C1…Cn-1为串值。Ci中i位置上的 字符 / 符号n 为字符串长度。长度为零的串不包含任何字符内容。理论上一个字符串的长度可以为任意的有限长度实际上 定长 具有固定的最大长度所用内存量始终如一变长 根据实际需要伸缩以提高内存空间利用率 字符 字符 的取值依赖于字符集。常用的字符集包括 由 {0, 1} 所构成的二进制字符集由4个字符组成的生物信息的DNA字符集由26个字符和标点符号等组成的英语语言由6763个常用汉字和682个全角非汉字符号等所构成的简体中文标准字符集GB2312适用于跨语言、跨平台的通用字符集USC Universal Character Set
这些 字符 在计算机里是如何存储和运算呢这就需要 字符编码 来建立 字符集 与计算机数字系统之间的对应关系。 字符编码 字符编码 会将 字符集 里的每一个字符编码为由0和1组成的序列。那么具体哪一个二进制序列表示哪一个符号则取决于我们所使用的编码方式。常用的编码方式有 ASCII 编码 使用单字节 8 bits 对字符集 charset 的128个符号进行编码基于拉丁字母的编码主要用于现代英语和多种西欧语言也为大多数程序设计语言所采用例如C和C 其他编码方式 ANSI 编码 支持多种东方语言GB2312、BIG5、JIS 等。不同国家/地区制定不同的标准不同 ANSI 编码间互不兼容Unicode跨语言跨平台 各种语言中的每一个字符具有唯一的数字编号便于跨平台的文本转换
无论采用哪一种编码方式对于一个给定字符集中的字符编码需要满足一组无歧义的规则使得字符集中的每一个字符都对应唯一的一个编码。且不同的字符编码之间要满足偏序关系。 所谓偏序关系是定义在集合上的一个二元关系满足自反性、反对称性和传递性。在偏序规则下 连续的数字 0 - 9 是要连续编码的。像在 ASCII 编码 下0 的编码是 48那么 1 的编码就是 49。连续的字符也是需要连续编码的。像在 ASCII 编码 下大写字母 A 的编码是65那么 B 的编码就是66。 通常在字符偏序下根据字符的自然含义两个字符之间是可以根据它的编码值进行直接的比较的。两个字符串就会按照构成的字符之间的编码进行大小的比较来得到字典序。 子串 一个 字符串 中任意个连续的字符组成的子序列称为该串的 子串 。 比如说一个长度为 n 的字符串 s1 和长度为 m 的 s20mn。若存在整数 j (0in-m) 使得 bj aijj 01…m-1同时成立则称串 s2 是串 s1 的字串或称 s1 包含串 s2。 另外空串是任意串的子串。任意串S都是其自身的子串。 子串 相关的应用有提取、插入、寻找、删除等等。 抽象数据类型 int length(); // 返回串的长度 int isEmpty(); // 判断串是否为空串 int find(const char c, const int s); // 从s开始搜索串寻找一个给定字符 int strcmp(const char *s1, const char *s2); // 串比较void clear(); // 清空串string substr(const int s, const int len); // 从s开始提取一个长度为len的子串 string insert(const char s, const int index); // 往串中给定位置插入一个字符 string append(const char c); // 往串尾添加字符 string concatenate(const char *s); // 往本串后面链接串schar *strcpy(char *s1, const char *s2); // 串复制存储与实现 字符串 是一种基本元素为 字符 的特殊线性表所以本质上它的存储也有线性表的顺序和链式两种方式。但是对于 字符串 这类特殊的线性表来说链式存储的结构性开销过大而很少被采用所以我们主要以顺序存储为主来介绍 字符串 的存储与实现。 顺序存储 对于定长的 字符串 采用顺序存储方式即事先申请固定长度的空间但需要有相应的机制来确切的知道当前串的长度。所以一般有3种处理方案 用 字符串 的第一个元素 S[0] 作为记录串长的存储单元 缺点该方式决定串的最大长度不能超过256 2。另辟空间存储串的长度 缺点串的最大长度一般是静态给定的而非动态申请特殊标记串的结束 C / C 的标准字符串 #include string.h C / C的标准字符串 C / C 的标准字符串是将字符串变量定义为字符数组 char s[M]。 字符串的结束标记是 ASII码中8位全0码 ‘\0’亦称 NULL。因此字符串的实际长度为 M-1。 例如chars s1[6]value;定义了一个名为 chars 的字符数组长度为6位但是只能存储5位字母。 需要注意的是标准串定义成了数组所以它是无法作为左值被赋值的。例如s1 s2 是不合规的。 标准串运算 函数库 string.h 提供字符串处理函数来方便字符串的运算。下面是 string.h 提供的一些常用的字符串的操作 函数作用int strlen(char *s)串长char *strcpy(char *s1, char*s2);串复制char *strcat(char *s1, char *s2);串拼接int strcmp(char *s1, char *s2);串比较char *strchr(char *s, char c);字符定位char *strrchr(char *s, char c);字符定位int strstr(char s2, char* s1)子串抓取 字符串长度 1. 求字符串的长度 int strlen(char s[]) {int i 0;while (s[i] ! 0)i ;return i; }2. 比较2个字符串的长度 int strcmp(const char *s1, const char *s2) // 定义2个字符串分别为s1、s2 {int i 0;while (s2[i] ! \0 s1[i] ! \0){ // 字符串的结束标记为 \0if (s1[i] s2[i])return 1; // s1比s2长else if (s1[i] s2[i])return -1; // s1比s2短i ;}if (s1[i] \0 s2[i] ! \0)return -1; // s1比s2短else if (s2[i] \0 s1[i] ! \0)return 1; // s2比s1短return 0; }或者 int strcmp_1(char *s1, char *s2) // 定义2个字符串分别为s1、s2 {int i;for (i0; s1[i] s2[i]; i){if (s1[i] \0 s2[i] \0)return 0; // 两个字符串相等}return (s1[i]-s2[i])/abs(s1[i]-s2[i]); // 不等比较第一个不同的字符 }字符串寻找字符 1. 在字符串 s 中正向寻找字符 c char * strchr(char *s, char c) {i 0;while (s[i] ! \0 s[i] ! c) // 循环跳过非c字符i;// 在循环结束后if (s[i] \0) // 当s不包含字符c则在s[i]即串尾return 0;else // 当s[i]c则返回s[i]return s[i]; }2. 在字符串 s 中反向寻找字符 c char * strrchr(char *s, char c) {i 0;while (s[i] ! \0) i; // 获得s字符串的长度while (s[–i] ! \0 s[i] ! c); // 循环反向跳过非c字符// 在循环结束后if (s[i] \0) // 当s不包含字符c则在串尾结束return 0;else // 若成功则返回相应位置return s[i]; }举例在 s [Hello world\0] 中寻找 o 寻找字符 ostrchar(s, o) 返回 4 反向寻找 ostrchar(s, o) 返回 7。 C的字符串类 String 除了采用标准字符串以外还可以采用字符串类 String 来表示和存储字符串以适应字符串的长度动态变化。 在 String 类中字符串不再是以字符数组 char S[M] 这种形式来直接出现而是采用一种动态变长的存储结构。 String 类是通过实例化标准模板库中的 STL 的 basic_string 而得到的。如下 typedef basic_string char string;它的存储结构如下 private: // 具体实现的字符串存储结构char *str; // 字符指针表示的串实体int size; // 字符串长度 public: // 成员函数String(char *s); // 构构子~String(); // 析构子String operator(String s); // 赋值String operator(String); // 拼接String substr(int index, int cout); // 子串int find(char c, int start); // 查找…字符串类运算 操作类别方法描述子串substr返回一个串的子串拷贝 / 交换copy将一个串拷贝到另一个串中swap交换两个串的内容赋值assign把一个串、一个字符、一个子串赋值给另一个串中把一个串或一个字符赋值给另一个串中插入 / 追加insert在给定位置插入一个字符、多个字符或串将一个字符或串追加到另一个串后append将一个或多个字符或串追加在另一个串后拼接通过将一个串放置在另一个串后面来构建新的新串查询find找到并返回一个子序列的开始位置替换 / 清除replace替换一个指定字符或一个串的子串clear清除串中的所有字符统计size返回串中字符的数目length返回size()max_size返回串允许的最大长度 构造算子 String 类有多个构造函数。构造一个带有初始值的 String 类可以参照以下方法 String::String(char *s){ // 确定新字符串需要的空间初始值为 char *ssize strlen(s); // 新字符串的长度由标准字符串函数 strlen(s) 确定str new char [size1]; // 在动态存储区域开辟一块空间用于存储初值s包括结束符assert(str ! \0); // 开辟空间不成功时运行异常退出strcpy(str, s); // 在空间申请成功后用标准字符串函数strcpy将s完全复制到指针str所指的存储空间 }例如我们可以通过上面的带参数的构造函数通过 String s1(hello); 定义一个 String 类的变量 s1初始值为 hello。那么我们就可以申请一个容纳下 hello 的空间来将 hello 容纳进去并且将 size 设置成相应的大小。 String s1(hello);private:char *s;size_t size; // 值为5赋值算子 String String::operator(String s){ // 参数s将被赋值并覆盖本串。if (size ! s.size){ // 比较本串和参数串s的大小若本串和参数串长度不一致则释delete [] str; // 放原本的串的存储空间str new char [s.size1]; // 按照参数s的大小申请新的空间并把参数s的串值复制到本串中assert(str!0);sizes.size;}strcpy(str, s.str); // 将参数串s赋值到本串return *this; // 返回得到的字符串 }例如我们通过构造函数构造一个串 s2它的初值为 hello world 并通过 String s2(hello world); s1s2; 将这个值赋值给 s1。而 s1 此前已经被赋值 hello所以可以看到 hello 的空间不足以存放新的值 hello world所以将原本的空间释放掉、申请一个新的空间来容纳新值。 提取子串 // 提取子串的函数是将本串从index开始提取连续的count个字符 作为子串返回放到temp中 String String::Substr(int index, int count){ // 取出一自下表index开始长度为count的子串返回int i;int left size - index; // 本串自下标index开始到串尾的长度为leftString temp; char *p *q;if (index size) // 若下标index超过本串实际串长则返回空串return temp;if (count left) // 若count超过自index开始剩余的子串长度count left; // 则count截取为剩余长度delete [] temp.str; // 释放原来的存储空间temp.str new char [count1];assert(temp.str ! 0); // 若开辟动态存储空间失败则退出p temp.str; // 若指针p指向目前暂无内容的字符数组的首字符处q str[index]; // 指针q指向本实例串的str数组的下标index字符for (i0; icount; i) // 从index开始逐个提取字符到串temp中*p *q;*p 0; // 循环结束后让temp.str的结尾为 \0temp.size count;return temp; }例如我们可以通过 s2 s1.substr(6 ,5) 从串 s1 hello world 的第6个位置开始连续提取5个字符形成子串 world 赋值给 s2。 模式匹配 概念 模式匹配 Pattern Matching 在目标文本 T 中寻找和定位一个给定模式 P Pattern 的过程。 应用 模式匹配 有着非常广泛的应用例如 进行文本编辑时对特定词语、语句的查找 大文本诸如句子、段落或书本中定位特定的模式UNIX / Linuxsed、awk、grep 在生物信息方面对DNA信息的提取用于确认是否具有某种特定形式的结构 函数式语言 … 分类 根据匹配结果的精确性模式匹配 可以分为 精确匹配 和 近似匹配。 精确匹配 精确匹配 Extract String Matching 若目标 T 中至少存在一处与模式 P 完全相同的子串则称为匹配成功。 根据模式的不同可以进一步的分为 单选模式 例如Set多选模式 例如包含通配符的 St正则表达式 单选模式 给定模式串 P在目标字符串 T 中搜索与模式 P 全同的子串简称为 配串。如果找到则返回 T 中第一个 P 的配串的首地址。 因为模式匹配频繁用于文本的模式查找所以效率是衡量模式匹配算法的一个重要指标。因此存在许多种用于模式匹配的算法。 这里列出一些常用的单选模式的字符串匹配算法包含每个算法的预处理时间和匹配时间 朴素匹配算法 朴素 匹配算法 Native / Brute Force 本质上是穷举尝试所有匹配的可能。 假设 T t0t1t2…tn P p0p2…pm-1。i, j 分别表示 T 和 P 当前字符的下标在目标字符串 T 中搜索与模式 P 的配串 将模式从头与目标串的第 i 个字符开始比较若相等则继续逐个比较后续字符匹配成功 p0 tkp1 tk1…pm-1 tkm-1即 T.substr(k, m) P若一趟匹配过程发生失配 pj ! ti 则将 P 整体右移1位开始下一趟的匹配 例如存在目标字符串 T ababababababb 和模式串 P abababb 将P从0开始与T的第 i 个字符开始比较若相等则继续逐个比较后续字符在第6个字符发生失配 P6 ! T6将P整体右移1位开始下一趟的匹配将P从1开始与T的第 i 个字符开始比较在第1个字符发生失配P0 T1 将P整体右移1位开始下一趟的匹配重复上述步骤直至 T.substr(k, m) P 匹配成功或者匹配失败。 例如存在目标字符串 T aaaaaaaaaab 和模式串 P aaaaaab 将P从0开始与T的第 i 个字符开始比较若相等则继续逐个比较后续字符在第6个字符发生失配 P6 ! T6将P整体右移1位开始下一趟的匹配将P从1开始与T的第 i 个字符开始比较在第1个字符发生失配P6 T7 将P整体右移1位开始下一趟的匹配重复上述步骤直至 T.substr(k, m) P 匹配成功或者匹配失败。 朴素模式 的匹配算法实现如下 int g, j;int FindPattern(string T, string P, int startindex)for (int gstartindex; gT.length()-P.length(); g){ // g为T的游标用模板P和目标T的第g位置子串进行比较for (int j0; ((jP.length()) (T[gj]P[j])); j);if (jP.length())return g;}return (-1); // for循环结束或者startindex溢出匹配失败 }朴素模式 的匹配算法的时间复杂度分析如下 最差情形 最佳情形 KMP 算法 Knuth - Morris - Pratt KMP 发现每个字符对应的 k 值仅依赖于模式 P 本身与目标串 T 无关。 1970年S.A.Cook 在进行抽象机的理论研究时证明了最差情况下模式匹配可在 ONM 时间内完成。 D.E.Knuth 和 V.R.Pratt 以 Cook理论为基础构造了一种在 ONM 时间内进行模式匹配的方法。 与此同时J.H.Morris 在开发文本编辑器时为了避免检索文本时的回溯也得到了同样的算法。 长度为m的模式PPp0p1p2p3…pm-1。特征向量N表示模式P的字符分布特征由m个特征数nj组成 N n0n1n2n3…nm-1。 特征向量简称 N向量。在很多文献中也称为 next 数组每个特征数 nj 对应 next 数组的一个元素。 【还是没搞懂KMP算法的思想…此处略…】 近似匹配 近似匹配 Approximate String Matching )若模式 P 与目标 T或其子串存在某种程度的相似则称为匹配成功。 字符串相似度通常定义串变换所需基本操作数目。 字符串基本操作包括 插入、删除 和 替换 三种操作。 参考链接 数据结构与算法 ↩︎ 详解计算机中的字、字节Byte、比特bit及它们之间的关系 ↩︎