系列文章目录
第五话 数据结构之串
文章目录
- 一、了解什么是串
- 二、串的基本特征
-
三、串的基本操作
- 串的初始化
- 串的输出
- 四、串的匹配模式
- 五、总结
前言
串（即字符串）是一种特殊的线性表，在信息检索、文本编辑等领域有广泛的应用。其特殊性体现在组成线性表的每个数据元素是单个字符，而由一个个字符串起的字符串却是最基本的非数值数据，在操作过程中常常作为一个整体来处理。研究串的特点、存储结构和基本操作实现，是非常有必要的。
一、串的定义
1.串的定义
串是由零个或任意多个字符组成有限序列。一般记为：s="a1a2a3...an"(n>=0)
串可以是字母、数字或其他字符，n为串的长度。
2.串的相关术语
（1）空串。不含任何字符的串称为空串，即串的长度n=0时，称为空串。
（2）空格串。由一个或多个称为空格的特殊字符组成的串称为空格串，其长度是串中空格字符的个数。
（3）子串。串中任意连续的字符组成的子序列称为该串的子串。另外，空串是任意串的子串，任意串是自身的子串。
（4）主串。包含子串的串称为该子串的主串。
（5）匹配模式。子串的定位运算又称为串的匹配模式，是一种求子串在主串中第一次出现的第一个字符的位置。
（6）串相等。两个串的长度相等且各个位置上对应的字符也都相同。
二、串的基本特征
对照串的定义和线性表的定义可知，串是一种其数据元素固定为字符的线性表。但是，串的基本操作对象和线性表的操作对象却有很大的不同。线性表上的操作是针对其某个元素进行的，而串上的操作主要是针对串的整体或串的一部分子串进行的。这也是把串单独作为一章的原因。
三、串的基本操作
1.定义存储结构--顺序存储
#include<stdio.h>
#include<stdlib.h>
#define maxsize 80
typedef char Elemtype;
typedef struct{
Elemtype date[maxsize];
int Len;
}String;2.将串进行初始化
String *init_string()
{
String *s;
s = (String*)malloc(sizeof(String));
if(s!=NULL){
s->Len=0;
}
return s;
}3. 创造一个串并求其串长度
void createstring(String *s)
{
printf("请输入一段字符串，按回车结束：\n");
gets(s->date);
int i=0,j=0;
while(s->date[i]!='\0'){
i++;
j++;
}
s->Len = j;
}4.在主函数中实现调用
int main()
{
String *s1;
s1 = init_string();
createstring(s1);
printf("%s",s1->date);
return 0;
} 
四、字符串的匹配模式
1.在主串中找子串第一次出现的位置
int stringindex(String *s1,String *s2)
{
int i=0,j=0,k;
while(i<s1->Len&&j<s2->Len){
if(s1->date[i]==s2->date[j]){
i++;
j++;
}else{
i = i-j+1;
j = 0;
}
}
if(j>=s2->Len){
k=i-s2->Len+1;
}else{
k=-1;//如果没找到则返回值-1;
}
return k;
}2.在主串中删除子串
void deletestring(String *s,int i,int j)
{
int k;
if(i+j-1>s->Len){
printf("所要删除的子串越界!");
}else{
for(k=i+j-1;k<s->Len;k++,i++){
s->date[i-1] = s->date[k];
}
s->Len = s->Len-j;
s->date[s->Len]= '\0';
}
}在主函数中实现 如下:
int main()
{
String *s1;
String *s2;
s1 = init_string();
s2 = init_string();
createstring(s1);//创造一个主串
createstring(s2);//创造一个子串
int a = stringindex(s1,s2);//得到子串的位置
int b = s2->Len;//得到子串的长度从而删除
deletestring(s1,a,b);
printf("%s",s1->date);
return 0;
}
3.在主串中插入子串
void insertstring(String *s1,String *s2,int i)//在第i位中插入
{
int j;
if(i>s1->Len+1){
printf("插入的位置错误");
}else if(s1->Len+s2->Len>maxsize){
printf("两串长度超过存储空间长度");
}else{
for(j=s1->Len-1;j>=i-1;j--){//将第i位开始的字符各向后移动s2串长度
s1->date[s2->Len+j] = s1->date[j];
}
for(j=0;j<s2->Len;j++){
s1->date[i+j-1] = s2->date[j];//将子串s2插入到s1的第i个位置处
}
s1->Len = s1->Len+s2->Len-1;
s1->date[s1->Len] = '\0';
}
}在主函数中实现 如下:
int main()
{
String *s1;
String *s2;
s1 = init_string();
s2 = init_string();
createstring(s1);//创造一个主串
createstring(s2);//创造一个子串
int a = s1->Len;//得到主串的位置
insertstring(s1,s2,a);
printf("%s",s1->date);
return 0;
4.比较两个串的大小
void cmpstring(String *s1,String *s2)
{
int i=0,flag=0;
while(s1->date[i]!='\0'&&s2->date[i]!='\0'){
if(s1->date[i]!=s2->date[i]){//两串对应的位置是否相等
flag = 1;
break;
}else{
i++;
}
}
if(flag==0&&s1->Len==s2->Len){
printf("两串相等\n");
}else{
printf("两个串不相等,两串ASCII差值为%d\n",s1->date[i]-s2->date[i]);
//不相等返回不同位置的ASCII码差值
}
}在主函数中实现 如下:
int main()
{
String *s1;
String *s2;
s1 = init_string();
s2 = init_string();
creatstring(s1);
creatstring(s2);
cmpstring(s1,s2);
return 0;
}
五、总结
1、串的基本概念
串是一种特殊的线性表，规定每个数据元素仅由一个字符组成。串上的操作主要是针对串的整体或串的一部分子串进行的。
2、串的存储结构
串是字符型的线性表，与线性表类似，串也有两种基本存储结构：顺序存储和链式存储。由于串的特殊性。主要运用顺序存储。
3、串的运算实现文章来源：https://www.toymoban.com/news/detail-415969.html
串的基本运算包括串的连接、插入、删除、比较、寻找等，要求重点掌握串的定长顺序存储的基本算法。文章来源地址https://www.toymoban.com/news/detail-415969.html
到了这里，关于数据结构--串的基本操作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
