数据结构——串的顺序存储实现

概念：

串（string）:零个或多个任意字符组成的有限序列

空串：（与空集合符号相同）

子串：串中任意个连续字符组成的子序列称为该串的子串

主串：包含子串的串相应地称为主串

字符位置：字符在序列中的序号为该字符在串中的位置

子串位置：子串第一个字符在主串中的位置

空格串：由一个或多个空格组成的串，与空串不同

串相等：当且仅当两个串的长度相等且各个对应位置上的字符都相同时，这两个串才是相等的

实现

#pragma once
#include <stdio.h>
#include <string.h>

# define MAXSIZE 10

typedef struct
{
	char ch[MAXSIZE];
	int length;
}SString;

int StrAssign(SString* S, char* str);
int Index_BF(SString* S, SString* T);
void StringCopy(SString* S1, SString* S2);
int LengthString(SString* S);
int PrintString(SString* S);
int StringCompare(SString* S1, SString* S2);
int ConcatString(SString* S, SString* S1, SString* S2);
int SubString(SString* Sub, SString* S, int pos, int len);
int StrInsert(SString* S1, int pos, SString* S2);
int StrDelete(SString* S, int pos, int len);
void get_next(SString* T, int* next);
int Index_KMP(SString* S, SString* T, int pos);

#include "string.h"

//暴力算法
int Index_BF(SString* S, SString* T)
{
	int i = 0, j = 0;
	while ((i < S->length) && (j < T->length))
	{
		if (S->ch[i] == T->ch[j])
		{
			i++;
			j++;
		}
//如果不匹配，i返回上一个匹配位置的下一个位置i-j+1
		else
		{
			i = i - j + 1;
			j = 1;
		}
	}
	if (j > T->length)
	{
		return (i - T->length);
	}
	else
	{
		return -1;
	}
}

//赋值
int StrAssign(SString* S, char* str)
{
	if ((strlen(str) + 1) > MAXSIZE - 1)
	{
		return 0;
	}
	int i = 0;
	for (i = 0; str[i] != '\0'; i++)
	{
		S->ch[i] = str[i];
	}
	S->length = strlen(str);
	return S->length;
}

//复制，将s2赋值给s1
void StringCopy(SString* S1, SString* S2)
{
	int i=0;
	while (i <= S2->length)
	{
		S1->ch[i] = S2->ch[i];
	}
	S1->length = S2->length;
}

//长度
int LengthString(SString* S)
{
	return S->length;
}

//打印
int PrintString(SString* S)
{
	int i = 0;
	if (S->length == 0)
	{
		return 0;
	}

	while (i <= S->length-1)
	{	
		printf("%c\n", S->ch[i]);
		i++;
	}
	return 0;
}

//比较
int StringCompare(SString* S1, SString* S2)
{
	int i = 0;
	 while(i <= S1->length && i <= S2->length) {
		if (S1->ch[i] > S2->ch[i])
		{
			return 1;
		}
		if(S1->ch[i] > S2->ch[i])
		{
			return -1;
		}
		if (S1->ch[i]==S2->ch[i])
		{
			i++;
			continue;
		}
		i++;
	}
	 if ((i == S1->length) && (i != S2->length)) {
		 return -1;
	 }
	 else if ((i != S1->length) && (i == S2->length)) {
		 return 1;
	 }
	 else
	 {
		 return 0;
	 }
}

//连接2个串
int ConcatString(SString* S, SString* S1, SString* S2) {
	int i, j;
//把1填进去
	for (i = 0; i < S1->length; i++)
	{
		S->ch[i] = S1->ch[i];
	}
	S->length = S1->length;
//把2填进去
	for (j = 0; j < S2->length; j++) {
		S->ch[S->length] = S2->ch[j];
		++S->length;
	}
	return 0;
}

//返回一个子串
int SubString(SString* Sub, SString* S, int pos, int len)
{
	if (pos < 1 || pos > S->length || len < 0 || len>S->length - pos + 1)
	{
		printf("输入有误!\n");
		return 0;
	}
	int j = 0;
	while (j < len) {
		Sub->ch[j] = S->ch[pos-1];
		++j;
		++pos;
	}
	Sub->length = len;
	return 0;
}

//插入
int StrInsert(SString* S1, int pos, SString* S2)
{
	if (pos<1 || pos>S1->length)
	{
		printf("输入有误！\n");
		return 0;
	}
	int i;
//移动1的元素
	for (i = (S1->length - 1); i >= pos - 1; i--)
	{
		S1->ch[i + S2->length] = S1->ch[i];
	}
	int j = 0;
	int k = pos - 1;
//插入2的元素
	for (j = 0; j < S2->length; j++) {
		S1->ch[k] = S2->ch[j];
		k++;
	}
	S1->length += S2->length;
	return 0;
}

//删除
int StrDelete(SString* S, int pos, int len)
{
	if (pos<1 || pos>(S->length - len + 1))
	{
		printf("输入有误！\n");
		return 0;
	}
	int i;
//将要删除的元素直接覆盖
	for (i = pos + len; i <= S->length; i++)
	{
		S->ch[i - len - 1] = S->ch[i - 1];
	}
	S->length -= len;
	return 0;
}

//谁能给我加个注释，我也看不懂呀，c了
void get_next(SString* T, int* next)
{
	int i, j;
	i = 1;
	j = 0;
	next[1] = 0;
	while (i < T->length) {
		if (j == 0 || T->ch[i - 1] == T->ch[j]) {
			++i;
			++j;
			next[i] = j;
		}
		else {
			j = next[j];
		}
	}
}


int Index_KMP(SString* S, SString* T, int pos)
{
	int i = pos;
	int j = 0;
	int next[255];
	get_next(T, next);
	while (i <= S->length && j <= T->length) {
		if (j == 0 || S->ch[i] == T->ch[j]) {
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}
	if (j > T->length) {
		return i - T->length;
	}
	else
	{
		return 0;
	}
}