热门标签
当前位置: article > 正文
数据结构：串(c语言 链串，块链和串的模式匹配KMP算法)_链串模式算法c语言
作者：小蓝xlanll | 2024-06-04 04:47:03
赞
踩
链串模式算法c语言
串
定义： 串是特殊的线性表，串(string)是零个或多个字符组成的有限序列。一般记作s=“a1a2…an”，其中s是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。
长度为零的串称为空串(EmptyString)，它不包含任何字符。
通常将仅由一个或多个空格组成的串称为空白串(Blank String)
注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。
子串：串中任意个连续字符组成的子序列。
主串：包含子串的串。
通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。
例如，设A和B分别为
A=“This is a string” ; B=“is”
则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。
因此，称B在A中的序号（或位置）为3。
注意：空串是任意串的子串，任意串是其自身的子串。
- 1
- 2
- 3
- 4
- 5
串的五个基本操作
- 字符串复制函数
char* strcpy(s1,s2)把字符串s2复制到s1，并返回指向串s1开始处的指针；
int main()
{
char s[20] = "abcdefg i";
char s1[10];
strcpy_s(s1, s);
printf("%s\n", s1);//输出结果为abcdefg i
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 字符串连接函数
char* strcat(s1,s2)该函数将串s2复制到串s1的末尾，并且返回一个指向串s1的开始处的指针；
int main()
{
char s[20] = "abcdefg i";
char s1[10] = "kdsja";
strcat_s(s, s1);
printf("%s\n", s);//输出结果为abcdefg ikdsja
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 字符串比较函数
int strcmp(s1,s2)s1、s2从左至右，逐个字符相比，比较ASCII码
s1=s2，返回0；
s1<s2，返回负数；
s1>s2，返回正数；
int main()
{
printf("%d", strcmp("11", "11"));//输出0
printf("%d", strcmp("11", "12"));//输出-1
printf("%d", strcmp("13", "12"));//输出1
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 字符串长度函数
int strlen(s)不包含‘\0’
int main()
{
char s[20] = "abcdefg i";
printf("%d\n", strlen(s));//输出结果为9
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 字符串定位函数
char *strchr(char *s, char ch);该库函数是找ch在字符串s中第一次出现的位置，若找到则返回该位置，否则返回NULL。
int main()
{
char s[20] = "abcdefg i";
char* p = strchr(s, 'b');
printf("%c\n", *p);//输出结果是a，说明p指向‘a’
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
串的两种表示方法
- 定长顺序存储表示
定长顺序存储表示,也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出。
例：
char s[100];//能容纳99个字符的顺序串
- 1
一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符‵\0′表示串值的终结，这就是为什么在上述定义中，串空间最大值为100，但最多只能存放99个字符的原因，因为必须留一个字节来存放‵\0′字符。
若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似：
typedef struct{
char str[100];
int length;
} s; //其优点是涉及到串长操作时速度快。
- 1
- 2
- 3
- 4
- 串的链式存储结构
为了使串插入和删除更加方便，我们可以使用链来存储字符串。就有了链串。
typedef struct node{
char data;
struct node *next;
}ls;
- 1
- 2
- 3
- 4
如果这样来存储链串那么由不得不面临一个问题：由于一个节点只存储一个字符，存储效率太低。 所以为了解决这个问题就有了块链，即每个节点存放多个字符的链表。
#define nodesize 80
typedef struct node{
char data[nodesize];
struct node *next;
}ls;
- 1
- 2
- 3
- 4
- 5
当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。
基础操作求子串
求主串s中从第 i个字符起、长度为 k的子串，当参数 i和 k满足条件时，所求子串由函数返回；否则函数返回空值
顺序串
#include <stdio.h> #define maxsize 200 typedef struct { char data[maxsize]; int leng=0; }S; S find(S s, int i, int k)//顺序求子串 { S s1; if (i + k >= s.leng) {//如果子串的起始位置和长度加起来大于主串的长度，则报错 printf("错误！！！"); s.data[0] = NULL; s.leng = 0; return s1; } int r = 0; while (k--) { s1.data[r++] = s.data[i++];//取子串 s1.leng++; } return s1; } int main() { S s; s.leng = 0; for (int i = 0; i < 20; i++) {//初始化主串 s.data[i] = 'a' + i; s.leng++; } S s1 = find(s, 5, 5); for(int i=0;i<5;i++) printf("%c",s1.data[i]); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
链串
#include <stdio.h> typedef struct Node {//元素节点 char data; Node* next; }node; typedef struct Head {//头结点 int leng; Node* next; }Head; void insert(Head* head, char element)//尾插 { node* tem = (node*)malloc(sizeof(node)); tem->data = element; tem->next = NULL; if (head->next == NULL) { head->next = tem; head->leng++; } else { node* p = head->next; while (p->next != NULL) { p = p->next; head->leng++; } p->next = tem; } } Head* find(Head* head, int i, int k)//求子串 { int n = head->leng, j; node* p, *v, *q; if (i >= 1 && i <= n && k > 0 && k <= n - i + 1) { p = head->next; for (j = 1; j < i; j++) p = p->next; //寻找子串起始位置 Head* head1 = (Head*)malloc(sizeof(Head)); head1->leng = k; //子串头结点的数据域存放长度 head1->next = NULL; //初始化头结点 for (int j = 0; j < k; j++) //建立子串头插法 { q = (node*)malloc(sizeof(node)); q->data = p->data; q->next = head1->next; head1->next = q; p = p->next; } return head1; } else return NULL; } int main() { Head* head = (Head*)malloc(sizeof(Head)); head->leng = 0; head->next = NULL; for (int i = 0; i < 15; i++) { //初始化建链串 insert(head, 'a' + i); } Head* head1=find(head, 5, 5); node* p = head1->next; while (p != NULL) { //输出 printf("%c", p->data); p = p->next; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
块链串
#include <stdio.h> #define maxsize 5 typedef struct Node { char data[maxsize]; Node* next; }node; typedef struct Head { int len; node *next; }head; void ShowString(head* hea) //输出 { node *p = NULL; int i; p = hea->next; while (p != NULL) { for (i = 0; i < maxsize; i++) { if (p->data[i] == '#') { return; } printf("%c", p->data[i]); } p = p->next; printf("|"); } printf("\n"); } void insert(head* hea, char s[])//建链串 { int num = 0, i = 0; node* p = (node*)malloc(sizeof(node)); //创建第一个节点 p->next = NULL; hea->next = p; //连接第一个节点 while (s[num] != '\0') { if (i >= maxsize) { //如果所存的数据数量大于一个块链能存的数量，就创建新节点 node* q = (node*)malloc(sizeof(node)); q->next = NULL; p->next = q; p = q; //更新p节点 i %= maxsize; //更新i hea->len++; } p->data[i++] = s[num++]; } for (int j = i; i != 0 && j < maxsize; j++) { //若最后没有把一个节点存满，则把空着的填上特殊字符作为结束标志 p->data[j] = '#'; } } head* find(head* hea, int i, int k)//求子串 { head* head1 = (head*)malloc(sizeof(head));//子串头结点 head1->len = 0; head1->next = NULL; node *t = hea->next; int num = i / maxsize, n = i % maxsize; if (num > hea->len||t == NULL || i + k > hea->len * maxsize) { printf("错误!!!"); return NULL; } node* p = (node*)malloc(sizeof(node)); //创建第一个节点 p->next = NULL; for (int j = 0; j < num; j++) { //寻找起始节点 t = t->next; } i = 0; head1->next = p; head1->len++; while (k--) { if (n == maxsize) { //主串一个节点元素取完 t = t->next; n = 0; } if (i >= maxsize) { //子串一个节点已存满 node* q = (node*)malloc(sizeof(node)); q->next = NULL; p->next = q; p = q; //更新p节点 i %= maxsize; //更新i head1->len++; } if (t->data[n] == '#') { return head1; } p->data[i++] = t->data[n++]; //取子串 } for (int j = i; i != 0 && j < maxsize; j++) { //若最后没有把一个节点存满，则把空着的填上特殊字符作为结束标志 p->data[j] = '#'; } return head1; } int main() { head* hea = (head*)malloc(sizeof(head)),*head1; hea->len = 1; hea->next = NULL; char s[11] = { 'a','b','c','d','e','f','g','h','i','j' }; insert(hea,s); ShowString(hea);//输出主串 head1=find(hea, 4, 4); ShowString(head1);//输出子串 return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
串的模式匹配
在一个主串中去匹配一个子串，并返回子串在主串中的位置（子串首字母的位置）
朴素算法
时间复杂度为O((m-n)n)
int index(char s[15], char s1[5]) { int i, j, k; int m = strlen(s); int n = strlen(s1); for (i = 0; i <= m - n; i++) { j = 0; k = i; while (j < m && s[k] == s1[j]) //匹配子串 { k++; j++; } if (j == n) //子串匹配成功 return i; } return -1; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
KMP模式匹配算法
朴素模式匹配每次匹配失败主串的i指针就要回溯，这样会增加时间复杂度，所以朴素算法在处理大量数据时会显得很吃力。所以为了解决这个问题，模式匹配的改进算法 KMP 应用而生。
第一步
简单来说就是先要求匹配子串的最长头和尾相同元素的个数加1，然后把这个数存在一个数组中，在后续匹配中使用。例如：next[6]=3,说明前6个字符中前2个等于 (顺序、字符都一样) 后2个，类似
abcaba；若next[6]=2,说明前6个字符中第1个等于第6个，类似adccba。
注意：在这一步，模式串既是主串也是子串！！
例：模式子串abaabcac
初始next[1]=0；next[j]=k,表明在模式串中满足p1···p2 == p(j-k+1)···p(j-1);
求next[j+1]有两种情况：
pk = pj；next[j+1] = next[j]+1;pk != pj；next[j+1] = next[k]若一直不相等，则到k=1就结束，此时next[j+1] = next[1] = 0;
例如：在上例abaabcac中求next[7]，先比较第6个和第(next[6])3个元素，发现他俩不相等，则再比较第6个元素和第 (next[next[6]]) 1个元素，也不相等,但是next[1] == 0,所以停止，next[7] = next[1]；其它都类似。
void get_next(char s[], int next[]) { int i = 1,j = 0; next[1] = 0; while (i <= strlen(s)) { if (j == 0 || s[i] == s[j]) { i++; j++; if (s[i] != s[j]) //第一种情况 next[i] = j; else //第二种情况 next[i] = next[j]; } else { //模式串向右滑动 j = next[j]; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
第二步
利用next数组在主串中匹配模式子串；此过程中主串指针 i 不需要回溯，需要回溯的仅仅是模式子串的指针 j 。
int index_KMP(char s[], char t[], int pos,int next[]) { int i = pos; //取主串中起始匹配位置 int j = 1; while (i <= strlen(s) && j <= strlen(t)) { if (j == 0 || s[i] == t[j]) { //继续比较后续字符 i++; j++; } else { //模式串向右滑动 j = next[j]; } if (j >= strlen(t)) { //匹配成功 return i - strlen(t) + 1; } } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
主函数
int main()
{
int next[11] = { 0 };
char t[10] = "3aba"; //t[0]存放串t的长度
char s[15] = "9bcbdabahd"; //s[0]存放串s的长度
get_next(t, next);
for (int i = 1; i < strlen(t); i++)
printf("%d ",next[i]);
printf("\n");
int m=index_KMP(s, t, 1, next);
printf("%d", m);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
虽然朴素算法在处理大量字符时不占优势，但是在处理少量字符时效率还是挺快的，所以至今朴素算法应用的较为广泛。
串的相关知识到这里就结束了，模式匹配KMP算法这里只是自己一些简单的理解，还需要继续深入理解，欢迎各位朋友在下方留言提问！下次见。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/670427
推荐阅读
相关标签
