文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

数据结构课的实验题目，涉及到LCA问题，这次暴力解决了，以后学了NB算法回来做个对比...

问题描述:

设计一个算法，计算出给定二叉树中任意2个结点之间的最短路径。

编程任务:

对于给定的二叉树，和二叉树中结点对，编程计算结点对之间的最短路径。

数据输入:

由文件input.txt给出输入数据。第1行有1个正整数n，表示给定的二叉树有n个顶点，编号为1，2，…，n。接下来的n行中，每行有3个正整数a,b,c，分别表示编号为a的结点的左儿子结点编号为b，右儿子结点编号为c。各结点信息按照层序列表的顺序给出。

文件的第n+2行是1个正整数m，表示要计算最短路径的m个结点对。接下来的m行，每行2 个正整数，是要计算最短路径的结点编号。

结果输出:

将编程计算出的m个结点对的最短路径长度输出到文件output.txt。每行3 个正整数，前2 个是结点对编号，第3 个是它们的最短路径长度。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

上周数据结构课在讲二叉树的遍历，老师只讲递归算法，没有什么技术含量，遂自己琢磨非递归算法实现...

前序遍历:先访问根节点，再访问左子树，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点进栈，在栈不空时一直如下循环:出栈，访问，将其右孩子进栈，再将左孩子进栈。

中序遍历:先访问左子树，再访问根节点，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点的左节点全部进栈，然后出栈一个节点，访问。将该节点的右孩子节点进栈，再将右孩子节点的所有左节点全部进栈...如此这般直到栈空为止。

后序遍历:先访问左子树，再访问右子树，最后访问根节点。设置一个栈。先将根节点的左节点全部进栈。出栈一个节点，将该节点的右孩子进栈，再将右孩子的左节点全部进栈...当一个节点的左、右孩子都被访问过后再访问该节点，如此这般直到栈空为止。(判断某节点的右孩子是否被访问，需要单独设置一个指针跟踪刚刚访问的节点。在后序遍历中，某节点的右孩子节点一定刚好在该节点之前被访问)

因为代码的重点是非递归遍历，所以建立二叉树的过程我就使用了"前序递归"。对于如下一棵树，以"#"代表空节点，前序递归建立二叉树需要的输入数据和前序遍历的顺序是一样的，且每个叶子节点的左右孩子均为"#"。

输入:ABDH##I##EJ##K##CF#L##G##
前序遍历:A B D H I E J K C F L G
中序遍历:H D I B J E K A F L C G
后序遍历:H I D J K E B L F G C A

代码如下:

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

今天数据结构课讲树的存储和遍历，老师讲的很简单，也没什么代码要发...唯一看到一个比较重要的东西，总结一下算法好了。

这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。

一、已知二叉树的前序序列和中序序列，求解树。

1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

二、已知二叉树的后序序列和中序序列，求解树。

1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。

2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。

3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。

举例说明：根据已知求解二叉树

中序序列 BDCEAFHG
后序序列 DECBHGFA

1、BDCEAFHG在后序序列中最后出现的元素为A，BDCE|A|FHG
2、BDCE在后序序列中最后出现的元素为B，|B|DCE|A|FHG
3、FHG在后序序列中最后出现的元素为F，|B|DCE|A||F|HG
4、DCE在后序序列中最后出现的元素为C，|B|D|C|E|A||F|HG
5、HG在后序序列中最后出现的元素为G，|B|D|C|E|A||F|H|G|
6、所有元素都已经定位，二叉树求解完成。

                 A
              /     \
             B       F
             \        \
              C       G
             /  \     /
            D    E   H

以前还写过一篇文章《求二叉树的后序遍历 C语言 数组实现》，是已知二叉树的前序遍历和后序遍历，求二叉树的后序遍历。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值，但是如果是考试，那就只能自己来手算这两个数组了，这里分享一下我的计算方法吧。

计算前缀 Next[i] 的值:

我们令 next[0] = -1 。从 next[1] 开始，每求一个字符的 next 值，就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是，这2个"字符串"不能是同一个"字符串")。如果一个都没有，这个字符的 next 值就是0；如果有，就看它有多长，这个字符的 next 值就是它的长度。

计算修正后的 Nextval[i] 值:

我们令 nextval[0] = -1。从 nextval[1] 开始，如果某位(字符)与它 next 值指向的位(字符)相同，则该位的 nextval 值就是指向位的 nextval 值(nextval[i] = nextval[ next[i] ])；如果不同，则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。

举个例子:

计算前缀 Next[i] 的值:

next[0] = -1;定值。
next[1] = 0;s[1]前面没有重复子串。
next[2] = 0;s[2]前面没有重复子串。
next[3] = 0;s[3]前面没有重复子串。
next[4] = 1;s[4]前面有重复子串s[0] = 'a'和s[3] = 'a'。
next[5] = 2;s[5]前面有重复子串s[01] = 'ab'和s[34] = 'ab'。
next[6] = 3;s[6]前面有重复子串s[012] = 'abc'和s[345] = 'abc'。
next[7] = 4;s[7]前面有重复子串s[0123] = 'abca'和s[3456] = 'abca'。

计算修正后的 Nextval[i] 值:

nextval[0] = -1;定值。
nextval[1] = 0;s[1] != s[0]，nextval[1] = next[1] = 0。
nextval[2] = 0;s[2] != s[0]，nextval[2] = next[2] = 0。
nextval[3] = -1;s[3] == s[0]，nextval[3] = nextval[0] = -1。
nextval[4] = 0;s[4] == s[1]，nextval[4] = nextval[1] = 0。
nextval[5] = 0;s[5] == s[2]，nextval[5] = nextval[2] = 0。
nextval[6] = -1;s[6] == s[3]，nextval[6] = nextval[3] = -1。
nextval[7] = 4;s[7] != s[4]，nextval[7] = next[7] = 4。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。

这周的数据结构课讲的是串，本以为老师会讲解KMP算法的，谁知到他直接略过了...没办法只能自己研究，这一琢磨就是3天，期间我都有点怀疑自己的智商...不过还好昨天半夜终于想明白了个中缘由，总结一些我认为有助于理解的关键点好了...

书上有的东西我就不说了，那些东西网上一搜一大片，我主要说一下我理解的由前缀函数生成的next数组的含义，先贴出求next数组的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void GetNext(char* t, int* next)
{
    int i, j, len;
    i = 0;
    j = -1;
    next[0] = -1;
    while(t[i] != '\0')
    {
        if (j == -1 || t[i] == t[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

当一个字符串以0为起始下标时，next[i]可以描述为"不为自身的最大首尾重复子串长度"。

也就是说，从模式串T[0...i-1]的第一个字符开始截取一段长度为m(m < i-1)子串，再截取模式串T[0...i-1]的最后m个字符作为子串，如果这两个子串相等，则该串就是一个首尾重复子串。我们的目的就是要找出这个最大的m值。

例如:

若 i = 4 ，则 i - 1 = 3 ， m = next[4] = 2

从T[0...3]截取长度为2的子串，为"ab"

从T[0..3]截取最后2个字符，为"ab"

此时2个子串相等，则说明 next[4] = 2 成立，也可证明 m = 2 为最大的m值。

本来一开始我是没有加"不为自身"这个限制条件的，可是后来我发现一种情况:

若 i = 4 ，则 i - 1 = 3 ， m = next[4] = 3

从T[0...3]截取长度为3的子串，为"aaa"

从T[0..3]截取最后3个字符，为"aaa"

此时2个子串相等，则说明 next[4] = 3 成立。

但是我发现如果next[4] = 4：

从T[0...3]截取长度为4的子串，为"aaaa"

从T[0..3]截取最后4个字符，为"aaaa"

此时2个子串也是相等的，那么是不是说明 next[4] 应该等于4呢？

仔细观察后发现，如果 next[4] = 4 ，那么T[0...3]的前4个字符和后4个字符是重合的，并且重复子串和T[0...3]也是相等的。看过教材后发现教材中给出的前缀函数定义有一句为：next[j] = max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]'}，应该不包含子串为本身的情况...

这样再做PKU 2406 和 PKU 1961 的时候就很简单了，用 length - next[length] 求出"不为自身的最大首尾重复子串长度"，此时需要多求一位next[length]值，若最大重复子串的长度是length的非1整数倍，则证明字符串具有周期重复性质。

PKU 2752 是求 前缀 == 后缀 的长度，也就是首尾重复子串长度，利用next数组记录的"不为自身的最大首尾重复子串长度"可以马上得到结果。

恩，先说这么多吧，可能有不对的地方，以后理解的更深了再回来改...哪位大牛路过看到错误请指出哈。

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

昨天数据结构课讲循环链表和双向链表，双向链表没什么意思，不写了；循环链表有个典型应用就是解约瑟夫问题(Josephus)，这里用的典型题目是"猴子选大王"。

题目描述：n只猴子要选大王，选举方法如下：所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第 k 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。

输入数据：猴子总数n，起始报数的猴子编号k，出局数字m

输出数据：猴子的出队序列和猴子大王的编号

代码修改了一天才完成，第一次是用多个函数写的，但是发觉C语言没有引用参数这个特性，使得形参指针不能被直接修改，必须靠返回值来修改才行，这样太麻烦了...于是第二次写的时候就没有使用函数，直接在main()里完成了循环链表的操作，感觉应该没什么问题，哪位大牛看出问题跟我说下，thx...

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

下午研究了一下全排列算法，然后发现C++的STL有一个函数可以方便地生成全排列，这就是next_permutation

在C++ Reference中查看了一下next_permutation的函数声明：

#include <algorithm>
bool next_permutation( iterator start, iterator end );

The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.

从说明中可以看到 next_permutation 的返回值是布尔类型。按照提示写了一个标准C++程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main()
{
    string str;
    cin >> str;
    sort(str.begin(), str.end());
    cout << str << endl;
    while (next_permutation(str.begin(), str.end()))
    {
        cout << str << endl;
    }
    return 0;
}

其中还用到了 sort 函数和 string.begin()、string.end() ，函数声明如下：

#include <algorithm>
void sort( iterator start, iterator end );

sort函数可以使用NlogN的复杂度对参数范围内的数据进行排序。

#include <string>
iterator begin();
const_iterator begin() const;

#include <string>
iterator end();
const_iterator end() const;

string.begin()和string.end() 可以快速访问到字符串的首字符和尾字符。

在使用大数据测试的时候，发现标准C++的效率很差...换成C函数写一下，效率提升了不止一倍...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 100
 
using namespace std;
 
int main()
{
    int length;
    char str[MAX];
    gets(str);
    length = strlen(str);
    sort(str, str + length);
    puts(str);
    while (next_permutation(str, str + length))
    {
        puts(str);
    }
    return 0;
}

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

本来不想发这么水的代码，可是最近也没什么好写的...纯当凑文章数目吧...

这是一个线性表操作的小玩具，此篇为链表版本，也就是用指针和动态内存分配的。

阅读全文...