串结构——顺序串、链串

串结构的定义和属性#

“串”即是我们平常讨论的字符串，串是由零个或多个字符（只能是字符）组成的有穷序列。

通常记为 $S=”a_1a_2a_3…a_n”$，每个 $a_i$ 代表一个字符，其中 $i$ 表示字符在串中的位置$(1<=i<=n)$。

串结构的几个属性：

长度：串中的字符个数
空串：长度为0的串称为空串
子串：在一个串中任意个连续字符组成的子序列（含空串），称为该串的子串
真子串：不包含自身的所有子串
串相等：长度相等，每个字符的位置也相等的两个串

一个长度等于n的串

真子串的数量：$\frac{n(n+1)}{2}$

子串的数量 = 真子串的数量 + 1 = $\frac{n(n+1)}{2} + 1$

例如串abcd，子串的组合情况和数量如下：

串长度数量子串

0 1 空串

1 4 a,b,c,d

2 3 ab,bc,cd

3 2 abc,bcd

4 1 abcd

total 11

串长度	数量	子串
0	1	空串
1	4	a,b,c,d
2	3	ab,bc,cd
3	2	abc,bcd
4	1	abcd
total	11

串结构的抽象数据类型#

ADT String
{
数据对象：
	D = {ai | ai∈ElemType, i=1,2,…,n, n≧0 } //ElemType为类型标识符
数据关系：
	R = {<ai, ai+1> | ai, ai+1∈D, i=1,3,…,n-1 }
数据操作：
    (1) strSeq * InitStr();                                 //  初始化串
    (2) void StrAssign(strSeq *s,char cstr[]);              //  字符串常量cstr赋给串s
    (3) void DispStr(strSeq *s);                            //  输出串
    (4) strSeq * InsStr(strSeq *s,int i,strSeq *s1);        //  串插入
    (5) strSeq * StrCopy(strSeq *s);                        //  复制串s，返回新串
    (6) Bool StrEqual(strSeq *s,strSeq *t);                 //  串相等
    (7) int StrLength(strSeq *s);                           //  求串长
    (8) strSeq * Concat(strSeq *s,strSeq *t);               //  串连接
    (9) strSeq * SubStr(strSeq *s,int i,int j);             //  求子串
    (10) strSeq * DelStr(strSeq *s,int i,int j) ;            //  串删除
    (11) strSeq * RepStr(strSeq *s,int i,int j,strSeq *t);   //  串替换
}

虽然串是一种特殊的线性表，与线性表具有类似的逻辑结构。
但是从抽象数据类型的抽象方法可以看出来，串和线性表的操作有较大的区别。

串通常以整体作为操作的对象，可以从作为参数的输入和作为结果的返回看出。
而线性表通常以单个元素作为操作的对象。

顺序串#

定义顺序串的存储结构：

#define MaxSize 100    
typedef struct
{   char data[MaxSize];         
    int length;                 
} strSeq;

字符变量cstr赋值给串方法 StrAssign 和串复制方法 StrCopy 比较类似，区别是遍历字符变量cstr时，是否以 '\0' 结束。

方法 InsStr, SubStr, DelStr, RepStr 中有参数 $i$ ，表示逻辑序号，需要转换成物理序号，避免发生越界错误。

顺序串代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100          
#define true 1
#define false 0

typedef int Bool;
typedef struct
{   char data[MaxSize];         
    int length;                 
} strSeq;

strSeq * InitStr();                                 //  初始化串
void StrAssign(strSeq *s,char cstr[]);              //  字符串常量cstr赋给串s
void DispStr(strSeq *s);                            //  输出串
strSeq * InsStr(strSeq *s,int i,strSeq *s1);        //  串插入
strSeq * StrCopy(strSeq *s);                        //  复制串s，返回新串
Bool StrEqual(strSeq *s,strSeq *t);                 //  串相等
int StrLength(strSeq *s);                           //  求串长
strSeq * Concat(strSeq *s,strSeq *t);               //  串连接
strSeq * SubStr(strSeq *s,int i,int j);             //  求子串
strSeq * DelStr(strSeq *s,int i,int j) ;            //  串删去
strSeq * RepStr(strSeq *s,int i,int j,strSeq *t);   //  串替换


int main()
{
    strSeq *s,*s1,*s2,*s3,*s4,*s5;
    printf("串的基本运算如下:\n");
    printf("  (0)初始化串s:\n");
    s = InitStr();
    char cstr[] = "abcdefghijklmn";
    printf("  (1)字符串 %s 赋值给s\n",cstr);
    StrAssign(s,cstr);
    printf("  (2)输出串s:");
    DispStr(s);
    printf("  (0)初始化串s1:\n");
    s1 = InitStr();
    StrAssign(s1,"123");
    printf("  (2)输出串s1:");
    DispStr(s1);
    printf("  (3)串s的长度:%d\n",StrLength(s));
    printf("  (4)在串s的第9个字符位置插入串s1而产生串s2\n");
    s2 = InsStr(s,9,s1);
    printf("  (5)输出串s2:");
    DispStr(s2);
    printf("  (6)删除串s第2个字符开始的5个字符而产生串s2\n");
    s2 = DelStr(s,2,5);
    printf("  (7)输出串s2:");
    DispStr(s2);
    printf("  (8)将串s第2个字符开始的5个字符替换成串s1而产生串s2\n");
    s2 = RepStr(s,2,5,s1);
    printf("  (9)输出串s2:");
    DispStr(s2);
    printf("  (10)提取串s的第2个字符开始的10个字符而产生串s3\n");
    s3 = SubStr(s,2,10);
    printf("  (11)输出串s3:");
    DispStr(s3);
    printf("  (12)将串s1和串s2连接起来而产生串s4\n");
    s4 = Concat(s,s1);
    printf("  (13)输出串s4:");
    DispStr(s4);
    printf("  (14)复制串s返回s5\n");
    s5 = StrCopy(s);
    printf("  (15)输出串s5:");
    DispStr(s5);
    printf("  (16)比较串s和s5\n");
    if(StrEqual(s,s5))
        printf("  (17)串s和s5相等");
    else
        printf("  (17)串s和s5不相等");
    
    return 0;
}

strSeq * InitStr()
{
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    return tmp;
}

void StrAssign(strSeq *s,char cstr[])
{
    int i = 0;
    while (cstr[i] != '\0')
    {
        s->data[i] = cstr[i];
        i++;
    }
    s->length = i;
}

strSeq * InsStr(strSeq *s,int i,strSeq *s1)
{
    int j,k;
    strSeq *tmp  = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    i--;
    if(i < 0 || i > s->length)
        return tmp;
    if(s->length + s1->length > MaxSize)
        return tmp;

    for ( j = 0; j < i; j++)
        tmp->data[j] = s->data[j];
    for ( k = 0; k < s1->length; k++)
        tmp->data[j+k] = s1->data[k];    

    for ( j = i; j < s->length; j++)
        tmp->data[j+s1->length] = s->data[j];

    tmp->length = s->length + s1->length;
    return tmp;
}

void DispStr(strSeq *s)
{
    for (int i = 0; i < s->length; i++)
    {
        printf("%c ",s->data[i]);
    }
    printf("\n");
}


strSeq * Concat(strSeq *s,strSeq *t)
{
    int k,l;
    strSeq *tmp  = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;

    for(k=0;k<s->length;k++)
        tmp->data[k] = s->data[k];

    for(k=0;k<t->length;k++)
        tmp->data[s->length+k] = t->data[k];

    tmp->length = s->length + t->length;
    return tmp;
}


int StrLength(strSeq *s)
{
    return s->length;
}

strSeq * SubStr(strSeq *s,int i,int j)
{
    int k,l;
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;

    if(i+j-1 > s->length)
        return tmp;
    i--;
    for(k=i,l=0;l<j;l++,k++)
        tmp->data[l] = s->data[k];

    tmp->length = j;
    return tmp;
}

strSeq * RepStr(strSeq *s,int i,int j,strSeq *t)
{
    int k,l;
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;

    if(i+j-1 > s->length)
        return tmp;
    i--;
    for(k=0,l=0;k<i;k++,l++)
        tmp->data[l] = s->data[k];

    for(k=0;k<t->length;k++,l++)
        tmp->data[l] = t->data[k];

    for(k=i+j;k<s->length;k++,l++)
        tmp->data[l] = s->data[k];

    tmp->length = s->length-j+t->length;
    return tmp;
}

strSeq * DelStr(strSeq *s,int i,int j)
{
    int k,l;
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    //  元素数量不够，返回空
    if (i+j-1 > s->length)
        return tmp;
    i--;
    for ( k = 0,l = 0; k < i; k++,l++)
        tmp->data[l] = s->data[k];
    
    for ( k = i+j; k < s->length; k++,l++)
        tmp->data[l] = s->data[k];
    
    tmp->length = s->length-j;
    return tmp;
}

//  复制串s，返回新串
strSeq *StrCopy(strSeq *s)
{
    strSeq *tmp = (strSeq *)malloc(sizeof(strSeq));
    tmp->length = 0;
    for(int i=0;i<s->length;i++)
        tmp->data[i] = s->data[i];

    tmp->length = s->length;
    return tmp;
}

Bool StrEqual(strSeq *s,strSeq *t)
{
    if(s->length != t->length)
        return false;

    for(int i=0;i<s->length;i++)
        if(s->data[i] != t->data[i])
            return false;

    return true;
}

链串#

链串的存储结构定义为：

typedef struct node
{
    char data;
    struct node *next;
} strLink;

链串代码实现：

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef int Bool;
typedef struct node
{
    char data;
    struct node *next;
} strLink;

strLink * InitStr();                                    //初始化串
void StrAssign(strLink *s,char cstr[]);                 //字符串常量cstr赋给串s
void DispStr(strLink *s);                               //输出串
int StrLength(strLink *s);                              //求串长
strLink * InsStr(strLink *s,int i,strLink *t);          //串插入
strLink * DelStr(strLink *s,int i,int j);               //串删去
strLink * RepStr(strLink *s,int i,int j,strLink *t);    //串替换
strLink * SubStr(strLink *s,int i,int j);               //求子串
strLink * Concat(strLink *s,strLink *t);                //串连接
strLink * StrCopy(strLink *s);                          //复制串s，返回新串
Bool StrEqual(strLink *s,strLink *t);                   //判串相等

int main()
{
    strLink *s,*s1,*s2,*s3,*s4,*s5;
    printf("链串的基本运算如下:\n");
    printf("  (1)建立串s和串s1\n");
    s = InitStr();
    StrAssign(s,"abcdefghijklmn");
    printf("  (2)输出串s:");
    DispStr(s);
    s1 = InitStr();
    StrAssign(s1,"123");
    printf("  (2)输出串s1:");
    DispStr(s1);
    printf("  (3)串s的长度:%d\n",StrLength(s));
    printf("  (4)在串s的第9个字符位置插入串s1而产生串s2\n");
    s2 = InsStr(s,9,s1);
    printf("  (5)输出串s2:");
    DispStr(s2);
    printf("  (6)删除串s第2个字符开始的5个字符而产生串s2\n");
    s2=DelStr(s,2,5);
    printf("  (7)输出串s2:");
    DispStr(s2);
    printf("  (8)将串s第2个字符开始的5个字符替换成串s1而产生串s2\n");
    s2 = RepStr(s,2,5,s1);
    printf("  (9)输出串s2:");
    DispStr(s2);
    printf("  (10)提取串s的第2个字符开始的10个字符而产生串s3\n");
    s3 = SubStr(s,2,10);
    printf("  (11)输出串s3:");
    DispStr(s3);
    printf("  (12)将串s和串s1连接起来而产生串s4\n");
    s4 = Concat(s,s1);
    printf("  (13)输出串s4:");
    DispStr(s4);

    printf("  (14)复制串s返回s5\n");
    s5 = StrCopy(s);
    printf("  (15)输出串s5:");
    DispStr(s5);

    printf("  (16)比较串s和s5\n");
    if(StrEqual(s,s5))
        printf("  (17)串s和s5相等");
    else
        printf("  (17)串s和s5不相等");
    return 0;
}

strLink * InitStr()
{
    strLink *tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;
    return tmp;
}

void StrAssign(strLink *s,char cstr[])
{
    int i = 0;
    strLink *tmp,*p;
    p = s;
    while(cstr[i] != '\0')
    {
        tmp = (strLink *)malloc(sizeof(strLink));
        tmp->data = cstr[i];
        p->next = tmp;
        p = tmp;
        i++;
    }
    p->next = NULL;
}

void DispStr(strLink *s)
{
    strLink *tmp = s->next;
    while (tmp != NULL)
    {
        printf("%c ",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}

int StrLength(strLink *s)
{
    strLink *tmp = s->next;
    int i = 0;
    while (tmp != NULL)
    {
        i++;
        tmp = tmp->next;
    }
    return i;
}

strLink * InsStr(strLink *s,int i,strLink *t)
{
    strLink *tmp,*p1=s->next,*p2=t->next,*q,*r;
    int j;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;
    i--;    //  逻辑顺序转物理顺序
    if(i < 0 || i > StrLength(s))
        return tmp;

    r = tmp;
    for ( j = 0; j < i; j++)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }

    while(p2 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p2->data;
        r->next = q;
        r = q;
        p2 = p2->next;
    }
    for ( j = i; j < StrLength(s); j++)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }
    r->next = NULL;
    
    return tmp;  
}

strLink *DelStr(strLink *s,int i,int j)
{
    strLink *tmp,*r,*q,*p = s->next;
    int k=0;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    if(i+j-1 > StrLength(s))
        return tmp;
    r = tmp;
    i--;
    while (k < i)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
        k++;
    }

    while (k < i+j){
        p = p->next;
        k++;
    }
    
    while ( k < StrLength(s))
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;  
        k++;    
    }
    r->next = NULL;
    return tmp;
}


strLink *RepStr(strLink *s,int i,int j,strLink *t)
{
    strLink *tmp,*r,*q,*p1=s->next,*p2=t->next;
    int k = 0;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    if(i+j-1 > StrLength(s))
        return tmp;
    r = tmp;
    i--;
    while (k < i)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
        k++;
    }

    while (p2 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p2->data;
        r->next = q;
        r = q;
        p2 = p2->next;
    }

    while (k < i+j)
    {
        p1 = p1->next;
        k++;
    }

    while ( k < StrLength(s))
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;  
        k++;    
    }
    r->next = NULL;

    return tmp;   
}

strLink * SubStr(strLink *s,int i,int j)
{
    int k = 0;
    strLink *tmp,*p = s->next,*r,*q;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    if(i-1+j > StrLength(s))
        return tmp;
    r = tmp;
    i--;
    while (k < i)
    {
        p = p->next;
        k++;
    }

    while (k < i+j)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p->data;
        r->next = q;
        r = q;
        p = p->next;
        k++;
    }
    r->next = NULL;
    return tmp; 
}

strLink * Concat(strLink *s,strLink *t)
{
    strLink *tmp,*r,*q,*p1 =s->next,*p2=t->next;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    r = tmp;
    while (p1 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }

    while (p2 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p2->data;
        r->next = q;
        r = q;
        p2 = p2->next;
    }
    r->next = NULL;
    return tmp;
}

//   复制串s，返回新串
strLink * StrCopy(strLink *s)
{
    strLink *tmp,*r,*q,*p1=s->next;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;

    r = tmp;
    while (p1 != NULL)
    {
        q = (strLink *)malloc(sizeof(strLink));
        q->data = p1->data;
        r->next = q;
        r = q;
        p1 = p1->next;
    }
    
    return tmp;
}

//  串相等
Bool StrEqual(strLink *s,strLink *t)
{
    strLink *p1=s->next,*p2=t->next;
    if(StrLength(s) != StrLength(t))
        return false;

    while (p1 != NULL)
    {
        if(p1->data != p2->data)
            return false;

        p1=p1->next;
        p2=p2->next;
    }
    return true;
}