本科算法实验-最长公共子序列

本科算法实验-最长公共子序列【数据+代码+说明+流程图+测试用例】

#include
#include

char a[500]b[500];
char num[501][501]; ///记录中间结果的数组
char flag[501][501];    ///标记数组，用于标识下标的走向，构造出公共子序列

void LCS（）
{
    int ij;
    for（i=1;i<=strlen（a）;i++）
    {
        for（j=1;j<=strlen（b）;j++）
        {
            if（a[i-1]==b[j-1]）   ///注意这里的下标是i-1与j-1
            {
                num[i][j]=num[i-1][j-1]+1;
                flag[i][j]=1;  ///斜向下标记
            }
            else if（num[i][j-1]>num[i-1][j]）
            {
                num[i][j]=num[i][j-1];flag[i][j]=2;  ///向右标记
            }
            else
            {
                num[i][j]=num[i-1][j];flag[i][j]=3;  ///向下标记
            }
        }
    }
}

void getLCS（）
{

    char res[500];
    int i=strlen（a）;
    int j=strlen（b）;
    int k=0;    ///用于保存结果的数组标志位
    while（i>0 && j>0）
    {
        if（flag[i][j]==1）   ///如果是斜向下标记
        {
            res[k]=a[i-1];k++;i--;j--;
        }
        else if（flag[i][j]==2）  ///如果是斜向右标记
            j--;
        else if（flag[i][j]==3）  ///如果是斜向下标记
            i--;
    }
  printf（“最长公共子序列：\n“）;
    for（i=k-1;i>=0;i--）printf（“%c“res[i]）;
}

int main（）
{
    int in;

    FILE *fp;
    char number;
    srand（（unsigned） time（NULL））; //用时间做种，每次产生随机数不一样
    printf（“两个序列的字母个数：“）;
    scanf（“%d“&n）;
    fp=fopen（“input.txt““w“）;
    if（fp==NULL）
    {
        printf（“open file failed\n“）;
        return -1;
    }

    for （i=0; i    {
        a[i] =rand（） % 4 + ‘a‘ ; //产生字母的随机数
        fprintf（fp“%c “a[i]）;
    }
    fprintf（fp“\n“）;

    for （i=0; i    {
        b[i] =  rand（） %4 + ‘a‘ ; //产生字母的随机数
        fprintf（fp“%c “b[i]）;
    }
    fprintf（fp“\n“）;
    fclose（fp）;
    printf（“随机产生的两个序列为：\n“）;
    for （i=0; i    {
        printf（“%c “a[i]）;
    }
    printf（“\n“）;

    for （i=0; i    {
        printf（“%c “b[i]）;
    }
    printf（“\n“）;

    memset（num0sizeof（num））;
    memset（flag0sizeof（flag））;
    LCS（）;
    printf（“长度：%d\n“num[strlen（a）][strlen（b）]）;
    getLCS（）;
    return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        2004  2016-12-05 12:09  最长公共子序列\input.txt
     文件        2274  2016-12-05 15:18  最长公共子序列\最长公共子序列.c
     文件       31523  2016-12-05 12:22  最长公共子序列\最长公共子序列.exe
     文件        3400  2016-12-05 12:22  最长公共子序列\最长公共子序列.o
     文件       10633  2016-12-05 12:11  最长公共子序列\测试用例.xlsx
     文件       76319  2016-12-05 15:17  最长公共子序列\说明+流程图.docx
     目录           0  2019-01-06 15:47  最长公共子序列\