看到之前最开始学的时候写的一个代码，关于串（string）的，今天分享一下。
串，在数据结构中即表示字符串，大多数信息都是以字符串的形式展现出来的，它由n个字符组成的一个整体（n>=0）,其中可以包括字母、数字或者其他字符组成。双引号（“”）括起来表示串，即使其中只有一个字符，也叫字符串，如“A”，实际上包含两个元素：A+\0，后面有一个结束符。单引号（‘’）括起来的是字符。
c/c++中可以用下面用几种种方式实现串（c++中有string类，使用更方便，以后会讲到）。
（1）定义字符数组存放字符串
#include<stdio.h> #include<iostream> using namespace std; void main() { char string[] = "hello world";//定义字符数组，并存放字符串(初始化时可以“=”) //char string[10]; //string ="abcf";//此操作是不允许的，非初始化时，不能用“=”，要用strcpy（） int lenth = sizeof(string);//sizeof()计算字符数组大小，包括最后的'\0' cout << lenth << endl;//输出12，,1个字符+'\0' cout << string<<endl;//输出字符数组 system("pause"); }字符数组也是数组，string是数组名，代表字符数组的首元素的地址 ，string[4]代表数组中序号为3的元素o，string[4]就是（string+4），string+4是一个地址，指向字符‘o’。
（2）用字符指针指向一个字符串
#include<stdio.h> #include<iostream> using namespace std; void main() { char *string = "hello world";//定义字符指针 //等价于下面两句 /*char *string; string = "hello world";//字符串的第一个字符的地址赋值给字符指针*/ int lenth1 = sizeof(string);//sizeof计算的是字符指针的大小，为4 int lenth2 = sizeof(*string);//*string等价于string[0],是一个字符，为1 cout << lenth1 <<' '<<lenth2 << endl;//输出4 1 cout << string<<endl; system("pause"); /*char string[] = "hello world"; int lenth = sizeof(string); cout << lenth << endl; cout << string<<endl; system("pause");*/ }（3）顺序串
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<string> using namespace std; #define MAXSIZE 100 //顺序串的定义 typedef struct { char data[MAXSIZE];//用来存储字符串 int length;//用来存储字符串长度 }SqString; //设计顺序串实现比较运算strcmp(s,t)的算法 /*算法思路： 1.比较s和t两个串公共长度范围内的对应字符： a.若s的字符>t的字符，返回1 b.若s的字符<t的字符，返回-1 c.若s的字符=t的字符，按上述规则继续比较 2.当1中对应字符均相同时，比较s和t的长度： a.若s的长度>t的长度，返回1 b.若s的长度<t的长度，返回-1 */ int Strcmp(SqString s, SqString t) { int comlen = 0;//公共长度 if (s.length <= t.length)//先求两个串的公共长度（取小） comlen = s.length; else comlen = t.length; for (int i = 0; i < comlen; i++)//循环比较公共长度内的字符 { if (s.data[i] > t.data[i])//s>t return 1; else if (s.data[i] < t.data[i])//s<t return -1; else(s.data[i] = t.data[i])//s等于t ;//空操作 }//循环结束，还没返回 if (s.length > t.length)//循环比较完，都相等，长度取大 return 1; else return -1; } int main() { SqString a;//定义一个SqString类型的结构体变量a SqString b;//定义一个SqString类型的结构体变量b a.length = 3;//a的长度 b.length = 5;//b的长度 //a.data="sbc";//这是不允许的 //a.data[0]='a';//可以依次单个字符赋值 strcpy_s(a.data, "fkl");//赋值字符串，给结构体中字符数组赋值，初始化可以直接赋值，否则不行 strcpy_s(b.data, "fknak");//赋值字符串 int res=Strcmp(a, b);//比较大小，a<b cout << res<<endl;//输出-1 system("pause"); }这里有个知识点需要注意，在主函数中，给结构体字符数组赋字符串时，只有在定义字符数组时才能用“=”来初始化变量，其他情况下不能直接用“=”来为字符数组赋值，要给字符数组赋值可以用<string.h>头文件中的strcpy（）函数要完成。用字符指针时，字符串“赋值”给字符指针实际上是把字符串的第一个字符的地址赋给指针变量。
（4）链串
#include<stdio.h> #include<iostream> using namespace std; typedef struct snode { char data;//数据域 struct snode *next;//指针 }LiString; /*在链串中，设计一个算法把最先出现的子串“ab”改成“xyz” 1.先找到第一次出现ab的位置，第一个出现a,下一个出现b; 2.将a换成x,将b换成z; 3.中间插入y(链表的插入形式); */ void exchange(LiString *s)//LiString *&指针的引用 { LiString *p= s->next, *q;//创建两个指针，一个指向s头节点的下一节点 q = (LiString*)malloc(sizeof(LiString));//开辟空间 int flag = 0;//确保找的是第一个子串"ab" while (flag==0 && p!=NULL)//循环条件 { if (p->data == 'a'&&p->next->data == 'b') { p->data = 'x';//a改为x p->next->data = 'z';//b改为z q->data = 'y'; q->next = p->next; p->next = q;//插入y flag = 1;//标志位置1 } else p = p->next;//让p指向p的下一个 } } LiString* initString()//初始化串,创建一个带头结点的空链串 { LiString *s; s = (LiString*)malloc(sizeof(LiString));//开辟空间 if (s == NULL) { cout << "开辟空间失败！" << endl; exit(-1); } else s->next = NULL;//头结点下一结点为NULL return s; } /*void stringAssign(LiString *s, char *ch) { LiString *q,*r,*t; r = s; //r指向头结点 t = s->next;//t指向下一个节点 for (int i = 0; ch[i] != '\0'; i++) { if (t != NULL) { t->data = ch[i];//存放数据 r = t;//r指向t t = t->next;//t指向下一结点 } else { q = (LiString*)malloc(sizeof(LiString)); q->data = ch[i]; r->next = q; r = q; } } r->next = NULL; while (t!=NULL) { q = t->next; free(t); t = q; } }*/ //串赋值操作，将一个字符串常量t赋给一个字符串变量s void assignString(LiString *s, char ch[]) { LiString *t, *p; t = s;//t指向头结点 p = s->next;//p指向头结点的下一结点 LiString * n;//用于新开辟空间用 for (int i = 0; ch[i] != '\0'; i++) { if (p != NULL)//可以直接存放数据 { p->data = ch[i];//存放数据 t = p;//t向后移 p = p->next;//p向后移 } else//后面无空间，需要新开辟空间 { n = (LiString*)malloc(sizeof(LiString));//开辟空间 n->data = ch[i];//存放数据 t->next = n; t = n;//t后移 } } t->next = NULL;//结尾给NULL while (p != NULL)//说明之前的字符串长于现在复制的，要把后面的全部清理掉 { LiString *de; de = p->next;//让de指向下一个 free(p);//释放当前的 p = de;//再让p指向de } } void list(LiString *s)//输出字符串 { LiString *p; p = s->next;//p指向头结点的下一结点 while (p != NULL)//当结点不为NULL { cout << p->data;//输出数据 p = p->next;//指针后移 } } int main() { LiString *string; char *t1 = "heablloab"; string=initString();//初始化串 //stringAssign(string, t1); assignString(string, t1);//串赋值 exchange(string);//在链串中，设计一个算法把最先出现的子串“ab”改成“xyz” list(string);//输出串 system("pause"); }链串的初始化、赋值、以及输出在里面都有，且有详细的注释。
本段代码中还是实现了一个小的算法题：把一个字符串中第一次出现的“ab”改为“xyz”，用链串实现起来非常容易，找到第一次出现的位置，‘a’改为‘x’，‘b’改为‘z’，并在中间插入一个‘y’即可，链串实现插入非常容易。
