字符串

1.串就是字符串,是一种特殊的线性表,它的每个结点仅由一个字符组成。串的长度是字符串中字符的长度
2.串值采用顺序存储和链表存储,由于串的数据元素是一个字符,它只有8位二进制数, 因此用链表存储时,通常一个结点中存放的不是一个字符,而是一个子串,例如: 在编辑系统中,整个文本编辑区可以看成是一个串,每一行是一个子串,构成一个结点（顺序存储和链式存储时两种最基本的存储结构，字符串通常采用顺序存储，但是字符串较长而没有那么大的连续空间时，可以把一个字符串分成多个小串，串与串之间采用链式存储）

3. 一个字符串有n个各不相同的字符，则该字符串子串的数目为：n(n+1)/2

分析：1.子串必须是连续的；2.空串也是子串；3.真子串； n+（n-1）+（n-2）....+1 = n(n+1)/2

4.以下代码输出的结果？

#include<stdio.h>
char *myString()
{
    char buffer[6] = {0};
    char *s = "Hello World!";
    for (int i = 0; i < sizeof(buffer) - 1; i++)
    {
        buffer[i] = *(s + i);
    }
    return buffer;
}
int main(int argc, char **argv)
{
    printf("%s
", myString());
    return 0;
}

分析：1.函数char *myString()中没有使用new或者malloc分配内存，所有buffer数组的内存区域在栈区

2. 随着char *myString()的结束，栈区内存释放，字符数组也就不存在了，所以会产生野指针，输出结果未知

5.string->stringBuilder->stringBuffer的区别

效率：StringString(大姐，出生于JDK1.0时代) 不可变字符序列； <StringBuffer(二姐，出生于JDK1.0时代) 线程安全的可变字符序列；<StringBuilder(小妹，出生于JDK1.5时代) 非线程安全的可变字符序列。
Java中的String是一个类，而并非基本数据类型。string是值传入，不是引用传入。 StringBuffer和StringBuilder可以算是双胞胎了，这两者的方法没有很大区别。但在线程安全性方面，StringBuffer允许多线程进行字符操作。这是因为在源代码中StringBuffer的很多方法都被关键字 synchronized 修饰了，而StringBuilder没有。 StringBuilder的效率比StringBuffer稍高，如果不考虑线程安全，StringBuilder应该是首选。
另外，JVM运行程序主要的时间耗费是在创建对象和回收对象上。

6.最优编码a=0, b=10, c=110, d=111

7.若初始序列为gbfcdae，那么至少需要 1 次两两交换，才能使该序列变为abcdefg。任给一个自由a--g这7个字母组成的排列，最坏的情况下需要至少 2 次两两交换，才能使序列变为abcdefg。

key：5次，6次（本质是图论里的拓扑排序问题）

1.将每个字符现在的位置与其排序后的位置连一条单向边，最小两两交换次数为：字符总数-连接后形成的环数（包括自环），gbfcdae中b为自环，而a->g->e->d->c->f->a为另一个环，所以最小交换次数=7-2=5次；

2.最坏情况下是所有字符形成一个环，如gabcdef需要至少6次交换才能变为abcdefg

8.哈弗曼编码又叫前缀编码，不能有任何一个编码是其他的前缀

9.字符串′ababaabab′的nextval为 (0,1,0,1,0,1,0,1,1)

  i       0    1    2    3    4    5    6    7    8
     s     a    b    a    b    a    a    b    a    b
next[i]  -1    0    0    1    2    3    1    2    3
先计算前缀next[i]的值：
next[i]的值主要是看s[i]之前的字符串中重复的子串长度。next[0] = -1，定值。  
next[1]是看s[1]之前的字符串“a”中重复的子串长度为0，故next[1] = 0。
next[2]是看s[2]之前的字符串“ab”中重复的子串长度为0，故next[2] = 0。
next[3]是看s[3]之前的字符串"aba"中重复的子串长度，s[0]与s[2]重复，长度为1，故next[3] = 1。
next[4]是看s[4]之前的字符串"abab"中重复的子串长度，s[01]与s[23]重复，长度为2，故next[4] = 2。
next[5]是看s[5]之前的字符串"ababa"中重复的子串长度，s[012]与s[234]重复，长度为3，故next[5] = 3。
next[6]是看s[6]之前的字符串"ababaa"中重复的子串长度，s[0]与s[5]重复(因为多了一个a，无法找到长度为3的重复字符串，这只能是s[0]和s[5]重复)，长度为1，故next[6] = 1。
同样的，求next[7]和next[8]分别为2和3。
接下来计算nextval[i]的值：
nextval[i]的求解需要比较s中next[i]所在位置的字符是否与s[i]的字符一致，如果一致则用s[next[i]]的nextval的值作为nextval[i]，如果不一致，则用next[i]做为nextval[i]。
nextval[0] = -1,和next[0]的值一样。
nextval[1]，比较s[next[1]] ?= s[1]，next[1] = 0，s[0] = a，而s[1] = b，二者不一致，则nextval[1] = next[1] = 0。
nextval[2]，比较s[next[2]] ?= s[2]，next[2] = 0，s[0] = a，而s[2] = a，二者一致，则nextval[2] = nextval[s[next[2]]] = nextval[s[0]] = -1(严谨来看这么表述是有问题的，因为nextval[2]表示nextval数组中 第3个数值，而nextval[s[0]]表示的是s[0]对应的字母‘a’所对应的nextval值 -1，这里nextval[]的用法并不严谨，只是为了表述方便 )。 
nextval[3]，比较s[next[3]] ?= s[3]，next[3] = 1，s[1] = b，而s[3] = b，二者一致，则nextval[3] = nextval[s[next[3]]] = nextval[s[1]] = 0。
nextval[4]，比较s[next[4]] ?= s[4]，next[4] = 2，s[2] = a，而s[4] = a，二者一致，则nextval[4] = nextval[s[next[4]]] = nextval[s[2]] = -1。
nextval[5]，比较s[next[5]] ?= s[5]，next[5] = 3，s[3] = b，而s[5] = a，二者不一致，则nextval[5] = next[5] = 3。
同样的求nextval[6]，nextval[7]，nextval[8]分别为 0 ，-1 ， 0。
这里是nextval的下标从-1开始，如果从1开始，则其余各位均＋1，nextval为0,1,0,1,0,4,1,0,1