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

#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算法原理：

#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;
}