《详解循环队栈》
目录：
顺序串的定义及其特点
顺序串的存储结构的和线性表一样，也是主要分为顺序存储结构和链式存储结构两类，前者简称顺序串，顺序串和顺序表一样，只不过它的每个元素仅由一个字符组成，在串的这一节中重点是串的处理，即串的相关算法。
顺序串的实现
结构体定义
除了构成串的基本元素都为字符外，顺序串的存储结构与顺序表基本一致。本次结构体定义中除了data（元素指针）与length（当前长度）外，还添加了maxSize（最大长度）。
1 /* 2 sequenceString（顺序串） 3 */ 4 5 typedef struct { 6 7 char* data;//数据存储指针 8 int maxSize;//串最大长度 9 int length;//当前长度 10 11 } SequenceString;
初始化
申请内存时多申请了一个字符长度，用于存储字符串结束标记 '\0'。
1 /** 2 * @brief 初始化字符串 3 * 4 * @param S 字符串指针 5 * @param MaxSize 字符串最大容量 6 * 7 * @return 状态码，0为成功 8 **/ 9 int initSequenceString(SequenceString* S, int MaxSize) { 10 11 S->data = (char*)malloc(sizeof(char) * (MaxSize + 1));//多申请一位用于存放字符串结束标记'\0' 12 if (!S->data) { 13 printf("%s", errorHint[0]); 14 15 return errorCode[0]; 16 } else { 17 18 S->maxSize = MaxSize; 19 S->length = 0; 20 21 return 0; 22 } 23 24 return 0; 25 }
复制字符串
复制字符串前先判断是否超出主串长度，超出则输出错误信息并返回错误码。反之则遍历字符指针，逐个将其中字符赋值给主串。
1 /** 2 * @brief 字符串赋值 3 * 4 * @param S 字符串指针 5 * @param str 字符指针 6 * 7 * @return 状态码，0为成功 8 **/ 9 int copySequenceString(SequenceString* S, char* str) { 10 11 int length = strlen(str); 12 13 if (length > S->maxSize) { 14 printf("%s", errorHint[1]); 15 16 return errorCode[1]; 17 } else { 18 19 for (int i = 0; i < length; i++) { 20 S->data[i] = str[i]; 21 } 22 23 S->data[length] = '\0'; 24 S->length = length; 25 // printf("%d", S->length); 26 } 27 28 return 0; 29 }
连接字符串
先对主串和连接子串的长度和进行判断，超过主串的maxSiz（最大容量），即打印错误信息，返回错误码。反之则遍历子串，将子串字符逐个放入主串尾部。
1 /** 2 * @brief 连接两个字符串 3 * 4 * @param S 字符串指针 5 * @param transcript 连接字符子串指针 6 * 7 * @return 状态码，0为成功 8 **/ 9 int linkSequenceString(SequenceString* S, SequenceString* transcript) { 10 11 int ultimatelyLength = (S->length + transcript->length); 12 13 if (ultimatelyLength > S->maxSize) { 14 printf("%s", errorHint[1]); 15 16 return errorCode[1]; 17 } else { 18 for (int i = S->length, j = 0; i <= ultimatelyLength; i++, j++) { 19 S->data[i] = transcript->data[j]; 20 } 21 S->data[ultimatelyLength] = '\0'; 22 S->length = ultimatelyLength; 23 24 printf("连接成功 ！\n当前主串为：%s\n", S->data); 25 } 26 27 return 0; 28 }
匹配字符串
先判断匹配子串长度是否超出主串，超出则打印错误信息，返回错误码。反之则用双循环对比主串与子串进行比较，直至主串剩余长度不足以容纳子串。字符匹配时 flag+1，不相匹时退出内循环，flag清零。当flag等于子串长度即为匹配成功，返回子串起始位置。
1 /** 2 * @brief 在主串中匹配子串 3 * 4 * @param S 字符串指针 5 * @param substring 匹配字符子串指针 6 * 7 * @return 状态码，0为成功 8 **/ 9 int matchingSequenceString(SequenceString* S, SequenceString* substring) { 10 11 int difference = S->length - substring->length; 12 13 if (difference < 0) { 14 printf("%s", errorHint[2]); 15 16 return errorCode[2]; 17 } else { 18 for (int i = 0; i <= difference; i++) { 19 int flag = 0; 20 int temp = i; 21 for (int j = 0; j < substring->length; j++) { 22 if (S->data[temp] == substring->data[j]) { 23 temp++; 24 flag++; 25 } else { 26 break; 27 } 28 } 29 if (flag == substring->length) { 30 printf("子串位置为%d~%d ！\n", (i + 1), ((i + substring->length))); 31 return i; 32 } 33 } 34 } 35 36 return 0; 37 }
比较字符串
将两个数据指针不断比较其当前位置字符的ASCLL码，当直至ASCLL出现差异或一方字符串完结，如双方ASCLL码一致且同时完结，则为相等。
1 /** 2 * @brief 3 * 4 * @param S 5 * @param s 6 * 7 * @return 8 **/ 9 int compareSequenceString(SequenceString* S, SequenceString* s) { 10 11 char* first = S->data; 12 char* second = s->data; 13 14 while (*first != '\0' && *second != '\0') { 15 16 if (*first < *second) { 17 printf("比较子串大于主串 ！\n\n"); 18 return -1; 19 20 } else if (*first > *second) { 21 printf("主串大于比较子串 ！\n\n"); 22 23 return 1; 24 25 } else { 26 first++; 27 second++; 28 } 29 30 } 31 32 if (*first == '\0' && *second == '\0') { 33 printf("字符串相等 ！\n\n"); 34 return 0; 35 36 } else if (*first == '\0') { 37 printf("比较子串大于主串 ！\n\n"); 38 return -1; 39 40 } else { 41 printf("主串大于比较子串 ！\n\n"); 42 return 1; 43 44 } 45 46 }
获取字符串长度
返回结构体中的length即可。
1 /** 2 * @brief 获取字符串当前长度 3 * 4 * @param S 字符串指针 5 * 6 * @return 字符串长度 7 **/ 8 int getSequenceStringLength(SequenceString* S) { 9 10 return S->length; 11 }
完整Demo
welcome.h（欢迎字符图案）：
1 char *welcome[] = { 2 " \n", 3 " 4&(\n", 4 " ` ~&&\\yM#1\n", 5 " ,_'Q!!NMW&\n", 6 " WCb 7N@4D Q%,,\n", 7 " PM'*MDk#M0p,\n", 8 " ]@J0&e~~4r' ,+bQEQ\n", 9 " F8I&#' _&B$$bW#&$\n", 10 " &0A1 L#DE&E~!Q&Q,\n", 11 " _=, ,#0RN1 _T@0$' ZN$Q. grNq5\n", 12 " ^ 'd ,0K0pK^ g*Q0g' #Q4p&,/g9X*&#,_/ (q\n", 13 " TA1 ,sDQWh4^ x&NM0` _ #FQ#K#fA# `*K#XWP~-\n", 14 " ^&p,wNMM0qD: /HE#EN' ..#g)~ '@NG0Qx, `=X*\n", 15 " ' '43$'hEk##m0D04f_g ~^ ~ `-00**0\n", 16 " =0#ONq2W0BF^#, _ p,,\n", 17 " ` ^''~ ~b'' **R3`\n", 18 " ow,F +#F~'\n", 19 " /-9! `\\ \n", 20 " R\n" 21 };
sequenceString.h（结构体与函数声明）：
1 /* 2 sequenceString（顺序串） 3 */ 4 5 typedef struct { 6 7 char* data;//数据存储指针 8 int maxSize;//串最大长度 9 int length;//当前长度 10 11 } SequenceString; 12 13 int initSequenceString(SequenceString* S, int MaxSize);//初始化字符串 14 15 int getSequenceStringLength(SequenceString* S);//字符串长度获取 16 17 int copySequenceString(SequenceString* S, char* str);//复制字符串 18 19 int linkSequenceString(SequenceString* S, SequenceString* transcript);//链接字符串 20 21 int matchingSequenceString(SequenceString* S, SequenceString* substring);//匹配字符串 22 23 int compareSequenceString(SequenceString* S, SequenceString* s);//比较字符串
sequenceString.c（函数实现）：
1 #include <stdio.h> 2 #include <malloc.h> 3 #include <string.h> 4 #include "sequenceString.h" 5 #include "error.h" 6 7 /** 8 * @brief 初始化字符串 9 * 10 * @param S 字符串指针 11 * @param MaxSize 字符串最大容量 12 * 13 * @return 状态码，0为成功 14 **/ 15 int initSequenceString(SequenceString* S, int MaxSize) { 16 17 S->data = (char*)malloc(sizeof(char) * (MaxSize + 1));//多申请一位用于存放字符串结束标记'\0' 18 if (!S->data) { 19 printf("%s", errorHint[0]); 20 21 return errorCode[0]; 22 } else { 23 24 S->maxSize = MaxSize; 25 S->length = 0; 26 27 return 0; 28 } 29 30 return 0; 31 } 32 33 /** 34 * @brief 获取字符串当前长度 35 * 36 * @param S 字符串指针 37 * 38 * @return 字符串长度 39 **/ 40 int getSequenceStringLength(SequenceString* S) { 41 42 return S->length; 43 } 44 45 /** 46 * @brief 字符串赋值 47 * 48 * @param S 字符串指针 49 * @param str 字符指针 50 * 51 * @return 状态码，0为成功 52 **/ 53 int copySequenceString(SequenceString* S, char* str) { 54 55 int length = strlen(str); 56 57 if (length > S->maxSize) { 58 printf("%s", errorHint[1]); 59 60 return errorCode[1]; 61 } else { 62 63 for (int i = 0; i < length; i++) { 64 S->data[i] = str[i]; 65 } 66 67 S->data[length] = '\0'; 68 S->length = length; 69 // printf("%d", S->length); 70 } 71 72 return 0; 73 } 74 75 /** 76 * @brief 连接两个字符串 77 * 78 * @param S 字符串指针 79 * @param transcript 字符串指针 80 * 81 * @return 状态码，0为成功 82 **/ 83 int linkSequenceString(SequenceString* S, SequenceString* transcript) { 84 85 int ultimatelyLength = (S->length + transcript->length); 86 87 if (ultimatelyLength > S->maxSize) { 88 printf("%s", errorHint[1]); 89 90 return errorCode[1]; 91 } else { 92 for (int i = S->length, j = 0; i <= ultimatelyLength; i++, j++) { 93 S->data[i] = transcript->data[j]; 94 } 95 S->data[ultimatelyLength] = '\0'; 96 S->length = ultimatelyLength; 97 98 printf("连接成功 ！\n当前主串为：%s\n", S->data); 99 } 100 101 return 0; 102 } 103 /** 104 * @brief 105 * 106 * @param S 107 * @param substring 108 * 109 * @return 110 **/ 111 int matchingSequenceString(SequenceString* S, SequenceString* substring) { 112 113 int difference = S->length - substring->length; 114 115 if (difference < 0) { 116 printf("%s", errorHint[2]); 117 118 return errorCode[2]; 119 } else { 120 for (int i = 0; i <= difference; i++) { 121 int flag = 0; 122 int temp = i; 123 for (int j = 0; j < substring->length; j++) { 124 if (S->data[temp] == substring->data[j]) { 125 temp++; 126 flag++; 127 } else { 128 break; 129 } 130 // printf("%d", flag); 131 } 132 if (flag == substring->length) { 133 printf("子串位置为%d~%d ！\n", (i + 1), ((i + substring->length))); 134 return i; 135 } 136 } 137 } 138 139 return 0; 140 } 141 142 /** 143 * @brief 144 * 145 * @param S 146 * @param s 147 * 148 * @return 149 **/ 150 int compareSequenceString(SequenceString* S, SequenceString* s) { 151 152 char* first = S->data; 153 char* second = s->data; 154 155 while (*first != '\0' && *second != '\0') { 156 157 if (*first < *second) { 158 printf("比较子串大于主串 ！\n\n"); 159 return -1; 160 161 } else if (*first > *second) { 162 printf("主串大于比较子串 ！\n\n"); 163 164 return 1; 165 166 } else { 167 first++; 168 second++; 169 } 170 171 } 172 173 if (*first == '\0' && *second == '\0') { 174 printf("字符串相等 ！\n\n"); 175 return 0; 176 177 } else if (*first == '\0') { 178 printf("主串大于比较子串 ！\n\n"); 179 return -1; 180 181 } else { 182 printf("比较子串大于主串 ！\n\n"); 183 return 1; 184 185 } 186 187 }
main.c（主函数）：
1 #include <stdio.h> 2 #include <stdint.h> 3 #include <string.h> 4 #include "welcome.h" 5 #include "sequenceString.h" 6 7 int main(int argc, char** argv) { 8 9 for (int i = 0; i < 19; i++) { 10 printf("%s", welcome[i]); 11 for (int j = 0; j <= 100000000; j++) { 12 for (int m; m <= 100000000; m++) { 13 ; 14 } 15 } 16 } 17 18 int operate; 19 int maxSize; 20 SequenceString S; 21 SequenceString s; 22 char str[10]; 23 24 printf("\n\n本应用程序为数据结构-字符串演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n"); 25 do { 26 printf("<---------------------------------------------------字符串演示程序-------------------------------------------------->\n"); 27 printf("0. 退出程序\n"); 28 printf("1. 初始化字符串\n"); 29 printf("2. 打印字符串\n"); 30 printf("3. 复制字符串\n"); 31 printf("4. 连接字符串\n"); 32 printf("5. 匹配字符串\n"); 33 printf("6. 比较字符串\n"); 34 printf("7. 获取字符串长度\n"); 35 printf("8. 帮助\n"); 36 printf("请输入操作选项(0~5,0为退出)："); 37 scanf("%d", &operate); 38 // getchar(); 39 switch (operate) { 40 case 1: 41 printf("请输入字符串最大容量："); 42 scanf("%d", &maxSize); 43 // getchar(); 44 if (!initSequenceString(&S, maxSize)) { 45 printf("初始化完成\n\n"); 46 } 47 break; 48 case 2: 49 printf("%s\n", S.data); 50 break; 51 case 3: 52 printf("请输入需要复制的字符串："); 53 getchar(); 54 gets(str); 55 // scanf("%s",str); 56 if (!copySequenceString(&S, str)) { 57 printf("字符串复制成功！\n\n"); 58 } 59 break; 60 case 4: 61 printf("请输入需要连接的子串："); 62 getchar(); 63 gets(str); 64 // getchar(); 65 initSequenceString(&s, S.maxSize); 66 copySequenceString(&s, str); 67 linkSequenceString(&S, &s); 68 break; 69 case 5: 70 printf("请输入需要匹配的子串："); 71 getchar(); 72 gets(str); 73 // scanf("%s", str); 74 initSequenceString(&s, S.maxSize); 75 copySequenceString(&s, str); 76 if (!matchingSequenceString(&S, &s)) { 77 printf("匹配失败，子串不存在 ！\n\n"); 78 } 79 80 break; 81 case 6: 82 printf("请输入需要比较的子串："); 83 getchar(); 84 gets(str); 85 // getchar(); 86 initSequenceString(&s, S.maxSize); 87 copySequenceString(&s, str); 88 compareSequenceString(&S, &s); 89 90 break; 91 case 7: 92 printf("字符串长度为%d\n", getSequenceStringLength(&S)); 93 break; 94 case 8: 95 printf("本应用程序为数据结构-字符串演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n"); 96 break; 97 case 0: 98 return 0; 99 break; 100 } 101 102 } while (operate != 0); 103 104 105 return 0; 106 }
error.h（错误信息）：
1 int errorCode[] = {100001, 100002, 100003}; 2 3 char* errorHint[] = { 4 "ERROR[100001]：申请内存错误，初始化失败 ！\n\n", 5 "ERROR[100002]：当前操作超出字符串最大长度 ！\n\n", 6 "ERROR[100003]：子串长度大于主串 ！\n\n", 7 };
运行截图
4.1 运行截图
小结
串的内容其实也不难，主要是字符操作较多，实现时比较繁琐。本篇也只是实现了几个基本的字符串操作。个人觉得需要注意的细节除了下标或是指针的变更外，还得仔细完成字符串在输入输出时的逻辑，防止值被污染。
每周闲篇：本周总算是将之前的APP结工了，也如愿开始了状态调整。身体方面，在戒烟的同时，恢复运动，早睡早起，控制摄入，确保营养均衡；学习方面，进度就不太如愿，下步切实将每天的英语学习落实，同时将新掌握的技术归纳总结，查漏补缺；心理方面，尚可，也该调整过来了，慢慢淡忘吧。
参考文献
王海艳等.《数据结构（C语言）》第二版[M].北京:人民邮电出版社,2020:10~14.