串的顺序存储的应用实例二

苏格拉底是古希腊著名的哲学家。有一天，他带领几个弟子来到一块麦地

边。那时正是麦子成熟的季节，地里满是沉甸甸的麦穗。苏格拉底对弟子们说：

“你们去麦地里摘一个最大的麦穗，只许进不许退。我在麦地的尽头等你们。”

弟子们陆续走进了麦地。到处都是大麦穗，哪一个才是最大的呢？他们埋

头向前走，看看这一株，摇了摇头；看看那一株，又摇了摇头。虽然有人也曾

试着摘了几穗，但想到前面可能还有更大的，于是就毫不犹豫地把手里的麦穗

扔掉了。

就这样，他们一边低着头往前走，一边用心地挑挑拣拣，经过了很长一段

时间。突然，他们听到苏格拉底苍老的、如同洪钟一般的声音：“你们已经到

头了。”这时两手空空的弟子们才如梦初醒。

苏格拉底对弟子们说：“这块麦地里肯定有一穗是最大的，但你们未必能

碰见它；即使碰见了，也未必能作出准确的判断。因此最大的一穗应该就是你

们刚刚摘下的。

---

我们从这个故事里,得到弟子们并没有把手中的麦穗和 遇到的麦穗进行比较 ,所以才会造成没有摘到最大的麦穗 , 我们先摘下第一株麦子 ,然后和遇到的麦子进行比较 ,如果比手中的麦子大, 那我们就丢弃手中的麦子 ,然后去摘更大的麦子 ,直到结束 ,我们一定能摘到想要的麦子.

现在我们就引入一个串比较的问题 :

● 问题

        • 求出串中 一个 最长的 连续相同的平台

 就是最长的连续的字符  ,就像我们找最大麦穗一样 ,逐个对比, 当遇到比当前存储的连续字符上的字符的话,我们就更新最长字符的位置 和 最长字符的长度

● 算法思路

        • 循环比较相邻字符

                ① 若相邻字符相等 , 累加相同字符的长度

                ② 否则:

                        更新最长连续相同字符信息

                        为继续找出做好准备

● 算法实操:

        思路其实很简单 ,我们先从第一个元素开始 , 遍历 ,初始长度是0 ,如果遇到相同的元素, 就把相同字符的长度加一 ,如果遇到 不同字符 ,就说明我们此时的相同字符串就断了 , 我们此时有断掉的字符串长度 ,然后和 保存的最长字符串比较 ,如果小于 ,就不更新  ,如果比保存的字符串大 ,就更新最长字符串 ,注意 我们更新的是 最长字符串的开始地址 和 字符串长度 ,

然后我们后续接着遍历 ,下一个字符串 ,寻找最长字符串 ,直到结束

//传入要进行比较的字符串 ，存储最大字符串的开始地址，存储最大的长度的地址
void LongestString(SqString s,int &index,int&max)
{
	//初始的时候，我们遇到的第一个元素，就默认是最大字符串，所有length标记为1	
	int length=1;
	//从开始出发 标记最大字符串开始地址的 start标记为0,从第一个元素开始 下标为0
	int i=0;
	int start=0;
	//刚开始默认最大的字符地址就是第一个数 ,位序为0, 最大的坐标还没有更新,就默认为0
	index = 0,max = 0;
	//开始遍历循环	
	//遍历的长度小于数组长度的时候,就一直循环遍历
	while (i-1)
	{	
		//如果第一个元素和第二个元素相等的话,就说明是相同字符,长度加一,然后后移
		if(s.data[i]==s.data[i+1])
		{
			//累加相同字符的长度
			//判断相同,则i后移到相同字符的位置,长度加一
			i++;
			length++;
		}
		//当不相等的时候,我们就把这一截截断了,;并且要判断其长度了
		else
		{
			//比较截断的字符串长度和存储的最长字符串信息的长度
			//更新最长连续相同字符信息
			//如果截断的字符串比最大的字符串长度大,则更新长度
			//更新字符串的开始地址
			if(max < length){
			//此时 i 指向的就是最长字符串的最后一个字符
			max=length;
			//最长字符的索引就是开头字符
			index=start;
			}
			//接下来就开始下一个车字符串的对比,每次计算的开始地址也更新为下一个字符串
			//长度也更新为1,从头开始
			//为继续找出做好准备
			// i指向截断字符的后面位置
			i++;
			//索引也更新
			stat=i;
			//长度默认为第一个元素为1
			length=1; 
		}
	
}