字符串

发表于 | 分类于
字数统计: 1.3k

字符串

字符串，简称串，一种特殊的线性表，表中的每个元素都是一个字符。一个串可以记为$S=”s_{0},s_{1},\dots,s_{n-1}”(n\geqslant 0)$,$S$是串的名字；字符序列$s_{0},s_{1},\dots,s_{n-1}$是串的值；字符个数称为串的长度。长度为0的串称为空串，写成s=””,与空白字符构成的串s=” “不同。

子串，字符串$s1$中任意个连续的字符组成的子序列$s2$被称为是$s1$的字串，而称$s1$是$s2$的主串。空串是任意串的子串，除s外，s的其他子串称为s的真子串。子串在主串中的位置指：该子串的第一个字符在主串中的位置。

两个字符串相等：两个字符串长度相等，且各个对应位置上的字符都相同。

如果整个字符集上有全（线）序关系，则两个字符串之间有如下字典序关系：设$A=a_{0}a_{2}\dots a{n-1},B=b_{0}b_{2}\dots b_{m-1}$,则$A\lt B$: 若存在$k$使$a_{i}=b_{i}(i=0,1,\dots,k-1)$,但是$a_{k}\lt b_{k}$；或者$n<m$,且$a_{i}=b_{i}(i=0,1,\dots,n-1)$。

抽象数据类型

1
2
3
4
5
6
7
8
9
ADT String is 
operations
	String createNullStr(void)/*创建一个空串*/
	int IsNullStr(String s)/*判断串s是否为空串，若为空串，则返回1，否则返回0*/
    int length(String s)/*返回串s的长度*/
    String concat(String s1,String s2)/*返回将串s1和s2拼接在一起构成的一个新串*/
    String subStr(String s,int i,int j)/*在串s中，求从串的第i个字符开始连续j个字符所构成的子串*/
    int index(String s1,String s2)/*如果串s2是s1的子串，则可求串s2在串s1中第一次出现的位置*/
end ADT String

字符串顺序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct SeqString {/*顺序串的类型*/
    int MAXNUM; /*串允许的最大字符个数*/
    int n; /*串的长度， n<=MAXNUM*/
    char *c; 
};
typedef struct SeqString * PSeqString;

//创建空顺序串
PSeqString createNullStr_seq(int m){
    PSeqString pstr = (PSeqString)malloc(sizeof(struct SeqString));
    if(pstr!=NULL){
        pstr->c = (char*)malloc(sizeof(char)*m);
        if(pstr->c){
            pstr->n=0;
            pstr->MAXNUM=m;
            return pstr;
        }
        else
            free(pstr);
    }
    printf("Out of space!!\n");
    return NULL;
}


//求顺序表示的串的子串
PSeqString subStr_seq(PSeqString s,int i,int j)
{
    PSeqString s1;
    int k;
    s1 = createNullStr_seq(j);/*创建一个空串*/
    if(s1==NULL)
        return NULL;
    if(i>0 && i<=s->n && j>0)
    {
        if(s->n<i+j-1)
            j=s->n-i+1;/*若从i开始取不了j个字符，则能取几个取几个*/
        for(k=0;k<j;k++)
            s1->c[k] = s->c[i+k-1];
        s1->n = j;
    }
    return s1;
}

字符串链接表示

在串的链接表示中，每个节点包含两个字段：字符和指针，分别用于存放字符和指向下一个节点的指针。这样一个串就可以用一个单链表来表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
struct StrNode; /*链串的节点*/
typedef struct StrNode * PStrNode;/*节点指针类型*/
struct StrNode{/*链串的节点结构*/
    char c;
    PStrNode link;
};
typedef struct StrNode * LinkString;/*链串的类型*/

//创建带头结点的空链表
LinkString createNullStr_link(void)
{
    LinkString pst;
    pst = (LinkString)malloc(sizeof(struct StrNode));
    if(pst!=NULL)
        pst->link = NULL;
    else
        printf("Out of space!\n");/*创建失败*/
    return pst;
}

//求单链表表示的串的子串
LinkString subStr_link(LinkString s,int i,int j)
    /*求从s所指的带头结点的链串中第i(i>0)个字符开始连续取j个字符所构成的子串。*/
{
 	LinkString s1;
    PStrNode p,q,t;
    int k;
    s1 = createNullStr_link();
    if(s1==NULL)
    {
        printf("Out of space!\n");
        return NULL;
    }
    if(i<1 || j<1)
        return s1;/*i,j值不合适，返回空串*/
    p = s;/*p为主串*/
    for (k=1;k<=i;k++)/*找到第i个节点*/
        if(p!=NULL)
            p=p->link;
    	else
            return s1;
    if(p==NULL)
        return s1;
    t=s1;/*t为子串尾*/
    for(k=1;k<=i;k++)/*连续取j个字符*/
        if(p!=NULL)
        {
            q=(PStrNode)malloc(sizeof(struct StrNode));
            if(q==NULL)
            {
                printf("Out of space!\n");
                return s1;
			}
            q->c = p->c;
            q->link = NULL;
            t->link=q;/*将节点放入子链串中*/
            t = q;
            p=p->link;
        }
    return s1;
}

//朴素的模式匹配
/*求串p在串t中第一次出现的位置，即p的第一个元素在串t中的序号（下表+1）*/
int index(PSeqString t,PSeqString p)
{
    int i=0,j=0;/*初始化*/
    while(i < p->n && j < t->n)/*反复比较*/
        if (p->c[i] == t->c[j])
        {
            ++i;++j;
        }
    else
    {
        j = j-i+1;
        i=0;
        /*i,j值回溯，再开始下一位置的匹配*/
	}
    if(i>=p->n)
        return (j-p->n+1);/*匹配成功*/
    else
        return 0;/*匹配失败*/
}

//无回溯的模式匹配算法
int pMatch(PSeqString t,PSeqString p,int * next)
{
    int i=0,j=0;/*初始化*/
    while(i<p->n && j<t->n)
    {
  		/*反复比较*/
        if(i==-1 || p->c[i]==t->c[j])
        {
            i++;j++;
		}
        else
            i = next[i];
    }
    if(i >= p->n)
        return (j-p->n+1);/*匹配成功，返回p中第一个字符在t中的序号*/
    return 0;/*匹配失败*/
}

//计算next数组
/*next是指向next数组的指针参数*/
makeNext(PSeqString p,int * next)
{
    int i=0,k=-1;
    next[0] = -1;
    while(i < p->n -1)
    {
        /*计算next[i+1]*/
        while(k>=0 && p->c[i]!=p->c[k])
            k = next[k];
        i++;k++;
        if(p->c[i]==p->c[k])
            next[i] = next[k];
        else
            next[i]=k;
	}
}