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

目录

一、串的基本概述

二、串的存储结构

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; }