串的基本操作--数据结构

目录

一、串的基本概述

二、串的存储结构

2.1定义属性存储结构

串长有两种表示方法: 

1、用一个额外的变量length来存放串的长度；

2、串值后面加一个不计入串长的结束标记字符“\0”，此时的串长为隐含值。 

2.2堆的顺序存储结构  

三、串的基本操作 

3.1在模式串中pos位置查找长度为len的子串

 3.2直接返回模式串的长度

 3.3比较两个字符串之间的大小长短

 3.4朴素模式匹配算法

原文 

一、串的基本概述

• 串是由零个或多个字符组成的有限序列；
• 串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串；
• 子串在主串中的位置以子串的第一个字符在主串中的位置来表示；
• 当两个串的长度相等且每个对应位置的字符都相等时，称这两个串是相等的；
• 由一个或多个空格(空格是特殊字符)组成的串称为空格串，其长度为串中空格字符的个数。

二、串的存储结构

存储结构：顺序存储与链式存储。考虑到存储效率和算法的方便性，串多采用顺序存储结构。

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

2.1定义属性存储结构

串长有两种表示方法: 

1、用一个额外的变量length来存放串的长度；

2、串值后面加一个不计入串长的结束标记字符“\0”，此时的串长为隐含值。 

我们这里采用方法1

​#define MAX_SIZE 25  //预定义最大串长为255
typedef struct{
    char ch[MAX_SIZE];   //每个分盘存储一个字符
    int length;         //串的实际长度
}SString;

2.2堆的顺序存储结构  

// 堆的顺序存储结构
struct HString{
    char *ch;     //按串长分配存储区，ch指向串的基地址
    int length;   //串的长度
} ;

三、串的基本操作 

3.1在模式串中pos位置查找长度为len的子串

//求子串
bool SubString(SString& Sub, SString S, int pos, int len) {
	if (pos + len - 1 < S.length) {
		return false;
	}
	for (int i = pos; i < pos + len; i++) {
		Sub.date[i] = S.date[i];
	}
	Sub.length = len;
}

 3.2直接返回模式串的长度

//求字符串长度
int length(SString S) {
	return S.length;
}

 3.3比较两个字符串之间的大小长短

//比较操作
bool compare(SString a,SString b) {
	for (int i = 0; i < a.length & i < b.length; i++) {
		if (a.date[i] != b.date[i]) {
			return a.date[i] - b.date[i];
		}
	}
	return a.length - b.length;
}

 3.4朴素模式匹配算法

//定位操作
int index(SString a, SString b) {
	SString Sub;
	int i = 1;
	int n = length(a), m =length(b);
	while (i <= n - m + 1) {
		SubString(Sub, a, i, m);
		if (compare(Sub, b) == 0)return i;
	}
	return 0;
}

原文 

#include<bits/stdc++.h>
using namespace std;
#define MAX_SIZE  23
struct SString {
	char date[MAX_SIZE];
	int length;
};
//求子串
bool SubString(SString& Sub, SString S, int pos, int len) {
	if (pos + len - 1 < S.length) {
		return false;
	}
	for (int i = pos; i < pos + len; i++) {
		Sub.date[i] = S.date[i];
	}
	Sub.length = len;
}
//比较操作
bool compare(SString a,SString b) {
	for (int i = 0; i < a.length & i < b.length; i++) {
		if (a.date[i] != b.date[i]) {
			return a.date[i] - b.date[i];
		}
	}
	return a.length - b.length;
}
//求字符串长度
int length(SString S) {
	return S.length;
}
//定位操作
int index(SString a, SString b) {
	SString Sub;
	int i = 1;
	int n = length(a), m =length(b);
	while (i <= n - m + 1) {
		SubString(Sub, a, i, m);
		if (compare(Sub, b) == 0)return i;
	}
	return 0;
}
//在主串里面查找模式串
int index2(SString a, SString b) {
	int i, j = 1;
	while (i <= length(a) && j <= length(b)) {
		if (a.date[i] == b.date[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;
			j = 1;
		}
	}
	if (j > length(b))return i-length(b);
	else return 0;
}