使用C++实现的CYK算法

使用C++实现的CYK算法。形式语言与自动机课程中的算法之一。使用VS2005编译通过。有说明文件。

/*输入示例
S->AB|BC//必须以S开头输入
A->BA|a
B->CC|b
C->AB|a

S->AB
A->AC|a
B->BC|b
C->CC|c

测试的字符串bbabaa
*/

#include 
#include 
#define cnf_length 10//单个表达式的长度（包括“->“）
#define test_length 10//测试表格的宽度
void get_cnf（ char cnf[][cnf_length]）;//得到CNF
int test（ char cnf[][cnf_length]char a[test_length]）;//测试函数
void new_table（ int linechar cnf[cnf_length][cnf_length]char table[][cnf_length]char create[][cnf_length*cnf_length*2]int b_length）;
int main（）
{
    char cnf[cnf_length][cnf_length];
    char a[test_length];

    printf（“请输入CNF，以连续输入两个回车表示输入结束：\n“）;
    get_cnf（cnf）;
    printf（“请输入要测试的字符串：\n“）;
    gets（a）;
    printf（“\n算法演示：\n\n“）;

    test（cnfa）;

    return 0;
}
void get_cnf（ char cnf[][cnf_length]）
{
    int i;

    for （i = 0;i        cnf[i][0] = ‘\0‘;
    i = 0;
    do
    {
        gets（cnf[i]）;
        i++;
    }
    while （ cnf[i-1][0] != ‘\0‘）;
}
int test（ char cnf[][cnf_length]char a[test_length]）
{
    char table[test_length*test_length/2 + test_length/2][cnf_length];
    int ijkmn;
    int a_length;
    int b_length;
    int c_length;
    int line = 0;
    int flag = 0;
    char create[test_length][cnf_length*cnf_length*2];

    for （i=0;i    {
        if （a[i] == ‘\0‘）
        {
            a_length = i;
            break;
        }
    }
    m = 0;
    for （i=0;i    {
        for （j=0;j        {
            for （k=0;k            {
                if （ cnf[j][k] == a[i] ）
                {
                    table[i][m] = cnf[j][0];
                    m++;
                    break;
                }
            }
        }
        table[i][m] = ‘\0‘;
        printf（“%s\t“table[i]）;
        m = 0;
    }
    printf（“\n“）;

    m = 0;
    n = 0;
    b_length = a_length;
    c_length = 0;
    for （i=1;i    {
        for （j=0;j        {
            while （table[j][n] != ‘\0‘）
            {
                for （k=0;table[j+1+c_length][k] != ‘\0‘;k++）
                {
                    create[j][m] = table[j][n];
                    m++;
                    create[j][m] = table[j+1+c_length][k];
                    m++;
                }
                n++;
            }
            n = 0;
            while （table[j+c_length][n] != ‘\0‘）
            {
                for （k=0;table[j+i][k] != ‘\0‘;k++）
                {
                    create[j][m] = table[j+c_length][n];
                    m++;
                    create[j][m] = table[j+i][k];
                    m++;
                }
                n++;
            }
            n = 0;
            create[j][m] = ‘\0‘;
            m = 0;
        }
        line += （b_length-1）;
        line++;
        new_table（linecnftablecreateb_length-1）;
        c_length += b_length;
        b_length--;
    }
    for

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       5971  2008-12-06 13:01  cyk.txt

     文件       4798  2009-06-09 13:44  CYK\CYK\CYK.cpp

     文件       3631  2009-06-09 13:44  CYK\CYK\CYK.vcproj

     文件       1427  2009-06-09 13:49  CYK\CYK\CYK.vcproj.LF-F03B34FFCA42.LFC.user

     文件     535552  2009-06-09 13:49  CYK\CYK.ncb

     文件        875  2009-06-09 13:44  CYK\CYK.sln

    ..A..H.      7680  2009-06-09 13:49  CYK\CYK.suo

     目录          0  2009-06-09 13:44  CYK\CYK

     目录          0  2009-06-09 13:44  CYK

----------- ---------  ---------- -----  ----

               559934                    9