搜索到
40
篇与
的结果
-
字符串的快速模式匹配(KMP算法) 字符串的快速模式匹配(KMP算法)#include <stdio.h> // 顺序存储的字符串 #define MAX_SIZE 100 typedef struct { char str[MAX_SIZE]; int length; }seqString; // 1.顺序字符串的初始化 void init(seqString *str) { str->length = 0; } // 2.根据用户输入构造字符串 void insert(seqString *str) { char c; printf("请输入字符，回车表示结束输入...\n"); while ((c = getchar()) != '\n' && str->length < MAX_SIZE) str->str[str->length++] = c; } // 根据模式串求对应的next数组 void getNext(seqString p,int next[]) { int i = 0, j = -1; next[0] = -1; while (i < p.length) { if(j == -1 || p.str[i] == p.str[j]) { i++; j++; next[i] = j; } else j = next[j]; } } // 4.2.2 字符串的KMP模式匹配算法 // 如果成功则返回p在t中首次出现的起始位置，否则返回-1 int kmp(seqString t, seqString p,int next[]) { int i = 0,j = 0; while (i < t.length && j <p.length) { if(j == -1 || t.str[i] == p.str[j]) { i++; j++; } else j = next[j]; } if(j == p.length) return i-p.length; return -1; } int main() { seqString t,p; init(&t); init(&p); insert(&t); insert(&p); int next[p.length]; getNext(p,next); // 求p的next数组 int i = kmp(t,p,next); if(i == -1) printf("模式串匹配失败！\n"); else printf("模式串在主串中首次出现的起始位置是%d",i); return 0; } -
字符串的朴素模式匹配 字符串的朴素模式匹配#include <stdio.h> // 顺序存储的字符串 #define MAX_SIZE 100 typedef struct { char str[MAX_SIZE]; int length; }seqString; // 1.顺序字符串的初始化 void init(seqString *str) { str->length = 0; } // 2.根据用户输入构造字符串 void insert(seqString *str) { char c; printf("请输入字符，回车表示结束输入...\n"); while ((c = getchar()) != '\n' && str->length < MAX_SIZE) str->str[str->length++] = c; } // 4.2.1 字符串的朴素模式匹配算法 // 如果成功则返回p在t中首次出现的起始位置，否则返回-1 int getIndex(seqString t, seqString p) { int i = 0,j,flag = 0;// flag为成功的标识 while (i <= t.length - p.length && !flag) { j = 0; flag = 1; // 每次匹配结束后j回溯，flag设置为真 while (j < p.length && flag) { if(p.str[j] == t.str[j+i]) // 对应相等则继续 j++; else flag = 0; // 否则退出当前循环 } i++; } if(flag) return i-1; return -1; } int main() { seqString t,p; init(&t); init(&p); insert(&t); insert(&p); int i = getIndex(t,p); if(i == -1) printf("模式串匹配失败！\n"); else printf("1模式串在主串中首次出现的起始位置是%d\n",i); return 0; }
-
字符串的链式存储和操作 字符串的链式存储和操作#include <stdio.h> #include <stdlib.h> typedef struct linkNode { char data; struct linkNode *next; }node, *linkStr; // 1.初始化字符串 void init(linkStr *s) { *s = NULL; } // 2.输出字符串 void display(linkStr s) { if(!s) { printf("字符串为空！\n"); return; } while (s) { printf("%c",s->data); s = s->next; } printf("\n"); } // 3.根据用户输入构造字符串 void strCreate(linkStr *s) { char c; node *p, *r = *s; printf("请输入字符，回车表示结束输入...\n"); while ((c = getchar()) != '\n') { p = (node*) malloc(sizeof(node)); p->data = c; if(!*s) *s = p; else r->next = p; r = p; } if(r) r->next = NULL; } // 4.查找第i个字符 node *find(linkStr s, int i) { if(i < 1 || !s) return NULL; if(i == 1) return s; int j = 1; while (s && i!=j) { s = s->next; j++; } return s; } // 5.将字符串t插入字符串s中第i个字符开始的位置上 void strInsert(linkStr *s, int i, linkStr t) { if(!t) return; if(i < 1) { printf("非法的插入操作！\n"); return; } node *p = find(*s,i-1),*r = t; while (r->next) r = r->next; if(i == 1) { r->next = *s; *s = t; return; } if(p) { r->next = p->next; p->next = t; // t还需删除 } else printf("非法的插入操作！\n"); } // 6.将串s从第i个字符起删除len个长度的子串 void strDel(linkStr *s, int i, int len) { if(!*s) { printf("字符串为空，无法删除！\n"); return; } if(i < 1 || len < 1) { printf("非法的删除操作！\n"); return; } node *pre = *s,*r,*q; int j = 1; while (pre && j < i-1) // 找到删除的前驱结点 { pre = pre->next; j++; } j = 0; r = pre; while (r && j < len) // 找到删除的最后一个结点 { j++; if(pre == *s && j == 1) continue; r = r->next; } if(r) { if(pre == *s) { q = pre; *s = r->next; free(q); } else { pre->next = r->next; pre = pre->next; while (pre != r->next) { q = pre; free(q); pre = pre->next; } } } else printf("非法的删除操作！\n"); } // 7.字符串的连接运算 void strConcat(linkStr *s,linkStr t) { node *p = *s; if(!t) // t为空串时 return; if(!*s) // s为空串时 *s = t; else { while (p->next) // 找到s的尾结点 p = p->next; p->next = t; } } // 8.截取子串 linkStr substring(linkStr s, int i, int len) { linkStr t; // 字串 init(&t); if(i < 1 || len < 1) { printf("非法的截取操作！\n"); return t; } node *p = s,*q,*r,*n; // p、q为主串工作指针，r指向字串尾指针 int j = 1; while (p && j < i) // 寻找第i个结点 { p = p->next; j++; } q = p,j = 1; while (q && j < len) // 寻找第i+len-1个结点 { j++; q = q->next; } if(!q) // 表示超过s的边界 { printf("非法的截取操作！\n"); return t; } while (p != q->next) { n = (node*) malloc(sizeof(node)); n->data = p->data; if(!t) // 处理首结点 t = n; else r->next = n; r = n; // 更新尾指针 p = p->next; } r->next = NULL; // 处理字串尾部 return t; } int main() { linkStr str,t,s; init(&str); init(&t); strCreate(&str); printf("字符串str: "); display(str); strCreate(&t); printf("字符串t: "); display(t); int i = 1,len = 5; printf("将字符t插到str中的第%d个字符开始的位置上\n",i); strInsert(&str,i,t); printf("字符串str: "); display(str); printf("将串str从第%d个字符起删除%d个长度的子串\n",i,len); strDel(&str,i,len); printf("字符串str: "); display(str); init(&t); strCreate(&t); printf("字符串t: "); display(t); printf("把字符串t拼接在str后\n"); strConcat(&str,t); printf("字符串str: "); display(str); s = substring(str,i,len); printf("字符串str从第%d个字符开始长度为%d的子串:\n",i,len); display(s); return 0; }
-
字符串的顺序存储和操作 字符串的顺序存储和操作#include <stdio.h> #include <stdlib.h> // 4.1字符串是元素类型为字符型的特殊线性表，因此也有顺序存储和链式存储 #define MAX_SIZE 100 typedef struct { char str[MAX_SIZE]; int length; }seqString; // 1.顺序表的初始化/置空表 void init(seqString *str) { str->length = 0; } // 2.打印顺序表各结点的值 void display(seqString slt) { if(!slt.length) { printf("顺序表是空的！\n"); return; } for (int i = 0; i < slt.length; i++) printf("%c ",slt.str[i]); printf("\n"); } // 3.在顺序表尾部追加值为x的元素 void append(seqString *str,char x) { if(str->length == MAX_SIZE) { printf("顺序表是满的，无法追加！\n"); exit(1); } str->str[str->length] = x; str->length++; } // 3.将字符t插到s中的第i个字符开始的位置上 void strInsert(seqString *s, int i, seqString *t) { if(i < 1 || i > s->length+1) { printf("插入的位置非法！"); return; } if(t->length+s->length > MAX_SIZE-1) { printf("字符串过长！"); return; } for (int j = s->length-1;j >= i-1; j--) s->str[j+t->length] = s->str[j]; for (int m=0; m < t->length; m++,i++) s->str[i-1] = t->str[m]; s->length += t->length; t->length = 0; } // 4.将串s从第i个字符起删除len个长度的字串 void del(seqString *s, int i, int len) { if(len < 1 || len > s->length-i+1) { printf("操作非法，无法删除！\n"); return; } for (; i < s->length; i++) { s->str[i-1] = s->str[i+len-1]; } s->length -= len; } // 5.字符串拼接 void strConcat(seqString *s, seqString *t) { if(s->length + t->length > MAX_SIZE) { printf("空间不足，无法拼接！\n"); return; } for (int i = 0; i < t->length; i++) { s->str[s->length++] = t->str[i]; } } // 6. 求字串 seqString *substring(seqString s, int i, int len) { seqString *p = (seqString*) malloc(sizeof(seqString)); init(p); if(len < 1 || len > s.length-i+1) { printf("获取字串操作非法!\n"); return p; } for (int j = 0; j < len; i++) p->str[j++] = s.str[i-1]; p->length = len; return p; } int main() { seqString s,t; init(&s); init(&t); for (int i = 'a'; i < 'f'; ++i) append(&s,(char)i); printf("字符串s: "); display(s); for (int i = 'A'; i < 'D'; ++i) append(&t,(char)i); printf("字符串t: "); display(t); printf("把字符串t拼接在s后\n"); strConcat(&s,&t); printf("字符串s: "); display(s); int i = 3; printf("将字符t插到s中的第%d个字符开始的位置上\n",i); strInsert(&s,i,&t); printf("字符串s: "); display(s); int len = 3; printf("将串s从第%d个字符起删除%d个长度的字串\n",i,len); del(&s,i,len); printf("字符串s: "); display(s); seqString *str = substring(s,i,len); printf("字符串s从第%d个字符开始长度为%d的字串:\n",i,len); display(*str); return 0; }
-
循环双链表的实现和相关操作 循环双链表的实现和相关操作#include <stdio.h> #include <stdlib.h> typedef int dataType; // 3.8.11 循环双链表 typedef struct dLinkNode { dataType data; struct dLinkNode *lLink,*rLink; }dNode,*dLinkList; // 1.初始化不带头结点的循环双链表 void init(dLinkList *head) { *head = NULL; } // 2.输出双链表各结点的值 void display(dLinkList head) { dNode *p = head; if(!p) { printf("双链表为空！\n"); return; } do{ printf("%d ",p->data); p = p->rLink; } while (p != head); printf("\n"); } // 3.查找双链表中第i个结点 dNode *find(dLinkList head, int i) { dNode *p = head; if(i < 1) { printf("非法的索引！\n"); return NULL; } if(!p) { printf("双链表为空！\n"); return NULL; } if(i == 1) return p; int j = 1; do { p = p->rLink; // 向后遍历直到末尾 j++; }while (p->rLink != head && i != j); if(i > j) return NULL; return p; } // 5.在双链表尾部插入值为x的结点 void rearInsert(dLinkList *head, dataType x) { dNode *q = (dNode*) malloc(sizeof(dNode)); q->data = x; if(!*head) // 链表为空时 { *head = q; q->lLink = q->rLink = q; } else { (*head)->lLink->rLink = q; // 插入新结点 q->rLink = *head; q->lLink = (*head)->lLink; (*head)->lLink = q; } } // 6.在双链表的第i个结点后插入值为x的新结点 void insert(dLinkList *head, int i, dataType x) { if(i < 0) { printf("非法的插入位置！\n"); return; } dNode *p, *q = (dNode*) malloc(sizeof(dNode)); q->data = x; if(i == 0) // 在表头插入 { if(*head) // 链表非空时 { q->rLink = *head; q->lLink = (*head)->lLink; (*head)->lLink->rLink = q; (*head)->lLink = q; } else q->lLink = q->rLink = q; *head = q; return; } p = find(*head,i); if(p) { if(p->rLink == *head) // 如果p是尾结点 { (*head)->lLink->rLink = q; // 插入新结点 q->rLink = *head; q->lLink = (*head)->lLink; (*head)->lLink = q; } else { q->lLink = p; q->rLink = p->rLink; p->rLink->lLink = q; p->rLink = q; } } else printf("插入索引越界！\n"); } // 7.双链表中删除一个值为x的结点 void del(dLinkList *head, dataType x) { dNode *p = *head; if(!p) { printf("链表为空，无法删除！\n"); return; } if(p->data == x) // 首结点特殊处理 { if(p->rLink == *head) // 只有一个结点时 *head = NULL; else { p->rLink->lLink = p->lLink; p->lLink->rLink = p->rLink; (*head) = p->rLink; // 更新头指针 } free(p); return; } do { p = p->rLink; // 向后找到x结点 } while (p != *head && p->data != x); if(p == *head) // 表示循环回到头结点 { printf("没有找到这样的结点，无法删除！\n"); } else { if(p->rLink == *head) // 需要删除的是尾结点 { p->lLink->rLink = *head; (*head)->lLink = p->lLink; } else { p->lLink->rLink = p->rLink; p->rLink->lLink = p->lLink; } free(p); } } int main() { dLinkList list; // 声明指向双链表的头指针 init(&list); // 初始化双链表 for (int i = 1; i <= 5; i++) rearInsert(&list,i); // 插入结点 display(list); // 输出双链表 int i = 5; dNode *n = find(list,i); if(n) printf("链表的第%d个元素是%d\n",i,n->data); else printf("链表访问越界！\n"); dataType x = 6; printf("在第%d个位置后面插入元素%d\n",i,x); insert(&list,i,x); display(list); printf("删除一个值为%d的元素\n",x); del(&list,x); display(list); return 0; }
