【数据结构】串（定长顺序串、堆串、块链串）的存储结构及基本运算（C语言）

【数据结构】串（定长顺序串、堆串、块链串）的存储结构及基本运算（C语言）

目录

1. 串的基本概念2. 定长顺序串

2.1 代码+注释2.2 运行结果 3. 堆串

3.1 代码+注释3.2 运行结果 4. 块链串

1. 串的基本概念

字符串（String）是由零个或多个字符组成的有限序列。记为 S = ‘a1a2…an’（n>0）
其中，S是串的名字，用单引号括起来的字符序列是串的值，每个 ai（1<=i<=n）可以是字母、数字或其它字符。n是串中字符的个数，称为串的长度，n=0时的串称为空串。

子串：串中任意个连续的字符组成的子序列称为该串的子串。
主串：包含子串的串称为主串。
子串在主串中的位置：通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
串相等：当且仅当两个串的值相等时，称这两个串是相等的，即只有当两个串的长度相等，并且每个对应位置的字符都相等时才相等。

串是一种特定的线性表，串的逻辑结构和线性表极为相似，其特定性仅在于串的数据对象限定为字符集。常用的实现方法有定长顺序串、堆串和块链串。

2. 定长顺序串

定长顺序串是将串设计成一种静态结构类型，用一组地址连续的存储单元来存储串的字符序列。

2.1 代码+注释

# include
# define MAXLEN 40
# define TRUE 1
# define FALSE 0



typedef struct {
	char ch[MAXLEN];
	int len;			//字符串长度
}SString;


void StrInit(SString* S) {
	S->len = 0;
}


void StrCreate(SString* S) {
	int n, i;
	printf("字符串长度为：");
	scanf("%d", &n);
	printf("请输入字符串：");
	for (i = 0; i < n; i++) {
		scanf(" %c", &(S->ch[i]));
	}
	S->len = n;
}


int StrInsert(SString* S, int pos, SString *t) {
//在串S中下标为pos的字符之前插入串t
	int i;
	if (pos < 0 || pos > S->len)				//插入位置不合法
		return FALSE;
	if (S->len + t->len <= MAXLEN) {			//插入后串长<=MAXLEN
		for (i = S->len + t->len - 1; i >= t->len + pos; i--)
			S->ch[i] = S->ch[i - t->len];		//位置pos后的字符串后移
		for (i = 0; i < t->len; i++)
			S->ch[i + pos] = t->ch[i];			//将t串插入
		S->len = S->len + t->len;
	}
	else if (pos + t->len <= MAXLEN) {			//插入后串长大于MAXLEN，但串t的字符序列可以全部插入
		for (i = MAXLEN - 1; i > t->len + pos - 1; i--)
			S->ch[i] = S->ch[i - t->len];
		for (i = 0; i < t->len; i++)
			S->ch[i + pos] = t->ch[i];
		S->len = MAXLEN;
	}
	else {										//插入后串长大于MAXLEN，并且串t的部分字符也要舍弃
		for (i = 0; i < MAXLEN - pos; i++)
			S->ch[i + pos] = t->ch[i];
		S->len = MAXLEN;
	}
	return TRUE;
}


int StrDelete(SString* S, int pos, int n) {
//在串S中删除从下标pos起n个字符
	int i;
	if (pos<0 || pos>(S->len - n))				//删除位置不合法
		return FALSE;
	for (i = pos + n; i < S->len; i++)
		S->ch[i - n] = S->ch[i];				//从pos+n开始至尾串依次向前移动，实现删除n个字符
	S->len = S->len - n;
	return TRUE;
}


int StrCompare(SString* S, SString* t) {
//若串S和t相等返回0；若S>t返回正数；Slen && i < t->len; i++) {
		if (S->ch[i] != t->ch[i])
			return (S->ch[i] - t->ch[i]);
	}
	return (S->len - t->len);
}


void Display(SString* S) {
	int i;
	for (i = 0; i < S->len; i++)
		printf("%c", S->ch[i]);
	printf("n");
}

int main() {
	SString S, t;
	int pos, n;
	printf("--------串的创建--------n");	//创建
	StrInit(&S);
	StrCreate(&S);
	printf("创建的字符串：");
	Display(&S);

	printf("n--------串的插入--------n");	//插入
	StrInit(&t);
	StrCreate(&t);
	printf("要插入位置为：");
	scanf("%d", &pos);
	StrInsert(&S, pos, &t);
	printf("插入后字符串：");
	Display(&S);

	printf("n--------串的删除--------n");	//删除
	printf("删除的位置及字符个数：");
	scanf("%d%d", &pos, &n);
	StrDelete(&S, pos - 1, n);
	printf("删除后字符串：");
	Display(&S);

	printf("n--------串的比较--------n");	//比较
	if (StrCompare(&S, &t) == 0)
		printf("串S = 串tn");
	else if(StrCompare(&S, &t) > 0)
		printf("串S > 串tn");
	else
		printf("串S < 串tn");
	return 0;
}

2.2 运行结果

3. 堆串

字符串包括串名和串值两部分，而串值采用堆串存储方法存储，串名用符号表存储。
堆串存储方法：以一组地址连续的存储单元顺序存放串中的字符，但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间，每当建立一个新串时，系统就从这个空间中分配一个大小和字符串长度相同的空间用于存储新串的串值。
串名符号表：所有串名的存储映像构成一个符号表，借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映像。

3.1 代码+注释

# include
# include
# define TRUE 1
# define FALSE 0



typedef struct {
	char* ch;									//ch域指示串的起始地址
	int len;
}HString;


void StrInit(HString* s) {
	s->ch = NULL;
	s->len = 0;
}


int StrAssign(HString* s, char* tval) {
//将字符串常量tval的值赋给堆串s
	int len = 0, i = 0;
	if (s->ch != NULL)
		free(s->ch);
	while (tval[i] != '')
		i++;
	len = i;
	if (len) {
		s->ch = (char*)malloc(len);				//申请空间
		if (s->ch == NULL)
			return FALSE;
		for (i = 0; i < len; i++)				//将字符串常量tval的值赋给堆串s
			s->ch[i] = tval[i];
	}
	else
		s->ch = NULL;
	s->len = len;
	return TRUE;
}


int StrInsert(HString* s, int pos, HString* t) {
//在串s中下标为pos的字符之前插入串t
	int i;
	char* temp;
	if (pos < 0 || pos > s->len || s->len == 0)	//插入位置不合法
		return FALSE;
	temp = (char*)malloc(s->len + t->len);
	if (temp == NULL)
		return FALSE;
	for (i = 0; i < pos; i++)
		temp[i] = s->ch[i];						//串s前半段插入temp
	for (i = 0; i < t->len; i++)
		temp[i + pos] = t->ch[i];				//串t插入temp
	for (i = pos; i < s->len; i++)
		temp[i + t->len] = s->ch[i];			//串s后半段插入temp
	s->len += t->len;
	free(s->ch);
	s->ch = temp;								//temp赋给串s
	return TRUE;
}


int StrDelete(HString* s, int pos, int n) {
	int i;
	char* temp;
	if (pos < 0 || pos>s->len - n)				//删除位置不合法
		return FALSE;
	temp = (char*)malloc(s->len - n);
	for (i = 0; i < pos; i++)
		temp[i] = s->ch[i];
	for (i = pos + n; i < s->len; i++)
		temp[i - n] = s->ch[i];
	s->len -= n;
	free(s->ch);
	s->ch = temp;
	return TRUE;
}


void Display(HString* s) {
	int i;
	if (s->len == 0)
		printf("空串！n");
	else {
		for (i = 0; i < s->len; i++) {
			printf("%c", s->ch[i]);
		}
		printf("n");
	}
}

int main() {
	int pos, n;
	HString s, t;
	char tval_s[6] = { 'a','b','c','d','e' };
	char tval_t[4] = { 'q','w','r' };
	printf("------堆串赋值------n");			//赋值
	StrInit(&s);
	StrAssign(&s, tval_s);						//串s赋值
	printf("串s为：");
	Display(&s);
	StrInit(&t);
	StrAssign(&t, tval_t);						//串t赋值
	printf("串t为：");
	Display(&t);

	printf("n------堆串插入------n");			//插入
	printf("插入位置：");
	scanf("%d", &pos);
	StrInsert(&s, pos - 1, &t);
	printf("插入后为：");
	Display(&s);

	printf("n------堆串删除------n");			//删除
	printf("删除位置和个数：");
	scanf("%d%d", &pos, &n);
	StrDelete(&s, pos - 1, n);
	printf("删除后为：");
	Display(&s);
	return 0;
}

3.2 运行结果

4. 块链串

一个链表存放一个串值，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。
块链串的存储结构

# define BLOCK_SIZE 4	//每结点存放字符个数为4

typedef struct Block {
	char ch[BLOCK_SIZE];
	struct Block* next;
}Block;

typedef struct {
	Block* head;
	Block* tail;
	int len;
}BLString;

链表中的结点分成两个域 data 和 link，其中结点大小是指 data 域中存放的字符个数，链域大小是指 link 域中占用字符的个数。
存储密度 = 串值占用的存储位 / 实际为串分配的存储位。串的存储密度越小，运算处理就越方便，但存储空间占用量越大。

参考：耿国华《数据结构——用C语言描述（第二版）》

更多数据结构内容关注我的《数据结构》专栏：https://blog.csdn.net/weixin_51450101/category_11514538.html?spm=1001.2014.3001.5482