// LD文本比较算法.cpp : 定义控制台应用程序的入口点。
//
#include<stdio.h>
#include<stdlib.h>
#include"ZXM.h"
#include"BXH.h"
/********************************主函数************************************/
int main()
{
/*第一部分，用于将用户输入的两行字符串暂存*/
char *String1 = NULL, *String2 = NULL;
/*链表头指针*/
struct node*NodeHead1 = NULL, *NodeHead2 = NULL;
/*获取用户输入和用户输入的字符串的长度（包括字符串结尾符）*/
int String1Length = GetUserInput(&NodeHead1);
int String2Length = GetUserInput(&NodeHead2);
/*将两链表的数据存入两字符串当中*/
GetNodeDate(NodeHead1, &String1, String1Length);
GetNodeDate(NodeHead2, &String2, String2Length);
/*第一部分，结束*/
/*第二部分，将第一部分暂存的字符串构成算法所需的矩阵*/
/*计算矩阵的行（row)、列（column）、以及两串字符串的最大长度（MaxLength)*/
int row, column, MaxLength;
if (String1Length <= String2Length)
{
row = String1Length + 1;
column = String2Length + 1;
MaxLength = String2Length;
}
else
{
row = String2Length + 1;
column = String1Length + 1;
MaxLength = String1Length;
}
/*构建二维矩阵*/
/*分配行*/
int ** Array = (int**)calloc(row, sizeof(int*));
if (!Array) {
puts("矩阵内存分配失败！");
exit(1);
}
/*分配列*/
for (int i = 0; i < row; i++)
{
Array[i] = (int*)calloc(column, sizeof(int));
if (!Array[i]) {
puts("矩阵列分配失败！");
exit(1);
}
}
/*将较长的字符串放置在矩阵第一行相应位置(称为longstring)，短的放在第一列相应位置(称为shortstring)*/
char*LongString = NULL, *ShortString = NULL;
if (String1Length >= String2Length)
{
LongString = String1;
ShortString = String2;
}
else
{
LongString = String2;
ShortString = String1;
}
/*对矩阵进行初始化*/
Array[1][1] = 0;
/*前两行初始化*/
for (int i = 2; i < column; i++)
{
Array[0][i] = LongString[i - 2];
Array[1][i] = i - 1;
}
/*前两列初始化*/
for (int i = 2; i < row; i++)
{
Array[i][0] = ShortString[i - 2];
Array[i][1] = i - 1;
}
/*剩余矩阵元素赋值*/
AssignValue(Array, row, column);
/**********开发测试内容，输出矩阵，便于调试*********/
/*for (int r = 0; r < row; r++)
{
for (int c = 0; c < column; c++)
{
printf("%d ", Array[r][c]);
}
puts("");
}*/
/******************开发测试内容结束***************/
/*第二部分，结束*/
/*第三部分，回溯输出比较结果*/
/*输出比较结果时，短字符串由于插入了空格符，故创建一个新的字符串储存结果*/
char *ModifiedShortString = (char*)calloc(MaxLength, sizeof(char));
if (ModifiedShortString == NULL)
{
puts("内存分配失败！");
exit(1);
}
/*回溯矩阵，创建比较后的字符串并输出结果*/
if (Array[row - 1][column - 1] == 0) /*判断字符串编译距离是否等于0*/
{
puts("两字符串完全相同");
}
else
{
/*回溯矩阵，创建比较后的字符串*/
OutputBackString(Array, row - 1, column - 1, LongString, ModifiedShortString);
/*输出比较后的字符串*/
puts("\n******完成比较后的字符串******\n");
for (int i = MaxLength - 2; i >= 0; i--) /*maxlength当中计入了字符串结尾'\0'*/
{
putchar(LongString[i]);
}
puts(""); /*换行*/
for (int i = MaxLength - 2; i >= 0; i--) /*length当中计入了字符串结尾'\0'*/
{
putchar(ModifiedShortString[i]);
}
puts("\n\n******比较完成了******\n"); /*换行*/
system("pause");
}
/*第三部分，结束*/
/*释放内存*/
free(String1);
free(String2);
free(ModifiedShortString);
for (int i = 0; i < row; i++)
{
free(Array[i]);
}
free(Array);
return 0;
}
/********************************主函数结束************************************/
