数据结构（C实现）------- 串

首页 > 代码库 > 数据结构（C实现）------- 串

数据结构（C实现）------- 串

2024-07-23 21:38:36 222人阅读

字符串（简称串）,可以将其看作是种特殊的线性表，其特殊性在于线性表的数据元素的类型总是字符性，字符串的数据对象红豆为字符集。

　串是由０个或多个字符组成的有限序列。一般记作：s = "s1 s2 s3 .... sn",，其中，s是串名，用双引号括起来的字符序列称为串的值，si（1<=i <= n）称为串的元素，可以是字母，数字或其他字符，是构成串的基本单位，字符的个数n称为串的长度.

串中的几个术语：

　　　　１. 空串：　由０个字符组成的串称为空串，空串不包含任何字符，其长度为０。

　　　　 2. 子串：　串中任意个连续的字符组成的子序列称为该串的子串，空串是任何串的子串。

　　　　 3. 主串：　包含子串的串相应的称为主串。

　　　　 4. 子串在主串的位置：通常称字符在序列中的序号为该字符在串的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。　　　　　　

　　　　 5. 两串相等：当且仅当两个串的长度相等，并且各个对应位置的字符都相等时才相等。

串的表示：

　　1. 串的顺序存储表示：

　　　串的顺序存储结构简称为顺序串，顺序串中的字符序列被顺序地存放在一组连续的存储单元中，主要有三种实现顺序串的方式，分别如下：

　　　(1) 定长字符数组

　　　在串的顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定大小的存储区，描述如下：

//定长字符数组描述
#define MAXSIZE 100
typedef char SString[MAXSIZE];

　　　(2) 带串长的字符数组

//带串长的字符数组
#define MAXSIZE 100
typedef struct{
	char ch[MAXSIZE];
	int length;
}SqString;

　　　(3) 串的堆分配(即动态数组)存储描述　

//串的堆分配存储描述
typedef struct{
	char *ch; //若是非空串，则按串长分配存储区，否则，ch为NULL
	int length; //串长度
}HString;

　　２.串的链式存储表示：

　　　　和线性表的链式存储结构相类似，也可以采用链表方法存储串值，有以下两个方法：

　　　　(1)串的链式结构类型描述：

//串的链式存储结构描述
typedef struct node{
	char str;
	struct node *next;
}CNode,*LinkString;

　　　　(2)串的块链存储类型描述：

//串的块链结构类型描述
#define NODESIZE 3
typedef struct node{
	char ch[NODESIZE];
	struct node *next;
}SNode,*LinkStr;
LinkStr head;

　　3.串的索引存储表示：

　　　　串也可以用索引的方式来表示，有以下两种方法：

　　　　(1)串的带长度的索引表：

//带长度的索引表
#define MAXSIZE 100
typedef struct{
	char name[MAXSIZE];
	int length;
	char *startadr;
}LSNode;

　　　 (2) 串的带末指针的索引表：

//串的带末指针的索引表
#define MAXSIZE 100
typedef struct{
	char name[MAXSIZE];
	int length;
	char *startadr;
	char *endadr;
}ENode;

　　以上介绍了三种存储结构来表示串，每一种存储结构又可以用几种不同的方式来描述串，那么，串的实现方法相应的也有多种，但不管有多少种，串的基本操作原理不变，变的只是处理的方式，所以也没有必要将所有方式都学会，只要会一种即可，这里就实现其中最常用动态数组来描述串，并以此种方式来实现口串的各种操作。

基本操作：

　　　这里所有的基本操作都是建立在上述的用动态数组，即堆结构来描述串的前提下的，直接给出代码，里面有注释。

//串的堆分配存储描述
typedef struct{
	char *ch; //若是非空串，则按串长分配存储区，否则，ch为NULL
	int length; //串长度
}HString;


//初始化一个空的顺序串
void Str_Init(HString *S){
	S->ch = NULL;
	S->length = 0;
}



//清空顺序串
void Str_Clear(HString *S){
	if(S->ch){
		free(S->ch);
		Str_Init(S);
	}
}


//判断顺序串是否为空
int Str_IsEmpty(HString *S){
	return S->length == 0;
}


//求取串的长度
int Str_GetLength(HString *S){
	return S->length;
}

//顺序串的赋值
void Str_Assign(HString *S,char *chars){
	int i = 0,j;
	char *c = chars;
	//先清空顺序串S
    Str_Clear(S);
	//求得赋值串的长度
	while(*c){
		i++;
		c++;
	}
	//如果赋值串的长度大于0，则进行赋值
	if(i > 0){
		S->ch = (char*)malloc(3*sizeof(char));
		for(j = 0;j < i;j++){
			S->ch[j] = chars[j];
		}
		S->length = i;
	}
}
//顺序串的复制,将Ｔ复制到Ｓ
void Str_Copy(HString *S,HString *T){
	int i;
	//先清空顺序串S
    Str_Clear(S);
    S->length = T->length;
   
    if(S->length){
		S->ch = (char *)malloc(sizeof(char)*S->length);
		for(i = 0;i < S->length;i++)
			S->ch[i] = T->ch[i];
	}
}




//顺序串的连接,将T连接到S后 
void Str_Concat(HString *S,HString *T){
	//临时存放S串 
	HString temp;
	int i,j;
	Str_Init(&temp);
	Str_Assign(&temp,S->ch);
	
	//清空S
	Str_Clear(S);
	//重新为S分配空间
	S->length = temp.length + T->length;
	S->ch = (char*)malloc(sizeof(char) * S->length);
	//分别将temp和T依次赋值给S
	for(i = 0;i < temp.length;i++)
		S->ch[i] = temp.ch[i];
	for(j = 0; j < T->length;j++)
		S->ch[i++] = T->ch[j];

	//将temp释放掉
	free(temp.ch);
}

//顺序串的比较,如果Ｓ>T,返回大于０的值，小于，则返回小于０的值
int Str_Compare(HString *S,HString *T){
	int i;
	for(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;
}


//求子串并用Ｓub返回
void Str_GetSub(HString *S,int pos,int len,HString *Sub){
	int i;
	//判断位置和长度的合法性
	if(pos < 1 || pos > S->length || len < 0 || len > S->length - pos + 1){
		printf("子串的位置或长度不合法！\n");
		exit(-1);
	}
	else{
		Str_Clear(Sub);
		if(len){
			Sub->ch = (char *)malloc(len * sizeof(char));
			for(i = 0;i < len;i++)
				Sub->ch[i] = S->ch[pos + i -1];
			Sub->length = len;
		}
	}
}

//在顺序串中找出给定子串给定位置后出现的第一个的位置
int Str_GetSubIndex(HString *S,HString *Sub,int pos){
	int i,j;
	//先判断位置的合法性
	if(pos < 1 || pos > S->length){
		printf("位置不合法!\n");
		exit(-1);
	}
	if(Str_IsEmpty(S)){
		printf("顺序串为空！\n");
		return -1;
	}
	if(Str_IsEmpty(Sub)){
		printf("给定子串为空，空串为任何串的子串！\n");
		return 0;
	}
	
	for(i = pos - 1; i < S->length - Sub->length + 1;i++){
		for(j = 0; j < Sub->length;j++)
			if(S->ch[i+j] != Sub->ch[j])
				break;
		// 如果找到子串，则j= sub->length
		if(j == Sub->length)
			return i + 1;			
	}
	//如果找不对，则返回-1;
	return -1;	
}




//顺序串中插入子串
void Str_Insert(HString *S,int pos,HString *T){
	int i;
	HString temp;
	if(pos < 1 || pos > S->length){
		printf("位置不合法!\n");
		exit(-1);
	}
	if(Str_IsEmpty(T)){
		printf("子串为空!\n");
		exit(0);
	}
	Str_Init(&temp);
	temp.length = S->length + T->length;
	printf("%d\n",temp.length);
	temp.ch = (char *)malloc(sizeof(char)*temp.length);
	for(i  = 0 ;i < pos ;i++)
		temp.ch[i] = S->ch[i];
	for(; i < pos + T->length;i++)
		temp.ch[i] = T->ch[i - pos];
	for(;i < temp.length;i++)
		temp.ch[i] = S->ch[i - T->length];
	//将串Ｓ　清空，并将串temp赋值给S
	Str_Clear(S);
	S->ch = temp.ch;
	S->length = temp.length;
	
}


//在顺序串删除子串
void Str_DeleteSub(HString *S,int pos,int len){
	int i;
	HString temp;
	//判断位置和长度的合法性
	if(pos < 1 || pos > S->length || len < 0 || len > S->length - pos + 1){
		printf("子串的位置或长度不合法！\n");
		exit(-1);
	}
	if(Str_IsEmpty(S)){
		printf("顺序串为空!\n");
		exit(0);
	}
	Str_Init(&temp);
	temp.length = S->length - len;
	temp.ch = (char *)malloc(sizeof(char)*temp.length);
	for(i = 0 ;i < pos - 1; i++)
		temp.ch[i] = S->ch[i];
	for(;i < temp.length;i++)
		temp.ch[i] = S->ch[i+len];
	//将串Ｓ清空，并将串temp赋值给S
	Str_Clear(S);
	S->ch = temp.ch;
	S->length = temp.length;
	
}
//打印顺序串
void Str_Print(HString *S){
	int i = 0;
	if(Str_IsEmpty(S)){
		printf("顺序串为空!\n");
		exit(0);
	}
	else
		printf("%s\n",S->ch);		
}

数据结构（C实现）------- 串

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 数据结构（C实现）------- 串