1.串的概念
串，即是字符串，也是一种特殊的线性表；其特殊性有两方面：
1.在逻辑结构方面，串是仅限数据类型为字符，不能是其他数据类型；
2.在运算方面，将一个串作为整体或者一部分进行运算。
2.几个概念的区别：
1.空串与空格组成的字符串：空串不包括任何字符，长度为0，而由空格组成的串由于空格也是字符，其长度为空格的个数；
2.子串与主串：串中任意个连续字符组成的子序列称为子串，包含子串的串称为主串；
3.字符和子串的位置：单个字符在串中的序号称为字符在串中的位置；子串的第一个字符在串中出现的位置称为子串在串中的位置；
4.串相等：参加比较的串的长度相等且个位置的字符也相等；
5.串的比较：以ASCII码值进行比较；
3.串的顺序结构存储及运算：
3.1.串的顺序结构存储：
1.顺序结构存储的串简称顺序串，是以一组连续的存储单元进行存储串中的字符序列。
2.一个字节需要8个字节，因此一个内存单元可以存储多个字符，如一个32位的内存单元可以存储4个字符，因此，串的顺序存储方式有两种：非紧缩格式和紧缩格式；
3.非紧缩格式是每个存储单元只存储一个字符，紧缩格式是一个存储单元可以存储多个字符；
4.一般采用的是非紧缩格式的定长存储，即直接按预定的大小，为每个串分配固定长度的存储区；
5.串的长度的标识有三种，常用的是：串末尾以不会出现在串中的字符'\0'作为结束标志；
3.2.串的基本运算：
1.求串长：
int str_len(char s[]){
int i=0;
while(s[i]!='\0'){
i++;
}
return i;
}
2.串连接：
int str_cat(char s1[],char s2[]){
int len1=str_len(s1);
int len2 =str_len(s2);
int i,j;
if(len1+len2>MAXSIZE-1){
puts("超过最大范围！！！");
return 0;
}else{
i=len1;
j=0;
while(s2[j]!='\0'){
s1[i++]=s2[j++];
}
s1[i]='\0';
}
return 1;
}
3.求子串：
//将s中从第i个位置开始，长度为len的子串通过ss返回
int sub_str(char s[],char ss[],int i,int len){
int slen=str_len(s);
if(i<1||i>slen||len<0||len>slen-i+1){
puts("参数有误！！！");
return 0;
}else{
int j;
for(j=0;j<len;j++){
ss[j]=s[i+j-1];
}
}
return 1;
}
4.串比较：
int str_cmp(char s1[],char s2[]){
int i=0;
while(s1[i]==s2[i]&&s1[i]!='\0'){
i++;
}
return s1[i]-s2[i];
}
5.串插入：
//将串s2插入到s1中i的位置
int str_insert(char s1[],int i,char s2[]){
int len1=str_len(s1);
int len2=str_len(s2);
int j,k;
char temp[10];
if(i<0||i>len1+1||len2+len1>MAXSIZE-1){
puts("参数有误！！！");
return 0;
}else{
k=i;
for(j=0;s1[k]!='\0';j++,k++){
temp[j]=s1[k];
}
temp[j]='\0';
j=0;
while(s2[j]!='\0'){
s1[i++]=s2[j++];
}
j=0;
while(temp[j]!='\0'){
s1[i++]=temp[j++];
}
s1[i]='\0';
}
return 1;
}
4.3.串的链式结构存储及运算：
4.1.概念：
1.串的链式存储结构又称链串，链串的形式一般与链表相同，唯一的区别就是：链串中的一个结点可以存储多个字符；
2.将链串中每个结点所存储的字符个数称为结点大小；
3.结点大小大于1时，存储密度高，但是操作效率不高。
4.2.链串的基本运算：
1.串赋值：将一个数组中的字符赋给链串
void init_Str(LinkStr **str,char s[]){
LinkStr *p,*q;
*s=(LinkStr *)malloc(sizeof(LinkStr));
q=*s;
int i,j;
for(i=0;s[i]!='\0';i++){
p=(LinkStr *)malloc(sizeof(LinkStr));
p->data=s[i];
q->next=p;
q=p;
}
q->next=NULL;
}
2.求串长：
int str_Length(LinkStr *s){
int i;
LinkStr *p=s->next;
while(p!=NULL){
i++;
p=p->next;
}
return i;
}
3.串连接：(t保持不变，因此不能直接将t进行操作)
void strCat(LinkStr *s,LinkStr *t){
LinkStr *p,*q,*str,*r;
str=(LinkStr *)malloc(sizeof(LinkStr));
r=str;
p=t->next;
while(p!=NULL){//先将t拷贝到临时变量str中：
q=(LinkStr *)malloc(sizeof(LinkStr));
q->data=p->data;
r->next=q;
r=q;
p=p->next;
}
p=s;
while(p->next!=NULL){//找到s的尾指针
p=p->next;
}
p->next=str->next;//进行链接
free(str);
}
4.求子串：
void strSub(LinkStr *f,LinkStr **s,int i,int len){
LinkStr *p,*q,*r;
int k;
p=f->next;//第一个元素节点
*s=(LinkStr *)malloc(sizeof(LinkStr));
*s->next=NULL;
r=*s;
if(i<0||i>str_Length(f)||len>str_Length(f)-i+1||len<0){
puts("参数错误！！！");
}else{
for(k=0;k<i-1;k++){//找到i位置结点的前驱结点
p=p->next;
}
for(k=0;k<len;k++){
q=(LinkStr *)malloc(sizeof(LinkStr));
q->data=p->data;
r->next=q;
r=q;
p=p->next;
}
r->next=NULL;
}
}
5.串插入：
void strInsert(LinkStr *s,int i,LinkStr *t){
LinkStr *p,*q;
p=s->next;//第一个元素节点
q=t;
int k;
for(k=0;k<i-1;k++){//找到i位置结点的前驱结点
p=p->next;
}
r=p->next;//将i元素结点位置的串暂时存在r中
p->next=t->next;//将t中的第一个元素链接到i-1的后面，即i的位置
p=t;
while(p->next!=NULL){//寻找t的尾结点
p=p->next;
}
p->next=r;
}
转载请注明原文地址: https://ju.6miu.com/read-23889.html
