分类： 代码练习

一个优化过的求所有出栈排列的函数。

        public static void GetAllStackArrangement(int[] array, int index, int[] ans,  int ansIndex, int stackIndex)
        {
            if (index >= array.Length && stackIndex >= ans.Length)
            {
                Console.WriteLine(string.Join(", ", ans));
                return;
            }
            if(stackIndex >= ans.Length)
            {
                int temp = ans[ans.Length - 1];
                ans[ans.Length - 1] = array[index++];
                GetAllStackArrangement(array, index, ans, ansIndex, ans.Length - 1);
                ans[ans.Length - 1] = temp;
            }
            else if(index >= array.Length)
            {
                int temp = ans[ansIndex], temp2 = ans[stackIndex];
                ans[ansIndex++] = ans[stackIndex++];
                GetAllStackArrangement(array, index, ans, ansIndex, stackIndex);
                ans[ansIndex - 1] = temp;
                ans[stackIndex - 1] = temp2;
            }
            else
            {
                int temp = ans[ansIndex] , temp2 = ans[stackIndex];
                ans[ansIndex++] = ans[stackIndex++];
                GetAllStackArrangement(array, index, ans, ansIndex, stackIndex);
                ansIndex--; stackIndex--;
                ans[ansIndex] = temp; ans[stackIndex] = temp2;
                temp = ans[--stackIndex];
                ans[stackIndex] = array[index++];
                GetAllStackArrangement(array, index, ans, ansIndex, stackIndex);
                ans[stackIndex] = temp;
            }
        }

啊，仿照数据结构上的二叉树递归写法根本实现不了，最后发现原来是要传递指针的呀，该死！还要注意形参与实参的区别，用于统计的数应该以指针的形式直接访问内存修改数据，而不是用形参。

无论如何，我实现了自己的第一棵完全二叉树及树的输入，嘻嘻嘻。下面放上代码（很烂）。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define status int
typedef struct Tree{
    char data;
    struct Tree *lchild;
    struct Tree *rchild;
}Tree,*tree;
tree CreatBiTree(char * string,int *p,tree t){
    if(*p>=strlen(string)) return NULL;
    if(string[*p]==' ')  return NULL;
    else{
        t=(Tree*)malloc(sizeof(Tree));
        t->data=string[*p];
        (*p)++;
        t->lchild=CreatBiTree(string, p, t->lchild);
        (*p)++;
        t->rchild=CreatBiTree(string, p, t->rchild);
    }
    return t;
}
status printTree(tree t){
    if(t==NULL) {
        printf("null ");
        return 0;
    }
    printf("%c ",t->data);
    printTree(t->lchild);
    printTree(t->rchild);
    return 0;
}
int main() {
    tree root;
    int *p;
    p=(int*)malloc(sizeof(int));
    *p=0;
    char * test;
    test=(char*)malloc(100* sizeof(char));
    gets(test);
    root=CreatBiTree(test,p,root);
    printf("root:      %c \nfull tree: ",root->data);
    printTree(root);
    printf("\np's trace: %d",*p);
    return 0;
}

在输出时候加上 “\033[ ; m …… \033[0m ” 即可使得输出的字体和背景是有颜色的。下面是颜色的定义：

字背景颜色范围:40 – 49

40:黑

41:深红

42:绿

43:黄色

44:蓝色

45:紫色

46:深绿

47:白色

字颜色:30 – 39

30:黑

31:红

32:绿

33:黄

34:蓝色

35:紫色

36:深绿

37:白色

下面看一下：ANSI控制码的说明

\33[0m 关闭所有属性 

\33[1m 设置高亮度 

\33[4m 下划线 

\33[5m 闪烁 

\33[7m 反显 

\33[8m 消隐 

\33[30m — \33[37m 设置前景色 

\33[40m — \33[47m 设置背景色 

\33[nA 光标上移n行 

\33[nB 光标下移n行 

\33[nC 光标右移n行 

\33[nD 光标左移n行 

\33[y;xH设置光标位置 

\33[2J 清屏 

\33[K 清除从光标到行尾的内容 

\33[s 保存光标位置 

\33[u 恢复光标位置 

\33[?25l 隐藏光标 

\33[?25h 显示光标

void removeBlanks(char * string) {
    int len = (int) strlen(string), count = 0;
    for (int i = 0; i < len; i++) {
        if (string[i] == ' ') {
            count++;
            continue;
        }
        string[i - count] = string[i];
    }
    string[len-count]=0;
}

用了几种复杂的方法，最后才回归本质😅。

先是看算法导论和数据结构

后来又自己又上YouTube看视频

然后附上代码做纪念：

int KMP(char * string, char * pattern){
    int len=(int)strlen(pattern),
        l=(int)strlen(string),
        *next;
    next=(int*)malloc((len+1)*sizeof(int));
    for(int i=1,j=0;i<len;i++){
        if(pattern[i]==pattern[j]) {
            next[i]=j+1;
            j++;
            continue;
        }
        if(j==0) continue;
        i--;
        j=(next[j]==0)?0:(next[j]-1);
    }
    for(int i=0,j=0;i<l;i++){
        if(string[i]==pattern[j]){
            j++;
            if(j==len) return i+1-len;
            continue;
        }
        if(j==0) continue;
        i--;
        j=next[j-1];
    }
    return -1;
}

以后再改进吧！继续努力💪！