17. #define MAX_LEN_OF_STR 30 // 字符串的最大长度 18. 19. typedef struct String // 这里需要的字符串数组,存放字符串及其长度 20. { 21. char str[MAX_LEN_OF_STR]; // 字符数组 22. int length; // 字符串的实际长度 23. } String, * PString; 24. 25. // 得到字符串的next数组 26. void GetNextArray(PString pstr, int next[]) 27. { 28. assert(NULL != pstr); 29. assert(NULL != next); 30. assert(pstr -> length > 0 ); 31. 32. // 第一个字符的next值是-1,因为C中的数组是从0开始的 33. next[ 0 ] = - 1 ; 34. for ( int i = 0 , j = - 1 ; i < pstr -> length - 1 ; ) 35. { 36. // i是主串的游标,j是模式串的游标 37. // 这里的主串和模式串都是同一个字符串 38. if ( - 1 == j || // 如果模式串游标已经回退到第一个字符 39. pstr -> str[i] == pstr -> str[j]) // 如果匹配成功 40. { 41. // 两个游标都向前走一步 42. ++ i; 43. ++ j; 44. // 存放当前的next值为此时模式串的游标值 45. next[i] = j; 46. } 47. else // 匹配不成功j就回退到上一个next值 48. { 49. j = next[j]; 50. } 51. } 52. } 53. 54. // KMP字符串模式匹配算法 55. // 输入: S是主串,T是模式串,pos是S中的起始位置 56. // 输出: 如果匹配成功返回起始位置,否则返回-1 57. int KMP(PString S, PString T, int pos) 58. { 59. assert(NULL != S); 60. assert(NULL != T); 61. assert(pos >= 0 ); 62. assert(pos < S -> length); 63. 64. if (S -> length < T -> length) 65. return - 1 ; 66. 67. printf( \主串\\t = %s\\n \ , S -> str); 68. printf( \模式串\\t = %s\\n \ , T -> str); 69. 70. int * next = ( int * )malloc(T -> length * sizeof ( int )); 71. // 得到模式串的next数组 72. GetNextArray(T, next); 73. 74. int i, j; 75. for (i = pos, j = 0 ; i < S -> length && j < T -> length; ) 76. { 77. // i是主串游标,j是模式串游标 78. if ( - 1 == j || // 模式串游标已经回退到第一个位置 79. S -> str[i] == T -> str[j]) // 当前字符匹配成功 80. { 81. // 满足以上两种情况时两个游标都要向前进一步 82. ++ i; 83. ++ j; 84. } 85. else // 匹配不成功,模式串游标回退到当前字符的next值 86. { 87. j = next[j]; 88. } 89. } 90. 91. free(next); 92. 93. if (j >= T -> length) 94. { 95. // 匹配成功 96. return i - T -> length; 97. } 98. else 99. { 100. // 匹配不成功 101. return - 1 ; 102. } 103. }
4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。 二叉树节点结构如下： typedef struct node_t {
char data;//数据域
struct node_t *lchild; //左孩子 struct node_t *rchild;//右孩子 }node, *tree; 1、前序遍历
a、前序遍历递归实现：
void preorder_traverse(tree root, void(*visit)(node)) {
if(NULL != root) {
visit(*root); //先访问根节点
preorder_traverse(root->lchild, visit);//先序遍历左子树 preorder_traverse(root->rchild, visit);//前序遍历右子树 } }
b、前序变量的非递归实现：
在非递归实现里面用栈来模拟递归的过程，这里用了一个线性的数组来模拟栈的功能。 void preorder_traverse_norec(tree root, void(*visit(node))) {
tree stack[32]; //这里用一个数组来模拟栈,假设节点不超过32个 int top = 0; tree p = root;
for(; top<32; top++) {
stack[top++] = NULL; //初始化栈 }
top = 0;
while(NULL != p || top > 0) {
while(p != NULL) {
visit(*p); //先访问根节点
stack[top++] = p;//把节点压入栈中 p = p->lchild;//将p指向其左孩子 }
p = stack[—top]; //弹出p，需要将NULL弹出 p = p->rchild; //p指向其右孩子 } }
2、二叉树的中序遍历
a、二叉树中序遍历的递归实现：
中序遍历的递归实现也比较直观，代码如下： void inorder_traverse(tree root, void(*visit)(node)) {
if(NULL != root) {
inorder_traverse(root->lchild, visit);//先遍历其左子树 visit(*root);//遍历该节点
inorder_traverse(root->rchild, visit);//最后遍历右子树 } }
b、中序遍历的非递归实现：
非递归实现同样用栈来模拟，这里还是使用线性数组来模拟栈的功能。 void inorder_traverse_norec(tree root, void(*visit)(node)) {
tree stack[32]; int top = 0; tree p = root;
for(; top<32; top++) {
stack[top] = NULL; }
top = 0;
while(p != NULL || top > 0) {
while(p != NULL) {
stack[top++] = p; //将所有左子树压入栈中 p = p->lchild; }
p = stack[—top]; //弹出空指针 visit(*p); //访问节点
p = p->rchild; //处理其右子树 } }
3、后序遍历二叉树
a、后序遍历二叉树递归实现：
void postorder_traverse(tree root, void(*visit)(node)) {
if(NULL != root) {
postorder_traverse(root->lchild, visit); //遍历其左子树 postorder_traverse(root->rchild, visit);//遍历其右子树 visit(*root);//访问节点 } }
b、后序遍历二叉树的非递归实现：
void postorder_travese_norec(tree root, void(*visit)(node)) {
tree stack[32]; int top = 0; tree p = root;
tree lastvisit = NULL; //用于标记上次访问的节点 for(; top<32; top++) {
stack[top] = NULL; }
top = 0;
while(p != NULL || top > 0) {
while(p != NULL) {
stack[top++] = p; //将所有左子树压入栈中 p = p->lchild; }
p = stack[top - 1]; //注意这里，不是p = stack[—top],因为我们还不知道是否要访问p if(p->rchild == NULL || lastvisit == p->rchild) //判断p的右子树是否访问过或者是否为空 {
visit(*p);//如果p的右子树为空或者已经访问过，则访问p lastvisit = p;//标记上次访问的是节点p
top--; //这里p已经访问过，则将栈中的p弹出即可 p = NULL; } else {
p = p->rchild; //如果p的右子树还没有访问过，那么访问其右子树 } } }
4. 堆，建堆算法，堆的插入和删除算法，堆排序。
堆是个完全二叉树，而且每个节点都比左右子节点大（或小），因为堆分为max堆和min堆。