数据结构例程——串的顺序存储应用

　　本文针对数据结构基础系列网络课程(4)：串中第3课时串的顺序存储应用。

例1：串比较
问题: 设计实现串比较运算的算法
算法思路
（1）比较s和t两个串共同长度范围内的对应字符:
① 若s的字符＞t的字符，返回1；
② 若s的字符＜t的字符，返回-1；
③ 若s的字符=t的字符,按上述规则继续比较。
（2）当（1）中对应字符均相同时，比较s和t的长度:
① 两者相等时，返回0；
② s的长度＞t的长度，返回1；
③ s的长度＜t的长度，返回-1。

#include <stdio.h>
#include "sqString.h"
int Strcmp(SqString s,SqString t)
{
    int i,comlen;
    if (s.length<t.length)
        comlen=s.length;    //求s和t的共同长度
    else
        comlen=t.length;
    for (i=0; i<comlen; i++)            //在共同长度内逐个字符比较
        if (s.data[i]>t.data[i])
            return 1;
        else if (s.data[i]<t.data[i])
            return -1;
    if (s.length==t.length)         //s==t
        return 0;
    else if (s.length>t.length)     //s>t
        return 1;
    else  return -1;                //s<t
}
int main()
{
    SqString s,t;
    StrAssign(s,"abcdefg");
    StrAssign(t,"ab");
    printf("s:");
    DispStr(s);
    printf("t:");
    DispStr(t);
    printf("Strcmp(s,t)=%d\n",Strcmp(s,t));

    StrAssign(s,"abcd");
    StrAssign(t,"abcd");
    printf("s:");
    DispStr(s);
    printf("t:");
    DispStr(t);
    printf("Strcmp(s,t)=%d\n",Strcmp(s,t));
    return 0;
}

例2：最长连续相同字符
问题: 求出串中 第一个 最长的 连续相同的 “平台”
算法思路: 循环比较相邻的字符
① 若相邻字符相等，累加相同字符的长度
② 否则
更新最长连续相同字符信息
为继续找出做好准备

#include <stdio.h>
#include "sqString.h"

void LongestString(SqString s,int &index,int &max)
{
    int length=1,i=0,start=0;   //length保存平台的长度
    index=0,max=0;              //index保存最长平台在s中的开始位置,max保存其长度
    while (i<s.length-1)//更正：这里应该为while (i<s.length)，视频中代码有bug
        if (s.data[i]==s.data[i+1])
        {
            i++;
            length++;
        }
        else                //上一个平台结束
        {
            if (max<length) //当前平台长度大,则更新max
            {
                max=length;
                index=start;
            }
            i++;
            start=i;    //初始化下一个平台的起始位置和长度
            length=1;
        }
}
int main()
{
    SqString s;
    int i,j,k;
    StrAssign(s,"aabcsaaaabcdeab");
    printf("s:");
    DispStr(s);
    LongestString(s,i,j);
    printf("最长平台:");
    for (k=i; k<i+j; k++)
        printf("%c",s.data[k]);
    printf("\n");
    return 0;
}