C语言串的链式存储

阳光穿透心脏的1/2处 2022-12-17 05:55 138阅读 0赞

**串的链式存储：**  
顺序串的插入和删除操作不方便，需要移动大量的字符。因此，可采用单链表方式存储串。由于串结构的特殊性一结构中的每个数据元素是 一个字符，则在用链表存储申值时，存在个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。例如，图中(a)所示为结点大小为4 (即每个结点存放4个字符)的链表，图中(b)所示为结点大小为1的链表。当结点大小大于1时，由于串长不一定是结点大小的整倍数， 则链表中的最后一个结点不一定全被串值占满，此时通常补上“\#”或其他的非串值字符(通常“\#”不属于串的字符集，是一个特殊的符号)。  
![串值得链表存储方式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
和单链表的操作只是多了个这个 “\#define MaxSize 4”，其中的4表示图中的（a）表图。可以自行增加。

总的来说，太 **难** **难** **难** 了，可能是对我来说难。  
而且还没做完整，链式串中的找子串函数写不出来\*\*(T\_T)\*\*

我写的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MaxSize 4 //链表中一个结点的最大容纳值 
    
    typedef struct Chunk
    { 
    	char ch[MaxSize];//结点数据域 
    	struct Chunk* next;//指针域 
    }Chunk;
    typedef struct
    { 
    	Chunk* head;
    	int length;//串长度 
    }SString;
    
    void InitString(SString &S)//串的初始化 
    { 
    	S.head = (Chunk*)malloc(sizeof(Chunk));//使S.head申请一个结点空间 
    	if(S.head == NULL)//判断是否申请到 
    		exit(1);
    	S.head->next = NULL;//头结点表示法（链表） 
    	S.length = 0;//长度至为0 
    }
    
    int StrAssign(SString &S,char chars[])//串的赋值，使数组chars[]中的数据元素填入串S中
    { 
    	int i=0,j=0;
    	Chunk* p = (Chunk*)malloc(sizeof(Chunk));//创建一个野结点，并为其申请一个结点空间 
    	S.head->next = p;//链表尾插法，S.head为链表的头结点 
    	p->next = NULL;
    	while(chars[j])//利用循环，使对串中的每一个值进行一对一赋值，当chars[i]等于空时，循环结束
    	{ 
    		if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 
    		{ 
    			i = i%MaxSize;
    			Chunk* s = (Chunk*)malloc(sizeof(Chunk));//重新申请一个结点空间 
    			p->next = s;//类似于链表尾插法 
    			s->next = NULL;
    			p = s;
    		}
    		p->ch[i] = chars[j];//赋值，i的值是在0~MaxSize之间，而j的值是总的循环次数 
    		i++;
    		j++;
    	}
    	S.length = j;//串长赋值 
    	if(i != MaxSize)//如果链表的最后一个结点没有存满，使其剩余部分填入‘#’ 
    		for(;i<MaxSize;i++)
    			p->ch[i] = '#';
    	return 0;
    }
    
    int IsEmpty(SString S)//判断串是否为空，如果为空返回1，否则返回0 
    { 
    	if(S.length == 0)
    		return 1;
    	return 0;
    }
    
    void OutputStr(SString S)//打印串 
    { 
    	if(IsEmpty(S))//判断是否为空串 
    	{ 
    		printf("ERROR!\n");
    		exit(1);
    	}
    	int i=0;
    	Chunk* p = S.head->next;//创建一个指针，并指向头结点的下一个结点 
    	while(1)//进入死循环
    	{ 
    		if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 
    		{ 
    			i = i%MaxSize;
    			p = p->next;//这里类似于链表的遍历 
    		}
    		if(p->next == NULL)//循环终止条件，首先先判断是否为最后一个结点 
    		{ 
    			for(;i<MaxSize;i++)//利用循环打印出最后一个结点的数据 
    			{ 
    				if(p->ch[i] == '#')//如果数据中出现“#”，跳出循环 
    					break;
    				printf("%c ",p->ch[i]);
    			}
    			break;//跳出死循环 
    		}
    		printf("%c ",p->ch[i]);//打印最后一个结点之前的所有结点数据 
    		i++;
    	}
    	printf("\n");
    }
    
    int StrCopy(SString &T,SString S)//串S的copy(复制)，使串S中的数据复制到空串T中
    { 
    	if(IsEmpty(T) == 0)//判断串T是否为空 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	int i=0;
    	S.head = S.head->next;//链的遍历，由于S链不用返回，故直接是头结点往后移进行遍历 
    	Chunk *p = (Chunk*)malloc(sizeof(Chunk));
    	T.head->next = p;//创建个野结点，链T的头结点指向该结点，类似于链表的尾插法 
    	p->next = NULL;
    	while(1)//进入死循环 
    	{ 
    		if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 
    		{ 
    			i = i%MaxSize;
    			Chunk *s = (Chunk*)malloc(sizeof(Chunk));
    			p->next = s;//这里创建个野结点s，类似于对链表T的尾插法 
    			s->next = NULL;
    			p = s;
    			S.head = S.head->next;//这里链S类似于链表的遍历 
    		}
    		if(S.head->next == NULL)//判断是否到达链表S的尾端 
    		{ 
    			for(;i<MaxSize;i++)//到达链S尾结点，使尾结点数据进行赋值，并破坏死循环 
    				p->ch[i] = S.head->ch[i];
    			break;
    		}
    		p->ch[i] = S.head->ch[i];//使链S结点上的数据赋值到链T上 
    		i++;
    	}
    	T.length = S.length;//链长 
    	return 0;
    }
    
    int StrCompare(SString S,SString T)//串的比较， 
    { 
    	S.head = S.head->next;//均利用头结点进行遍历 
    	T.head = T.head->next;
    	int i=0,j=1;
    	while(j<=S.length && j<=T.length)//利用循环找出 从第一个元素开始，出现不相同元素的位置 ，循环终止条件是出现一个串比较到最后，
    	{ 
    		if(i == MaxSize)//判断i的值是否超出或等于最大值，如果等于，对结点最大值求余 
    		{ 
    			i = i%MaxSize;
    			S.head = S.head->next;
    			T.head = T.head->next;
    		}
    		if(S.head->ch[i] != T.head->ch[i])
    			return S.head->ch[i] - T.head->ch[i];//出现不同位置，直接返回其相减的值，其值时ASCII码对应数相减 
    		i++;
    		j++;
    	}
    	return S.length - T.length;//如果没出现，直接输出串长相减
    }
    
    int SubString(SString &T,SString S,int i,int len)//求子串，将串S中的从第i个位置长度为len的子串复制到空串T中 
    { 
    	if(IsEmpty(T) == 0)//判断串T是否为空，如果不为空结束此函数 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	if(i<1||i>S.length)//判断位置是否错误 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	if(i+len > S.length+1)//判断所求子串是否在串S的范围内 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	S.head = S.head->next;
    	Chunk* p = (Chunk*)malloc(sizeof(Chunk));
    	T.head->next = p;
    	p->next = NULL;
    	int j=0,k=0,a;
    	a = i;
    	for(;j<i-1;j++)//利用循环找到串S的第i个位置 
    	{ 
    		if(k == MaxSize)//判断k的值是否超出或等于最大值，如果等于，对结点最大值求余
    		{ 
    			k = k%MaxSize;
    			S.head = S.head->next;//类似于链表的遍历 
    		}
    		k++;
    	}
    	for(j=0;i<a+len;i++)//将第i个位置长度为len的子串赋值给空串T 
    	{ 
    		if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
    			S.head = S.head->next;
    		}
    		if(j == MaxSize)
    		{ 
    			j = j%MaxSize;
    			Chunk *s = (Chunk*)malloc(sizeof(Chunk));
    			p->next = s;
    			s->next = NULL;
    			p = p->next;
    		}
    		p->ch[j] = S.head->ch[k];
    		k++;
    		j++;
    	}
    	T.length = len;//串T长度为len 
    	if(j != MaxSize)//判断串T的尾结点是否存满，如果没存满，用‘#’进行填充 
    		for(;j<MaxSize;j++)
    			p->ch[j] = '#';
    	return 0;
    }
    
    SString StrInset(SString S,SString T,int i)//串的插入，使串T插入到串S的第i个位置，返回串S和串T组合的新串 
    { 
    	if(IsEmpty(T))//判断串T是否为空，如果为空结束此函数，直接返回串S 
    	{ 
    		printf("ERROR!\n");
    		exit(1);
    	}
    	if(i<1||i>S.length+1)//判断插入位置i是否合理 
    	{ 
    		printf("ERROR!\n");
    		exit(1);
    	}
        S.head = S.head->next;
        SString L;
        InitString(L);//重新申请一个串，并初始化 
        L.length = S.length+T.length;//合并后的串长为两串长相加 
        Chunk* p = (Chunk*)malloc(sizeof(Chunk));//创建一个野结点，进行串L数据的插入，类似于链表尾插法 
        L.head->next = p;
        p->next = NULL;
        int j=0,k=0;
        for( ;j<i-1;j++)//首先使串S的第i个位置之前的数据都插入到新串L中 
        { 
            if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
    			S.head = S.head->next;
                Chunk *s = (Chunk*)malloc(sizeof(Chunk));
    			p->next = s;
    			s->next = NULL;
    			p = p->next;
    		}
            p->ch[k] = S.head->ch[k];
            k++;
        }
        int a=k,b=i;i=0;
        T.head = T.head->next;
        for(j=0;j<T.length;j++) //其次使串T整个插入到新串L中 
        { 
            if(i == MaxSize)
    		{ 
    			i = i%MaxSize;
                T.head = T.head->next;
            }
            if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
                Chunk *s = (Chunk*)malloc(sizeof(Chunk));
    			p->next = s;
    			s->next = NULL;
    			p = p->next;
    		}
            p->ch[k] = T.head->ch[i];
            k++;
            i++;
        }
        for(j=T.length+b-1;j<L.length;j++)//最后使串S剩余的部分插入新串L中 
        { 
            if(a == MaxSize)
    		{ 
    			a = a%MaxSize;
                S.head = S.head->next;
            }
            if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
                Chunk *s = (Chunk*)malloc(sizeof(Chunk));
    			p->next = s;
    			s->next = NULL;
    			p = p->next;
    		}
            p->ch[k] = S.head->ch[a];
            a++;
            k++;
        }
        if(k != MaxSize)//判断串L尾结点是否存满，没存满用#填充 
    		for(;k<MaxSize;k++)
    			p->ch[k] = '#';
        //free(T.head);
    	return L;
    }
    
    int StrDelete(SString &S,int i,int len)//串S的删除，删除串S从第i位开始长度为len的子串，并返回S 
    { 
    	if(IsEmpty(S))//判断S是否为空 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	if(i<1||i>S.length)//判断删除位置i是否合理 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	if(i+len > S.length+1)//判断所删除子串是否在串S的范围内
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
        int j=0,k=0;
        Chunk *p = S.head->next;
        for( ;j<i-1;j++)//找到串S的第i个位置 
        { 
            if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
    			p = p->next;
    		}
            k++;
        }
        Chunk *s=p;
        int a=k,b=i;
        for(i=0;i<len;i++)//其次是找到串S的第i+len的位置 
        { 
            if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
    			s = s->next;
    		}
            k++;
        }
        for(i=0;i<S.length-b-len+1;i++)//最后使删除部分的后端填充删除部分，数据往前挪，
        { 
            if(k == MaxSize)
    		{ 
    			k = k%MaxSize;
    			s = s->next;
    		}
            if(a == MaxSize)
    		{ 
    			a = a%MaxSize;
    			p = p->next;
    		}
            p->ch[a] = s->ch[k];
            a++;
            k++;
        }
        if(a != MaxSize)//判断串S尾结点是否存满，没存满用#填充
    		for(;a<MaxSize;a++)
    			p->ch[a] = '#';
        p->next = s;
        p->next = NULL;//当数据填充完后，释放后面的空链结点 
        free(s);
        return 0; 
    }
    
    int main()
    { 
    	char a[] = "ihdhdgfidpfop";
    	char b[] = "djihsdgz";
    	SString S,T,L;
    	InitString(S);
    	InitString(T);	//初始化 
    	StrAssign(S,a);	//将数组a的数据赋值给链串S 
    	StrAssign(T,b);	//将数组b的数据赋值给链串T 
    	OutputStr(S);	//打印链S 
    	printf("%d\n",S.length);	//打印串S的长度 
    	//下面的函数中的常数都是为了方便验证代码结果，可以定义为变量 
    	//SubString(T,S,15,8); //使串S中从第i个位置开始长度为len的子串，填入到空串T中 ，其中的常数是用于测试运行结果的 
    	//StrCopy(T,S); //使串S中的数据填入空串T中
    	OutputStr(T);	//打印串T
    	printf("%d\n",T.length);	//打印串T的长度 
    	StrDelete(S,2,8);	//删除串S的从第i个位置开始长度为len的子串
    	//OutputStr(S);
       // L=StrInset(S,T,10); //使串T插入到串S的第i个位置 
        OutputStr(S);
    	printf("%d\n",StrCompare(S,T));	//比较串T和串S的大小
    	free(S.head); //释放空间 
    	free(L.head); 
    	free(T.head); 
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c63ef27281454123b0bd53d88b8dc423.png