数据结构课程设计第二周解题报告——有关两个字符串的编辑距离

目录

题目A 手撕STL sort (40 分)

题目B 冬奥会接驳车 (40 分)

题目C 自动纠错 (20 分) 

C++ STL是Standard Template Library的简称，即标准模板库。简单来说，STL将常用的数据结构与算法进行了封装，用户需要时可以直接调用，不用重新开发。排序算法sort( )是STL包含的一个重要算法。

 

STL中的sort()函数基于快速排序算法实现，众所众知，快速排序是目前已知平均情况下最快的排序算法，被IEEE评选为20世纪十大算法之一，但其最坏情况下时间复杂度会退化为O(n2)。STL中的sort()对传统快速排序做了巧妙的改进，使其最坏情况下时间复杂度也能维持在O(nlogn)，它是如何实现的呢？

快速排序算法最坏情况下时间复杂度退化为O(n2)的主要原因是，每次划分（Partition）操作时，都分在子数组的最边上，导致递归深度恶化为O(n)层。而STL的sort()在Partition操作有恶化倾向时，能够自我侦测，转而改为堆排序，使效率维持在堆排序的O(nlogn)。其具体方法是：侦测快速排序的递归深度，当递归深度达到⌊2log2​n⌋=O(logn)层时，强行停止递归，转而对当前处理的子数组进行堆排序。

此外，传统的快速排序在数据量很小时，为极小的子数组产生许多的递归调用，得不偿失。为此，STL的sort()进行了优化，在小数据量的情况下改用插入排序。具体做法是：当递归处理的子数组长度（子数组包含的元素个数）小于等于某个阈值threshold 时，停止处理并退出本层递归，使当前子数组停留在“接近排序但尚未完成”的状态，最后待所有递归都退出后，再对整个序列进行一次插入排序（注意不是对当前处理的子数组进行插入排序，而是在快速排序的所有递归完全退出后，对整个数组统一进行一次插入排序）。实验表明，此种策略有着良好的效率，因为插入排序在面对“接近有序”的序列时拥有良好的性能。

在本题中，请你按照上述思路，自己实现STL的sort()函数。

备注：Partition操作选取第1个元素作为基准元素。Partition操作的不同实现可能导致不同的输出结果，为保证输出结果唯一，该操作的实现请以教材为准。 

输入格式:

输入第一行为2个正整数n和threshold，n为待排序的元素个数，不超过50000，threshold为改用插入排序的阈值，不超过20，含义如上所述。第二行为n个空格间隔的整数。本题中读入数据的操作无需你来实现，而由框架程序完成。已经将框架直接加入代码。

输出格式:

输出第一行为以depth_limit:开头的整数，表示转为堆排序的递归深度，即⌊2log2​n⌋。从第二行开始，输出对某子数组转为堆排序后，该子数组初始建堆的结果，每个元素后一个空格，每个堆占一行，以Heap:开头。注意，可能不止一个堆。接下来下一行，输出n个整数，每个整数后一个空格，为快速排序所有递归退出后，插入排序执行前的数组元素，以Intermediate:开头。最后一行为n整数，每个整数后一个空格，表示排序后的数组，以Final:开头

输入样例1：

10 2
10 9 8 7 6 5 4 3 2 1

输出样例1

depth_limit:6
Heap:7 6 5 4 
Intermediate:1 2 3 4 5 6 7 8 9 10 
Final:1 2 3 4 5 6 7 8 9 10 

输入样例2

60 2
66 61 92 22 50 80 39 2 25 60 49 17 37 19 24 57 40 82 11 52 45 0 33 78 32 25 19 42 92 50 39 87 74 87 56 79 63 63 80 83 50 3 87 2 91 77 87 10 59 23 25 6 49 85 9 95 60 16 28 1 

输出样例2

depth_limit:11
Heap:24 19 23 19 17 22 
Intermediate:1 0 2 2 3 6 10 9 11 16 17 19 19 22 23 24 25 25 25 28 32 33 37 39 39 42 40 45 49 49 50 50 50 52 56 57 59 60 60 61 63 63 66 77 74 78 79 80 80 82 83 85 87 87 87 87 91 92 92 95 
Final:0 1 2 2 3 6 9 10 11 16 17 19 19 22 23 24 25 25 25 28 32 33 37 39 39 40 42 45 49 49 50 50 50 52 56 57 59 60 60 61 63 63 66 74 77 78 79 80 80 82 83 85 87 87 87 87 91 92 92 95 

函数接口定义： 

void sort(int *R, int n);

void sort(int *R,int n)
{
	R[n+1]=100000000;//将n+1赋值成无穷大 
	value = 2*log(n)/log(2);//计算递归层数上限 
	printf("depth_limit:%dn",value);
    QSort(R,1,n,0);//快速排序
	printf("Intermediate:");//无论是否插入排序，都要输出
	for(int i = 1;i<=n;i++)
	{
		printf("%d ", R[i]);
		if(i==n)printf("n");
	}
    if(flag==1)
    {
    	insertSort(R,n);
	}
	return;
}

解题思路：

本题的目的是实现C++STL库中的sort()排序，它只是简单的排列整数，但是也让我们感受了一波sort的内部实现过程：最开始先快排，在递归层数达到限制2*logn/log2时，在本层对子数组进行堆排序，（防止快排退化）若分划子数组长度可以减小达到threshold值，（插入排序更加合适）做标记，记得最后进行插入排序。值得注意的是：无论是否进行插入排序，"Intermediate:"必然要输出。解题思路题目中也已经给出，我们直接看代码吧。 

#include
#include
#include
using namespace std;


int threshold; 
int b[50010];
int value;
int flag = 0;

void restore(int f,int e){ //大根堆 
	int j=f;//指向树根 
	int m;
	while(j<=e/2)
	{
		if(2*jb[j])
		{
			swap(b[m],b[j]);
			j=m;
		}
		else j=e;
	}
}
void heapSort(int *R,int m,int n)//堆排序 
{	
    //初始建堆 
	int len= n- m +1;
	for(int i=len/2;i>=1;i--){
		restore(i,len);
	}
	printf("Heap:");//输出初始建堆的子数组 
    for(int i = 1;i <= len;i++)
    {
    	printf("%d ",b[i]);
    	if(i==len)printf("n");
	}
	// 堆排序 
	for(int i=len;i>=2;i--)
	{
		swap(b[1],b[i]);
		restore(1,i-1);
	}
	return;
}

int Partition(int *R,int m,int n)
{//分划函数，按照要求，以第一个元素为基准元素 
	int i = m, j = n+1, k = R[m];
	while(ik){j--;}
		if(i= 0; j--)
            if (R[i] > R[j])break;
            if (j != i - 1)
            {
                value0  = R[i];
                for (int k = i - 1; k > j; k--)
                    R[k + 1] = R[k];
                R[j + 1] = value0;
            }
     }
}


void sort(int *R,int n)
{
	R[n+1]=100000000;//将n+1赋值成无穷大 
	value = 2*log(n)/log(2);//计算递归层数上限 
	printf("depth_limit:%dn",value);
    QSort(R,1,n,0);
	printf("Intermediate:");
	for(int i = 1;i<=n;i++)
	{
		printf("%d ", R[i]);
		if(i==n)printf("n");
	}
    if(flag==1)
    {
    	insertSort(R,n);
	}
	return;
}


int main()
{
    int n,i;
    int a[50010];
    scanf("%d %d", &n, &threshold);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    sort(a,n);
    
    printf("Final:");
    for (i = 1; i <= n; i++)
        printf("%d ",a[i]);
    printf("n");
    return 0;
}

艾灵是冬奥会的一名运动员，今天她准备从奥运村前往比赛场馆进行比赛，本届冬奥会科技感十足，奥组委配备了无人驾驶的接驳车。假定你是奥组委的软件工程师，请你为无人接驳车编写路径规划程序，使其载着艾灵以最短的时间到达目的地。

接驳车的运行范围可以被建模为一张由n行m列单元格组成的地图。有的单元格是空地，可以走；有的单元格处是障碍物，不能走。假定接驳车只可以朝上、下、左、右四个方向行驶，不能斜着走。每行驶过一个位置（单元格）需要1分钟。给定地图以及艾灵的起点和终点，请输出接驳车从起点行驶到终点所需的最短时间。 

输入格式:

输入包含多组数据。每组数据第一行是两个整数n和m (1≤ m, n ≤100)，表示地图的长和宽；接下来是n行，每行m个数字，表示整个地图。空地格子用0表示，障碍物用1表示，艾灵所在起点用3表示，目的地用4表示。

输出格式:

对于每组数据，如果接驳车能够到达目的地，输出一个整数，表示艾灵从起点到目的地所需的最短时间，如果不能到达目的地，输出“unreachable”。

输入样例:

5 5
1 0 1 1 1
1 0 4 1 0
1 0 0 1 0
0 0 0 1 0
1 0 3 0 1
5 5
3 0 1 1 1
1 0 1 1 0
1 0 1 1 0
0 0 0 1 0
1 0 1 0 4

输出样例:

3
unreachable

解题思路+注意：

这道题就是典型的迷宫问题 ，站在某一块空地上，只能朝前后左右四个方向走去，第一个思路应该是回溯法+深度优先搜索，但是深度优先搜索对于找最短路径迷宫问题，深搜就有些效率不高，因为找到一条通路我们也没法保证他就是最短的路径。如果用广度优先遍历的话，就可以一层一层找，将队列头部节点所有符合情况的儿子节点放入队列，如果出现到达目的地的情况，显然就是最短情况。

题目中用到的数据结构是队列，由于不允许使用STL，所以我简单模拟了Queue，first是头指针，rear是尾指针。

需要注意到的是，要防止数组访问越界，因为不是对任意一块空地，都可以朝四个方向走，并且为了优化，我做了一个标记，记录到达此块空地的方式，例如：若到某块空地是由上一步向下移动得来的，那么从这块空地出发时，就不再向上了；若到某块空地是由上一步向左移动得来的，那么从这块空地出发时，就不再向右了。虽然进入过队列的节点之后也一定不会再进入队列，因为box[i][j]值被赋值-1，变成了不可走的格子，但是通过做标记跳过一种情况可以相对减少一些赋值和比较操作，更节省时间。

 代码如下：

#include
using namespace std;


int box[102][102];

struct site
{
	int i;
	int j;
	int ceng ;//层数
	int num0;//标记自己是怎么得来的。 
};
typedef struct 
{
	site data[10005];
	int first ;
	int rear;
}Queue;

Queue store;
int path(int n, int m,int x1,int y1,int x2,int y2)
{
	int i,j;
	int Case;
	store.first = 0;
	store.rear = 0;
	store.data[store.rear].i = x1;
	store.data[store.rear].j = y1;
	store.data[store.rear].ceng = 0;
	store.data[store.rear].num0 = -1;
	store.rear++;
	box[x1][y1] = -1 ;//入队列标记负值
	while(store.first != store.rear)
	{
		Case = -1;
		while(Case<4)
		{
			Case++;
			if(Case==(store.data[store.first].num0+2)%4)continue;//若它由向下移得来，则不考虑向下移动
			switch(Case)
			{
				case 0: {i = store.data[store.first].i;j = store.data[store.first].j-1;break;}//向上 
				case 1: {i = store.data[store.first].i+1;j = store.data[store.first].j;break;}//向右 
				case 2: {i = store.data[store.first].i;j = store.data[store.first].j+1;break;}//向下 
				case 3: {i = store.data[store.first].i-1;j = store.data[store.first].j;break;}//向左 
			}
			
			if((box[i][j]==0)&&i>=0&&j>=0)
			{
			    store.data[store.rear].i = i;
			    store.data[store.rear].j = j;
			    store.data[store.rear].num0 = Case;//记住它是怎么得来的
			    store.data[store.rear].ceng = store.data[store.first].ceng+1;
                box[i][j] = -1 ;//入队列标记负值
			    store.rear = (store.rear+1)%10000;
			}//找到可以走的格子
			else if(i == x2 && j == y2)
			{
				return store.data[store.first].ceng + 1;
			}
		}
        //box[store.data[store.first].i][store.data[store.first].j] = 0;
		store.first = (store.first+1)%10000;
	}
	return 0;
}

int main()
{
	int n,m;
	int x1,y1,x2,y2;
	while((scanf("%d %d",&n,&m))!=EOF)
	{
		memset(box,1,sizeof(box));
		for(int i = 0;i < n;i++)
    	{
    		for(int j = 0;j < m;j++)
	    	{
	    		scanf("%d",&box[i][j]);
	    		if(box[i][j]==3){x1=i,y1=j;}
	   	    	if(box[i][j]==4){x2=i;y2=j;}
       		}
    	}
    	int sum = path(n,m,x1,y1,x2,y2);
    	if(sum==0)
    	{
    		printf("unreachablen");
		}
		else
		{
			printf("%dn",sum);
		}
	}
	return 0;
}

百度、谷歌等搜索引擎，以及Word等文字处理软件往往包含这样一个功能：当用户输入了错误的单词时，系统能够自动识别并向用户建议正确的单词。这个功能是如何实现的呢？一种典型的实现方法是：系统后台维护一个“字典”，当用户输入的单词不在字典中时，则认为是错误的单词，并在字典中查找与用户所输单词相似度高且用户使用频率高的单词，向用户建议。

采用“距离”衡量两个单词的相似度。两个字符串的距离定义为一个字符串转化成另一个字符串，所需的最少“操作”次数。有三种操作：增加一个字符、删除一个字符、替换一个字符。显然，距离越大，说明两个字符串的相似程度越小；距离越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串，距离为 0。

例如将FOOD转换成MONEY，最少通过如下4步操作：第1位F替换为M，第3位O替换为N，在第4位插入E，第5位D替换为Y。故FOOD和MONDY的距离为4。

这样，当用户输入错误单词后，则系统可以在字典中查找与该错误单词距离不超过n（n一般不超过3）的单词建议给用户。字典通常包含几万个单词，如果将用户输入单词与字典里的单词逐一比对，显然非常耗时。一种高效的处理方法是：结合各单词间的距离，将字典组织成一棵多叉树。在该树中，每个结点表示一个单词，对于每个结点p，其第 i 棵子树包含与 p 的距离为 i 的所有单词对应的结点。

树的创建过程如下：取字典中任意单词作为根结点，比如第一个单词。然后将剩余单词逐个插入到树中，插入一个新单词 w 时，首先计算该单词与根结点的距离 d 。若根结点的第 d 个子树为空，则将单词 w 对应的结点作为根结点的第 d 个子结点。若根结点的第 d 个子树非空，即根结点已有第 d 个子结点 pd​ 。则按上述规则将单词 w 递归插入以 pd​ 为根的子树，即计算 w 与 pd​ 的距离......。

例如字典为{help, hell, hello, shell, helper, sloop, helps, troop}，将help作为根结点，然后将hell插入，hell与help的距离为1，故hell作为help的第一个子结点。hello与help的距离为2，故hello作为help的第2个子结点。如下图(a)所示。

然后插入shell，shell与help的距离为2，故应在help的第2个子树里，但help已经有第2个子结点hello了，此时将shell递归插入以hello为根结点的子树：计算shell与hello的距离为2，将shell作为hello的第2个子结点，如上图(b)所示。插入helper时，helper与help的距离为2，将helper递归插入以hello为根结点的子树：计算helper与hello的距离为3，将helper作为hello的第3个子结点。以此类推，最终上述字典对应的树结构如上图(c)所示。该树结构保证与任意结点距离为d的单词都在该结点的第d棵子树里。

假定我们需要向用户返回与错误单词距离不超过n的单词，当用户输入一个单词w时，在树中查询w，计算w与根结点T的距离d，接下来我们不必考察T的所有子树中是否包含与w距离不超过n的结点/单词，而只需要递归考察根结点T的第d-n到第d+n棵子树即可。例如n=1，d=5，我们只需要递归考察根T的第4、第5、第6棵子树是否包含与w距离不超过1的结点/单词。其他子树无需考察，为什么呢？举个例子，我们考虑根T的第3棵子树的任意结点P。w与T的距离为d=5，即w最少经过5步操作才能转换为T，T与P的距离为3，T经过最少3步操作才能变为P，这意味着w至少需要2步操作才能变为P。不可能通过1步操作变为P。故第3棵子树的所有结点都不满足条件。

由于n通常很小，因此该方法在查询时往往可以排除很多子树，进而节省时间。当考察一个结点时，计算w与该结点的距离d；若d=0，意味着用户输入的单词w在字典中，是正确的单词；若d > n则该结点不是候选单词，继续递归考察该结点第d-n到d+n的子树。若d ≤ n则该结点就是候选单词之一，此时可有两种策略，一是将该单词直接返回给用户，二是继续向下考察子树，找出所有候选单词并选择用户历史使用频率最高的单词返回给用户。

在本题中，请你编写程序实现上述功能。 

 

输入格式:

输入第1行为3个正整数n、m、d。n为字典中单词个数。m为用户查询数，即用户输入的单词个数。对于用户输入的每个错误单词，程序需要返回与错误单词距离不超过d的单词。接下来n行，表示字典信息，字典包含n个单词及其历史使用频率。每行为1个整数和一个由字母组成的字符串，整数表示单词的历史使用频率，字符串表示单词。接下来m行，表示用户的查询，每行一个字母组成的字符串，表示用户输入的单词。 (n ≤ 10000, m ≤ 1000, d ≤ 2, 每个单词长度不超过15，单词历史使用频率小于231)

输出格式:

对于用户输入的每个单词，若该单词正确（其在字典中），则直接输出该单词；若该单词错误（不在字典中），则输出字典中与该单词距离不超过d的所有单词中历史使用频率最高的单词，若多个满足条件的单词使用频率相等，则返回字典序最靠前的单词；若没有满足条件的单词，则输出No similar word in dictionary。

输入样例：

9 8 2
327769900    my
322417800    are
302713400    me
283256900    one
282026500    their
280248100    so
264141700    an
263713600    said
250991700    them
me
wne
therr
xxxxx
they
ax
sy
sds

输入样例:

me
are
their
No similar word in dictionary
their
my
my
so

解题思路：

这道题的整体思路已经给出，

建字典树（buildTree（int n））：

每存一个单词，都从树的节点开始遍历，然后计算经过节点与所存单词的编辑距离冷，接着访问第len个儿子，直到遍历到空指针。把此单词存入。

检索（queryWord(char str[],node *root,int d)）

递归检测，当len==0，证明找到单词，然后做标记结束递归。当len<=d，符合条件，然后选取最大频率的。

求解编辑距离（stringMatch_MaxSize(char *str1,char *str2)）

关键的算法：计算两个字符串的距离（即两个字符串的编辑距离）可参考：博文https://blog.csdn.net/ac540101。

详细见题目中的详细思路，具体实现看代码。

代码如下：

#include
using namespace std;

struct node
{
	char str[20];
	int num;
	node *next[20]={NULL};
};

node * treeRoot = new node; //字典树的根节点
int maxNum = 0;//最大频率
char similarWord[20];//保留需要输出的单词
int flag = 0;//标记是否距离有<=d的单词或者单词本身


struct dot
{
	char str[20];
	int num;
};

dot word[10010];

int stringMatch_MaxSize(char *str1,char *str2)
{   
    //计算编辑距离
	int max_len[20][20];
	memset(max_len,0,sizeof(max_len));
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	
	//初始化 
	for(int i = 1; i<=len1; i++)
	{
		max_len[i][0]= i;
	}
	for(int i = 1; i<=len2; i++)
	{
		max_len[0][i] = i;
	}
	
	for(int i = 1;i<=len1;i++)
	{
		for(int j = 1; j<=len2; j++)
		{
			if(str1[i-1]==str2[j-1])
			{
				max_len[i][j] = max_len[i-1][j-1];
			}
			else
			{
				if(max_len[i][j - 1] < max_len[i-1][j])max_len[i][j] = max_len[i][j- 1];
				else max_len[i][j] = max_len[i-1][j];
				if (max_len[i][j] > max_len[i - 1][j - 1]) max_len[i][j] = max_len[i - 1][j - 1];
				max_len[i][j] += 1;
			}
		} 
	}
	return max_len[len1][len2];	
}

void buildTree(int n)
{
	node * p;
	for(int i=1;istr);
		//printf("word[%d]:%sn",i,word[i].str);
	    p = treeRoot; 
		int len = stringMatch_MaxSize(p->str,word[i].str);
		while(p->next[len]!=NULL&&len>0)
		{
			//printf("len:%dn",len);
			p = p->next[len];
			len = stringMatch_MaxSize(p->str,word[i].str);
		}
		if(len == 0)continue;
		if(p->next[len]==NULL)
		{
			p->next[len] = new node;
			strcpy(p->next[len]->str,word[i].str);
			p->next[len]->num = word[i].num;
		}
	}		
}

void queryWord(char str[],node *root,int d)
{
	if(root==NULL)return;
	int len = stringMatch_MaxSize(root->str,str);
	if(len == 0)
	{
		//printf("找到了！！！！n");
		flag=1;
        memset(similarWord,'',sizeof(similarWord));
	    strcpy(similarWord,root->str);
    	return;
	}
	else if(len<=d)
	{
		//printf("长度小，欸嘿！！！：%dn",len); 
		flag=2;
		if(maxNumnum)
		{
			maxNum=root->num;
            memset(similarWord,'',sizeof(similarWord));
		    strcpy(similarWord,root->str);
		}
		else if(maxNum==root->num)
		{
			if(strcmp(similarWord,root->str)>0)
			{
                memset(similarWord,'',sizeof(similarWord));
				strcpy(similarWord,root->str);
			}
		}
	}
	int m1;
	if(len-d<=0){m1=1;}
    else {m1 = len-d;}
    int m2;
    if(len +d >15){ m2 = 15;}
    else{m2 = len +d;}
	for(int i = m1; i<= m2 ; i++)
	{
		if(flag==1)break;
		//printf("开始搜索字子树！！！n");
		queryWord(str,root->next[i],d);
	}
	//printf("递归呀！！n"); 
	return;
}

int main()
{
	int n,m,d;
	scanf("%d%d%d",&n,&m,&d);
	for(int i = 0;i < n; i++)
	{
		scanf("%d%s",&word[i].num,word[i].str); 
	}          
	strcpy(treeRoot->str,word[0].str);//初始化根节点 
	treeRoot->num = word[0].num;
	buildTree(n);
	for(int i = 0; i < m; i++)
	{
		char findWord[20];
		memset(findWord,'',sizeof(findWord));
		memset(similarWord,'',sizeof(similarWord));
		flag = 0;
		maxNum = 0;
		scanf("%s",findWord);
		queryWord(findWord,treeRoot,d);
		if(flag>=1)printf("%sn",similarWord);
		else{printf("No similar word in dictionaryn");}
	}
	return 0;
}

请勿直接粘贴抄袭哈！