串是由零个或者多个字符组成的有序序列。串中字符的个数称为串的长度,含有零个元素的串叫空串。web
//这就比如一个名为str的串 char str[] = "today is greate day";
串中任意连续的字符组成的子序列称为该串的子串,包含子串的串称为主串,某个字符在串中的序号称为这个字符的位置。一般用子串第一个字符做为子串在主串中的位置。要注意,空格也是串字符集合中的一个元素,由一个或者多个空格组成的串称为空格串(注意:空格串不是空串)数组
串的逻辑和线性表相似,串限定了元素为字符的线性表。从操做集上讲,串和线性表有很大的区别,线性表的操做主要针对表内的某一个元素,而串操做主要针对串内的一个子串数据结构
通常不采用刚才的那种方式来定义并初始化一个串。缘由是仅仅以'\0'做为串结束的标记在求串长的时候须要扫描整个串,时间复杂度为O(n)。不如额外来定义一个变量,专门来存储串的长度,这样一来求串长的时间复杂度为 O(1)svg
#define MAXSIZE 100 typedef struct { char str[MAXSIZE + 1]; //MAX + 1 是为了多出一个 \0 做为结束标记 int length; }Str;
在程序执行的过程根据须要动态分配函数
typedef struct { char *ch; //指向动态分配存储区首地址的字符指针 int length; //串的长度 }Str;
这种存储方式在使用时,须要用函数malloc()来分配一个长度为length,类型为char的存储空间,分配的空间能够用函数free()释放掉。用函数malloc()分配存储的空间若是成功,则返回一个指向起始地址的指针,做为串的基地址,这个地址由ch指针来指向。若是分配失败,则返回NULL。post
动态分配存储比顺序存储更加灵活,所以在串处理应用程序中,更为经常使用。spa
与普通变量赋值操做不一样,串的赋值操做不能直接用=来表示,由于串是一个数组,必须对数组中的每一个元素进行逐一赋值。操做串的赋值操做能够用strassign()实现。其功能是将一个常量字符串赋值给str。成功返回1,失败返回0.net
int strassign(Str &str,char *ch) { int len = 0,i; char* c = ch; //将ch赋给c,这样操做c时候,就不会破坏原来的ch //求串c的长度 while (*c) { len++; c++; } if (len == 0) { //若是ch为空串,则返回空串 str.ch = NULL; str.length = 0; return 1; } else { //动态分配空间,取 len + 1 是为了多出一个空间存放 '\0' str.ch = (char*)malloc(sizeof(char) * (len + 1)); if (str.ch == NULL) { return 0; } else { //把ch从新赋值给c,这样c又恢复到初始值 c = ch; for (i = 0; i <= len; ++i,++c) { str.ch[i] = *c; str.length = len; return 1; } } } }
int strlength(Str str) { return str.length; }
串的比较操做是串排序应用中的核心操做。一般是用ASCLL码进行比较指针
//串的比较操做 int strcompare(Str s1,Str s2) { int i; //任何一个串被遍历完毕就跳出循环 for (i = 0; i < s1.length && i < s2.length; ++i) { //当两个串遇到不相同的字符的时候,就进行ASCLL比较 if (s1.ch[i] != s2.ch[i]) { return s1.ch[i] - s2.ch[i]; } } //假如两个串彻底相同,就进行长度比较 return s1.length - s2.length; }
将两个串首尾相接,合并成一个字符串的操做称为串链接操做code
//串的连接操做 int concat(Str& str, Str str1, Str str2) { int i = 0, j = 0; //这里 + 1是为了给 '\0' 留个位置 str.ch = (char*)malloc(sizeof(char) * (str1.length + str2.length + 1)); if (str.ch == NULL) { return 0; } while (i < str1.length) { str.ch[i] = str1.ch[i]; ++i; } //这里使用 <= 是为了连同 str2.ch最后 '\0' 一块儿复制 while (j <= str2.length) { //从i的坐标开始赋值 str.ch[i + j] - str2.ch[j]; ++j; } str.length = str1.length + str2.length; return 1; }
求从给定串中某一位置结束的串的操做称为求字串操做(规定开始位置总在结束位置的前边)。
//str串中从post开始到len,由substr返回 int substring(Str&substr,Str str,int pos,int len) { int i = 0, j = 0; if (pos < 0 || pos >= str.length || len < 0 || len > str.length - pos) { return 0; } if (substr.ch) { free(substr.ch); substr.ch = NULL; } if (len == 0) { substr.ch = NULL; substr.length = 0; return 1; } else { substr.ch = (char*)malloc(sizeof(char) * (len + 1)); i = pos; j = 0; while (i < pos + len) { substr.ch[j] = str.ch[i]; ++i; ++j; } substr.ch[j] = '\0'; substr.length = len; return 1; } }
int clearstring(Str &str) { if (str.ch) { free(str.ch); str.ch = NULL; } str.length = 0; return 1; }