串的数据结构表——顺序串与链式串（C语言版）

清疚 2022-05-24 10:08 262阅读 0赞

# `` #

#include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100
    
    //串的顺序存储
    typedef struct st
    {
    	char *ch;       //串存放的起始地址，串中第i个字符存储在ch[i-1]中
    	int length;     //串的长度
    	int strsize;    //分配的存储空间的大小，如果不足，在通过realloc()分配增加空间
    }string;
    
    //串的初始化操作
    string CreateNullString()
    {
    	string s;
    	s.length = 0;
    	s.ch = (char*)malloc(MAXSIZE *sizeof(char));
    	s.strsize = MAXSIZE;
    	return s;
    }
    
    //判断空串
    int isEmpty(string s)
    {
    	if (s.length == 0)
    		return 1;
    	else
    		return 0;
    }
    
    //赋值操作
    void StringAssign(string *s1, char s2[])
    {
    	int i = 0;
    	while (s2[i] != '\0')  // '\0' 是字符串的结束符，任何字符串之后都会自动加上'\0'
    		i++;            //计算s2的长度
    	if (i>s1->strsize)
    	{
    		//所赋值的字符数组超过字符串的默认容量，则增加存储空间
    		s1->ch = (char*)malloc(i*sizeof(char));
    		s1->strsize = i;
    	}
    	s1->length = i;
    	for (i = 0; i<s1->length; i++)
    		s1->ch[i] = s2[i]; //从第一个字符开始逐个字符赋值
    }
    
    //串拷贝操作
    void StringCopy(string *s1, string s2)
    {
    	if (s1->strsize<s2.length)
    	{
    		//realloc则对malloc申请的内存进行大小的调整.
    		s1->ch = (char*)realloc(s1->ch, s2.length*sizeof(char));
    		s1->strsize = s2.length;
    	}
    	s1->length = s2.length;
    	int i;
    	for (i = 0; i<s1->length; i++)
    		s1->ch[i] = s2.ch[i];
    }
    
    //求串的长度
    int StringLength(string s)
    {
    	return s.length;
    }
    
    //串的连接操作
    void concat(string *s, string s1, string s2)
    {
    	if (s->strsize<s1.length + s2.length)
    	{
    		s->ch = (char*)realloc(s->ch, (s1.length + s2.length)*sizeof(char));
    		s->strsize = s1.length + s2.length;
    	}
    	s->length = s1.length + s2.length;       //两串连接
    	int i;
    	for (i = 0; i<s1.length; i++)         //将s1复制到s中
    		s->ch[i] = s1.ch[i];
    	for (; i<s->length; i++)
    		s->ch[i] = s2.ch[i - s1.length]; //将s2复制到s中去
    }
    
    //取子串操作
    int substr(string s, int i, int len, string *t)
    {
    	/*
    	i表示从字符串s的第i个位置开始截取（索引从1开始）
    	len表示截取字符串的长度
    	*/
    	if (i <= 0 || i>s.length || len<0 || len>s.length - i + 1)    //参数不合法
    		return 0;
    	if (t->length<len) //存储空间不够，继续分配存储空间
    	{
    		t->ch = (char*)realloc(t->ch, len*sizeof(char));
    		t->strsize = len;
    	}
    	t->length = len;
    	int k;
    	for (k = 0; k<t->length; k++)
    		t->ch[k] = s.ch[i - 1 + k];
    	return 1;
    }
    
    //插入操作
    int insertString(string *s, int i, string t)
    {
    	//在字符串s的第i个位置插入字符串t
    	if (i <= 0 || i>s->length + 1)
    		return 0;
    	if (s->strsize<s->length + t.length)  //空间不足
    	{
    		s->ch = (char*)realloc(s->ch, (s->length + t.length)*sizeof(char));
    		s->strsize = s->length + t.length;
    	}
    	int k;
    	for (k = s->length - 1; k >= i - 1; k--) //将s中的后i个字符后移到后面
    		s->ch[k + t.length] = s->ch[k];//end[][][] ==> e[][][]nd
    
    	s->length = s->length + t.length;//s->length=3+3
    	for (k = 0; k<t.length; k++)              //将t的值赋值给s
    		s->ch[k + i - 1] = t.ch[k];//e[][][]nd==>eaaand
    	return 1;
    }
    
    //删除操作
    int deleteString(string *s, int i, int len)
    {
    	//从s的第i个字符开始删除len个字符
    	if (i <= 0 || i>s->length || len<0 || len>s->length - i + 1)    //参数不合法
    		return 0;
    	int k;
    	for (k = i + len - 1; k<s->length; k++)    //从s的i+len-1个位置开始将其后的所有字符前移
    		s->ch[k - len] = s->ch[k];
    	s->length -= len;
    	return 1;
    }
    
    //输出操作
    void print(string s)
    {
    	int i;
    	for (i = 0; i<s.length; i++)
    		printf("%c", s.ch[i]);
    	printf("\n");
    }
    
    void main()
    {
    	string s1 = CreateNullString();
    	string s2 = CreateNullString();
    	string s3 = CreateNullString();
    	char ch[MAXSIZE];
    	printf("请输入主串：\n");
    	//输入friend
    	gets(ch);
    	//赋值操作
    	StringAssign(&s1, ch);
    	printf("主串 s1 为：");
    	print(s1);
    	//将字符s1拷贝到s2
    	StringCopy(&s2, s1);
    	printf("拷贝串操作结果如下，结果如下 s2 ：");
    	print(s2);
    	printf("删除操作（1——s1.length-3 全删）：");
    	//删除操作
    	deleteString(&s2, 1, s1.length - 3);
    	print(s2);
    	printf("插入操作,插入到s2的第2个位置上，请输入插入的字符串：");
    	gets(ch);
    	//赋值操作 把输入的字符放到s3中
    	StringAssign(&s3, ch);
    	//进行插入操作,将s3插入到s2的第二个位置上
    	insertString(&s2, 2, s3);
    	print(s2);
    	printf("取子串操作（取s1的子串【2-4】)：");
    	//提取friend 中[2-4]位置元素-rie
    	substr(s1, 2, 3, &s3);
    	print(s3);
    	//s1==>friend s3==>rie
    	printf("串连接操作【将s1与s3合并】：");
    	concat(&s1, s1, s2);
    	print(s1);
    	system("pause");
    }

# `运行结果：` #

`串的数据结构表——顺序串与链式串 　　串的结构类似与线性表，只不过串的数据元素是一个字符，即是由零个或多个字符组成的有限序列。 一、串的顺序存储 　　串的顺序存储结构也就是顺序存储，即串中的字符被依次的存在一组连续的存储单元中，可以类比线性表的顺序存储，可以写出其数据结构如下： typedef struct st { char *ch;       //串存放的起始地址，串中第i个字符存储在ch[i-1]中 int length;     //串的长度 int strsize;    //分配的存储空间的大小，如果不足，在通过realloc()分配增加空间 }string; 　　 假设现在的字符串是“friend”，其结构可以用如图所示： 　　 　　现在我们拿到这个数据结构第一步是要初始化一个串，即首先在内存中开辟一段连续的存储空间（大小可以假先预定MAXSIZE个存储空间），初始化其长度length为0，同时制定其串的最大容量是MAXSZIE，如下： 二、串的链式存储 　　串的链式存储结构称为串的链式存储，即串中的每一个节点包括两个部分：数据域和指针域，其中数据域用来存放字符，指针域用来存放指向下一个节点的指针。 　　由此可得串的链式数据结构如下： 1 2 3 4 5 typedef  struct  node {      char  ch;             //字符域      struct  node *next;   //指针域，存放下一个结点的地址 }node,*linkstr; 　如下所示： 　    其初始化操作主要是开辟头结点，同时让它的下一个指针指向为NULL：`

//串的链式存储结构设计与实现
    #include<stdio.h>
    #include<stdlib.h>
    
    
    //链式串的结构
    typedef struct _tag_LinkString
    {
    	char ch;//字符域
    	struct _tag_LinkString *next;//指针域 存放下一个结点地址域
    }LinkString;
    
    //初始化操作：建立一个空串
    LinkString* CreatNULLString()
    {
    	LinkString *tmp = NULL;
    	tmp = (LinkString *)malloc(sizeof(LinkString));
    	if (NULL == tmp)
    	{
    		printf("func err malloc\n");
    	}
    	tmp->next = NULL;
    	return tmp;
    }
    
    //判断空串
    int iEmpty(LinkString *str)
    {
    	if (str->next == NULL )
    	{
    		return 1;
    	}
    	else{
    		return 0;
    	}
    }
    
    //赋值操作
    void StringAssignment(LinkString *str,char sourse[])
    {
    	if (NULL == str || NULL == sourse)
    	{
    		printf("func err (NULL == str || NULL == sourse)\n");
    	}
    	LinkString *tmp1 = NULL, *tmp2 = NULL, *tmp3 = NULL;
    	tmp3 = str;//tmp3始终指的是尾结点(最后一个非空结点,而不是最后一个NULL结点)
    	tmp2 = str->next;
    	int i;
    	for ( i = 0; sourse[i] != '\0'; i++)
    	{ 
    		//(初始化时只给头结点分配了存储空间或者其他情况)，如果需要继续添加数据（其他节点没分配空间）需要继续分配
    		if (tmp2 != NULL)
    		{
    			tmp2->ch = sourse[i];
    			tmp3 = tmp2;
    			tmp2 = tmp2->next;
    		}
    		else
    		{
    			tmp1 = (LinkString *)malloc(sizeof(LinkString));
    			//添加结点
    			tmp1->ch = sourse[i];
    			tmp3->next = tmp1;
    			tmp3 = tmp1;
    		}
    		tmp3->next = NULL;
    	}
    	//将s中原来多余的空间释放掉
    	while (tmp2 != NULL)
    	{
    		tmp1 = tmp2->next;
    		free(tmp2);
    		tmp2 = tmp1;
    	}
    }
    
    //串的拷贝操作
    void StringCopy(LinkString *str, LinkString *other)
    {
    	//1 将other串的值拷贝到str串
    	LinkString *p, *q, *r, *u;
    	p = other->next;
    	q = str->next;
    	r = str;
    	while (p!=NULL)
    	{
    		//原串原先分配了空间
    		if (q != NULL)
    		{
    			q->ch = p->ch;
    			r = q;
    			q = q->next;
    		}
    		//若串s原先的空间不够用
    		else
    		{
    			u = (LinkString *)malloc(sizeof(LinkString));
    			u->ch = p->ch;
    			r->next = u;
    			r = u;
    		}
    
    		//p节点后移
    		p = p->next;
    	}
    	//同理，若q的长度过长，可以释放多余的空间
    	while (q != NULL)
    	{
    		p = p->next;
    		free(q);
    		q = p;
    	}
    	r->next = NULL;
    }
    
    
    
    //求串的长度
    int length(LinkString *s)
    {
    	LinkString *p = NULL;
    	int n = 0;
    	p = s->next;
    	while (p != NULL)
    	{
    		n++;
    		p = p->next;
    	}
    	return n;
    }
    
    //串的连接操作
    void contact(LinkString *s, LinkString *s1, LinkString *s2)
    {
    	LinkString *p, *q, *r, *t;
    	r = s;
    	p = s1->next;
    	q = s->next;
    	while (p != NULL)
    	{
    		if (q != NULL)
    		{
    			q->ch = p->ch;
    			q = q->next;
    			r = q;
    		}
    		else
    		{
    			//串s原来没有分配存储空间，需要申请空间
    			t = (LinkString *)malloc(sizeof(LinkString));
    			t->ch = p->ch;
    			r->next = t;
    			r = t;
    		}
    		p = p->next;
    	}
    	p = s2->next;
    	while (p != NULL)
    	{
    		if (q != NULL)
    		{
    			q->ch = p->ch;
    			q = q->next;
    			r = q;
    		}
    		else
    		{
    			//串s原来没有分配存储空间，需要申请空间
    			t = (LinkString *)malloc(sizeof(LinkString));
    			t->ch = p->ch;
    			r->next = t;
    			r = t;
    		}
    		p = p->next;
    	}
    
    
    
    	//将串s的多余的空间清除掉(这个情况只可能发生在while的if循环中)
    	while (q != NULL)
    	{
    		p = q->next;
    		free(q);
    		q = p;
    	}
    	r->next = NULL;
    
    }
    
    //截取子串
    int substr(LinkString *s, int i, int len, LinkString *t)
    {
    	LinkString *p, *q, *r, *u;
    	if (i <= 0 || i>length(s) || i + len - 1>length(s))
    		return 0;
    	//指针指向s的第i-1个位置
    	int j, k;
    	for (j = 0, p = s; j<i; j++)
    		p = p->next;
    
    	for (k = 0, r = t, q = t->next; k<len; k++)
    	{
    		if (q != NULL)
    		{
    			q->ch = p->ch;
    			r = q;
    			q = q->next;
    		}
    		else
    		{
    			u = (LinkString *)malloc(sizeof(LinkString));
    			u->ch = p->ch;
    			r->next = u;
    			r = u;
    		}
    		p = p->next;
    	}
    
    	while (q != NULL)
    	{
    		p = q->next;
    		free(q);
    		q = p;
    	}
    	r->next = NULL;
    	return 1;
    }
    
    
    //插入操作
    int insert(LinkString *s, int i, LinkString *t)
    {
    	LinkString *p, *q, *r;
    	if (i <= 0 || i>length(s) + 1)
    		return 0;
    	//指向第i-1个位置
    	int j;
    	for (j = 0, p = s; j<i - 1; j++)
    		p = p->next;
    	q = t->next;
    	while (q != NULL)
    	{
    		r = (LinkString *)malloc(sizeof(LinkString));
    		r->ch = q->ch;
    		r->next = p->next;
    		p->next = r;
    		q = q->next;
    		p = r;
    
    	}
    	return 1;
    }
    
    //删除操作
    int deleteString(LinkString *s, int i, int len){
    	LinkString *p, *q;
    	//防止非法输入
    	if (i <= 0 || i>length(s) || i + len - 1>length(s))
    		return 0;
    	int j;
    	//将p移动到删除位置i
    	for (j = 0, p = s; j<i - 1; j++)
    		p = p->next;
    	//将i后的位置元素进行删除
    	for (j = 0; j<len; j++)
    	{
    		q = p->next;
    		p->next = q->next;
    		free(q);
    	}
    	return 1;
    
    }
    
    //打印输出
    void print(LinkString *s)
    {
    	LinkString *p = s->next;
    	while (p != NULL)
    	{
    		printf("%c", p->ch);
    		p = p->next;
    	}
    	printf("\n");
    }
    void main()
    {
    	LinkString *s1 = NULL;
    	LinkString *s2 = NULL;
    	LinkString *s3 = NULL;
    	//1 初始化操作
    	s1 = CreatNULLString();
    	s2 = CreatNULLString();
    	s3 = CreatNULLString();
    	char str[100];
    	printf("请输入字符串：\n");
    	gets(str);
    	//2 str赋值操作于s1
    	StringAssignment(s1, str);
    	printf("串s1：");
    	print(s1);
    	printf("串s1的长度为：%d\n", length(s1));
    	//3 串拷贝操作
    	StringCopy(s2, s1);
    	printf("串s2：");
    	print(s2);
    	printf("串s2删除操作(第三个位置的三个字符删除 ：");
    	//4 删除操作
    	deleteString(s2, 3, 3);
    	print(s2);
    	printf("串连接操作（s3=s1+s2 ）：");
    	//5 串的连接操作
    	contact(s3, s1, s2);
    	print(s3);
    	printf("插入操作(从s1的第6个位置插入s3)：");
    	//6 串的插入操作
    	insert(s1, 6, s3);
    	print(s1);
    	printf("测试截取子串的功能s2（截取s3的第四个位置长度为4的字符串：");
    	//7 串的截取操作
    	substr(s3, 4, 4, s2);
    	print(s2);
    	printf("测试字Contact的清除过多存储空间的功能：(将两个较短的字符[两个s2]合并写到s1上去：");
    	//8 串的连接操作
    	contact(s1, s2, s2);
    	print(s1);
    
    	system("pause");
    }

KMP算法原理：

![70][]

![70 1][]

![70 2][]

![70 3][]

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    void prefix_table(char pattern[], int prefix[], int n)
    {
    	prefix[0] = 0;
    	int len = 0;//比较的长度
    	int i = 1;
    	while (i < n)
    	{
    		printf("i = %d,len = %d\n",i,len);
    		if (pattern[i] == pattern[len])
    		{
    			len++;
    			prefix[i] = len;
    			i++;//往后检测下个
    		}
    		else
    		{
    			if (len > 0)
    			{
    				len = prefix[len -1];//
    			}
    			else
    			{
    				//这里len = 0
    				prefix[i] = len;
    				i++;
    			}
    		}
    	}
    }
    
    //将前缀表后移一位，并且在第一位放上-1
    void move_prefix_table(int prefix[], int n)
    {
    	int i;
    	for ( i = n - 1; i > 0; i--)
    	{
    		prefix[i] = prefix[i-1];
    	}
    	prefix[0] = -1;
    }
    
    //KMP搜索
    void Kmp_search(char text[], char pattern[])
    {
    	int n = strlen(pattern);
    	int m = strlen(text);
    	int *prefix = malloc(sizeof(int) * n);
    	//调用弄出前缀表
    	prefix_table(pattern, prefix, n);
    	//做移位处理
    	move_prefix_table(prefix, n);
    
    	//text[i]  ,len(text)=n
    	//pattern[j]  len(pattern)=m
    	int i = 0, j = 0;
    	while (i < m)
    	{
    		if (j == n -1&&text[i] == pattern[j])
    		{
    			printf("Found pattern at %d\n", i - j);
    			j = prefix[j];
    		}
    		if (text[i] == pattern[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = prefix[j];
    			if (j == -1)
    			{
    				i++;
    				j++;
    			}
    		}
    	}
    }
    
    int main()
    {
    	char pattern[] = "ABABCABAA";
    	char text[] = "ABABABCABAABCABAAADDDUUU";
    	Kmp_search(text,pattern);
    	/*
    	int prefix[9];
    	int n = 9;
    	//调用弄出前缀表
    	prefix_table(pattern,prefix,n);	
    	//做移位处理
    	move_prefix_table(prefix,n);
    	int i;
    	for ( i = 0; i < n; i++)
    	{
    		printf("%d\n",prefix[i]);
    	}
        */
    
    	system("pause");
    	return 0;
    }

[70]: /images/20220524/752df592d7d44eaf8c8f9920d65a4b0e.png
[70 1]: /images/20220524/283bc4d847844c75b22c1ddb728ef9d0.png
[70 2]: /images/20220524/c5f21a19e7b64cf08439d3305e56fc5c.png
[70 3]: /images/20220524/dcd6bd527862445ebfc4a13d31444c2f.png