数据结构Part3 串

数据结构（完结）
数据结构Part1 绪论与线性表
数据结构Part2 栈和队列
数据结构Part3 串
数据结构Part4 树与二叉树
数据结构Part5 图
数据结构Part6 查找
数据Part7 排序

串：即字符串(String)，是由零个或多个字符组成的有限序列、一般记为S = “a₁a₂a₃······a_n”，n>=0。是一种特殊的线性表（串的数据类型只能属于字符集），数据元素之间呈现线性关系。

注意：字符串用双引号括起来：java，c，c++，python；字符串用单引号括起来：python。

空串：串长度为零的串叫做空串

子串：串中任意个连续的字符组成的子序列，空串是任意串的子串。

串的基本操作是对”字串“为对象进行操作的。

假设有串T=""，S=" iPhone 11 Pro Max?"，W="Pro"
StrAssign(&T,chars)			//赋值操作。把串T赋值为chars;
StrCopy(&T,S)				//复制操作。由串S复制得到串T;
StrEmpty(S)					//判空操作。若s为空串，则返回TRUE，否则返回FALSE;
StrLength(S)				//求串长。返回串s的元素个数;
ClearString(&S)				//清空操作。将s清为空串,不释放空间;
DestroyString(&S)			//销毁串。将串s销毁(回收存储空间);
Concat(&T,S1,S2)			//串联接。用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len)	//求子串。用sub返回串s的第pos个字符起长度为len的子串。
Index(S,T)					//定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现位置;否则函数值为0。
StrCompare(S,T)				//比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S 
不同编码规则下每个字符所占的空间不同，考试默认为1B。
 
附录：ASCII码表：
 
dec
oct
hex
ch
dec
oct
hex
ch
dec
oct
hex
ch
dec
oct
hex
ch
0
0
00
NULL (空)
32
40
20
(空格)
64
100
40
@
96
140
60
` (锐音符)
1
1
01
SOH (标题开始)
33
41
21
!
65
101
41
A
97
141
61
a
2
2
02
STX (正文开始)
34
42
22
"
66
102
42
B
98
142
62
b
3
3
03
ETX (正文结束)
35
43
23
#
67
103
43
C
99
143
63
c
4
4
04
EOT (传送结束)
36
44
24
$
68
104
44
D
100
144
64
d
5
5
05
ENQ (询问)
37
45
25
%
69
105
45
E
101
145
65
e
6
6
06
ACK (确认)
38
46
26
&
70
106
46
F
102
146
66
f
7
7
07
BEL (响铃)
39
47
27
'
71
107
47
G
103
147
67
g
8
10
08
BS (退格)
40
50
28
(
72
110
48
H
104
150
68
h
9
11
09
HT (横向制表)
41
51
29
)
73
111
49
I
105
151
69
i
10
12
0a
LF (换行)
42
52
2a
*
74
112
4a
J
106
152
6a
j
11
13
0b
VT (纵向制表)
43
53
2b
+
75
113
4b
K
107
153
6b
k
12
14
0c
FF (换页)
44
54
2c
,
76
114
4c
L
108
154
6c
l
13
15
0d
CR (回车)
45
55
2d
-
77
115
4d
M
109
155
6d
m
14
16
0e
SO (移出)
46
56
2e
.
78
116
4e
N
110
156
6e
n
15
17
0f
SI (移入)
47
57
2f
/
79
117
4f
O
111
157
6f
o
16
20
10
DLE (退出数据链)
48
60
30
0
80
120
50
P
112
160
70
p
17
21
11
DC1 (设备控制1)
49
61
31
1
81
121
51
Q
113
161
71
q
18
22
12
DC2 (设备控制2)
50
62
32
2
82
122
52
R
114
162
72
r
19
23
13
DC3 (设备控制3)
51
63
33
3
83
123
53
S
115
163
73
s
20
24
14
DC4 (设备控制4)
52
64
34
4
84
124
54
T
116
164
74
t
21
25
15
NAK (反确认)
53
65
35
5
85
125
55
U
117
165
75
u
22
26
16
SYN (同步空闲)
54
66
36
6
86
126
56
V
118
166
76
v
23
27
17
ETB (传输块结束)
55
67
37
7
87
127
57
W
119
167
77
w
24
30
18
CAN (取消)
56
70
38
8
88
130
58
X
120
170
78
x
25
31
19
EM (媒介结束)
57
71
39
9
89
131
59
Y
121
171
79
y
26
32
1a
SUB (替换)
58
72
3a
:
90
132
5a
Z
122
172
7a
z
27
33
1b
ESC (退出)
59
73
3b
;
91
133
5b
[
123
173
7b
{
28
34
1c
FS (文件分隔符)
60
74
3c
<
92
134
5c
124
174
7c
|
29
35
1d
GS (组分隔符)
61
75
3d
=
93
135
5d
]
125
175
7d
}
30
36
1e
RS (记录分隔符)
62
76
3e
>
94
136
5e
^
126
176
7e
~
31
37
1f
US (单元分隔符)
63
77
3f
?
95
137
5f
_
127
177
7f
DEL (删除)
2. 串的存储结构 
2.1 顺序存储 
定长字符串：定义一个静态数组来存储定长的串，与线性表相同，只不过数据类型为字符类型（char）。
 
可变长字符串：定义一个基地址指针，使用动态数组的方式实现（堆分配存储）。
 
插入和删除不方便，字符串末尾有一个’’(对应的ASCII码为0)，没有length变量，所占空间为字符串长度加一。
 
define MAXLEN 255
typedef struct{
	char ch[MAXLEN];		//创建一个定长的字符串数组
	int length;				//串的长度
}SString;
typedef struct{
	char *ch;				//按串长分配存储区，ch指向串的基地址
	int length;				//串的长度
}HString;

//使用完毕后需要手动free
HString S;
S.ch = (char *) malloc(MAXLEN * sizeof(char));		
S.length = 0;
 
2.2 链式存储 
不具备随机存储的特性。
 
typedef struct StringNode{
	char ch[4];		//每个节点一般存多个字符，提高存储密度，结尾可以特殊字符填充，如''。
	struct StringNode *next;	
}StringNode， *String;
 
所以说为什么想不开要用链表存字符串呢，搞不懂哦。
 
2.3 基于顺序存储实现基本操作(模式匹配) 
define MAXLEN 255
typedef struct{
	char ch[MAXLEN];		//创建一个定长的字符串数组
	int length;				//串的长度
}SString;
SubString(&Sub,S,pos,len)	//求子串。用sub返回串s的第pos个字符起长度为len的子串。
bool SubString(SString &sub, SString S, int pos, int len){
	//子串范围越界
	if (pos+len-1 > S.length)
		return false;
	for (int i=pos; iT，则返回值>0;若S=T，则返回值=0;若S 
串的模式匹配算法：在主串中找到与模式串相同的子串，并返回其所在位置（Index(S, T)）。
 
朴素模式匹配：依次检查子串，时间复杂度为O(nm)。
 
int Index(SString s, sstring T){
	int k = 0;
	int i=k, j=0;
	while(i < s.length && j < T.length){
		if(S.ch[i]==T.ch[j]){
			++i;
			++j;		//继续比较后继字符
		} eise {
			k++;		//检查下一个子串
			i=k;
            j=1;
		}
	}
	if(j>T.length)	return k;
    else			return 0;
}
 
模式串长度为m，主串长度为n，(n>>m)
 
时间复杂度
匹配成功
匹配失败
最好
O(m)
O(n-m+1)=O(n-m)≈O(n)
最坏
O((n-m+1)*m)≈O(nm)
O((n-m+1)*m)≈O(nm)
*KMP算法(重点) 
主串指针不回溯，只有字串指针回溯，不用一位一位得比较，而是记下回退几个能对上，关键在于求字串数组回溯得个数next[i]；
 
 
int IndexKMP(SString S, SString T, int next[]){
	int i = 0，j = 0;
	while( i < s.length && j < T.length){
		if(j==-1 || s.ch[i]==T.ch[j] ){
			++i;
            ++j; 		//继续比较后继字符
        } else j=next[j]; 	//模式串向右移动
	}
    if(j > T.length)
        return i-T.length;	//匹配成功
    else return -1;
}
 
求模式串的next数组
 
void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j < t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         next[j] = k;
      }
      else k = next[k];		//核心代码
   }
}
 
重点来看看 k = next[k] 这句，首先要明确得是，k表示的是一个用来生成next数组得游标，是可以向左移动来取数的，而j才是用来标记next数组最新下标的，是只能向右移动的，其次是next数组的值的含义，next[i]表示当模式串扫描到第i个位置与主串不同时，模式串游标移动到的位置。因此这句话相当于是创建了一个新串ss来做模式串，之前的模式串做主串。这里的ss是在动态变动的，而这句话表示得是表示的是字符串t的0到k-1子串(构建的新字串ss)与j-k到j-1子串(长度均为k)是相同的。
 
 
改进的kmp算法，改进点依然在next数组上。按照原方案，当主串i位置与模式串j位置不同时，应该进行移动，使得主串的i位置与模式串的**next[j]**位置对应，然而若这两个位置无法对应，那么这次移动就是无意义的，因此需要在构建next数组时添加一个判断。
 
 
void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j < t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         if(t[j]==t[k])				//当两个字符相同时，就跳过
            next[j] = next[k];
         else
            next[j] = k;
      }
      else k = next[k];
   }
}