串的结构类似与线性表，只不过串的数据元素是一个字符，即是由零个或多个字符组成的有限序列。

一、串的顺序存储

　　串的顺序存储结构也就是顺序存储，即串中的字符被依次的存在一组连续的存储单元中，可以类比线性表的顺序存储，可以写出其数据结构如下：

1
2
3
4
5
6
typedef struct st
{
    char *ch;       //串存放的起始地址，串中第i个字符存储在ch[i-1]中
    int length;     //串的长度
    int strsize;    //分配的存储空间的大小，如果不足，在通过realloc()分配增加空间
}string;

　　 假设现在的字符串是“friend”，其结构可以用如图所示：

　　电脑培训,计算机培训,平面设计培训,网页设计培训,美工培训,Web培训,Web前端开发培训

　　现在我们拿到这个数据结构第一步是要初始化一个串，即首先在内存中开辟一段连续的存储空间（大小可以假先预定MAXSIZE个存储空间），初始化其长度length为0，同时制定其串的最大容量是MAXSZIE，如下：

1
2
3
4
5
6
7
8
9
//串的初始化操作
string CreateNullString()
{
    string s;
    s.length=0;
    s.ch=(char*)malloc(MAXSIZE *sizeof(char));
    s.strsize=MAXSIZE;
    return s;
}

　初始化完成之后，我们可以类比顺序表，对串完成一系列操作，如串拷贝、取子串、串赋值等，

　程序示例如下：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
 
typedef struct st
{
    char *ch;       //串存放的起始地址，串中第i个字符存储在ch[i-1]中
    int length;     //串的长度
    int strsize;    //分配的存储空间的大小，如果不足，在通过realloc()分配增加空间
}string;
 
//串的初始化操作
string CreateNullString()
{
    string s;
    s.length=0;
    s.ch=(char*)malloc(MAXSIZE *sizeof(char));
    s.strsize=MAXSIZE;
    return s;
}
 
//判断空串
int isEmpty(string s)
{
    if(s.length==0)
        return 1;
    else
        return 0;
}
 
//赋值操作
void StringAssign(string *s1,char s2[])
{
    int i=0;
    while(s2[i]!='\0')  // '\0' 是字符串的结束符，任何字符串之后都会自动加上'\0'
        i++;            //计算s2的长度
    if(i>s1->strsize)
    {
        //所赋值的字符数组超过字符串的默认容量，则增加存储空间
        s1->ch=(char*)malloc(i*sizeof(char));
        s1->strsize=i;
    }
    s1->length=i;
    for(i=0;i<s1->length;i++)
        s1->ch[i]=s2[i]; //从第一个字符开始逐个字符赋值
}
 
//串拷贝操作
void StringCopy(string *s1,string s2)
{
    if(s1->strsize<s2.length)
    {
        s1->ch=(char*)realloc(s1->ch,s2.length*sizeof(char));
        s1->strsize=s2.length;
    }
    s1->length=s2.length;
    int i;
    for(i=0;i<s1->length;i++)
        s1->ch[i]=s2.ch[i];
}
 
//求串的长度
int StringLength(string s)
{
    return s.length;
}
 
//串的连接操作
void concat(string *s,string s1,string s2)
{
    if(s->strsize<s1.length+s2.length)
    {
        s->ch=(char*)realloc(s->ch,(s1.length+s2.length)*sizeof(char));
        s->strsize=s1.length+s2.length;
    }
    s->length=s1.length+s2.length;       //两串连接
    int i;
    for(i=0;i<s1.length;i++)         //将s1复制到s中
        s->ch[i]=s1.ch[i];
    for(;i<s->length;i++)
        s->ch[i]=s2.ch[i-s1.length]; //将s2复制到s中去
}
 
//取子串操作
int substr(string s,int i,int len,string *t)
{
    /*
        i表示从字符串s的第i个位置开始截取（索引从1开始）
        len表示截取字符串的长度
    */
    if(i<=0 || i>s.length  || len<0 || len>s.length-i+1)    //参数不合法
        return 0;
    if(t->length<len) //存储空间不够，继续分配存储空间
    {
        t->ch=(char*)realloc(t->ch,len*sizeof(char));
        t->strsize=len;
    }
    t->length=len;
    int k;
    for(k=0;k<t->length;k++)
        t->ch[k]=s.ch[i-1+k];
    return 1;
}
 
//插入操作
int insertString(string *s,int i,string t)
{
    //在字符串s的第i个位置插入字符串t
    if(i<=0 || i>s->length+1)
        return 0;
    if(s->strsize<s->length+t.length)  //空间不足
    {
        s->ch=(char*)realloc(s->ch,(s->length+t.length)*sizeof(char));
        s->strsize=s->length+t.length;
    }
    int k;
    for(k=s->length-1;k>=i-1;k--) //将s中的后i个字符后移到后面
        s->ch[k+t.length]=s->ch[k];
    s->length=s->length+t.length;
    for(k=0;k<t.length;k++)              //将t的值赋值给s
        s->ch[k+i-1]=t.ch[k];
    return 1;
}
 
//删除操作
int deleteString(string *s,int i,int len)
{
    //从s的第i个字符开始删除len个字符
    if(i<=0 || i>s->length  || len<0 || len>s->length-i+1)    //参数不合法
        return 0;
    int k;
    for(k=i+len-1;k<s->length;k++)    //从s的i+len-1个位置开始将其后的所有字符前移
        s->ch[k-len]=s->ch[k];
    s->length-=len;
    return 1;
}
 
//输出操作
void print(string s)
{
    int i;
    for(i=0;i<s.length;i++)
        printf("%c",s.ch[i]);
    printf("\n");
}
 
void main()
{
    string s1=CreateNullString();
    string s2=CreateNullString();
    string s3=CreateNullString();
    char ch[MAXSIZE];
    printf("请输入主串：\n");
    gets(ch);
    StringAssign(&s1,ch);
    printf("主串 s1 为：");
    print(s1);
    StringCopy(&s2,s1);
    printf("拷贝串操作结果如下，结果如下 s2 ：");
    print(s2);
    printf("删除操作（1——s1.length-3 全删）：");
    deleteString(&s2,1,s1.length-3);
    print(s2);
    printf("插入操作,插入到s2的第2个位置上，请输入插入的字符串：");
    gets(ch);
    StringAssign(&s3,ch);
    insertString(&s2,2,s3);
    print(s2);
    printf("取子串操作（取s1的子串【2-4】)：");
    substr(s1,2,3,&s3);
    print(s3);
    printf("串连接操作【将s1与s3合并】：");
    concat(&s1,s1,s2);
    print(s1);
}

　　结果如下：
电脑培训,计算机培训,平面设计培训,网页设计培训,美工培训,Web培训,Web前端开发培训

 

 

二、串的链式存储

　　串的链式存储结构称为串的链式存储，即串中的每一个节点包括两个部分：数据域和指针域，其中数据域用来存放字符，指针域用来存放指向下一个节点的指针。

　　由此可得串的链式数据结构如下：

1
2
3
4
5
typedef struct node
{
    char ch;            //字符域
    struct node *next;  //指针域，存放下一个结点的地址
}node,*linkstr;

　如下所示：

　电脑培训,计算机培训,平面设计培训,网页设计培训,美工培训,Web培训,Web前端开发培训

 

 其初始化操作主要是开辟头结点，同时让它的下一个指针指向为NULL：

1
2
3
4
5
6
7
8
9
//初始化操作
linkstr CreateNullString()
{  
    linkstr s;
    s=(linkstr)malloc(sizeof(node));
    if(s!=NULL)
        s->next=NULL;
    return s;
}

http://www.cnblogs.com/helloworldcode/p/6978746.html


延伸阅读

万码学堂学员王*全 [青岛一阁供应链有限公司]-Java培训,做最负责任的教育,学习改变命运,软件学习,再就业,大学生如何就业,帮大学生找到好工作,lphotoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训万码学堂学员王*全 [青岛一阁供应链有限公司]