数据结构 --- 串

工程目录结构:

common.h:

 1 //#ifndef __common_h__
 2 //#define __common_h__
 3 
 4 #define OK 1
 5 #define ERROR 0
 6 #define TRUE 1
 7 #define FALSE 0 
 8 
 9 #define MAXSIZE 20
10 
11 typedef int Status;        //函数的返回结果，OK、ERREO、TRUE、FALSE
12 typedef int ElemType;   //结点数据域的数据类型
13 
14 //#endif

common.c:

1 #include "common.h"
2 
3 Status visit(ElemType e)
4 {
5     printf("%d , ", e);
6     return OK;
7 }

String.h:

1 typedef char String[MAXSIZE + 1];   // 0 号位存储串的长度

String.c:

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <malloc.h>
  4 #include "common.h"
  5 #include "String.h"
  6 
  7 void InitString(String Str)
  8 {
  9     Str[0] = 0;
 10 }
 11 
 12 //生成一个其值等于chars的串 Str
 13 Status StringAssign(String Str, char *chars)
 14 {
 15     if (strlen(chars) > MAXSIZE)
 16         return ERROR;
 17     Str[0] = strlen(chars);
 18     for (int i = 1; i <= Str[0]; ++i)
 19         Str[i] = *(chars + i - 1);
 20 
 21     return OK;
 22 }
 23 
 24 //由串oldStr复制得串newStr
 25 Status CopyString(String newStr, String oldStr)
 26 {
 27     for (int i = 0; i <= oldStr[0]; ++i)
 28         newStr[i] = oldStr[i];
 29     return OK;
 30 }
 31 
 32 Status EmptyString(String Str)
 33 {
 34     if (Str[0] == 0)
 35         return TRUE;
 36     else
 37         return FALSE;
 38 }
 39 
 40 //前提是: str1 和 str2 均不为空串
 41 // 0: str1 == str2  正数: str1 > str2  负数: str1 < str2   
 42 int CompareString(String str1, String str2)
 43 {
 44     for (int i = 1; i <= str1[0] && i <= str2[0]; ++i)
 45     {
 46         if (str1[i] != str2[i])
 47             return str1[i] - str2[i];
 48     }
 49     return str1[0] - str2[0];
 50 }
 51 
 52 int StringLength(String Str)
 53 {
 54     return Str[0];
 55 }
 56 
 57 Status StringClear(String Str)
 58 {
 59     Str[0] = 0;
 60     return OK;
 61 }
 62 
 63 //用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE
 64 Status StringConcat(String T, String S1, String S2)
 65 {
 66     int i;
 67     if (S1[0] + S2[0] <= MAXSIZE)  //未截断
 68     {
 69         for (i = 1; i <= S1[0]; ++i)
 70             T[i] = S1[i];
 71 
 72         for (i = 1; i <= S2[0]; ++i)
 73             T[S1[0] + i] = S2[i];
 74 
 75         T[0] = S1[0] + S2[0];
 76 
 77         return FALSE;
 78     }
 79     else    //截断,按照这里定义的String，截断也是截断S2
 80     {
 81         for (i = 1; i <= S1[0]; ++i)
 82             T[i] = S1[i];
 83 
 84         for (i = 1; i <= MAXSIZE - S1[0]; ++i)
 85             T[S1[0] + i] = S2[i];
 86 
 87         T[0] = MAXSIZE;
 88 
 89         return TRUE;
 90     }
 91 }
 92 
 93 //用Sub返回串S的第pos个字符起长度为len的子串
 94 Status SubString(String sub, String S, int pos, int len)
 95 {
 96     if (pos < 1 || pos > S[0] || len < 0 || len > S[0] - pos + 1)
 97         return FALSE;
 98 
 99     for (int i = 1; i <= len; ++i)
100         sub[i] = S[pos + i - 1];
101 
102     sub[0] = len;
103 
104     return TRUE;
105 }
106 
107 //返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 
108 //其中,T非空,1≤pos≤StrLength(S)。
109 int Index(String S, String T, int pos)
110 {
111     int i = pos,   //主串开始匹配的位置
112         j = 1;       //子串匹配的索引
113 
114     while (i <= S[0] && j <= T[0])
115     {
116         if (S[i] == T[j])
117         {
118             ++i;
119             ++j;
120         }
121         else
122         {
123             i = i - j + 1 + 1;  //j可以间接用来记录i++的次数，通过简单的计算即可转换为i下一次匹配的位置
124             j = 1;
125         }
126     }
127 
128     if (j > T[0])
129         return i - T[0];
130     else
131         return 0;
132 }
133 
134 /*  T为非空串。若主串S中第pos个字符之后存在与T相等的子串， */
135 /*  则返回第一个这样的子串在S中的位置，否则返回0 */
136 int Index2(String S, String T, int pos)
137 {
138     if (pos > 0)
139     {
140         int lenS = S[0];
141         int lenT = T[0];
142         int i = pos;
143         String sub;
144         while (i <= lenS - lenT + 1)
145         {
146             /* 取主串中第i个位置长度与T相等的子串给sub */
147             SubString(sub, S, i, lenT);
148             if (CompareString(sub, T) != 0)
149                 ++i;
150             else
151                 return i;
152         }
153     }
154     return 0;
155 }
156 
157 //输出串
158 void StringPrint(String Str)
159 {
160     for (int i = 1; i <= Str[0]; ++i)
161         printf("%c", Str[i]);
162     printf("
");
163 }
164 
165 void StringStart()
166 {
167     String Str;
168     InitString(Str);
169     printf("创建字符串  str = ABCDEFG
");
170     char chars[] = "ABCDEFG";
171     if (OK == StringAssign(Str, chars))
172         printf("
字符串创建成功!
");
173     else
174         printf("
字符串创建失败!
");
175 
176     printf("
Str= ");
177     StringPrint(Str);
178 
179     printf("
Str 的长度: %d
", StringLength(Str));
180 
181     String NewStr;
182     InitString(NewStr);
183 
184     if (EmptyString(NewStr) == TRUE)
185         printf("
NewStr 是空串!
");
186     else
187         printf("
NewStr 不是空串!
");
188 
189     CopyString(NewStr, Str);
190 
191     printf("
复制穿 Str -> NewStr, NewStr = ");
192     StringPrint(NewStr);
193 
194     if (EmptyString(NewStr) == TRUE)
195         printf("
NewStr 是空串!
");
196     else
197         printf("
NewStr 不是空串!
");
198 
199     printf("
NewStr 的长度: %d
", StringLength(NewStr));
200 
201     String Str1, Str2, Str3;
202     InitString(Str1);
203     InitString(Str2);
204     char chars1[] = "ABCDEFABCDEGHHIJKLMN";
205     char chars2[] = "1234567891011121314";
206     char chars3[] = "ABCDE";
207     StringAssign(Str1, chars1);
208     StringAssign(Str2, chars2);
209     StringAssign(Str3, chars3);
210 
211     printf("
Str1 = ");
212     StringPrint(Str1);
213     printf("Str2 = ");
214     StringPrint(Str2);
215     printf("Str3 = ");
216     StringPrint(Str3);
217 
218     if (0 == CompareString(Str1, Str))
219         printf("
Str1 == Str");
220     else if (CompareString(Str1, Str) > 0)
221         printf("
Str1 > Str");
222     else
223         printf("
Str1 < Str");
224 
225     if (0 == CompareString(Str2, Str))
226         printf("
Str2 == Str");
227     else if (CompareString(Str2, Str) > 0)
228         printf("
Str2 > Str");
229     else
230         printf("
Str2 < Str");
231 
232     if (0 == CompareString(Str3, Str))
233         printf("
Str3 == Str");
234     else if (CompareString(Str3, Str) > 0)
235         printf("
Str3 > Str");
236     else
237         printf("
Str3 < Str");
238 
239     String T;
240     if (StringConcat(T, Str1, Str2) == TRUE)
241         printf("

Str2 被截断!
");
242     else
243         printf("

Str2 未被截断!
.");
244 
245     printf("
T = ");
246     StringPrint(T);
247 
248     String sub;
249 
250     printf("
从T中第7个位置开始，截取长度为5的 Sub, Sub = ");
251     if (SubString(sub, T, 7, 5) == TRUE)
252         StringPrint(sub);
253 
254     String Str5;
255     char chars5[] = "HIJ";
256     StringAssign(Str5, chars5);
257     int pos = 3;
258 
259     int index = Index(Str1, Str5, pos);
260     printf("

Str5 = ");
261     StringPrint(Str5);
262     printf("
Str5在Str1中的位置是: %d
", index);
263 
264     pos = Index2(Str1, Str3, 2);
265     printf("
Str1中，从第二个位置开始，与Str3相等的子串的 Pos = %d
", pos);
266     printf("
");
267 }

main.c:

int main()
{
    //LinkListStart();
    //StackStart();
    //LinkStackStart();
    //StartQueue();
    //LinkQueueStart();
    StringStart();
    getchar();
    return 0;
}