数据结构-第四章-串

串的基本操作

串的顺序存储

#include <stdio.h>
#include <malloc.h>
#define Maxlength 255

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

typedef struct {
	char* ch;
	int length;
}HString;

//动态生成
void InitHString(HString &S) {
	S.ch = (char*)malloc(Maxlength * sizeof(char));
	S.length = 0;
}

串的链式存储

#include <stdio.h>

//存储密度低
//typedef struct {
//	char ch;
//	struct StringNode* next;
//}StringNode, * String;

//提高存储密度
typedef struct {
	char ch[4];
	struct StringNode* next;
}StringNode, *String;

基本操作的实现

#include <stdio.h>
#include <string.h>
#define Maxlen 255

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

//初始化
void InitString(SString& S) {
	strcpy_s(S.ch, "abcdefghijk");
	S.length = 11;
}

//求子串
void SubString(SString S, int pos, int len) {
	if (pos + len - 1 > S.length)
	{
		printf("越界了");
	}
	else
	{
		printf("从字符串%s的第%d位开始取%d位的结果为：", S.ch, pos, len);
		for (int i = pos - 1; i < pos - 1 + len; i++)
		{
			printf("%c", S.ch[i]);
		}
	}
}

bool SubString(SString& Sub, SString S, int pos, int len) {
	if (pos + len - 1 > S.length)
	{
		return false;
	}
	else
	{
		for (int i = pos - 1; i < pos + len - 1; i++)
		{
			Sub.ch[i - pos] = S.ch[i];
		}
	}
	return true;
}

//比较操作
int StrCompare(SString S, SString T) {
	for (int i = 0; i < S.length && i < T.length; i++)
	{
		if (S.ch[i] != T.ch[i])
		{
			return S.ch[i] - T.ch[i];
		}
	}
	return S.length - T.length;
}

//定位操作
int IndexString(SString S, SString T) {
	int i = 0, n = S.length, m = T.length;
	SString Sub;
	while (i <= n - m)
	{
		SubString(Sub, S, i, m);
		if (StrCompare(Sub, T) != 0)
		{
			i += 1;
		}
		else
		{
			return i;
		}
	}
	return 0;
}

int main() {
	SString S;
	InitString(S);
	SubString(S, 2, 4);
	return 0;
}

朴素模式匹配算法

#include <stdio.h>
#include <string.h>
#define Maxlen 255

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

//初始化字符串赋值
void InitString(SString &S, const char *element) {
	strcpy_s(S.ch, element);
	S.length = strlen(element);
}

int Index(SString S, SString T) {
	int i = 0;
	int j = 0;
	int k = 0;
	while (i<S.length && j<T.length)
	{
		if (S.ch[i] == T.ch[j])
		{
			i += 1;
			j += 1;
		}
		else
		{
			k += 1;
			i = k;
			j = 0;
		}
	}
	if (j = T.length)
	{
		return k + 1;
	}
	else
	{
		return 0;
	}
}

int main() {
	SString S;
	InitString(S, "fioqnionqvnnakmdl1kasmopgqowmc");
	SString T;
	InitString(T, "qowmc");
	printf("从%d位置开始相同", Index(S, T));
	return 0;
}

KMP算法

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define Maxsize 255

typedef struct {
	char ch[Maxsize];
	int length;
}String;

void InitString(String& S, const char* c) {
	strcpy_s(S.ch, " ");
	strcat_s(S.ch, c);
	S.length = strlen(c);
}

void PrintString(String S) {
	printf("字符串为%s 长度为%d\n", S.ch, S.length);
}

int Get_Length(String S) {
	return S.length;
}

void Get_Next(String S, int *next) {
	int i = 1, j = 0;
	next[0] = -1;
	next[1] = 0;
	while (i < S.length)
	{
		if (j==0 || S.ch[i] == S.ch[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

int KMP(String S, String T, int *next) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (j == 0 || S.ch[i] == T.ch[j])
		{
			i += 1;
			j += 1;
		}
		else {
			j = next[j];
		}
	}
	if (j > T.length)
	{
		return i - T.length;
	}
	else
	{
		return 0;
	}
}

int main() {
	String S;
	InitString(S, "ababaa");
	int* next = (int*)malloc(S.length * sizeof(int));
	Get_Next(S, next);
	String string;
	InitString(string, "cccccababaaccccc");
	printf("%d", KMP(string, S, next));
	return 0;
}

KMP算法的优化

void Get_Nextval(String S, int *next) {
	int i = 0, j = 0;
	next[0] = -1;
	next[1] = 0;
	while (i < S.length)
	{
		if (j == 0 || S.ch[i] == S.ch[j])
		{
			++i;
			++j;
			if (S.ch[i] != S.ch[j])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
			}
		}
		else
		{
			j = next[j];
		}
	}
}

int main() {
	String S;
	InitString(S, "aaaab");
	int* next = (int*)malloc(S.length * sizeof(int));
	Get_Next(S, next);
	for (int i = 1; i < S.length + 1; i++)
	{
		printf("%d ", next[i]);
	}
	printf("\n");
	Get_Nextval(S, next);
	for (int i = 1; i < S.length + 1; i++)
	{
		printf("%d ", next[i]);
	}
	return 0;
}