串（KMP，BF算法实现），数组（矩阵压缩），广义表

串、数组、广义表

串

基本概念

• 串是由零个或者多个字符组成，一般记作s=‘a1a2a3…an’，其中s是串的串名，ai是串的值，n是串的长度，零个字符叫做空串。
• 字串：串中任意个连续的字符组成的子序列成为字串
• 主串：包含字串的字符序列
• 空格串不等同于空串

串的基本操作

定义

#define MAXSIZE 255
#define CHUNKSIZE 50
#define INITSIZE 200
#define OK	1
#define ERROR 0
#define OVERFLOW -2

//串的三种表示方式
//定长顺序存储
typedef struct SString {
	char ch[MAXSIZE + 1];
	int length;
}SString;

//堆分配存储表示
typedef struct HString {
	char* ch;
	int length;
}HString;

//块链的存储表示
typedef struct Chunk {
	char ch[CHUNKSIZE];
	struct Chunk* next;
}Chunk;			//块链的结点

//块链的定义
typedef struct LString {
	Chunk* head, * tail;
	int curlen;			//串的当前长度
};


//串基本操作的定义
int InitString(HString& S);					//初始化一个空串，INITSIZE大小
int AssignString(HString& S, char str[);		//初始化一个串，值为串常量
int GetStringLength(HString S);				//得到串的长度
int InsertString(HString& S, int pos, HString T);		//将T串在pos位置插入串
int CompareString(HString S, HString T);				//比较串的大小
int GetSubString(HString& Sub, HString S, int pos, int len);			//返回串S的第pos个字符起长度

串基本操作的实现

#include <stdio.h>
#include <stdlib.h>
#include "Structure.h"


int main() {

	//测试
	HString S,T,Sub;
	char str[] = "abcdefg";
	int flag = AssignString(S,str);
	printf("%d", flag);
	char str2[] = "ooo";
	flag = AssignString(T, str2);
	printf("%d", flag);
	flag = InsertString(S, 2, T);
	printf("%d", flag);
	flag = GetSubString(Sub, S, 2, 3);
	printf("%d", flag);
	return 0;
}

int AssignString(HString& S, char *str) {
	//if (S.ch)
	//	free(S.ch);					//如果存在，则先释放

	int i;
	char *c = str;
	for (i = 0; *c; ++i, ++c);
	if (!i) {
		S.ch = NULL;
		S.length = 0;
		return OK;
	}
	S.ch = (char*)malloc(sizeof(char) * i);
	if (!S.ch)
		exit(OVERFLOW);
	for (int j = 0; j < i; j++)
		S.ch[j] = str[j];

	S.length = i;
	return OK;
}

int InitString(HString& S) {
	S.ch = (char*)malloc(sizeof(char)*INITSIZE);
	if (!S.ch)
		exit(OVERFLOW);
	S.length = 0;
	return OK;
}


int GetStringLength(HString S) {
	return S.length;
}

int InsertString(HString& S, int pos, HString T) {
	if (pos<0 || pos>S.length)
		return ERROR;
	if (T.length) {
		S.ch = (char*)realloc(S.ch, sizeof(char) * (S.length + T.length));
		if (!S.ch)
			exit(OVERFLOW);
		for (int i = S.length - 1; i >= pos; i--) {
			S.ch[i + T.length] = S.ch[i];				//为T字符串腾出位置
		}

		for (int i = pos,j=0; j < T.length; i++,j++)
		{
			S.ch[i] = T.ch[j];
		}
		S.length += T.length;			//长度的调整
		return OK;
	}
}

int	CompareString(HString S, HString T) {
	for (int i = 0; i < S.length; i++)
	{
		if (S.ch[i] != T.ch[i])
			return S.ch[i] - T.ch[i];
	}
	return S.length - T.length;
}

int GetSubString(HString& Sub, HString S, int pos, int len) {
	//pos 从第零个位置开始取
	if (pos < 0 || pos >= S.length || len < 0 || len > S.length - pos)
		return ERROR;	
	if(!len)
	{
		Sub.ch = NULL;
		Sub.length = 0;
	}
	else {
		Sub.ch = (char*)malloc(sizeof(char) * len);
		for (int i = pos,j=0; j < len; i++,j++) {
			Sub.ch[j] = S.ch[i];
		}
		Sub.length = len;
	}
	return OK;
}

BF算法的实现（时间复杂度O(m*n)）

定义

#define MAXSIZE 255
typedef struct SString {
	char ch[MAXSIZE + 1];			//存放字符串的数组
	int length;						//存放字符串的长度
}SString;



int BF(SString S, SString T);

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "structrue.h"

int main() {

	SString S, T;
	//S.ch[MAXSIZE + 1];
	strncpy_s(S.ch," DABCDABD",9);				//前面留一个空格是因为不用ch[0]
	S.length = 8;
	T.length = 3;
	strncpy_s(T.ch, " CDA", 4);
	int index = BF(S, T);
	printf("%d", index);

	return 0;
}



int BF(SString S, SString T) {
	int i = 1;
	int j = 1;
	while (i <= S.length && j <= T.length) {

		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		else {
			i = i - j + 2;
			j = 1;
		}
		
	}
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

BMF算法的结构定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Structure.h"


int main() {

	SString S,T;
	strncpy_s(S.ch, " ababaabcacasdasd", 18);
	strncpy_s(T.ch, " abaabcac", 9);
	S.length = 17;
	T.length = 8;
	getNext(T, next);
	int index = indexKMP(S, T, 1);
	printf("index:%d", index);


}



void getNext(SString S, int next[]) {
	int i = 1, j = 0;
	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 indexKMP(SString S, SString T, int pos) {
	int i = pos, j = 1;
	while (i <= S.length && j <= T.length) {
		if (j == 1 || S.ch[i] == T.ch[j])
		{
			j++;
			i++;

		}
		else {
			j = next[i];
		}
		
	}
	if (j > T.length)
		return i - T.length;
	else
		return 0;
}

数组

基本概念

由n个相同元素组成的有序集合，数组可以看做是线性表的推广，二维数组可以看做是线性表的线性表

存储地址公式：LOC（ai）=LOC(a1)+(i-1)*L

数组的存储方式：

• 以行序为先
• 以列序为先

特殊矩阵的压缩

对称矩阵

​ 压缩方式：n阶方阵A[n] [n]存储在一个长度为[n*(n-1)/2]的一维数组中

​ 他的存储位置：aij

1. 左下：i*(i+1)/2+j
2. 右上: j*(j+1)/2+i

三角矩阵的压缩

​ 压缩方式：n阶方阵A[n] [n]存储在一个长度为[n*(n-1)/2+1]的一维数组中，多了一个常数c

对角矩阵的压缩

​ 压缩方式：A[n] [n]的方阵存储在[kn-2]的数组中

稀疏矩阵的压缩

用三元组表示：i，j,value

数据结构的定义十字链表

typedef struct OLNode{
    int row,col;
    ELemType value;
    struct OLNode *right,*down;
}OLNode;

广义表

表头，表尾：除表头外所有元素的集合，注意加（）