IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> C语言数据结构与算法--------串全面总结 -> 正文阅读

[数据结构与算法]C语言数据结构与算法--------串全面总结

目录

一、基本概念

二、串的类型

1.定长顺序串

2.堆串

3.块链串

三、模式匹配

四、总结与提高

String函数:

五、附录:


一、基本概念

  • 串(string):由0个或多个字符组成的有序序列,称为字符串,记为s='abcdefg' 其中s是字符串的名字,a b c称为串的值,可以是字母、数字或者字符
  • 串长度:串中元素个数
  • 空串:不含任何字符的串,串长度为0
  • 子串:主串中任意连续字符组成的字符串
  • 串s1、s2相等的条件:
    1. s1、s2长度相等
    2. s1、s2对应位置的元素处处相等

二、串的类型

1.定长顺序串

??定义:用一组地址连续的存储单元存储串值的字符序列,类似于线性表的顺序存储结构。

?静态存储分布代码实现:

#define MAXLEN 30 // 用户可在255以内定义最大串长    
typedef struct 
{
    char ch[MAXLEN];
    int len;
} SString ;

动态演示:?

  • 其实就是依次插入

算法:

串插入:

int StrInsert(SString *s, int pos, SString t)
/*在串s中下标为pos的字符之前插入串t */
{	int i;
	if (pos<0 || pos>s->len)   /*插入位置不合法*/
		return(0); 
	if (s->len + t.len<=MAXLEN) /*插入后串长≤MAXLEN*/
	{
		for (i=s->len + t.len-1;i>=t.len + pos;i--)
			s->ch[i]=s->ch[i-t.len]; //将插入位置现有字符后移
		for (i=0;i<t.len;i++) 
			s->ch[i+pos]=t.ch[i];   //在空出的位置逐个插入字符串
		s->len=s->len+t.len;
	}	
else
	{         if (pos+t.len<=MAXLEN) 
             /*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/
		{
			for (i=MAXLEN-1;i>t.len+pos-1;i--) 
				s->ch[i]=s->ch[i-t.len]; //将插入位置现有字符后移
			for (i=0;i<t.len;i++)
				s->ch[i+pos]=t.ch[i]; //在空出的位置逐个插入字符串
			s->len=MAXLEN;
		}
		else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/
		{ 	for (i=0;i<MAXLEN-pos;i++)
				s->ch[i+pos]=t.ch[i];
			s->len=MAXLEN;
		}
		return(1);
	}
}

串删除:

int StrDelete(SString *s, int pos, int len)
/*在串s中删除从下标pos起len个字符*/
{ 
	int i;
	if (pos<0 || pos>(s->len-len))  /*删除参数不合法*/
		return(0); 
	for (i=pos+len;i<s->len;i++)
		s->ch[i-len]=s->ch[i];   /*从pos+len开始至串尾依次向前移动,实现删除len个字符*/
	s->len=s->len - len;    /*s串长减len*/
	return(1);
}

串复制:

void StrCopy(SString *s, SString t)
/*将串t的值复制到串s中*/
{ 
	int i;
	for (i=0;i<t.len;i++)
		s->ch[i]=t.ch[i];
	s->len=t.len;
}

串比较:

int StrCompare(SString s, SString t)
/*若串s和t相等则返回0;若s>t则返回正数;若s<t则返回负数*/
{ 
	int i;
	for (i=0;i<s.len&&i<t.len;i++)
		if (s.ch[i]!=t.ch[i]) 
			return(s.ch[i] - t.ch[i]);   //按字符的字典顺序比较
	return(s.len - t.len);
}

串连接:

int StrCat(SString *s, SString t)
/*将串连接在串s的后面*/
{ 	int i, flag;
	if (s->len + t.len<=MAXLEN) 
                   /*连接后串长小于MAXLEN*/
	{ 
		for (i=s->len; i<s->len + t.len; i++)
			s->ch[i]=t.ch[i-s->len]; //t的下标从0开始
		s->len+=t.len;
		flag=1;
	}
	else 
    {
        if (s->len<MAXLEN)  
       /*连接后串长大于MAXLEN,但串s的长度小于MAXLEN,即连接后串t的部分字符序列被舍弃*/
	    { 
		    for (i=s->len;i<MAXLEN;i++)
		    	s->ch[i]=t.ch[i-s->len];
		    s->len=MAXLEN;
	    	flag=0;
	    }
	    else 
	    	flag=0;  /* 串s的长度等于MAXLEN ,串t不被连接*/
	return(flag);
    }

求子串:

int SubString(SString *sub, SString s, int pos, int len) 
/*将串s中下标pos起len个字符复制到sub中*/
{ 	int i;
	if (pos<0 || pos>s.len || len<1 || len>s.len-pos) //位置或长度不合法时
    {
		sub->len=0;
		return(0); 
	}
	else 
	{	for (i=0; i<len; i++)
			sub->ch[i]=s.ch[i+pos];
		sub->len=len;
		return(1);
	}
}

2.堆串

  • 堆:自由存储区域,malloc()实现
  • 一组地址连续的存储单元存储串值?????? 的字符序列,在程序执行过程中由动态分配而得到

代码:

typedef struct {  
      char *ch; // 若非空串则按串长分配存储区,否则为NULL
      int length;// 串长度
} HString;

3.块链串

  • 定义:与链表类似,但每一个结点可以存放多个字符,结尾增加尾指针

?代码实现:

#define BLOCK_SIZE 4 // 可由用户定义的块大小   
typedef struct Block
 { 
     char ch[BLOCK_SIZE];
     struct Block *next;
} Block;

三、模式匹配

  • 定义:求解子串首次在主串中出现的位置
  • 模式匹配也称为子串的定位操作,用函数StrIndex(S,pos,T)实现,T被称为模式串

代码:?

int StrIndex(SString s,int pos, SString t) 
/*求从主串s的下标pos起,串t第一次出现的位置,成功返回位置序号,不成功返回-1*/
{ 	int i, j, start;
	if (t.len==0)  return(0);   /* 模式串为空串时,是任意串的匹配串 */
	start=pos; i=start; j=0;  /* 主串从pos开始,模式串从头(0)开始 */
	while (i<s.len && j<t.len)
		if (s.ch[i]==t.ch[j]) 
		{    i++;   j++;	}   /* 当前对应字符相等时推进 */
		else 
		{   start++;        /* 当前对应字符不等时回溯 */
		     i=start;    j=0;   /* 主串从start+1开始,模式串从头(0)开始*/
		} 
		if (j>=t.len) 
			return(start);    /* 匹配成功时,返回匹配起始位置 */
		else 
			return(-1);    /* 匹配不成功时,返回-1 */
}

演示图:

?解析:

  • 设置两个指针i和k,输入目标串Hello World!,模式串orl

  • 如果i指向的值和模式串首个元素不一致,则指针i j同时向后移动

  • 如果i指向的值和模式串首个元素一致,则只是指针j向后移动

  • 如果j指向的元素和模式串后续元素一致,继续移动,直到查找完成

  • 如果j指向的元素和模式串后续元素不一致,指针i到k的位置,继续开始

四、总结与提高

在C++中,C++ 标准库提供了?string?类类型,支持上述所有的操作,另外还增加了其他更多的功能。

编程时加入头文件:

#include<string>//或者万能头文件#include<bits/stdc++.h>
using namespace std;

String函数:

用string定义s类(定义什么都可以,只要把s变成定义的字母就可以调用C++中的函数),具体使用方法为:

函数用法
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 常见操作
s.resize(10)设置字符串长度为10
string s("ABC")构造字符串s的值为ABC
s.empty()判断字符串是否为空
s.length()或者s.size()求解字符串长度
s.begin()开始值
s.end()结尾值
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 查找(查找成功返回元素位置,失败返回-1)
s.find('A')查找字符A
s.find("ABC")查找字符串ABC
s.find('A',2)从位置2开始查找字符A
s.find("ABCD",1,2)从位置1开始,查找ABCD的前两个字符
s.rfind()从字符串尾部开始查找
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 插入
s.insert(2,3,'A')在下标为2的地方添加三个A
s.insert(2,"ABC")在下标为2的地方添加字符串ABC
s.insert(2,"ABC",1)在下标为2的地方添加ABC中的一个
s.insert(2,"ABCD", 2,2)在下标为2的地方从字符串ABCD中位置2开始的2个字符
s.push_back('A')在尾部添加字符A
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?替换
s.replace(2,4,"ABCD")从下标2的位置,替换4个字符为 "ABCD"
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?删除
s.erase(2)删除下标2以后的全部元素
s.erase(2,1)删除下标2以后的第一个元素
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?翻转
reverse(s.begin(),s.end())翻转所有字符串,即逆序输出
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 复制
s1=s.substring(2)提取字符串s从2到尾部赋值给s1
s1=s.substring(2,3)提取字符串s从2开始三个字符赋值给s1
const char*s1=s.data()将string类转为字符串数组
s.copy(s1,2,3)将s中从第3个位置拷贝2个字符到s1中
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 比较(假设原字符串为ABCD)
s.compare("ABCD")相等返回0,大于原字符串返回1,小于返回-1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 清空
s.assign("ABC")清空字符串,并置为ABC
s.assign("ABC",2)清空字符串,并置为ABC的前2个字符AB
s.assign("ABC",2,1)清空字符串,并置为ABC的从2开始的1个字符
s.assign(5,‘A’)清空字符串,并置为5个A
s.clear()清空字符串所有字符

文档的具体内容可以参考:C++标准官方文档

五、附录:

几道经典的题目链接:1.无重复的最长子串

? ? ? ? ? ? ? ? ??????????????????? 2.最长回文串

? ? ? ? ? ? ? ? ????????????????? ? 3.模式匹配

? ? ? ? ? ? ? ? ??????????? ????????4.回文串

? ? ? ? ? ? ? ? ??????????????????? 5.最长回文子序列

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-10 11:18:39  更:2021-12-10 11:19:02 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/10 2:54:29-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码