串
串（字符串）是有另个或多个组成的有限序列，一般记为S=‘a1...an’(n>=0),其中的S是串名，用单引号括起来的的字符序列是串的值，串中字符的数目n称为串的长度，零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。
称两串相等是指两个串的长度相等且对应位置的字符都相等，也可以说当且仅当两个串的值相等。
由一个或者多个空格组成的串叫做空格串，它的长度为串中空格的个数。为了清楚起见，一般用Ø来表示空串（不是空格串）。
串的逻辑结构和线性表极为相似，区别仅在于传的数据对象约束为字符集。然而串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，而串通常以“串的整体”作为操作对象。
如果在程序设计语言中，串只是作为输入输出的常量出现，则只需存储此串的串值，即字符串序列即可，但大多数非数值处理的程序中，串也以变量的形式出现。
类似于线性表的顺序存储结构，用一组地址连续的存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组描述。串的实际长度可在预定义长度的范围内随意分配，超过预定义长度的串值则被舍去，称之为“截断”。而对串长的有两种表示方法，一是以下标为0的数组分量存放串的实际长度（PASCAL），二是在串值后面加一个不计入串长的标记字符（C）。
实现串操作的原操作（各种操作的基础）为“字符序列的复制”，其操作的时间复杂度基于复制的字符序列的长度，如果在操作中出现串值序列的长度超过上限时，约定用截尾处理，克服这个弊病的唯用不限定串长的最大长度，即动态分配串值的存储空间。
堆分配存储表示
名字什么的在高大上也不过是个名字，堆是机内和栈一样重要的自由存储区，一般栈是由计算机管理的，而堆是由程序员管理的。
这种存储表示的特点是：仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是程序执行过程中动态分配而得。
这种存储结构表示时的串操作仍然是基于“字符序列的复制”进行的。
其实也不是多么NB，只不过是在拼接序列等可能超出空间的操作，先开一个两个串长度和的空间（保证操作完能完全存放），然后把两个串复制过去，最后把两个串释放掉。
由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长无限制，更显灵活。（但个人感觉好慢）。
曾经幻想过能不能把字符串像链表一样连起来，自己最终得到的模型是n段离散的字符串，通过一个记录地址的链表来把n段字符串链接起来。
但看到第四章发现还真有这样的结构，称为块链结构，为了便于进行串的操作，当以链表存储串值时，除头指针外，还附属一个尾指针指示链表中的最后一个元素。
对串进行操作时，只需要从头到尾顺序扫描即可，设尾指针的目的是为了便于进行联接操作，但联结时一定要注意处理串尾的无效字符。
#define CHUNKSIZE 80 //由用户定义的块大小
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk * next;
}Chunk;
typedef struct{
Chunk * head,*tail; //头指针和尾指针
int len; //串的当前长度
}Lstring;
在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效率，由于所处理的串往往很长或很多，这就要求我们考虑串值的存储密度：
存储密度= 串值所有的存储位/实际分配的存储位
显然存储密度小（如结点为1），运算处理方便，然而存储占用量大，如果在串处理过程中需进行内、外存交换的话，则会因为内外存交换操作过多而影响总效率。
还有，串的字符集的大小也是一个重要因素，一般地，字符集小，其机内编码就短，这也影响串值的存储方式的选取。
串值的链式结构对某些串操作，如联接等，有一定的方便性，但对插入等又有着大量的复杂操作，又不是十分方便。总的来说，顺序结构和链式结构各有优势，分具体情况选用是最棒的选择。
话说数据结构包括存储方式和操作，下面说说操作。
在串中最常用的功能莫过于子串的定位操作，也称模式串的匹配。一般使用一个被王政称为朴素算法的时间复杂度为O（n*m）的东西，其中n和m分别是主串和模式串的长度，其实这也是最容易想到的算法。
节选《数据结构》中关键代码：
while(i T[0])
return i - T[0];
return 0;
算法的基本思想是：从主串S的第一个字符起和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否者从主串的下一个字符起再重新和模式串的第一个字符起逐个比较，以此类推，直到把主串比较完（匹配不成功）或找到匹配串的位置（匹配成功）。
这种算法容易理解也是最直接简单的查找算法，但往往越好理解的都是越笨拙的，这个算法最大的问题就是慢。有慢的，便必然有快的算法，要看快的，要先直到这个慢的是为什么慢的。
上面那个笨拙的算法，须要两个指针分别指向两个串，当匹配不成功时，两个串都有不同程度的回溯，如果指针不回溯哪怕只有一个指针回溯想必也是极好的。这样，新算法（也可以说是改良算法）就诞生了。
K（Knuth）M（Morris）P（Prate）算法，由前面那3个人同时发现，简称KMP算法，它便实现了只让一个指针回溯，这个指针利用已经得到的“部分匹配”，滑动到模式串的“敲到好处”的位置，继续匹配。
至于怎么确定这个“恰到好处”的位置，就是利用了一个被称之为next函数的东西。
若令next[j] = k，则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。由此可以引出模式串的next函数的含义：
next[j] = 0当j=1时
= Max(R|1 1...pk-1'=='pj-k+1...pj-1')
= 1 其他情况
说白了，就是记录了模式串当前位置和前面几个元素相同。
在寒假ACM集训的时候第一次接触了，KMP，其实KMP中的精华就在next函数中，其中的意义使用灵活，但实在是一种难以总结感觉，更像是经验问题，详情见当时的总结 月球美容计划之那些天我们学过的KMP。
在暑假给第3批队员培训的时候，又好好的研究了 KMP，但最后发现王政的KMP理解的比较深入，他的教案文档《Kmp 算法引论》深入浅出，在集训群里又找到这份文档，作为最后对KMP的补充吧。资源链接：KMP字符串匹配算法
总结：
-
传统算法（朴素算法）最坏情况是O(nm)，但一般是在O(n+m)，也不是太坏，所以一般没有特殊要求的程序还在用这种算法；
-
KMP算法在有大量重复的情况下优化明显，对主串较大时比较有效；
-
next函数还是有缺陷的，比如模式串'aaaab'与主串'aabaaaab'匹配时，用时几乎和朴素算法一样；
-
以发展的眼光看问题，其实作为常用算法之一，匹配算法也有发展，KMP已经不是主流。
文本编辑程序问题
文本编辑程序中通过设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。如果在某行内插入或删除若干字符，则要修改行表中该行的长度。若该行的长度超出了分配给它的存储空间，则要为该行重新分配存储空间，同时还要修改该行的起始位置。
为了查找方便，行表是按行号递增顺序存储的，因此，对行表惊醒的插入或删除运算需移动操作位置以后的全部表项，页表的维护则和行表类似。
由于访问是以页表和行表作为引索的，所以在作行和页的删除操作时，可以只对行表和页表相应的修改，不必删除所涉及的字符，可以节省不少空间。
第四章其实已经看完三天了，这三天又是亚洲区域赛网络赛又是去打针，没有什么比不健康的身体状况更糟糕了，几天终于好些了，一口气把第四章的笔记整理完毕，好收拾旧行装，继续上路。
C++ 基本概念
又回到了刚开始大学生活的感觉，当时在啃蓝书，厚厚的一本，感觉没有尽头。现在的C++更厚，而且，做笔记看书是最慢的，感觉没有尽头。
C++能够使用printf，scanf和其他所有标准C的输入输出函数，只需要包含常规C语言的stdio.h头文件。
C++和C一样，也是用终止符，而不是分隔符，终止符是一个分毫，它是语句的结束标记，是语句的组成部分。而不是语句之间的标记。
C++句法要求main（）函数的定义以函数头int main（）开始，main函数有返回值是个好习惯，到现在为止上课老师依然是void实在蛋疼。
Main函数如果没有参数，则应加上void。对于main函数来说，可以不加return 0，ANSI/ISO C++标准允许这么做，当不加return语句时会自动补上return 0，但是这个标准不适用于其他函数，当然，不加return 是个不好的习惯。
像iostream这样的文件叫做包含文件，C语言的传统是头文件使用拓展名.h，将其作为一种通过名称标识文件类型的简单方式，而C++的头文件没有拓展名，有些头文件被转换为C++头文件，这些文件被重新命名，去掉了拓展名.h，并加上了前缀c，如stdio.h变为cstdio。对于去掉h，，不是C++形式上的变化，没有h的头文件可以包含名称空间。
如果使用iostream而不是iostream.h（C++旧式风格）应使用using namespace std；名称空间编译指令来使iostream中的定义对程序可用。
名称空间支持是一项C++的特性，旨在编写大型程序以及将多个厂商现有的代码组合起来的程序时更容易。
名称空间：：内容；
按着这种方法，类、函数和变量便是Ｃ＋＋编辑器的标准组件。
“C++拓展了运算符重载的概念允许为用户定义的类型（类）重定义运算符的含义。
诸如endl等对cout来说有特殊含义的特殊符号被称为控制符。
C++也支持Ｃ的旧式方法换行“n”，但与endl的区别是endl确保程序继续运行前刷新输出（刷新缓冲区，立即显示在屏幕上），而是用“n”不能提供这样的保证。
C++源代码的风格
- 每条语句占一行
- 每个函数都有一个开始花括号和一个结束花括号，这两个花括号各占一行
- 函数中的语句都相对于花括号进行缩进
- 与函数名称相关的圆括号周围没有空白
空行将声明语句与程序其它部分非开，这是C常用方法但在C++中不那么常见。
与printf相比，cont能识别类型，cout的设计更灵活，更好用，另外，它是可扩展的，也就是说可以重新定义“<<”运算符，使cout能够识别和显示所开发的新数据类型，如果喜欢printf提供的细致的控制功能，可以使用更高级的cout来获得相同的效果。（C的输入输出和C++的输入输出是两个不同的缓存区，导致C++输入输出较慢，如何解决C++输入慢）。
类之于对象，如同数据类型之于变量，类定义描述了数据格式及其用法。类描述了一种数据类型的全部属性（包括可执行的操作）。
C++程序应当为程序中使用的每个函数提供原理。
在特定函数中使用类似using std::cont这样的编译命令而不是using namespace std；更节省。
个人命名风格特别值得注意，它有助于保持一致性和精确性，精确、让人一目了然的个人命名约定是良好的软件工程的标识。
C++有六种类型的语句：
- 声明语句
- 赋值语句
- 消息语句：将消息发送给对象，激发某种行为
- 函数调用
- 函数原型
- 返回语句
类是用户定义的数据类型规范，详细描述了如何表示信息以及可对数据执行哪些操作，对象是根据类规范创建的实体。
C++ PP前十章的内容算是过第二遍了，而前七章和蓝书无差，都看烦了= =，感觉再看下去就要背下来了。不过再简单的东西，为了十章以后的深入，就这样忍了吧。
Copyright © 2020 Powered by MWeb, Theme used GitHub CSS.