# 串的存储结构

## 顺序存储

```typedef struct
{
char data[maxsize];
int len;
}stype;```

## 下面是串的顺序结构的常用操作：

```package bind;

class SqString {
final int MaxSize = 100;
char data[];
int length;

public SqString() {
data = new char[MaxSize];
length = 0;
} // 字符串赋值 char[]

public void StrAssign(char cstr[])	{
int i;
for (i = 0; cstr[i] != '/0'; i++)
data[i] = cstr[i];
length = i;	}
// 将串s复制给当前串SqSting
public void StrCopy(SqString s) {
int i;
for (i = 0; i < s.length; i++)
data[i] = s.data[i];
length = i;
}
// 判断串是否相等
public boolean StrEqual(SqString s) {
boolean b = true;
if (s.length != length)
b = false;
else
for (int i = 0; i < length; i++)
if (s.data[i] != data[i]) {
b = false;
break;
}
return b;
}
// 求串长
public int StrLength() {
return length;
}
// 当前串与串s连接
public void Concat(SqString s) {
SqString str = new SqString();
int i;
str.length = length + s.length;
for (i = 0; i < length; i++)
str.data[i] = data[i];
for (i = 0; i < s.length; i++)
str.data[length + i] = s.data[i];
this.StrCopy(str);
}
// 返回串从第i开始之后j个字符组成的子串
public SqString SubStr(int i, int j) {
SqString s = new SqString();
if (i <= 0 || i > length || j < 0 || i + j - 1 > length)
return s;
for (int k = i - 1; k < i + j - 1; k++) {
s.data[s.length++] = data[k];
}
return s;
}
// 在当前串在第i位插入S2
public void InsStr(int i, SqString s2) {
int j;
SqString str = new SqString();
if (i <= 0 || i > s2.length + 1) {
System.out.println("Error:out of index! ");
return;
}
for (j = 0; j < i - 1; j++)
str.data[str.length++] = data[j];
for (j = 0; j < s2.length; j++)
str.data[str.length++] = s2.data[j];
for (j = i - 1; j < length; j++)
str.data[str.length++] = data[j];
this.StrCopy(str);
}

// 删除第i位开始长度为j的子串
public void DelStr(int i, int j) {
int k;
SqString s = new SqString();
if (i <= 0 || i > length || i + j > length + 1) {
System.out.println("Error: out of index!");
return;
}
for (k = 0; k < i - 1; k++)
s.data[s.length++] = data[k];
for (k = i + j - 1; k < length; k++)
s.data[s.length++] = data[k];
this.StrCopy(s);
}

// 用串t代替当前串中第i位开始的j个字符构成的子串
public void RepStr(int i, int j, SqString t) {
this.DelStr(i, j);
this.InsStr(i, t);
}

public void DispStr() {
int i;
if (length > 0) {
for (i = 0; i < length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
}

public class MySqString {
public static void main(String args[])	{
char cstr1[] =		{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', '/0' };
char cstr2[] =		{ '1', '2', '3', '4', '5', '6', '7', '/0' };
SqString s1 = new SqString();
s1.StrAssign(cstr1);
System.out.print("s1:");
s1.DispStr();
SqString s2 = new SqString();
s2.StrAssign(cstr2);
System.out.print("s2:");
s2.DispStr();
SqString s3 = new SqString();
s3.StrCopy(s1);
System.out.print("s3=s1/ns3:");
s3.DispStr();
System.out.println("s3.length=" + s3.length);
s3.Concat(s2);
System.out.print("s3=s3+s2:");
s3.DispStr();
System.out.println("s3.length=" + s3.length);
SqString s4 = new SqString();
System.out.println("返回串3从第1开始之后2个字符组成的子串");
s4 = s3.SubStr(1, 2);
s4.DispStr();
System.out.println("在当前串在第i位插入S2");
s4.InsStr(2, s2);
s4.DispStr();
System.out.println("删除第2位开始长度为1的子串");
s4.DelStr(2, 1);
s4.DispStr();
System.out.println("用串s2代替当前串中第2位开始的3个字符构成的子串");
s4.RepStr(2, 3, s2);
s4.DispStr();	}
}}```

## 堆式存储

```Typedef struct
{  char *ch;   //指针域，指向存放串值的存储空间基址
int length;  // 整型域：存放串长
}HString;```

## 链式存储

```//串的链式存储表示
typedef struct{
char ch
LStrNode *next;
}LStrNode,*LString;```

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*字符结点*/
struct Node{
char c;
struct Node * next;
};

typedef struct Node * PNode;

/*函数声明*/
int insertBeforeElement(PNode pstr);
int dtempteElement(PNode pstr);
void printString(PNode pstr);

/*----------创建一个空的字符串---------------*/
PNode pstr=(PNode)malloc(sizeof(struct Node));
if(pstr != NULL){
pstr->next=NULL;
pstr->c='-';
printf("创建成功！\n");
}
else{
pstr=NULL;
printf("创建失败！\n");
}
return pstr;
}

/*-----------判断串是否为空----------------*/
if(pstr->next == NULL){
printf("空串！\n");
return 1;
}
else{
printf("非空串！\n");
return 0;
}
}

/*----------初始化一个空字符串-------------*/
PNode cur = pstr;

while(1){
char c;
printf("输入字符(@结束)>>>");
scanf("%c",&c);
getchar();
if(c =='@'){
break;
}
// 申请要插入的结点
PNode temp = (PNode)malloc(sizeof(Node));
temp->next = NULL;
temp->c = c;
if(pstr->next == NULL){
pstr->next = temp;
cur = pstr;
}else{
cur->next->next = temp;
cur = cur->next;
}
}
printf("初始化完毕！\n");
printString(pstr);
return 1;
}else{
printf("初始化失败！\n");
return 0;
}
}

/*-----------在指定字符之前插入字符---------------*/
int insertBeforeElement(PNode pstr,char c,char s){
PNode cur = pstr;
while(cur->next != NULL){
// 找到指定字符
if(cur->next->c == c) {
PNode temp = (PNode)malloc(sizeof(PNode));
temp->c = s;
temp->next = cur->next;
cur->next = temp;
printf("插入成功！\n");
printString(pstr);
return 1;
}
cur = cur->next;
}
printf("未找到指定字符，插入失败\n");
return 0;
}

/*---------删除指定元素----------*/
int deleteElement(PNode pstr,char c){
PNode cur = pstr;
while(cur->next != NULL){
// 找到指定字符
if(cur->next->c == c){
cur->next = cur->next->next;
printf("删除成功！\n");
printString(pstr);
return 1;
}
cur = cur->next;
}
printf("删除失败！\n");
return 0;
}

/*----------打印当前字符串----------*/
void printString(PNode pstr){
PNode cur = pstr;

printf("[");
while(cur->next != NULL){
printf(" %c ",cur->next->c);
cur = cur->next;
}
printf("]");
}
/*-------主控-------*/
int main(void){
PNode pstr= NULL;
printf("\n--------字符串的基本操作---------\n");
char c,s,ch;
int input;
while(1){
printf("\n 1_创建空串\n 2_判断当前是否为空\n 3_初始化空串\n");
printf(" 4_在指定字符之前插入字符\n 5_删除指定字符\n 6_打印串\n");
printf("\n请选择>>>");
scanf("%d",&input);
scanf("%c",&ch);
switch(input){
case 1 :
break;
case 2 :
break;
case 3 :
break;
case 4 :
printf("请指定字符>>>");
scanf("%c",&c);
getchar();
printf("请输入要插入的字符>>>");
scanf("%c",&s);
insertBeforeElement(pstr,c,s);
break;
case 5 :
printf("请指定字符>>>");
scanf("%c",&s);
deleteElement(pstr,s);
break;
case 6 :
printString(pstr);
break;
default:
printf("输入错误,请重新输入");
break;
}
}
return 0;
}  ```

# 串的比较

## 串的抽象数据类型

```Data
串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
strCopy(T,S):串S存在，由串S复制得串T
ClearString(S):串S存在，将串清空
StringEmpty(S):若串S为空，返回true，否则false
StrLength(S):返回串S的元素个数，即串的长度
StrCompare(S,T):若S>T,返回值大于0;若S=T,返回0,若S<T,返回值0
Concat(T,S1,S2):用串T返回S1和S2连接而成的新串
SubString(Sub,S,pos,len):串S存在,1≤pos≤StrLength(S)
且0≤len≤StrLength(S)-pos+1,用Sub
返回值S的第pos个字符起长度为len的子串
Index(S,T,pos):串S和串T存在,T是非空串1≤ pos ≤StrLength(S)
若主串S中存在和串T相同的子串，则返回它在主串S中
第pos个字符后第一个出现的位置，否则返回0
Replace(S,T,V):串S、T和V存在，T是非空串。用V替换主串中出现的
所有与T相等的不重叠的子串
StrInset(S,pos,T):串S和T存在,1 ≤ pos ≤StrLength(S) + 1
在串S的第pos个字符之前插入串T
StrDelete(S,pos,len):串S存在，1≤pos≤StrLengthS-len+1
从串S中删除第pos个字符起长度为len的子串。```

```int Index(String S,String T,int pos)
{
int n,m,i;
String sub;
if(pos > 0)
{
n = StrLength(S);//得到主串S的长度
m = StrLength(T);
i = pos;
while(i <= n-m+1)
{
SubString(sub,S,i,m);//取主串第i个位置,m长度的子串
if(StrCompare(sub,T) != 0)//如果两串不相等
i++;
else                      //如果相等
return i;             //返回i值
}
}
return 0;//若无子串与T相等，返回0
}```

## 串的模式匹配

```int Index(String S,String T,int pos)
{
int i = 0;
int j = 0;
int SLen = 0;
int TLen = 0;
while(s[i] != '\0')//计算S长度
{
SLen++;
}
while(T[i] != '\0')//子串T的长度
{
TLen++;
}
int i = pos;
while(i <= SLen - TLen && j <= TLen)
{
if(S[i] == T[i])
{
i++;
j++;
}
else
{
i = i - j + 1;//匹配失败回到开始的地方的下一个位置
j = 0;//子串回到原来位置
}
}
if(j > TLen)
{
return i - TLen;
}
else
return 0;
}```

1007 篇文章104 人订阅

0 条评论

## 相关文章

48811

1424

1142

### 获取对象具体类型的功能函数

HTML5学堂：JavaScript当中，时常会使用到typeof来进行数据类型的检测，但是我们觉得typeof不能够满足我们的需求，对于数组、函数、时间对象等...

3287

3496

4630

### Go语言interface详解

interface Go语言里面设计最精妙的应该算interface，它让面向对象，内容组织实现非常的方便，当你看完这一章，你就会被interface的巧妙设计...

3709

1622

1582

### Go语言interface详解

interface Go语言里面设计最精妙的应该算interface，它让面向对象，内容组织实现非常的方便，当你看完这一章，你就会被interface的巧妙设计...

3717