数据结构 (Data Structure)
人总对有规律的数据处理更得心应手，同样计算机对有规律的数据处理也更加方便(计算机语言毕竟是人写的嘛)。为了处理不同的问题的数据，我们可以通过不同的数据结构来构建，然后通过与之对应的特殊算法来处理，从而高效解决问题。
链状数据结构 (Linked Data Structure)
数组 (Array)
无序数组 (Unordered Array)
实现代码
#include <stdio.h>
#include <stdbool.h>
int *CreateArray(int maxLen, int *len)
{
*len = 0;
return (int *)malloc(maxLen * sizeof(int));
}
int InsertArray(int *array, int maxLen, int *len, int val)
{
if (*len + 1 >= maxLen) {
return -1;
}
array[*len] = val;
*len = *len + 1;
return 0;
}
int DeleteArray(int *array, int *len, int val)
{
for (int i = 0; i < *len; i++) {
if (array[i] == val) {
for (int j = i; j + 1 < *len; j++) {
array[j] = array[j + 1];
}
*len = *len - 1;
return 0;
}
}
return -1;
}
int UpdateArray(int *array, int len, int val, int updateVal)
{
for (int i = 0; i < len; i++) {
if (array[i] == val) {
array[i] = updateVal;
return 0;
}
}
return -1;
}
int SeletcArray(int *array, int len, int val)
{
for (int i = 0; i < len; i++) {
if (array[i] == val) {
return i;
}
}
return -1;
}
int DestoryArray(int *array)
{
free(array);
return 0;
}
void PrintfArray(int *array, int len)
{
printf("[");
for (int i = 0; i < len; i++) {
printf("%d", array[i]);
if (i < len - 1) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
int *array = NULL;
int maxLen = 1000;
int len = 0;
array = CreateArray(maxLen, &len);
InsertArray(array, maxLen, &len, 1);
InsertArray(array, maxLen, &len, 2);
InsertArray(array, maxLen, &len, 2);
InsertArray(array, maxLen, &len, 3);
InsertArray(array, maxLen, &len, 3);
InsertArray(array, maxLen, &len, 4);
InsertArray(array, maxLen, &len, 6);
DeleteArray(array, &len, 3);
DeleteArray(array, &len, 2);
UpdateArray(array, len, 6, 5);
printf("select=%d\r\n", SeletcArray(array, len, 5));
PrintfArray(array, len);
DestoryArray(array);
return 0;
}
有序数组 (Ordered Array)
定义
数组为递增或递降存储。由于是有序的，则在增删改查的时候可以用二分法
实现代码
#include <stdio.h>
#include <stdbool.h>
int *CreateArray(int maxLen, int *len)
{
*len = 0;
return (int *)malloc(maxLen * sizeof(int));
}
static int GetLocationFromArray(int *array, int len, int val)
{
int location = -1;
int l = 0, r = len - 1, m = (l + r) / 2;
while (l <= r) {
if (val < array[m]) {
r = m - 1;
m = (l + r) / 2;
} else if (val > array[m]) {
l = m + 1;
m = (l + r) / 2;
} else {
location = m;
break;
}
}
return location;
}
int InsertArray(int *array, int maxLen, int *len, int val)
{
if (*len + 1 >= maxLen) {
return -1;
}
int end = *len;
while (end - 1 >= 0 && val < array[end - 1]) {
array[end] = array[end - 1];
end--;
}
array[end] = val;
*len = *len + 1;
return 0;
}
int DeleteArray(int *array, int *len, int val)
{
for (int i = 0; i < *len; i++) {
if (array[i] == val) {
for (int j = i; j + 1 < *len; j++) {
array[j] = array[j + 1];
}
*len = *len - 1;
return 0;
}
}
return -1;
}
int UpdateArray(int *array, int len, int val, int updateVal)
{
int location = GetLocationFromArray(array, len, val);
if (location >= 0) {
if (updateVal > val) {
int end = location + 1;
array[location] = updateVal;
while (end < len && updateVal > array[end]) {
array[end - 1] = array[end];
array[end] = updateVal;
end++;
}
} else if (updateVal < val) {
int end = location - 1;
array[location] = updateVal;
while (end >= 0 && updateVal < array[end]) {
array[end + 1] = array[end];
array[end] = updateVal;
end--;
}
}
return 0;
}
return -1;
}
int SeletcArray(int *array, int len, int val)
{
return GetLocationFromArray(array, len, val);
}
int DestoryArray(int *array)
{
free(array);
return 0;
}
void PrintfArray(int *array, int len)
{
printf("[");
for (int i = 0; i < len; i++) {
printf("%d", array[i]);
if (i < len - 1) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
int *array = NULL;
int maxLen = 1000;
int len = 0;
array = CreateArray(maxLen, &len);
InsertArray(array, maxLen, &len, 1);
InsertArray(array, maxLen, &len, 2);
InsertArray(array, maxLen, &len, 2);
InsertArray(array, maxLen, &len, 3);
InsertArray(array, maxLen, &len, 3);
InsertArray(array, maxLen, &len, 4);
InsertArray(array, maxLen, &len, 6);
DeleteArray(array, &len, 3);
DeleteArray(array, &len, 2);
PrintfArray(array, len);
UpdateArray(array, len, 6, 5);
PrintfArray(array, len);
printf("select=%d\r\n", SeletcArray(array, len, 4));
UpdateArray(array, len, 5, 0);
PrintfArray(array, len);
printf("select=%d\r\n", SeletcArray(array, len, 0));
printf("select=%d\r\n", SeletcArray(array, len, 9));
DestoryArray(array);
return 0;
}
字符串 (String)
定义
全部为ascii字符组成，最后一位为'\0'
实现代码
#include <stdio.h>
#include <stdbool.h>
char *CreateString(int maxLen, int *len)
{
*len = 0;
return (char *)malloc(maxLen * sizeof(char));
}
int InsertString(char *str, int maxLen, int *len, char c)
{
if (*len + 1 >= maxLen) {
return -1;
}
str[*len] = c;
*len = *len + 1;
str[*len] = '\0';
return 0;
}
int DeleteString(char *str, int *len, char c)
{
for (int i = 0; i < *len; i++) {
if (str[i] == c) {
for (int j = i; j + 1 < *len; j++) {
str[j] = str[j + 1];
}
*len = *len - 1;
str[*len] = '\0';
return 0;
}
}
return -1;
}
int UpdateString(char *str, int len, char c, char updateC)
{
for (int i = 0; i < len; i++) {
if (str[i] == c) {
str[i] = updateC;
return 0;
}
}
return -1;
}
int SeletcString(char *str, int len, char c)
{
for (int i = 0; i < len; i++) {
if (str[i] == c) {
return i;
}
}
return -1;
}
int DestoryString(char *str)
{
free(str);
return 0;
}
void PrintfString(char *str)
{
printf("\"%s\"\r\n", str);
}
int main(void)
{
char *str = NULL;
int maxLen = 1000;
int len = 0;
str = CreateString(maxLen, &len);
InsertString(str, maxLen, &len, '1');
PrintfString(str);
InsertString(str, maxLen, &len, '2');
PrintfString(str);
InsertString(str, maxLen, &len, '3');
PrintfString(str);
InsertString(str, maxLen, &len, '3');
PrintfString(str);
InsertString(str, maxLen, &len, '4');
PrintfString(str);
InsertString(str, maxLen, &len, '6');
PrintfString(str);
DeleteString(str, &len, '3');
PrintfString(str);
UpdateString(str, len, '6', '5');
PrintfString(str);
printf("select=%d\r\n", SeletcString(str, len, '5'));
printf("select=%d\r\n", SeletcString(str, len, '0'));
DestoryString(str);
return 0;
}
栈 (Stack)
普通栈 (Normal Stack)
定义
先进后出后进先出链状数据结构
实现代码
#include <stdio.h>
#include <stdbool.h>
struct Stack {
int *buf;
int maxLen;
int end;
};
struct Stack *CreateStack(int maxLen)
{
struct Stack *s = (struct Stack *)malloc(sizeof(struct Stack));
s->buf = (int *)malloc(maxLen * sizeof(int));
s->maxLen = maxLen;
s->end = -1;
return s;
}
int PushStack(struct Stack *s, int val)
{
if (s->end + 1 >= s->maxLen) {
return -1;
}
s->buf[++s->end] = val;
return 0;
}
int PopStack(struct Stack *s)
{
if (s->end < 0) {
return -1;
}
return s->buf[s->end--];
}
int DestoryStack(struct Stack *s)
{
free(s->buf);
free(s);
return 0;
}
void PrintfStack(struct Stack *s)
{
printf("maxLen=%d,end=%d,buf=[", s->maxLen, s->end);
for (int i = 0; i <= s->end; i++) {
printf("%d", s->buf[i]);
if (i < s->end) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
struct Stack *s = NULL;
int maxLen = 1000;
s = CreateStack(maxLen);
PushStack(s, 3);
PrintfStack(s);
PushStack(s, 2);
PrintfStack(s);
PushStack(s, 1);
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
DestoryStack(s);
return 0;
}
单调栈 (Monotonic Stack)
定义
每次新入元素后保持栈有序
实现代码
#include <stdio.h>
#include <stdbool.h>
struct Stack {
int *buf;
int maxLen;
int end;
};
struct Stack *CreateStack(int maxLen)
{
struct Stack *s = (struct Stack *)malloc(sizeof(struct Stack));
s->buf = (int *)malloc(maxLen * sizeof(int));
s->maxLen = maxLen;
s->end = -1;
return s;
}
int PushStack(struct Stack *s, int val)
{
if (s->end + 1 >= s->maxLen) {
return -1;
}
int end = s->end + 1;
while (end - 1 >= 0 && val < s->buf[end - 1]) {
s->buf[end] = s->buf[end - 1];
end--;
}
s->buf[end] = val;
s->end += 1;
return 0;
}
int PopStack(struct Stack *s)
{
if (s->end < 0) {
return -1;
}
return s->buf[s->end--];
}
int DestoryStack(struct Stack *s)
{
free(s->buf);
free(s);
return 0;
}
void PrintfStack(struct Stack *s)
{
printf("maxLen=%d,end=%d,buf=[", s->maxLen, s->end);
for (int i = 0; i <= s->end; i++) {
printf("%d", s->buf[i]);
if (i < s->end) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
struct Stack *s = NULL;
int maxLen = 1000;
s = CreateStack(maxLen);
PushStack(s, 3);
PrintfStack(s);
PushStack(s, 2);
PrintfStack(s);
PushStack(s, 1);
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
printf("pop=%d\r\n", PopStack(s));
PrintfStack(s);
DestoryStack(s);
return 0;
}
最大频率栈 (Maximum Frequency Stack)
定义
出栈的时候返回出现频率最高的元素，如果频繁的元素不止一个，则返回最接近栈顶的元素
实现思路
通过哈希表记录每个值的数量，每次入栈+1 出栈-1
记录一个最大的频率值
每个频率值用一个栈
实现代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct Stack {
int *buf;
int maxLen;
int end;
};
struct Stack *CreateStack(int maxLen)
{
struct Stack *s = (struct Stack *)malloc(sizeof(struct Stack));
s->buf = (int *)malloc(maxLen * sizeof(int));
s->maxLen = maxLen;
s->end = -1;
return s;
}
int PushStack(struct Stack *s, int val)
{
if (s->end + 1 >= s->maxLen) {
return -1;
}
s->buf[++s->end] = val;
return 0;
}
int PopStack(struct Stack *s)
{
if (s->end < 0) {
return -1;
}
return s->buf[s->end--];
}
int DestoryStack(struct Stack *s)
{
free(s->buf);
free(s);
return 0;
}
void PrintfStack(struct Stack *s)
{
printf("maxLen=%d,end=%d,buf=[", s->maxLen, s->end);
for (int i = 0; i <= s->end; i++) {
printf("%d", s->buf[i]);
if (i < s->end) {
printf(",");
}
}
printf("]\r\n");
}
struct MaxFreqStack {
int maxFreq;
int curMaxFreq;
int *intHashMap;
struct Stack *stackTbl;
};
struct MaxFreqStack *CreateMaxFreqStack(int maxStackLen, int maxHashInt, int maxFreq)
{
struct MaxFreqStack *mfs = (struct MaxFreqStack *)malloc(sizeof(struct MaxFreqStack));
mfs->maxFreq = maxFreq;
mfs->curMaxFreq = 0;
mfs->intHashMap = (int *)malloc((maxHashInt + 1) * sizeof(int));
memset(mfs->intHashMap, 0, (maxHashInt + 1) * sizeof(int));
mfs->stackTbl = (struct Stack *)malloc((maxFreq + 1) * sizeof(struct Stack));
memset(mfs->stackTbl, 0, (maxFreq + 1) * sizeof(struct Stack));
for (int i = 0; i <= maxFreq; i++) {
mfs->stackTbl[i].buf = (int *)malloc(maxStackLen * sizeof(int));
mfs->stackTbl[i].maxLen = maxStackLen;
mfs->stackTbl[i].end = -1;
}
return mfs;
}
int PushMaxFreqStack(struct MaxFreqStack *mfs, int val)
{
mfs->intHashMap[val] += 1;
if (mfs->intHashMap[val] > mfs->curMaxFreq) {
mfs->curMaxFreq = mfs->intHashMap[val];
}
return PushStack(&mfs->stackTbl[mfs->intHashMap[val]], val);
}
int PopMaxFreqStack(struct MaxFreqStack *mfs)
{
if (mfs->curMaxFreq <= 0) {
return -1;
}
int ret = -1;
while (mfs->curMaxFreq != 0) {
ret = PopStack(&mfs->stackTbl[mfs->curMaxFreq]);
if (ret == -1) {
mfs->curMaxFreq -= 1;
} else {
mfs->intHashMap[ret] -= 1;
break;
}
}
return ret;
}
int DestoryMaxFreqStack(struct MaxFreqStack *mfs)
{
free(mfs->intHashMap);
for (int i = 0; i <= mfs->maxFreq; i++) {
free(mfs->stackTbl[i].buf);
}
free(mfs->stackTbl);
free(mfs);
return 0;
}
void PrintfMaxFreqStack(struct MaxFreqStack *mfs)
{
printf("maxFreq=%d,curMaxFreq=%d\r\n", mfs->maxFreq, mfs->curMaxFreq);
for (int i = 1; i <= mfs->curMaxFreq; i++) {
printf("freq=%d,", i);
PrintfStack(&mfs->stackTbl[i]);
}
}
int main(void)
{
struct MaxFreqStack *mfs = NULL;
mfs = CreateMaxFreqStack(100, 100, 10);
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 1);
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 2);
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 3);
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 3);
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 3);
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 2);
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
PushMaxFreqStack(mfs, 3);
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
printf("pop=%d\r\n", PopMaxFreqStack(mfs));
PrintfMaxFreqStack(mfs);
DestoryMaxFreqStack(mfs);
return 0;
}
队列 (Queue)
普通队列 (Normal Queue)
定义
先进先出、后进后出
实现代码
#include <stdio.h>
#include <stdbool.h>
struct Queue {
int *buf;
int maxLen;
int start, end;
};
struct Queue *CreateQueue(int maxLen)
{
struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
q->buf = (int *)malloc(maxLen * sizeof(int));
q->maxLen = maxLen;
q->start = -1;
q->end = -1;
return q;
}
int EnQueue(struct Queue *q, int val)
{
if (q->end + 1 >= q->maxLen) {
q->end = -1;
}
q->buf[++q->end] = val;
return 0;
}
int DeQueue(struct Queue *q)
{
if (q->start + 1>= q->maxLen) {
q->start = -1;
}
if (q->start == q->end) {
q->start = -1;
q->end = -1;
return -1;
}
return q->buf[++q->start];
}
int DestoryQueue(struct Queue *q)
{
free(q->buf);
free(q);
return 0;
}
void PrintfQueue(struct Queue *q)
{
printf("maxLen=%d,start=%d,end=%d,buf=[", q->maxLen, q->start, q->end);
for (int i = q->start + 1; i <= q->end; i++) {
printf("%d", q->buf[i]);
if (i < q->end) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
struct Queue *q = NULL;
int maxLen = 1000;
q = CreateQueue(maxLen);
EnQueue(q, 1);
PrintfQueue(q);
EnQueue(q, 2);
PrintfQueue(q);
EnQueue(q, 3);
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
DestoryQueue(q);
return 0;
}
优先队列 (Priority Queue)
定义
最大优先队列：无论入队顺序如何，都是当前最大的元素优先出队
最小优先队列：无论入队顺序如何，都是当前最小的元素优先出队
实现思路
利用二叉堆的思想。插入元素的时候上浮到合适位置；出队的时候，将原堆顶出队，把最后一个节点替换到堆顶，然后下沉到合适位置
实现代码
#include <stdio.h>
#include <stdbool.h>
struct Queue {
int *buf;
int maxLen;
int start, end;
};
static int GetParent(int pos)
{
return (pos - 1) / 2;
}
static int GetLeftChild(int pos)
{
return (2 * pos + 1);
}
static int GetRightChild(int pos)
{
return (2 * pos + 2);
}
static int swim(int *buf, int end)
{
int pos = end;
int parent = GetParent(pos);
while (pos >= 0 && parent >= 0 && buf[pos] > buf[parent]) {
int tmp = buf[pos];
buf[pos] = buf[parent];
buf[parent] = tmp;
pos = parent;
parent = GetParent(pos);
}
return 0;
}
static int sink(int *buf, int end)
{
int pos = 0;
int left = GetLeftChild(pos);
int right = GetRightChild(pos);
while (left <= end) {
int maxChild = left;
if (right <= end) {
maxChild = (buf[left] > buf[right]) ? left : right;
}
if (buf[pos] >= buf[maxChild]) {
break;
}
int tmp = buf[pos];
buf[pos] = buf[maxChild];
buf[maxChild] = tmp;
pos = maxChild;
left = GetLeftChild(pos);
right = GetRightChild(pos);
}
return 0;
}
struct Queue *CreateQueue(int maxLen)
{
struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
q->buf = (int *)malloc(maxLen * sizeof(int));
q->maxLen = maxLen;
q->start = -1;
q->end = -1;
return q;
}
int EnQueue(struct Queue *q, int val)
{
if (q->end + 1 >= q->maxLen) {
q->end = -1;
}
q->buf[++q->end] = val;
swim(q->buf, q->end);
return 0;
}
int DeQueue(struct Queue *q)
{
if (q->start + 1 >= q->maxLen) {
q->start = -1;
}
if (q->end < 0 || q->start == q->end) {
q->start = -1;
q->end = -1;
return -1;
}
int max = q->buf[0];
q->buf[0] = q->buf[q->end--];
sink(q->buf, q->end);
return max;
}
int DestoryQueue(struct Queue *q)
{
free(q->buf);
free(q);
return 0;
}
void PrintfQueue(struct Queue *q)
{
printf("maxLen=%d,start=%d,end=%d,buf=[", q->maxLen, q->start, q->end);
for (int i = q->start + 1; i <= q->end; i++) {
printf("%d", q->buf[i]);
if (i < q->end) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
struct Queue *q = NULL;
int maxLen = 1000;
q = CreateQueue(maxLen);
EnQueue(q, 1);
PrintfQueue(q);
EnQueue(q, 2);
PrintfQueue(q);
EnQueue(q, 3);
PrintfQueue(q);
EnQueue(q, 4);
PrintfQueue(q);
EnQueue(q, 10);
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
DestoryQueue(q);
return 0;
}
单调队列 (Monotonic Queue)
定义
每次队列新入元素后保持有序
实现代码
#include <stdio.h>
#include <stdbool.h>
struct Queue {
int *buf;
int maxLen;
int start, end;
};
struct Queue *CreateQueue(int maxLen)
{
struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
q->buf = (int *)malloc(maxLen * sizeof(int));
q->maxLen = maxLen;
q->start = -1;
q->end = -1;
return q;
}
int EnQueue(struct Queue *q, int val)
{
if (q->end + 1 >= q->maxLen) {
q->end = -1;
}
++q->end;
int pos = q->end;
q->buf[pos] = val;
while (pos - 1 > q->start && q->buf[pos - 1] > q->buf[pos]) {
q->buf[pos] = q->buf[pos - 1];
pos = pos - 1;
}
q->buf[pos] = val;
return 0;
}
int DeQueue(struct Queue *q)
{
if (q->start + 1>= q->maxLen) {
q->start = -1;
}
if (q->start == q->end) {
q->start = -1;
q->end = -1;
return -1;
}
return q->buf[++q->start];
}
int DestoryQueue(struct Queue *q)
{
free(q->buf);
free(q);
return 0;
}
void PrintfQueue(struct Queue *q)
{
printf("maxLen=%d,start=%d,end=%d,buf=[", q->maxLen, q->start, q->end);
for (int i = q->start + 1; i <= q->end; i++) {
printf("%d", q->buf[i]);
if (i < q->end) {
printf(",");
}
}
printf("]\r\n");
}
int main(void)
{
struct Queue *q = NULL;
int maxLen = 1000;
q = CreateQueue(maxLen);
EnQueue(q, 1);
PrintfQueue(q);
EnQueue(q, 2);
PrintfQueue(q);
EnQueue(q, 3);
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
printf("pop=%d\r\n", DeQueue(q));
PrintfQueue(q);
DestoryQueue(q);
return 0;
}
例子
单调队列解决滑动窗口问题
#include <limits.h>
void QEnter(int* q, int *qLen, int value)
{
int cur = (*qLen) - 1;
while (cur >= 0 && q[cur] < value) {
cur--;
}
q[cur + 1] = value;
*qLen = cur + 2;
}
void QOut(int* q, int *qLen, int value)
{
int cur = 0;
if (qLen > 0 && value == q[0]) {
while (cur < *qLen) {
q[cur] = q[cur + 1];
cur++;
}
(*qLen) -= 1;
}
}
int QMax(int* q, int *qLen)
{
return q[0];
}
int* maxInWindows(int* num, int numLen, int size, int* returnSize ) {
// write code here
int left = 0, right = 0;
*returnSize = numLen - size + 1;
int *outBuf = malloc((*returnSize) * sizeof(int));
int outPoi = 0;
int qBuf[numLen];
int qLen = 0;
for (right = 0; right < numLen; right++) {
QEnter(qBuf, &qLen, num[right]);
/*
printf("[");
for (int i = 0; i < qLen; i++) {
printf("%d ", qBuf[i]);
}
printf("]\r\n");
*/
if (right - left == size - 1) {
outBuf[outPoi++] = QMax(qBuf, &qLen);
QOut(qBuf, &qLen, num[left]);
left++;
}
}
return outBuf;
}
链表 (Linked List)
单向链表 (Single Linked List)
实现代码
#include <stdio.h>
#include <stdbool.h>
struct LinkedList {
int val;
struct LinkedList *next;
};
static struct LinkedList *CreateLinkedList(int val)
{
struct LinkedList *node = (struct LinkedList *)malloc(sizeof(struct LinkedList));
node->val = val;
node->next = NULL;
return node;
}
int AddLinkedList(struct LinkedList **head, int val)
{
struct LinkedList *node = CreateLinkedList(val);
if (*head == NULL) {
*head = node;
} else {
struct LinkedList *pre = *head;
struct LinkedList *cur = (*head)->next;
while (cur != NULL) {
pre = cur;
cur = cur->next;
}
pre->next = node;
}
return 0;
}
int DelLinkedList(struct LinkedList **head, int val)
{
if (*head != NULL) {
struct LinkedList dummy;
struct LinkedList *pre;
struct LinkedList *cur;
dummy.next = *head;
pre = &dummy;
cur = *head;
while (cur != NULL) {
if (cur->val == val) {
pre->next = cur->next;
free(cur);
cur = NULL;
*head = dummy.next;
break;
}
pre = cur;
cur = cur->next;
}
}
return 0;
}
int DestoryLinkedList(struct LinkedList **head)
{
if (*head != NULL) {
struct LinkedList *pre = *head;
struct LinkedList *cur = *head;
while (cur != NULL) {
pre = cur;
cur = cur->next;
free(pre);
pre = NULL;
}
*head = NULL;
}
return 0;
}
void PrintfLinkedList(struct LinkedList *head)
{
printf("head=%p, buf=[", head);
if (head != NULL) {
struct LinkedList *cur = head;
while (cur != NULL) {
printf("%d", cur->val);
cur = cur->next;
if (cur != NULL) {
printf(",");
}
}
}
printf("]\r\n");
}
int main(void)
{
struct LinkedList *head = NULL;
AddLinkedList(&head, 1);
PrintfLinkedList(head);
AddLinkedList(&head, 2);
PrintfLinkedList(head);
AddLinkedList(&head, 3);
PrintfLinkedList(head);
DelLinkedList(&head, 1);
PrintfLinkedList(head);
DelLinkedList(&head, 2);
PrintfLinkedList(head);
DelLinkedList(&head, 3);
PrintfLinkedList(head);
DelLinkedList(&head, 3);
PrintfLinkedList(head);
DestoryLinkedList(&head);
return 0;
}
循环链表 (Circular Linked List)
定义
尾节点指向头结点
实现代码
#include <stdio.h>
#include <stdbool.h>
struct LinkedList {
int val;
struct LinkedList *next;
};
static struct LinkedList *CreateLinkedList(int val)
{
struct LinkedList *node = (struct LinkedList *)malloc(sizeof(struct LinkedList));
node->val = val;
node->next = NULL;
return node;
}
int AddLinkedList(struct LinkedList **head, int val)
{
struct LinkedList *node = CreateLinkedList(val);
if (*head == NULL) {
*head = node;
node->next = *head;
} else {
struct LinkedList *pre = *head;
struct LinkedList *cur = (*head)->next;
while (cur != *head) {
pre = cur;
cur = cur->next;
}
pre->next = node;
node->next = *head;
}
return 0;
}
int DelLinkedList(struct LinkedList **head, int val)
{
if (*head != NULL) {
struct LinkedList *pre;
struct LinkedList *cur;
pre = *head;
cur = (*head)->next;
while (cur != *head) {
if (cur->val == val) {
break;
}
pre = cur;
cur = cur->next;
}
if (cur->val == val) {
pre->next = cur->next;
if (cur == *head) {
*head = (pre == *head) ? (NULL) : (pre);
}
free(cur);
}
}
return 0;
}
int DestoryLinkedList(struct LinkedList **head)
{
if (*head != NULL) {
struct LinkedList *pre = *head;
struct LinkedList *cur = (*head)->next;
while (cur != *head) {
pre = cur;
cur = cur->next;
free(pre);
pre = NULL;
}
*head = NULL;
}
return 0;
}
void PrintfLinkedList(struct LinkedList *head)
{
printf("head=%p, buf=[", head);
if (head != NULL) {
struct LinkedList *pre = head;
struct LinkedList *cur = head->next;
while (cur != head) {
printf("%d,", pre->val);
pre = cur;
cur = cur->next;
}
printf("%d", pre->val);
}
printf("]\r\n");
}
int main(void)
{
struct LinkedList *head = NULL;
AddLinkedList(&head, 1);
PrintfLinkedList(head);
AddLinkedList(&head, 2);
PrintfLinkedList(head);
AddLinkedList(&head, 3);
PrintfLinkedList(head);
DelLinkedList(&head, 1);
PrintfLinkedList(head);
DelLinkedList(&head, 2);
PrintfLinkedList(head);
DelLinkedList(&head, 3);
PrintfLinkedList(head);
DelLinkedList(&head, 3);
PrintfLinkedList(head);
DestoryLinkedList(&head);
return 0;
}
双向链表 (Doubly Linked List)
实现代码
#include <stdio.h>
#include <stdbool.h>
struct LinkedList {
int val;
struct LinkedList *prior;
struct LinkedList *next;
};
static struct LinkedList *CreateLinkedList(int val)
{
struct LinkedList *node = (struct LinkedList *)malloc(sizeof(struct LinkedList));
node->val = val;
node->prior = NULL;
node->next = NULL;
return node;
}
int AddLinkedList(struct LinkedList **head, int val)
{
struct LinkedList *node = CreateLinkedList(val);
if (*head == NULL) {
*head = node;
} else {
struct LinkedList *pre = *head;
struct LinkedList *cur = (*head)->next;
while (cur != NULL) {
pre = cur;
cur = cur->next;
}
pre->next = node;
node->prior = pre;
}
return 0;
}
int DelLinkedList(struct LinkedList **head, int val)
{
if (*head != NULL) {
struct LinkedList dummy;
struct LinkedList *pre;
struct LinkedList *cur;
dummy.next = *head;
pre = &dummy;
cur = *head;
while (cur != NULL) {
if (cur->val == val) {
pre->next = cur->next;
if (cur->next != NULL) {
cur->next->prior = pre;
}
free(cur);
cur = NULL;
*head = dummy.next;
break;
}
pre = cur;
cur = cur->next;
}
}
return 0;
}
int DestoryLinkedList(struct LinkedList **head)
{
if (*head != NULL) {
struct LinkedList *pre = *head;
struct LinkedList *cur = *head;
while (cur != NULL) {
pre = cur;
cur = cur->next;
free(pre);
pre = NULL;
}
*head = NULL;
}
return 0;
}
void PrintfLinkedList(struct LinkedList *head)
{
printf("head=%p, buf=[", head);
if (head != NULL) {
struct LinkedList *cur = head;
while (cur != NULL) {
printf("%d", cur->val);
cur = cur->next;
if (cur != NULL) {
printf(",");
}
}
}
printf("]\r\n");
}
int main(void)
{
struct LinkedList *head = NULL;
AddLinkedList(&head, 1);
PrintfLinkedList(head);
AddLinkedList(&head, 2);
PrintfLinkedList(head);
AddLinkedList(&head, 3);
PrintfLinkedList(head);
DelLinkedList(&head, 1);
PrintfLinkedList(head);
DelLinkedList(&head, 2);
PrintfLinkedList(head);
DelLinkedList(&head, 3);
PrintfLinkedList(head);
DelLinkedList(&head, 3);
PrintfLinkedList(head);
DestoryLinkedList(&head);
return 0;
}
双向循环链表 (Doubly Circular Linked List)
树状数据结构 (Tree Data Structure)
哈希表(Hash Table)
- 普通哈希表(Hash Table)
参考
实现代码
静态实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define MAX_HASH_MAP_SIZE 1000
#define MAX_HASH_MAP_LINK_LEN 100
#define MAX_KEY_LEN 30
#define MAX_VALUE_LEN 30
struct HashMapNode {
char key[MAX_KEY_LEN];
char value[MAX_VALUE_LEN];
};
struct HashMapNode g_HashMap[MAX_HASH_MAP_SIZE][MAX_HASH_MAP_LINK_LEN];
void InitHashMap(void)
{
memset(g_HashMap, 0, sizeof(g_HashMap));
}
static int KeyToIndex(char* key)
{
int index = 0;
while (*key != '\0') {
index += *key;
key++;
}
return index;
}
struct HashMapNode *FindKeyEmptyNode(char *key)
{
int index = KeyToIndex(key);
struct HashMapNode *head = g_HashMap[index];
for (int i = 0; i < MAX_HASH_MAP_LINK_LEN; i++) {
if (head[i].key[0] == '\0') {
return &head[i];
}
}
return NULL;
}
struct HashMapNode *FindKeyNode(char *key)
{
int index = KeyToIndex(key);
struct HashMapNode *head = g_HashMap[index];
for (int i = 0; i < MAX_HASH_MAP_LINK_LEN; i++) {
if (strcmp(head[i].key, key) == 0) {
return &head[i];
}
}
return NULL;
}
int AddHashMap(char *key, char *value)
{
struct HashMapNode *node = FindKeyEmptyNode(key);
strcpy(node->key, key);
strcpy(node->value, value);
return 0;
}
int DelHashMap(char *key)
{
struct HashMapNode *node = FindKeyNode(key);
memset(node, 0, sizeof(struct HashMapNode));
return 0;
}
char *SearchHashMap(char *key)
{
struct HashMapNode *node = FindKeyNode(key);
return node->value;
}
int DestoryHashMap(void)
{
return 0;
}
void PrintfHashMap(void)
{
printf("HaspMap=[\r\n");
for (int i = 0; i < MAX_HASH_MAP_SIZE; i++) {
bool isEmpty = true;
for (int j = 0; j < MAX_HASH_MAP_LINK_LEN; j++) {
if (g_HashMap[i][j].key[0] != '\0') {
isEmpty = false;
break;
}
}
if (!isEmpty) {
printf("HashKey=%d [", i);
for (int j = 0; j < MAX_HASH_MAP_LINK_LEN; j++) {
if (g_HashMap[i][j].key[0] != '\0') {
printf("{%s->%s} ", g_HashMap[i][j].key, g_HashMap[i][j].value);
}
}
printf("]\r\n");
}
}
printf("]\r\n");
}
int main(void)
{
InitHashMap();
AddHashMap("jone", "60");
PrintfHashMap();
AddHashMap("david", "23");
PrintfHashMap();
AddHashMap("bluse", "34");
PrintfHashMap();
AddHashMap("mike", "100");
PrintfHashMap();
AddHashMap("mijf", "23");
PrintfHashMap();
printf("jone=%s\r\n", SearchHashMap("jone"));
DelHashMap("david");
PrintfHashMap();
DestoryHashMap();
return 0;
}
二叉树(Binary Tree)
普通二叉树 (Binary Tree)
实现代码
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
static struct TreeNode *CreateTreeNode(int val)
{
struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int AddTreeNode(struct TreeNode **root, int val)
{
struct TreeNode *node = CreateTreeNode(val);
if (*root == NULL) {
*root = node;
} else {
struct TreeNode *nextQueue[100];
int nextLen = 0;
struct TreeNode *curQueue[100];
int curLen = 0;
curQueue[curLen++] = *root;
while (curLen > 0) {
bool isFind = false;
for (int cur = 0; cur < curLen; cur++) {
if (curQueue[cur]->left == NULL) {
curQueue[cur]->left = node;
isFind = true;
break;
}
nextQueue[nextLen++] = curQueue[cur]->left;
if (curQueue[cur]->right == NULL) {
curQueue[cur]->right = node;
isFind = true;
break;
}
nextQueue[nextLen++] = curQueue[cur]->right;
}
if (isFind) {
curLen = 0;
} else {
memcpy(curQueue, nextQueue, nextLen * sizeof(struct TreeNode *));
curLen = nextLen;
nextLen = 0;
}
}
}
return 0;
}
int DelTreeNode(struct TreeNode **root, int val)
{
if (*root != NULL) {
struct TreeNode *findFather = NULL;
struct TreeNode *find = NULL;
struct TreeNode *endFather = NULL;
struct TreeNode *end = *root;
struct TreeNode *nextQueue[100];
int nextLen = 0;
struct TreeNode *curQueue[100];
int curLen = 0;
curQueue[curLen++] = *root;
if ((*root)->val == val) {
if (findFather == NULL) {
findFather = NULL;
find = *root;
}
}
while (curLen > 0) {
for (int cur = 0; cur < curLen; cur++) {
if (curQueue[cur]->left != NULL) {
nextQueue[nextLen++] = curQueue[cur]->left;
if (curQueue[cur]->left->val == val) {
if (findFather == NULL) {
findFather = curQueue[cur];
find = curQueue[cur]->left;
}
}
if (curQueue[cur]->left->left == NULL && curQueue[cur]->left->right == NULL) {
endFather = curQueue[cur];
end = curQueue[cur]->left;
}
}
if (curQueue[cur]->right != NULL) {
nextQueue[nextLen++] = curQueue[cur]->right;
if (curQueue[cur]->right->val == val) {
if (findFather == NULL) {
findFather = curQueue[cur];
find = curQueue[cur]->right;
}
}
if (curQueue[cur]->right->left == NULL && curQueue[cur]->right->right == NULL) {
endFather = curQueue[cur];
end = curQueue[cur]->right;
}
}
}
memcpy(curQueue, nextQueue, nextLen * sizeof(struct TreeNode *));
curLen = nextLen;
nextLen = 0;
}
if (find != NULL) {
if (endFather != NULL) {
if (endFather->left == end) {
endFather->left = NULL;
}
if (endFather->right == end) {
endFather->right = NULL;
}
}
if (findFather != NULL) {
if (findFather->left == find) {
findFather->left = end;
}
if (findFather->right == find) {
findFather->right = end;
}
}
end->left = find->left;
end->right = find->right;
if (find == *root) {
if (endFather == NULL) {
*root = NULL;
} else {
*root = end;
}
}
free(find);
}
}
return 0;
}
int DestoryTreeNode(struct TreeNode **root)
{
if (*root != NULL) {
struct TreeNode *nextQueue[100];
int nextLen = 0;
struct TreeNode *curQueue[100];
int curLen = 0;
while (curLen > 0) {
for (int cur = 0; cur < curLen; cur++) {
if (curQueue[cur]->left != NULL) {
nextQueue[nextLen++] = curQueue[cur]->left;
}
if (curQueue[cur]->right != NULL) {
nextQueue[nextLen++] = curQueue[cur]->right;
}
free(curQueue[cur]);
}
memcpy(curQueue, nextQueue, nextLen * sizeof(struct TreeNode *));
curLen = nextLen;
nextLen = 0;
}
*root = NULL;
}
return 0;
}
void PrintfTreeNode(struct TreeNode *root)
{
printf("root=%p, buf=[", root);
if (root != NULL) {
struct TreeNode *nextQueue[100];
int nextLen = 0;
struct TreeNode *curQueue[100];
int curLen = 0;
curQueue[curLen++] = root;
while (curLen > 0) {
for (int cur = 0; cur < curLen; cur++) {
if (curQueue[cur]->left != NULL) {
nextQueue[nextLen++] = curQueue[cur]->left;
}
if (curQueue[cur]->right != NULL) {
nextQueue[nextLen++] = curQueue[cur]->right;
}
printf("%d", curQueue[cur]->val);
if (!(cur == curLen - 1 && nextLen == 0)) {
printf(",");
}
}
memcpy(curQueue, nextQueue, nextLen * sizeof(struct TreeNode *));
curLen = nextLen;
nextLen = 0;
}
}
printf("]\r\n");
}
int main(void)
{
struct LinkedList *root = NULL;
AddTreeNode(&root, 1);
PrintfTreeNode(root);
AddTreeNode(&root, 2);
PrintfTreeNode(root);
AddTreeNode(&root, 3);
PrintfTreeNode(root);
AddTreeNode(&root, 4);
PrintfTreeNode(root);
AddTreeNode(&root, 5);
PrintfTreeNode(root);
PrintfTreeNode(root);
AddTreeNode(&root, 6);
PrintfTreeNode(root);
DelTreeNode(&root, 1);
PrintfTreeNode(root);
DelTreeNode(&root, 2);
PrintfTreeNode(root);
DelTreeNode(&root, 3);
PrintfTreeNode(root);
DelTreeNode(&root, 6);
PrintfTreeNode(root);
DelTreeNode(&root, 5);
PrintfTreeNode(root);
DelTreeNode(&root, 4);
PrintfTreeNode(root);
DelTreeNode(&root, 3);
PrintfTreeNode(root);
DestoryTreeNode(&root);
return 0;
}
字典树 (Trie)
实现代码
静态实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TRIE_SIZE 10000
#define ASCII_SIZE 256
struct TrieNode {
int next;
int cnt;
bool isEnd;
};
struct TrieNode g_trie[MAX_TRIE_SIZE][ASCII_SIZE];
static int g_nextEmptyNode;
void InitTrie(void)
{
memset(g_trie, 0, sizeof(g_trie));
g_nextEmptyNode = 0;
}
int SearchTrie(char *str)
{
int sLen = strlen(str);
int root = 0;
for (int i = 0; i < sLen; i++) {
if (g_trie[root][str[i]].next == 0) {
return -1;
}
root = g_trie[root][str[i]].next ;
}
return g_trie[root][str[sLen - 1]].isEnd ? 0 : -1;
}
int AddTrie(char *str)
{
int sLen = strlen(str);
int root = 0;
for (int i = 0; i < sLen; i++) {
if (g_trie[root][str[i]].next == 0) {
g_trie[root][str[i]].next = ++g_nextEmptyNode;
}
root = g_trie[root][str[i]].next;
if (i == sLen - 1) {
g_trie[root][str[i]].isEnd = true;
} else {
g_trie[root][str[i]].cnt++;
}
}
return 0;
}
int DelTrie(char *str)
{
if (SearchTrie(str) != 0) {
return -1;
}
int sLen = strlen(str);
int root = 0;
for (int i = 0; i < sLen; i++) {
g_trie[root][str[i]].cnt--;
root = g_trie[root][str[i]].next;
}
g_trie[root][str[sLen - 1]].isEnd = false;
return 0;
}
int GetPrefixWordAmountFormTrie(char *prefix)
{
int sLen = strlen(prefix);
int root = 0;
for (int i = 0; i < sLen; i++) {
g_trie[root][prefix[i]].cnt--;
root = g_trie[root][prefix[i]].next;
}
return g_trie[root][prefix[sLen - 1]].cnt;
}
int DestoryTrie(void)
{
return 0;
}
void PrintfTrieRecursive(int root, int curDepth, char *stack)
{
for (int i = 0; i < ASCII_SIZE; i++) {
if (g_trie[root][i].next == 0) {
continue;
}
stack[curDepth] = i;
if (g_trie[g_trie[root][i].next][i].isEnd) {
stack[curDepth + 1] = '\0';
printf("%s\r\n", stack);
}
PrintfTrieRecursive(g_trie[root][i].next, curDepth + 1, stack);
}
}
void PrintfTrie(void)
{
printf("buf=[\r\n");
char stack[100];
PrintfTrieRecursive(0, 0, stack);
printf("]\r\n");
}
int main(void)
{
InitTrie();
AddTrie("aaa");
PrintfTrie();
printf("GetPrefixWordAmountFormTrie=%d\r\n", GetPrefixWordAmountFormTrie("a"));
AddTrie("aba");
PrintfTrie();
DelTrie("aaa");
DelTrie("aaa");
printf("GetPrefixWordAmountFormTrie=%d\r\n", GetPrefixWordAmountFormTrie("a"));
PrintfTrie();
AddTrie("aab");
printf("GetPrefixWordAmountFormTrie=%d\r\n", GetPrefixWordAmountFormTrie("a"));
PrintfTrie();
AddTrie("zab");
PrintfTrie();
printf("GetPrefixWordAmountFormTrie=%d\r\n", GetPrefixWordAmountFormTrie("za"));
return 0;
}
动态实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define ASCII_SIZE 256
struct TrieNode {
int cnt;
bool isEnd;
struct TrieNode *next[ASCII_SIZE];
};
struct TrieNode *CreateTrieNode(void)
{
struct TrieNode *node = (struct TrieNode *)malloc(sizeof(struct TrieNode));
node->cnt = 0;
node->isEnd = false;
for (int i = 0; i < ASCII_SIZE; i++) {
node->next[i] = NULL;
}
return node;
}
int SearchTrie(struct TrieNode *root, char *str)
{
if (root == NULL) {
return -1;
}
int sLen = strlen(str);
struct TrieNode *cur = root;
for (int i = 0 ; i < sLen; i++) {
cur = cur->next[str[i]];
if (cur == NULL) {
return -1;
}
if (i == sLen - 1) {
if (!cur->isEnd) {
return -1;
}
} else {
if(cur->cnt == 0) {
return -1;
}
}
}
return 0;
}
int AddTrie(struct TrieNode **root, char *str)
{
int sLen = strlen(str);
if (*root == NULL) {
*root = CreateTrieNode();
}
if (SearchTrie(*root, str) == 0) {
return 0;
}
struct TrieNode *cur = *root;
for (int i = 0 ; i < sLen; i++) {
if (cur->next[str[i]] == NULL) {
cur->next[str[i]] = CreateTrieNode();
}
cur = cur->next[str[i]];
if (i == sLen - 1) {
cur->isEnd = true;
} else {
cur->cnt += 1;
}
}
return 0;
}
int DelTrie(struct TrieNode **root, char *str)
{
if (*root == NULL) {
return -1;
}
if (SearchTrie(*root, str) != 0) {
return -1;
}
int sLen = strlen(str);
struct TrieNode *cur = *root;
for (int i = 0 ; i < sLen; i++) {
cur = cur->next[str[i]];
if (i == sLen - 1) {
cur->isEnd = false;
} else {
cur->cnt -= 1;
}
}
return 0;
}
int GetPrefixWordAmountFormTrie(struct TrieNode *root, char *prefix)
{
if (root == NULL) {
return -1;
}
int sLen = strlen(prefix);
struct TrieNode *cur = root;
for (int i = 0 ; i < sLen; i++) {
cur = cur->next[prefix[i]];
if (cur == NULL) {
return -1;
}
if (i == sLen - 1) {
return cur->cnt;
}
}
return 0;
}
int DestoryTrie(struct TrieNode **root)
{
if (*root == NULL) {
return 0;
}
struct TrieNode *cur = *root;
for (int i = 0; i < ASCII_SIZE; i++) {
if (cur->next[i] != NULL) {
DestoryTrie(&cur->next[i]);
free(cur->next[i]);
}
}
free(*root);
*root = NULL;
return 0;
}
void PrintfTrieRecursive(struct TrieNode *root, int curDepth, char *stack)
{
for (int i = 0; i < ASCII_SIZE; i++) {
if (root->next[i] == NULL) {
continue;
}
if (root->next[i]->cnt == 0 && !root->next[i]->isEnd) {
continue;
}
stack[curDepth] = i;
if (root->next[i]->isEnd) {
stack[curDepth + 1] = '\0';
printf("%s\r\n", stack);
}
PrintfTrieRecursive(root->next[i], curDepth + 1, stack);
}
}
void PrintfTrie(struct TrieNode *root)
{
printf("root=%p, buf=[\r\n", root);
if (root != NULL) {
char stack[100];
PrintfTrieRecursive(root, 0, stack);
}
printf("]\r\n");
}
int main(void)
{
struct TrieNode *root = NULL;
AddTrie(&root, "aaa");
PrintfTrie(root);
AddTrie(&root, "aaf");
PrintfTrie(root);
AddTrie(&root, "abz");
PrintfTrie(root);
AddTrie(&root, "zas");
PrintfTrie(root);
AddTrie(&root, "zzz");
PrintfTrie(root);
AddTrie(&root, "zdsadasdas");
PrintfTrie(root);
AddTrie(&root, "dsadas");
PrintfTrie(root);
DelTrie(&root, "zzz");
PrintfTrie(root);
DelTrie(&root, "dsadas");
PrintfTrie(root);
DelTrie(&root, "zdsadasdas");
PrintfTrie(root);
DelTrie(&root, "zas");
PrintfTrie(root);
DelTrie(&root, "abc");
PrintfTrie(root);
DelTrie(&root, "aaf");
PrintfTrie(root);
DelTrie(&root, "aaa");
PrintfTrie(root);
DestoryTrie(&root);
return 0;
}
并查集 (Disjoint Set Union)
代码实现
静态实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 10
int g_Buf[MAX_SIZE];
void InitDSU(void)
{
for (int i = 0; i < MAX_SIZE; i++) {
g_Buf[i] = i;
}
}
int FindDSU(int child)
{
int root = child;
while (g_Buf[root] != root) {
root = g_Buf[root];
}
int cur = child;
while (g_Buf[cur] != cur) {
int next = g_Buf[cur];
g_Buf[cur] = root;
cur = next;
}
return root;
}
int UnionDSU(int val1, int val2)
{
int root1 = FindDSU(val1);
int root2 = FindDSU(val2);
if (root1 == root2) {
return 0;
}
g_Buf[root1] = root2;
return 0;
}
int IsConnectedDSU(int val1, int val2)
{
int root1 = FindDSU(val1);
int root2 = FindDSU(val2);
return (root1 == root2) ? 0 : -1;
}
int PrintfLinkedNumDSU(void)
{
int num = 0;
for (int i = 0; i < MAX_SIZE; i++) {
if (i == g_Buf[i]) {
num++;
}
}
printf("PrintfLinkedNumDSU num=%d\r\n", num);
return num;
}
int DestoryDSU(void)
{
return 0;
}
void PrintfDSU(void)
{
printf("DUS=");
for (int i = 0; i < MAX_SIZE; i++) {
printf("{%d->%d} ", i, g_Buf[i]);
}
printf("\r\n");
}
int main(void)
{
InitDSU();
PrintfDSU();
UnionDSU(1, 2);
PrintfDSU();
UnionDSU(2, 3);
PrintfDSU();
UnionDSU(4, 5);
PrintfDSU();
UnionDSU(5, 6);
PrintfDSU();
UnionDSU(6, 3);
PrintfDSU();
UnionDSU(9, 1);
PrintfDSU();
UnionDSU(8, 6);
PrintfDSU();
UnionDSU(0, 7);
PrintfDSU();
UnionDSU(7, 0);
PrintfDSU();
UnionDSU(0, 9);
PrintfDSU();
PrintfLinkedNumDSU();
DestoryDSU();
return 0;
}
动态实现
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
struct DSUNode {
int val;
int cnt;
struct DSUNode *parent;
};
struct DSUNode* CreateDSU(int *buf, int len)
{
struct DSUNode* head = malloc(len * sizeof(struct DSUNode));
for (int i = 0; i < len; i++) {
head[i].val = buf[i];
head[i].cnt = 1;
head[i].parent = &head[i];
}
return head;
}
struct DSUNode* FindDSU(struct DSUNode* child)
{
struct DSUNode* root = child;
while (root->parent != root) {
root = root->parent;
}
struct DSUNode* cur = child;
while (cur->parent != cur) {
struct DSUNode* parent = cur->parent;
cur->parent = root;
cur = parent;
}
return root;
}
int UnionDSU(struct DSUNode* head, int len, int val1, int val2)
{
struct DSUNode *val1Node = NULL, *val2Node = NULL;
for (int i = 0; i < len; i++) {
if (head[i].val == val1) {
val1Node = &head[i];
}
if (head[i].val == val2) {
val2Node = &head[i];
}
if (val1Node != NULL && val2Node != NULL) {
break;
}
}
if (val1Node == NULL || val2Node == NULL) {
return -1;
}
struct DSUNode *val1Root = FindDSU(val1Node);
struct DSUNode *val2Root = FindDSU(val2Node);
if (val1Root == val2Root) {
return 0;
}
if (val1Root->cnt < val2Root->cnt) {
val1Root->parent = val2Root;
val2Root->cnt += val1Root->cnt;
} else {
val2Root->parent = val1Root;
val1Root->cnt += val2Root->cnt;
}
return 0;
}
int IsConnectedDSU(struct DSUNode* head, int len, int val1, int val2)
{
struct DSUNode *val1Node = NULL, *val2Node = NULL;
for (int i = 0; i < len; i++) {
if (head[i].val == val1) {
val1Node= &head[i];
}
if (head[i].val == val2) {
val2Node= &head[i];
}
if (val1Node != NULL && val2Node != NULL) {
break;
}
}
if (val1Node == NULL || val2Node == NULL) {
return -1;
}
struct DSUNode *val1Root = FindDSU(val1Node);
struct DSUNode *val2Root = FindDSU(val1Node);
return (val1Root == val2Root) ? 0 : -1;
}
int PrintfLinkedNumDSU(struct DSUNode* head, int len)
{
int num = 0;
for (int i = 0; i < len; i++) {
if (head[i].parent == &head[i]) {
num++;
printf("num=%d,cnt=%d\r\n", num, head[i].cnt);
}
}
return num;
}
int DestoryDSU(struct DSUNode* head)
{
free(head);
return 0;
}
void PrintfDSU(struct DSUNode* head, int len)
{
printf("DUS=");
for (int i = 0; i < len; i++) {
printf("{%d->%d} ", head[i].val, head[i].parent->val);
}
printf("\r\n");
}
int main(void)
{
int buf[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int len = sizeof(buf) / sizeof(int);
struct DSUNode *head = CreateDSU(buf, len);
PrintfDSU(head, len);
UnionDSU(head, len, 1, 2);
PrintfDSU(head, len);
UnionDSU(head, len, 2, 3);
PrintfDSU(head, len);
UnionDSU(head, len, 4, 5);
PrintfDSU(head, len);
UnionDSU(head, len, 5, 6);
PrintfDSU(head, len);
UnionDSU(head, len, 6, 3);
PrintfDSU(head, len);
UnionDSU(head, len, 9, 1);
PrintfDSU(head, len);
UnionDSU(head, len, 8, 6);
PrintfDSU(head, len);
UnionDSU(head, len, 0, 7);
PrintfDSU(head, len);
UnionDSU(head, len, 7, 0);
PrintfDSU(head, len);
UnionDSU(head, len, 0, 9);
PrintfDSU(head, len);
PrintfLinkedNumDSU(head, len);
DestoryDSU(head);
return 0;
}
算法模型 (Algorithmic Model)
位运算
大小写转换
/* 转化成小写 */
(c | ' ')
/* 转化成大写 */
(c & ' ')
/* 大小写互换 */
(c ^ ' ')
消除二进制中的最后一个1
n & (n - 1)
异或特性
/* 一个数与自己异或等于0 */
n ^ n == 0
/* 一个数与0异或等于自己 */
n ^ 0 == n
数学类算法
阶乘后的0的个数
思路
计算可以提供5的因子个数。如5的倍数可以提供第一个1个因子的5，25的倍数可以提供第二个因子的5，依次类推
代码实现
long long TrailingZeroes(long long n)
{
long long res = 0;
long long divisor = 5;
while (divisor <= n) {
res += n / divisor;
divisor *= 5;
}
return res;
}
质数
思路
欧几里德算法求最大公约数，公约数为1的则互质。
代码实现
int gcd(int x, int y)
{
int t;
while(y % x != 0) {
t = x;
x = y % x;
y = t;
}
return x;
}
素数
定义
一个数如果只能被1和它本身整除,1除外
思路
如果当前数是素数，则其之后的倍数都不是，如 3是素数，则 3 + 3， 3 + 3 + 3 ... 都不是。而且一个数在其平方根前后相乘是对称的，如6=23; 6=32
代码实现
int CountPrimes(int n)
{
bool isPrime[n + 1];
for (int i = 0; i <= n; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
int IsPrimes(int n)
{
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
幂函数
思路
利用幂运算的性质
代码实现
unsigned long long mypow(unsigned long long a, unsigned long long k)
{
if (k == 0) {
return 1;
}
if (k % 2 == 1) {
return (a * mypow(a, k - 1));
}
unsigned long long sub = mypow(a, k / 2);
return (sub * sub);
}
两数相除
思路
采用逐次逼近法
如 11 / 3
3 < 11
3 * 2 = 6 < 11
6 * 2 = 12 > 11 停止，得到一个2接着用11 - 6 = 5 逐次逼近
3 < 5
3 * 2 > 5 停止，得到一个1接着用5 - 3 = 2 逐次逼近
3 > 2 停止
最终结果为 3
代码实现
int mydiv(int a, int b)
{
if (a < b) {
return 0;
}
int ta = a;
int tb = b;
while (tb <= ta) {
tb = tb * 2;
}
return (tb / 2 / b) + mydiv(ta - tb / 2, b);
}
小而美的算法技巧
前缀和
思路
利用已经求出的结果，推导未知结果，从而减少计算量
例子
差分数组
思路
构造差分数组是为了让前后的数据产生关系，一旦要操作某个区间的时候，只要操作边界两个位置就能对整个区间产生影响，从而减少计算量
例子
路径和
思路
例子
双指针
左右指针
思路
两个指针相向或相背而行
例子
有序数组中的查找某个值的位置
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int binarySearch(int *a, int aLen, int target)
{
int left = 0, right = aLen - 1;
int mid = (left + right) / 2;
while (left <= right) {
mid = (left + right) / 2;
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
left = mid + 1;
} else if (a[mid] > target) {
right = mid - 1;
}
}
return -1;
}
int main(void)
{
int a[10] = {-2, 1, 3, 5, 7, 8, 1000, 10000, 10001, 1000000};
printf("binarySearch(a, %d)=%d\r\n", 1000000, binarySearch(a, sizeof(a) / sizeof(int), 1000000));
return 0;
}
快慢指针
两个指针相向或相背而行，一快一慢
例子
删除有序数组中的重复项
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
void removeDuplicates(int *a, int aLen, int *outLen)
{
int slow = 0, fast = slow + 1;
for (fast = slow + 1; fast < aLen; fast++) {
if (a[slow] != a[fast]) {
a[++slow] = a[fast];
}
}
*outLen = slow + 1;
}
int main(void)
{
int a[10] = {-2, 1, 3, 5, 7, 8, 8, 8, 9, 9};
int resLen =0;
removeDuplicates(a, sizeof(a) / sizeof(int), &resLen);
printf("ResLen=%d\r\n", resLen);
return 0;
}
滑动窗口
两个指针相向而行，但要保证窗口里的数据规律不变。如果因为窗口的变化导致数据规律变化了，则需缩小窗口，达到规律
例子
给你一个字符串S，一个字符串T,请在S中找出所有字母的最小子串
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int minWindow(char *s, char *t)
{
int sLen = strlen(s);
int tLen = strlen(t);
int need[256] = {0};
int window[256] = {0};
int needCnt = 0;
int windowCnt = 0;
for (int i = 0; i < tLen; i++) {
if (need[t[i]] == 0) {
needCnt++;
}
need[t[i]]++;
}
int left = 0, right = 0;
int minLen = sLen;
int pos = -1;
while (right < sLen) {
if (need[s[right]] != 0) {
window[s[right]]++;
if (window[s[right]] == need[s[right]]) {
windowCnt++;
}
}
right++;
while (windowCnt == needCnt) {
if ((right - left) < minLen) {
minLen = right - left;
pos = left;
}
if (need[s[left]] != 0) {
window[s[left]]--;
if (window[s[left]] != need[s[left]]) {
windowCnt--;
}
}
left++;
}
}
return pos;
}
int main(void)
{
char *s = "ADOBECODEBANC";
char *t = "ABC";
printf("Res=%d\r\n", minWindow(s, t));
return 0;
}
常见算法题
正则表达式匹配
递归解法
bool match(char* str, char* pattern ) {
if (str[0] == '\0' || pattern[0] == '\0') {
if (str[0] == '\0' && pattern[0] == '\0') {
return true;
} else if (str[0] != '\0' && pattern[0] == '\0') {
return false;
} else if (str[0] == '\0' && pattern[0] != '\0') {
if (pattern[1] == '*') {
return match(str, pattern + 2);
} else {
return false;
}
}
}
if (pattern[1] == '*') {
if (str[0] == pattern[0] || pattern[0] == '.') {
return match(str + 1, pattern) || match(str, pattern + 2);
} else {
return match(str, pattern + 2);
}
} else {
if (str[0] == pattern[0] || pattern[0] == '.') {
return match(str + 1, pattern + 1);
} else {
return false;
}
}
}
动态规划解法
Dijkstra算法
struct queueNode {
int cur;
int dist;
};
struct queue {
struct queueNode *buf;
int maxLen;
int start;
int end;
};
struct queue *CreateQueue(int maxLen)
{
struct queue *q = malloc(sizeof(struct queue));
q->buf = malloc(maxLen * sizeof(struct queueNode));
q->maxLen = maxLen;
q->start = 0;
q->end = 0;
return q;
}
bool QueueIsEmpty(struct queue *q)
{
return q->start == q->end;
}
void QueuePush(struct queue *q, int cur, int dist)
{
#if 0
struct queueNode node;
int end = (q->end - 1 < 0) ? (q->maxLen - 1) : (q->end - 1 < 0);
int start = (q->start - 1 < 0) ? (q->maxLen - 1) : (q->start - 1 < 0);
node.cur = cur;
node.dist = dist;
q->buf[q->end] = node;
while (end != start && q->buf[end].dist > dist) {
int nextEnd = ((end + 1) >= q->maxLen) ? (0) : (end + 1);
q->buf[nextEnd] = q->buf[end];
q->buf[end] = node;
end--;
if (end < 0) {
end = q->maxLen - 1;
}
}
#endif
#if 1
q->buf[q->end].cur = cur;
q->buf[q->end].dist = dist;
#endif
q->end = q->end + 1;
if (q->end >= q->maxLen) {
q->end = 0;
}
}
struct queueNode QueuePop(struct queue *q)
{
struct queueNode res = q->buf[q->start];
q->start = q->start + 1;
if (q->start >= q->maxLen) {
q->start = 0;
}
return res;
}
int networkDelayTime(int** times, int timesSize, int* timesColSize, int n, int k){
int graphColSize = n + 1;
int **graph = malloc(graphColSize * sizeof(int *));
for (int i = 0; i < graphColSize; i++) {
graph[i] = malloc(graphColSize * sizeof(int));
for (int j = 0; j < graphColSize; j++) {
graph[i][j] = -1;
}
}
for (int i = 0; i < timesSize; i++) {
graph[times[i][0]][times[i][1]] = times[i][2];
}
int distTo[graphColSize];
for (int i = 0; i < graphColSize; i++) {
distTo[i] = INT_MAX;
}
distTo[k] = 0;
struct queue *q = CreateQueue(1000);
QueuePush(q, k, 0);
while (!QueueIsEmpty(q)) {
struct queueNode node = QueuePop(q);
if (distTo[node.cur] < node.dist) {
continue;
}
for (int next = 1; next < graphColSize; next++) {
if (graph[node.cur][next] < 0) {
continue;
}
int distToNext = distTo[node.cur] + graph[node.cur][next];
if (distTo[next] > distToNext) {
distTo[next] = distToNext;
QueuePush(q, next, distToNext);
}
}
}
int max = 0;
for (int i = 1; i < graphColSize; i++) {
if (distTo[i] == INT_MAX) {
return -1;
}
if (max < distTo[i]) {
max = distTo[i];
}
}
return max;
}