数据结构笔记
本笔记主要根据华中科技大学计算机学院数据结构教材记录
有些内容则出自严蔚敏老师的《数据结构》
中间可能会有些撕裂~
绪论
基本概念和定义
数据 所有能进计算机的东西
数据元素 struct
数据项 struct里面的成员
数据对象 由同类数据元素组成的集合
数据结构 由数据元素组成的集合结构
存储结构 线性/非线性
数据类型 ElemType
抽象数据类型 ADT,约等于java里面的class
1 2 3 4 5
| ADT List { 数据对象:D 数据关系:S 操作P(约等于函数) } ADT ADTName
|
算法复杂度
时间复杂度
语句的执行次数叫做频度
频度是一个和数据个数 相关的函数
这个函数具有不同的阶数,基本分为 等
满足
空间复杂度
同上,递归函数基本是
正常函数都是
考试不常考
数列的一些算法
轮换计算单个项
1 2 3 4 5 6 7 8 9
| int fib1(int n) { int f1 = 1, f2 = 1, f = 1; while(n-- >= 3) { f = fi + f2; f1 = f2; f2 = f; } return f; }
|
空间不随着 的改变而改变,空间复杂度为 $ O(n) $
计算之后用数组 $ f $ 保存前面 $ n $ 项
1 2 3 4 5 6 7 8 9
| int fib2(int n) { int f[n] = {0}; f[0] = 1; f[1] = 1; for(int i = 2; i < n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n - 1]; }
|
由于有保存,空间复杂度为 $ O(n) $
使用递归
1 2 3 4 5 6
| int fib3(int n) { if(n <= 2) { return 1; } return fib3(n - 1) + fib3(n - 2); }
|
由于递归,空间复杂度与树深度成正比,空间复杂度为 $ O(n) $
的一些算法
最基本的冒泡排序,通过一步步冒泡让目前剩余项里面的最大值“冒”出来
1 2 3 4 5 6 7 8 9 10 11
| void bubble1(int a[], int n) { int temp; for(int i = 1; i < n; i++) for(int j = 0; j < n - i; j--) if(a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j - 1] = temp; } for(int i = 0; i < n; i++) printf("%d ", a[i]); }
|
改进思路
首先,通过 的思想锁定了它的时间复杂度必然是
既然无法通过优化时间复杂度来优化算法,那么就可以通过 提前截断(Early Termination)来一定程度上优化算法执行的时间
接下来讨论如何提前截断
在冒泡的时候什么行为会浪费时间呢?假如剩下的所有元素都已有序,那么循环便可以提前截断,否则只是重复地检查了多次 “该数组已经被排序” 这一个事实。所以我们引入了一个变量来记录数组剩下的部分是否有序,这样来提前截断排序过程。
以下是书上的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void bubble2(int a[], int n) { int i = n - 1; int temp, change; do { change = 0; int j; for(j = 0; j < i; j++) if(a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; change = 1; } } while(change && --i >= 1); }
|
以下是我仿照基础的代码改的,也许可以更好地两相对比
1 2 3 4 5 6 7 8 9 10 11 12 13
| void bubble2(int a[], int n) { int temp, change = 1; for(int i = 1; i < n; i++) { if(change == 0) break; change = 0; for(int j = 0; j < n - i; j++) if(a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; change = 1; } } }
|
二分
问题:现在有 两个正序数组,分别有 个元素,现在希望找出其中第 小的数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| int getKthElement(int a[], int b[], int m, int n, int k) { int index1 = 0, index2 = 0; int c_A, c_B; while(k != 1) { if(index1 == m) return B[index2 + k - 1]; if(index2 == n) return A[index1 + k - 1]; c_A = (index1 + k / 2 < m) ? (index1 + k / 2 - 1) : (m - 1); c_B = (index2 + k / 2 < n) ? (index2 + k / 2 - 1) : (n - 1); if(A[c_A] <= B[c_B]) { k -= c_A - index1 + 1; index1 = c_A + 1; } else { k -= c_B - index2 + 1; index2 = c_B + 1; } } return A[index1] < B[index2] ? A[index1] : B[index2]; }
|
时间复杂度 ,空间复杂度
线性表
概念摘要
数据项 线性表中的一个数据元素的成员
记录 线性表中的一个数据元素
文件 含有大量记录的线性表
ADT定义见书,在此不做赘述
算法摘要
对于集合 ,求集合 中的元素
1 2 3 4 5 6 7
| void union(List &La, List &b) { La_len = ListLength(La); Lb_len = ListLength(Lb); for(int i = i; i < Lb_len; i++) { GetElem(Lb, i, e); if(!LocateElem(La, e, equal)) ListInsert(La, ++La_len, e); } }
|
顺序表
定义
顺序存储结构的线性表完整定义如下:
1 2 3 4 5 6
| #define MaxLength 100 typedef struct { ElemType elem[MaxLength]; int length; int last; } Sqlist;
|
不难发现这里 last
其实和 length
是相关的,因此一般定义时只需要保留其中一个即可,例如:
1 2 3 4 5
| #define MaxLength 100 typedef struct { ElemType elem[MaxLength]; int length; } SqList;
|
顺序存储结构的顺序表有以下的动态分配定义:
1 2 3 4 5 6 7
| #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ELemType *elem; int length; int listsize; } SqList;
|
插入新元素
静态分配链表插入如下:
1 2 3 4 5 6 7 8 9 10 11
| Status Insert(SqList *L, int i, ELemType e) { int j; if(i < 1 || i > L->length + 1) return ERROR; if(L->length > MaxLength) return OVERFLOW; for(j = L->length-1; j >= i - 1; j--) L->elem[j+1] = L->elem[j]; L->elem[i-1] = e; L->length++; return OK; }
|
动态分配链表插入如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| Status Insert(SqList *L, int i, ElemType e) { int j; if(i < 1 || i > L->length + 1) return ERROR; if(L->length >= L->listsize) { ElemType *newbase; newbase = (ElemType*)realloc(L->elem, sizeof(ElemType) * (L->listsize + LISTINCREMENT)); if(newbase == NULL) return OVERFLOW; L->elem = newbase; L->listsize += LISTINCREMENT; } for(j = L->listsize - 1; j >= i-1; j--) L->elem[j+1] = L->elem[j]; L->elem[i-1] = e; L->length++; return OK; }
|
删除新元素
1 2 3 4 5 6 7 8 9 10
| Status Delete(SqList &L, int i) { if(i < 1 || i > L->length) return ERROR; int j; for(j = 1; j <= L->length-1; j++) L->elem[j-1] = L->elem[j]; L->length--; return OK; }
|
链表
单个节点的声明:
1 2 3 4
| typedef struct node { ElemType data; node* next; } node, *Linklist;
|
先进先出链表:
1 2 3 4 5 6 7 8 9 10 11 12 13
| Status addNode(linklist &List) { node a; tail->next = &a; tail = &a; return OK; }
Status delNode(linklist &List, int x) { linklist p = head; head = head->next; free(p); return OK; }
|
先进后出链表:
1 2 3 4 5 6 7 8 9 10 11 12 13
| Status addNode(linklist &List) { node a; a.next = head; head = &a; return OK; }
Status delNode(linklist &List) { linklist p; head = p->next; free(p); return OK; }
|
循环单链表
求表长
1 2 3 4 5 6 7 8 9 10 11
| int length(node *head) { int len = 0; node *p; p = head->next; while(p != head) { printf("%d", p->data); len++; p = p->next; } return len; }
|
双向链表
节点定义
1 2 3 4
| typedef struct Dnode { ElemType data; Dnode *prior, *next; } Dnode, *DLList;
|
算法大合集
递增有序单链表生成
问题阐述 输入一列整数,以 0 为结束标志,生成递增有序单链表(不包括 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
| node* InsertList1(node *head, int e) { node *q = NULL; node *p = head; while(p && e > p->data) { q = p; p = p->next; } node *f = (node *)malloc(LENG); f->data = e; if(p == NULL) { f->next = NULL; if(q == NULL) head = f; else q->next = f; } else if(q == NULL) { f->next = p; head = f; } else {f->next = p; q->next = f;} return head; }
int main() { node *head; head = NULL; int e; scanf("%d", &e); while(e != 0) { head = InsertList1(head, e); scanf("%d", &e); } return 0; }
|
带表头节点的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| node * InsertListII(node *head, int e) { node *q = NULL; node *p = head->next; while(p && e>p->data) { q = p; p = p->next; } node *f = (node *)malloc(LENG); f->data = e; f->next = p; q->next = f; }
int main() { node *head = (node *)malloc(LENG); head->next = NULL; int e; while(e != 0) { head = InsertList2(head, e); scanf("%d", &e); } return 0; }
|
单链表插入、删除算法
插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| Status insert(Linklist L, int i, ElemType e) { node *p = L; int j = 1; while(p && j < i) { p = p->next; j++; } if(i < 1 || p == NULL) return ERROR; node *f = (node *)malloc(LENG); f->data = e; f->next = p->next; p ->next = f; return OK; }
|
删除
1 2 3 4 5 6 7 8 9 10 11 12
| Status Delete(Linklist head, int e) { while(p && p->data != e) { q = p; p = p->next; } if(p) { q->next = p->next; free(p); return YES; } return ERROR; }
|
删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| Status Delete(Linklist L, int i) { node *p = L; int j = 1; while(p->next && j < i) { p = p->next; j++; } if(i<1 || p->next == NULL) return ERROR; node *q = p->next; p->next = q->next; free(q); return OK; }
|
单链表合并算法
将两个带表头结点的有序单链表 La 和 Lb 合并为有序单链表 Lc, 该算法利用单链表的节点。
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
| void mergeList(Linklist La, Linklist Lb, Linklist Lc) { struct node *pa, *pb, *pc; pa = La->next; pb = Lb->next; pc = La; free(Lb); while(pa && pb) { if(pa->data <= pb->data) { pc->next = pa; pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } } while(pa != NULL) { pc->next = pa; pa = pa->next; } while(pb != NULL) { pc->next = pb; pb = pb->next; } }
|
单链表的逆置
递归
1 2 3 4 5 6 7 8 9 10 11 12 13
| void reverse1(Linklist L) { Linklist p,q; if(L->next == NULL) return; p = L; q = L->next; while(q->next) { p = q; q = q->next; } p->next = NULL; reverse1(L); q->next = L->next; L->next = q; }
|
递归
1 2 3 4 5 6 7 8 9
| void reverse2(Linklist L) { Linklist p = L->next; if(L->next == NULL || p->next == NULL) return; L->next = p->next; reverse2(L); p->next->next = p; p->next = NULL; }
|
折半与递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| Linklist reverse3(Linklist L) { node *p, *q; if(!L->next || !L->next->next) return L; node* L1 = (node *)malloc(LENG); p = q = L; while(q) { q = q->next; if(q) { q = q->next; p = p->next; } } q = p->next; L1->next = q; p->next = NULL; L = reverse3(L); L1 = reverse3(L1); q->next = L->next; free(L); L = L1; return L; }
|
优化算法
1 2 3 4 5 6 7 8 9 10 11
| void reverse4(Linklist L) { node *p, *q; p = L->next; L->next = NULL; while(p) { q = p->next; p->next = L->next; L->next = p; p = q; } }
|
栈
概念
进栈 push 向栈中插入一个元素
出栈 pop 从栈删除一个元素
栈顶 允许插入、删除元素的一端
栈顶元素 处在栈顶位置的元素(表尾元素)
栈底 不允许插入、删除元素的一端(表头)
空栈 不含元素的栈
基本结构
顺序静态结构
1 2 3 4 5 6
| typedef struct { ElemType elem[LENGTH]; int top; } SqStack; SqStack S;
|
顺序动态结构
1 2 3 4 5 6 7 8 9 10 11 12 13
| #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { ELemType *base; int top; int stacksize; } SqStack; void InitStack(SqStack *S) { S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); S.top = 0; S.stacksize = STACK_INIT_SIZE; }
|
顺序栈方法
进栈
1 2 3 4 5 6 7 8 9 10 11 12 13
| Status Push(SqStack *S, ElemType e) { if(S.top >= S.stacksize) { ElemType *newbase = (ElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType)); if(!newbase) { return OVERFLOW; } S.base = newbase; S.stacksize += STACKINCREMENT; } S.base[S.top] = e; S.top++; return OK; }
|
出栈
1 2 3 4 5 6
| Status Pop(SqStack &S, ElemType &e) { if(S.top == 0) return OVERFLOW; S.top--; e = S.base[top]; return OK; }
|
链式栈方法
链式栈结构
1 2 3 4 5
| typedef struct node { ElemType data; struct node* next; } Unit, *StackNode, *top = NULL;
|
链式栈的 方法
1 2 3 4 5 6 7 8 9
| StackNode Push_link(StackNode top, ElemType e) { StackNode *p; int length = sizeof(Unit); p = (StackNode)malloc(length); p->data = e; p->next = top; top = p; return top; }
|
链式栈的 方法
1 2 3 4 5 6 7 8 9
| StackNode Pop_link(StackNode top, ElemType *e) { StackNode p; if(top == NULL) return NULL; p = top; (*e) = p->data; top = top->next; free(p); return top; }
|
栈的应用
数值转换
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| char * base_convert(int x, int base) { SqStack S; int e; InitStack(S); while(x != 0) { Push(S, x % base); x /= base; } char * res = (char *)malloc((S.top + 1) * sizeof(char)); int i = 0; int *e = &i; while(Pop(S, e) == OK) res[i++] = (char)e + 48; res[i] = '\0'; return res; }
|
括号匹配
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| int bracket_match(char brackets[]) { SqStack S; ElemType e; InitStack(S); for(int i = 0; i < strlen(brackets); i++) { char c = brackets[i], x; switch(c) { case ')': if(Pop(S, x) == OK && x == '(') break; else return false; case ']': if(Pop(S, x) == OK && x == '[') break; else return false; case '}': dafault: Push(S, c); } } return StackEmpty(S); }
|
表达式求值
运算符优先级关系表(其中 #
用来标记程序是否运行完毕)
S1\S2 |
+ |
- |
* |
/ |
( |
) |
# |
+ |
> |
> |
< |
< |
< |
> |
> |
- |
> |
> |
< |
< |
< |
> |
> |
* |
> |
> |
> |
> |
< |
> |
> |
/ |
> |
> |
> |
> |
< |
> |
> |
( |
< |
< |
< |
< |
< |
= |
|
) |
> |
> |
> |
> |
|
> |
> |
# |
< |
< |
< |
< |
< |
|
= |
上表中,左侧代表第一个符号,上方代表第二个符号。由以上的关系可以得到下方的表达式求值方法
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
| int eval(char *s) { SqStack_Int s1; SqStack_Char s2; InitStack(s1); InitStack(s2); int i = -1, result; Push(s2, s[++i]); char w = s[++i], e; while(w != '#' || GetTop(s2, e) == OK && e != '#') { if('0' <= w && w <= '9') { int num = 0; while('0' <= w && w <= '9') { num = num * 10 + (w - '0'); w = s[++i]; } Push(s1, num); } } else { GetTop(s2, e); int res = prior(e, w); if(res == -1) Push(s2, w); w = s[++i]; else if(res == 0 && w == ')') Pop(s2, e); w = s[++i]; else if(res == 1) { int a = 0, b = 0; Pop(s2, e); Pop(s1, b);Pop(s1, a); switch(e) { case '+': Push(s1, a+b); break; case '-': Push(s1, a-b); break; case '*': Push(s1, a*b); break; case '/': Push(s1, a/b); break; } } else { return ERROR; } } GetTop(s1, result); return result; }
int prior(char a, char b) { if(a == '+' || a == '-') { if(b == '*' || b == '/' || b == '(') return -1; else return 1; } else if(a == '*' || a == '/') { if(b == '(') return -1; else return 1; } else if(a == '(') { if(b == ')') return 0; else if(b == '#') return ERROR; else return -1; } else if(a == ')') { if(b == '(') return ERROR; else return 1; } else if(a == '#') { if(b == '#') return 0; else if(b == ')') return ERROR; else return -1; } return ERROR; }
|
队列
概念
空队列 不含元素的队列
队首 队列中只允许删除元素的一端。一般称为 front 或 head
队尾 队列中只允许插入元素的一端。一般称为 rear 或 tail
队首元素 处于队首的元素
队尾元素 处于队尾的元素
进队 插入一个元素到队列中。也称为入队
出队 从队列中删除一个元素
顺序基本结构
静态顺序存储结构
1 2 3 4 5 6
| #define MAXLENGTH 100 typedef struct { ELemType elem[MAXLENGTH]; int front, rear; } SeQueue; SeQueue Q;
|
//动态顺序存储结构(书上没提,照猫画虎)
1 2 3 4 5 6
| #define MAXLENGTH 100 #define INCREMENT 10 typedef struct { ElemType *elem; int front, rear; } SeQueue;
|
顺序队列方法
入队
1 2 3 4 5 6 7
| Status En_Queue(SqQueue &Q, ElemType e) { if((Q.rear + 1) % MAXLENGTH == Q.front) return OVERFLOW; Q.elem[Q.rear] = e; Q.rear++; Q.rear %= MAXLENGTH; return OK; }
|
出队
1 2 3 4 5 6
| Status De_Queue(SqQueue &Q, ElemType e) { if(Q.front == Q.rear) return ERROR; e = Q.elem[Q.front]; Q.front = (Q.front + 1) % MAXLENGTH; return OK; }
|
链式存储结构
存放元素的节点类型定义
1 2 3 4
| typedef struct Qnode { ELemType data; struct Qnode *next; } Qnode, *QnodePtr;
|
由头尾元素构成的链表基本定义
1 2 3 4
| typedef struct { Qnode *front; Qnode *rear; } LinkQueue;
|
空队列生成方法
1 2 3 4 5
| #define LENGTH sizeof(Qnode) void InitQueue(LinkQueue Q) { Q.front = Q.rear = (QueuePtr)malloc(LENGTH); Q.front->next = NULL; }
|
队列插入方法
1 2 3 4 5 6 7 8 9
| Status EnQueue(LinkQueue &Q, ElemType e) { Qnode *p = (Qnoode *)malloc(sizeof(LENGTH)); if(!p) return ERROR; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; }
|
队列删除算法
1 2 3 4 5 6 7 8 9
| Status DeQueue(LinkQueue &Q, ElemType e) { if(Q.front == Q.rear) return ERROR; Queue *p = Q.front->next; Q.front->next = p->next; e = p->data; if(Q.rear == p) Q.rear = Q.front; free(p); return OK; }
|
栈的应用实例
编码
现在有一种简易的编码规则为 k[encoded_string] ,它表示方括号内部的 encoded_string 刚好重复 k 次、
例如,字符串 2[ab]3[c]def 表示的字符串是 ababcccdef
另外,这种编码允许嵌套,解码的时候需要由左向右,由内到外进行嵌套。
例如,字符串 3[a2[bc]]2[d] 表示的字符串是 abcbcabcbcabcbcdd
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
| string decode(string str) { SqStack_Int s1; SqStack_String s2; InitStack(s1); InitStack(s2); for(int i = 0; i < str.length(); i++) { char ch = str[i]; int num = 0; if(isdigit(ch)) { while(isdigit(ch)) { num = num * 10 + (ch - '0'); ch = str[++i]; } Push(s1, num); i--; } else if(isalpha(ch)) { Push(s2, string(1, ch)); } else if(ch == ']') { Pop(s1, num); string top = "", tmp = "", repeat = ""; while(Pop(s2, top) && top != "[") tmp = top + tmp; while(num--) repeat += tmp; Push(s2, repeat); } } string res = "", tmp = ""; while(Pop(s2, tmp)) res = tmp + res; return res; }
|
队列的应用实例
银行排队叫号系统
问题背景:在银行办理业务时,客户依次取号进入客户队列排队,然后根据银行广播提示,到指定的空闲窗口办理业务。
1 2 3 4 5
| typedef struct Customer { int index; int window; int time; } Customer;
|
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
| void bank_service(int n, int serviceTime) { LinkQueue wait_queue; InitQueue(wait_queue); Customer *windows[n]; for(int i = 0; i < n; i++) windows[i] = (Customer *)malloc(sizeof(Customer)); int windowsStatus[n]; for(int i = 0; i < n; i++) windows_status[i] = 0; int idx = 0; for(int t = 0; t < serviceTime || !QueueEmpty(wait_queue) || !AllWindowsEmpty; t++) { printf("time now: %d\n", t); if(t < service) { if(rand() % (1 + n)) { Customer c; c.index = ++idx; c.time = 1 + rand() % 5; EnQueue(wait_queue, c); printf("%d 号客户入队,模拟时长为%d\n", idx, c.time); } } for(int i = 0; i < n; i++) { if(WindowsStatus[i]) { if(--windows[i]->time <= 0) { printf("%d 号客户离开窗口%d", windows[i]->index, windows[i]->window); WindowsStatus[i] = 0; } } if(!WindowsStatus[i] && !QueueEmpty(wait_queue)) { DeQueue(wait_queue, *windows[i]); windows[i]->window = i+1; windowsStatus[i] = 1; printf("请 %d 号客户到 %d 号窗口办理业务", windows[i]->index, windows[i]->window); } } printf("\n"); } for(int i = 0; i < n; i++) free(windows[i]); }
|
字符串
概念
字符串 由零个或者多个字符组成的有限序列,一般记为 $ S = \space “a_1 \space a_2 \space a_3 …a_n” $
串值 双引号内的内容
串长 n 的大小
空串 n = 0
空格串 仅含若干空格的字符串
存储结构
静态存储分配的字符串
也被称为串的定长顺序存储表示
1 2 3
| #define MAXLENGTH 256 typedef unsigned char SeqString[MAXLENGTH]; SeqString S;
|
这个时候可能有人要问了,主播主播,你这个有点太简单了,我们数据结构应该实现的东西不是应该都非常具有结构吗?
有的,结构我们是有的,毕竟我们在这本书里已经学过了 顺序表
1 2 3 4
| typedef struct { unsigned char ch[MAXLENGTH]; int length; } SeqString;
|
动态存储分配的字符串
1 2 3 4
| typedef struct { unsigned char *ch; int length; } HString;
|
串的链式存储
1 2 3 4
| typedef struct node { char data; struct node *next; } LinkStrNode, *LinkString;
|
在这里引入存储密度的概念,其公式为:
因此如果按以上的方式存储字符串,那么存储的无用信息比有用的还多,那就很神人了。
怎么提升这个存储密度呢?在一个节点里多塞几个信息就完了
1 2 3 4 5
| #define NODESIZE 4 typedef struct node { char data[NODESIZE]; struct node *next; } LinkStrNode, *LinkString;
|
这时候字符串增添啥的岂不是很麻烦啊!没事,反正也不用这种方式做算法~大模拟会写就完了
字符串的模式匹配算法
朴素的模式匹配算法
比较简单粗暴,大不了就一个一个字母进行比较嘛~怎么确定这个字符串完整的出现过了?从第一位开始一个一个比较就可以了,总体的一个一个比较需要拿另一个 index 来存储
1 2 3 4 5 6 7 8 9 10 11
| int StrIndex(SeqString S, SeqString T, int pos) { int i, j; for(int i = pos, j = 1; i <= S[0] - T[0] + 1;i++, j++) { if(S.ch[i] != T.ch[j]) { i = i - j + 1; j = 0; } else if(j == T.ch[0]) return i-j+1; } return 0; }
|
KMP模式匹配算法
不难发现,前面那个算法会导致每次一遇到不一样的就得回滚,实在是太麻烦了我天。那么有没有匹配的时候还能够灵活的调整匹配区间的算法呢?
假如一个字符串里面某个位置和前缀的某些元素相同,那么我可以通过存下相同前缀的位置来减少回滚的长度。
例如 ababc 这个字符串,不难发现abab里面都有 ab,那么遇到不一样的字符时可以首先考虑一直到对比位置的前缀相同位置是否都符合条件,以此来减少滚动长度。
我们完全可以通过另外保存一个数组来实现这个功能,即记录下当前字符串位置的前缀相同位置。
不妨将这个新的由位置组成的顺序表视作一个串,将其命名为next
Position j |
1 |
2 |
3 |
4 |
5 |
ModeString |
a |
b |
a |
b |
c |
next[j] |
0 |
1 |
1 |
2 |
1 |
其中 数组应该满足
这个 next 数组怎么求呢?
基于不同存储类型实现的一些其它字符串方法
串插入方法
串比较方法
串赋值算法
求子串方法
串联接方法
多维数组
广义表
树
二叉树
图(结构)
图的最小生成树问题
图的最短路径问题
排序
查找
大数据
后记