最长公共子序列程序和实验报告

算法导论实验 最长公共子序列程序源码 实验报告

// LCS.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h“
#define SLANT 0
#define VERTICAL -1
#define CROSSWISE 1




void lengthLCS（string &xint xLenstring &yint yLenint **recordint **direct）
{
	int ij;
	i = j = 0;
	
	for（i=0 ; i		record[i][0] = 0;
	}
	for（j=0 ; j		record[0][j] = 0;
	}

	for（i=1 ; i		for（j=1 ; j			if（x[i-1] == y[j-1]）{
				record[i][j] = record[i-1][j-1] + 1;
				direct[i][j] = SLANT;
			}else{
				if（record[i-1][j] >= record[i][j-1]）{
					record[i][j] = record[i-1][j];
					direct[i][j] = VERTICAL;
				}else{
					record[i][j] = record[i][j-1];
					direct[i][j] = CROSSWISE;
				}
			}
		}
	}
}

void printLCS（string xint xLenint **directint iint j）
{
	if（0==i || 0==j）{
		return;
	}
	if（SLANT == direct[i][j]）{
		printLCS（xxLendirecti-1j-1）;
		cout<	}else if（VERTICAL == direct[i][j]）{
		printLCS（xxLendirecti-1j）;
	}else{
		printLCS（xxLendirectij-1）;
	}
}

void generateString（string &xstring &yint length）
{
	string s = “ABCDEFGHIJKLMNOPQRSTUVWXYZ“;
	for（int i=0 ; i		int num1 = rand（）%26;
		int num2 = rand（）%26;
		string s1（1s[num1]）;
		x = x.append（s1）;
		string s2（1s[num2]）;
		y = y.append（s2）;
	}
	return;
}

int _tmain（int argc _TCHAR* argv[]）
{
	string xy;
	int length = 10000;
	generateString（xylength）;
	/*string x = “ABCBDAB“;
	string y = “BDCABA“;*/
	int xLen = x.length（）;
	int yLen = y.length（）;
	int **record = （int**）malloc（（yLen+1）*sizeof（int*））;
	int **direct = （int**）malloc（（yLen+1）*sizeof（int*））;
	for（int i=0 ; i<=xLen ; ++i）{
		record[i] = （int*）malloc（（xLen+1）*sizeof（int））;
		direct[i] = （int*）malloc（（xLen+1）*sizeof（int））;
	}
	
	lengthLCS（xxLenyyLenrecorddirect）;
	printLCS（xxLendirectxLenyLen）;
	
	getchar（）;
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-12-07 10:02  LCS\
     目录           0  2013-12-07 08:22  LCS\Debug\
     文件       61440  2013-12-07 08:48  LCS\Debug\LCS.exe
     文件      743804  2013-12-07 08:48  LCS\Debug\LCS.ilk
     文件      904192  2013-12-07 08:48  LCS\Debug\LCS.pdb
     目录           0  2013-12-07 06:44  LCS\ipch\
     目录           0  2013-12-07 06:44  LCS\ipch\lcs-48a42a15\
     文件    15532032  2013-12-07 10:00  LCS\ipch\lcs-48a42a15\lcs-65ebb98e.ipch
     目录           0  2013-12-13 18:22  LCS\LCS\
     文件     6180864  2013-12-07 10:02  LCS\LCS.sdf
     文件         876  2013-09-22 18:17  LCS\LCS.sln
     文件       14848  2013-12-07 10:01  LCS\LCS.suo
     目录           0  2013-12-07 08:48  LCS\LCS\Debug\
     文件        2962  2013-12-07 08:48  LCS\LCS\Debug\cl.command.1.tlog
     文件       20326  2013-12-07 08:48  LCS\LCS\Debug\CL.read.1.tlog
     文件        1738  2013-12-07 08:48  LCS\LCS\Debug\CL.write.1.tlog
     文件         406  2013-09-22 18:37  LCS\LCS\Debug\LCS.exe.embed.manifest
     文件         472  2013-12-07 06:45  LCS\LCS\Debug\LCS.exe.embed.manifest.res
     文件         381  2013-12-07 08:48  LCS\LCS\Debug\LCS.exe.intermediate.manifest
     文件          77  2013-12-07 08:48  LCS\LCS\Debug\LCS.lastbuildstate
     文件        2206  2013-12-07 08:48  LCS\LCS\Debug\LCS.log
     文件       93725  2013-12-07 08:48  LCS\LCS\Debug\LCS.obj
     文件     7929856  2013-12-07 06:45  LCS\LCS\Debug\LCS.pch
     文件         196  2013-09-22 18:37  LCS\LCS\Debug\LCS_manifest.rc
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link-cvtres.read.1.tlog
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link-cvtres.write.1.tlog
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link.2784-cvtres.read.1.tlog
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link.2784-cvtres.write.1.tlog
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link.2784.read.1.tlog
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link.2784.write.1.tlog
     文件           2  2013-12-07 08:48  LCS\LCS\Debug\link.2952-cvtres.read.1.tlog
............此处省略29个文件信息