C++、QT文本比较源码

#include "dlgcompareimpl.h" #include <qtextedit.h> DlgCompareImpl::DlgCompareImpl( QWidget* parent /*= 0*/, const char* name /*= 0*/, WFlags fl /*= 0 */ ) { // tEditIcs->setReadOnly(true); // tEditIed->setReadOnly(true); LD("", "CGAATTCAGTTAB"); } DlgCompareImpl::~DlgCompareImpl() { } /* [功 能]： LD算法（Levenshtein Distance）又称为编辑距离算法（Edit Distance）。 他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B，那 么操作的过程的次数表示两个字符串的差异。 */ int DlgCompareImpl::LD( const QString& icsStr, const QString& iedStr ) { //建立LD算法矩阵 INTARRAY L; int icsLength = icsStr.length(); int iedLength = iedStr.length(); L[0][0] = 0; //初始化第一行 for(int i=1; i<=icsLength; i++) L[i][0] = i; //初始化第一列 for (int j=1; j<=iedLength; j++) L[0][j] = j; char icsCh[MAX_CHAR_SIZE]; sprintf(icsCh, icsStr.ascii()); char iedCh[MAX_CHAR_SIZE]; sprintf(iedCh, iedStr.ascii()); qDebug("===%d", L[0][0]); for (int m=1; m<=icsLength; m++) { for (int n=1; n<=iedLength; n++) { //若ai=bj，则LD(i,j)=LD(i-1,j-1) //若ai≠bj，则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1 if(icsCh[m-1] == iedCh[n-1]) L[m][n] = L[m-1][n-1]; else L[m][n] = Min(L[m-1][n-1], L[m][n-1], L[m-1][n]) + 1; qDebug("==%d", L[m][n]); } } QString icsTemp; //记录字符串A的回溯字符 QString iedTemp; //记录字符串B的回溯字符 int mm = icsLength; int nn = iedLength; //开始回溯 while (1) { if (mm ==0 && nn ==0) break; //若当前单元格是在矩阵的第一行，则回溯至左边的单元格，将_添加到匹配字串A，将bj添加到匹配字串B if (mm == 0) { icsTemp = QString(TXT_ADD).arg("_") + icsTemp; iedTemp = QString(TXT_ADD).arg(iedCh[nn-1]) + iedTemp; nn--; } //若当前单元格是在矩阵的第一列，则回溯至上边的单元格，将ai添加到匹配字串A，将_添加到匹配字串B else if (nn == 0) { icsTemp = QString(TXT_ADD).arg(icsCh[mm-1]) + icsTemp; iedTemp = QString(TXT_ADD).arg("_") + iedTemp; mm--; } //若ai=bj，则回溯到左上角单元格，将ai添加到匹配字串A，将bj添加到匹配字串B else if (icsCh[mm-1] == iedCh[nn-1]) { icsTemp = icsCh[mm-1] + icsTemp; iedTemp = iedCh[nn-1] + iedTemp; mm--; nn--; } else { //若ai≠bj，回溯到左上角、上边、左边中值最小的单元格，若有相同最小值的单元格，优先级按照左上角、上边、左边的顺序 Direction nextDir = GetNextDiff(mm, nn, L); switch (nextDir) { case TopLeft: { //若回溯到左上角单元格，将ai添加到匹配字串A，将bj添加到匹配字串B icsTemp = QString(TXT_MODIFY).arg(icsCh[mm-1]) + icsTemp; iedTemp = QString(TXT_MODIFY).arg(iedCh[nn-1]) + iedTemp; mm--; nn--; } break; case Top: { //若回溯到上边单元格，将ai添加到匹配字串A，将_添加到匹配字串B icsTemp = QString(TXT_ADD).arg(icsCh[mm-1]) + icsTemp; iedTemp = QString(TXT_ADD).arg("_") + iedTemp; mm--; } break; case Left: { //若回溯到左边单元格，将_添加到匹配字串A，将bj添加到匹配字串B icsTemp = QString(TXT_ADD).arg("_") + icsTemp; iedTemp = QString(TXT_ADD).arg(iedCh[nn-1]) + iedTemp; nn--; } break; default: break; } } } tEditIcs->setText(icsTemp); tEditIed->setText(iedTemp); return L[icsLength][iedLength]; } int DlgCompareImpl::Min( int a, int b, int c ) { int t = a < b ? a : b; t = t < c ? t : c; return t; } DlgCompareImpl::Direction DlgCompareImpl::GetNextDiff( int i, int j, INTARRAY& array ) { if (array[i-1][j-1] <= array[i][j-1] && array[i-1][j-1] <= array[i-1][j]) return TopLeft; else if(array[i-1][j] <= array[i][j-1]) return Top; else return Left; }