数据结构串的实现（堆分配存储表⽰法）————————————————————————————————————————————堆分配存储表⽰法————————————————————————————————————————————
存储结构：
构建堆来存储字符串，本质上是顺序表————————————————————————————————————————————
实现代码：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4#define OK 1
5#define ERROR 0
6#define TRUE 1
7#define FALSE 0
8#define OVERFLOW -2
9#define STR_INIT_SIZE 100
10#define STRINCREMENT 10
11 typedef int Status;
12 typedef struct
13 {
14char *ch; //空串时指向NULL,⾮空串时按串长分配存储区
15int length;
16 } HString;
17 Status InitString(HString *T) //初始化字符串
18 {
19//指针指向NULL，长度为0即可
20//p.s.申请内存空间的过程在赋值中完成
21 T->ch = NULL;
22 T->length = 0;
23return OK;
24 }
25 Status StrAssign(HString *T, char *p) //字符串赋值
26 {
27//1.判断T是否已有内容，有则释放
28//2.判断赋值的内容是否为空，为空则不赋值
29//3.根据长度向内存申请空间，遍历赋值给T，长度等于字符串长度
30//p.s.在这⾥赋值不赋\0，在打印时通过长度来判断字符串结尾
31int i, len = strlen(p);
32if (T->ch)
33free(T->ch);
34if (!len)
35 {
36 T->ch = NULL;
37 T->length = 0;
38return ERROR;
sql 字符串转数组39 }
40else
41 {
42 T->ch = (char *)malloc(len * sizeof(char));
43if(!T->ch)
44 exit(OVERFLOW);
45for (i = 0; i < len; ++i)
46 T->ch[i] = p[i];
47 T->length = len;
48return OK;
49 }
50 }
51 Status StrPrint(HString T) //打印字符串
52 {
53//通过长度判断打印的字符数
54int i;
55for (i = 0; i < T.length; ++i)
56 printf("%c", T.ch[i]);
57 printf("\n");
58 }
59 Status StrLength(HString T) //字符串长度
60 {
61return T.length;
62 }
63 Status StrEmpty(HString T) //字符串判空
64 {
65if (T.length == 0)
66return TRUE;
67else
68return FALSE;
69 }
70 Status Concat(HString *T, HString S1, HString S2) //字符串联接
71 {
72//1.申请长度为S1和S2之和的字符串空间
73//2.先将S1的元素逐个赋值到T中
74//3.再将S2的元素逐个赋值到T中
75int i;
76if (T->ch)
77free(T->ch);
78 T->ch = (char *)malloc((S1.length + S2.length) * sizeof(char));
79if (!T->ch)
80 exit(OVERFLOW);
81for (i = 0; i < S1.length; ++i)
82 T->ch[i] = S1.ch[i];
83for (i = 0; i < S2.length; ++i)
84 T->ch[i + S1.length] = S2.ch[i];
85 T->length = S1.length + S2.length;
86return OK;
87 }
88 Status StrDelete(HString *T, int pos, int len) //删除字符串中某个位置固定长度的⼦串
89 {
90//pos是字符串中的位置，删除包括pos的len长度
91int i;
92if (pos >= T->length)
93return ERROR;
94else if(pos + len > T->length)
95 len = T->length - pos + 1;
96for (i = pos - 1; i < T->length - len; ++i)
97 T->ch[i] = T->ch[i + len];
98 T->length -= len;
99 T->ch = (char *)realloc(T->ch, T->length * sizeof(char));
100if (!T->ch)
101 exit(OVERFLOW);
102return OK;
103 }
104 Status StrInsert(HString *S, int pos, HString T)
105 {
106//pos是字符串中的位置，插⼊时原来的元素(包括pos位)后移
107int i, len;
108 --pos;
109 len = StrLength(T);
110 S->ch = (char *)realloc(S->ch, (S->length + len) * sizeof(char));
111if (pos > S->length)
112 pos = S->length;
113for (i = S->length - 1; i > pos - 1; --i)
114 S->ch[i + len] = S->ch[i];
115for (i = 0; i < len; ++i)
116 S->ch[i + pos] = T.ch[i];
117 S->length += len;
118if (!S->ch)
119 exit(OVERFLOW);
120return OK;
121 }
122 Status Index(HString S, HString T, int pos) //在字符串S中索引位置pos之后的⼦串t
123 {
124//同定长顺序存储表⽰法
125//p.s.传⼊的pos是字符串的位置，从1开始
126//p.s.初始状态下T为⾮空串
127if (StrEmpty(T))
128return ERROR;
129int i = pos - 1, j = 0;
130while(i < S.length && j < T.length)
131 {
132if (S.ch[i] == T.ch[j])
133 {
134 ++i;
135 ++j;
136 }
137else
138 {
139 i = i - j + 1;
140 j = 0;
141 }
142 }
143if (j >= T.length)
144return i - j + 1;
145else
146return0;
147 }
148 Status Replace(HString *T, HString S1, HString S2) //将字符串T中等于S1的⼦串替换成为S2
149 {
150//循环索引⼦串S1在字符串T中的位置(每次的位置从上⼀次位置后开始查) 151//从查到的位置-1开始替换
152//p.s.初始状态下S1为⾮空串
153int pos = 0;
154if (StrEmpty(S1))
155return ERROR;
156//当pos存在时循环，当全部索引完毕后pos为0
157//将索引到的该位置对应的⼦串删除后再插⼊新的⼦串
158do
159 {
160 pos = Index(*T, S1, pos);
161if (pos)
162 {
163 StrDelete(T, pos, StrLength(S1));
164 StrInsert(T, pos, S2);
165 }
166 }
167while(pos);
168return OK;
169 }
170 Status SubString(HString *Sub, HString S, int pos, int len)
171 {
172int i;
173if (pos < 1 || len > S.length || len < 0 || len > S.length - pos + 1)
174 exit(OVERFLOW);
175if (Sub->ch)
176free(Sub->ch);
177//如果查询的长度为0，则⼦串置空
178if (len == 0)
179 {
180 Sub->ch = NULL;
181 Sub->length = 0;
182 }
183else
184 {
185 Sub->ch = (char *)malloc(len * sizeof(char));
186for (i = 0; i < len; ++i)
187 Sub->ch[i] = S.ch[pos + i - 1];
188 Sub->length = len;
189 }
190return OK;
191 }
192int main()
193 {
194int pos;
195 HString t, s, r;
196char *p = "Hello,String!", *q = "Bye,Bye!";
197 printf("String *p: %s\n", p);
198 InitString(&t);
199 StrAssign(&t, p);
200 printf(" OK.\nString t : ");
201 StrPrint(t);
202 printf("------------------------------\n");
203 printf(" OK.\nString Length : %d\n", StrLength(t));
204 printf(" OK.\n");
205if (StrEmpty(t))
206 printf("String is Empty.\n");
207else
208 printf("String is not Empty.\n");
209 printf("------------------------------\n");
210 InitString(&s);
211 StrAssign(&s, q);
212 printf("String s : ");
213 StrPrint(s);
214 printf("------------------------------\n");
215 InitString(&r);
216 Concat(&r, t, s);
217 printf(" OK.\n");
218 printf("String r : ");
219 StrPrint(r);
220 printf("------------------------------\n");
221 printf(" OK.\n");
222 StrDelete(&r, 14, 4);
223 printf("String r : ");
224 StrPrint(r);
225 printf("------------------------------\n");
226 printf(" OK.\n");
227 StrAssign(&t, "Bye,Bye,Bye!");
228 StrInsert(&r, 14, t);
229 printf("String r : ");
230 StrPrint(r);
231 printf("------------------------------\n");
232 StrAssign(&t, "ye");
233 printf(" ");
234 StrPrint(t);
235 pos = 1;
236while(pos)
237 {
238 pos = Index(r, t, pos + 1);
239if (!pos)
240break;
241 printf("Position : %d\n", pos); 242 }
243 printf("------------------------------\n"); 244 StrAssign(&t, "ye");
245 StrAssign(&s, "oo");
246 Replace(&r, t, s);
247 printf("Replace ye -> ooo ... OK.\n"); 248 printf("String r : ");
249 StrPrint(r);
250 printf("------------------------------\n"); 251 SubString(&t, r, 7, 4);
252 printf(" OK.\n");
253 printf("String SubString : ");
254 StrPrint(t);
255 printf("------------------------------\n"); 256return OK;
257 }
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论