DS板子

// 栈的定义 与 预处理
#define ElemType int /*Type of Elem*/ 
#define ElemType_Error -1 /*Type of Elem*/
typedef struct Stack{
    ElemType elem;
    struct Stack *next;
}Stack;

//生成栈
Stack* Create_Stack(){
    Stack* SNode = (Stack*)malloc(sizeof (Stack));
    SNode->elem = ElemType_Error;
    SNode->next = NULL;
    return SNode;
}

//判断栈是否为空
int IsEmpty_Stack(Stack* stack){
    return (stack->next == NULL);
}

//向栈中加入元素
void Push_Stack(Stack* stack, ElemType elem){
    Stack *SNode = (Stack *) malloc(sizeof(Stack));
    SNode->elem = elem;
    SNode->next = stack->next;
    stack->next = SNode;
}

//将栈顶元素弹出
ElemType Pop_Stack(Stack* stack){
    if(!(stack->next)) return ElemType_Error;
    Stack *SNode = stack->next;
    stack->next = SNode->next;
    ElemType TopElem = SNode->elem;
    free(SNode);
    return TopElem;
}

//队的定义 与 预处理
#define ElemType int /*Type of Elem*/
#define ElemType_Error -1 /* untouchable num */
typedef struct Queue{
    ElemType *elem_array;
    int MaxSize;
    int front;
    int rear;
}Queue;

//创建一个空队（MaxSize 至少比元素最多数量大 1）
Queue* Create_Queue(Queue* queue,int MaxSize){
    queue = (Queue*) malloc(sizeof(Queue));
    queue->elem_array = (ElemType*) malloc((MaxSize)*sizeof (ElemType));
    queue->MaxSize = MaxSize;
    queue->front = queue->rear = 0;
    return queue;
}

//求队的长度
int Length_Queue(Queue* queue){
    return (queue->rear - queue->front + queue->MaxSize) % queue->MaxSize;
}

//判断队是否为空
int IsEmpty_Queue(Queue* queue){
    return (queue->rear == queue->front);
}

//判断队是否已满
int IsFull_Queue(Queue* queue){
    return ((queue->rear+1)%queue->MaxSize == queue->front);
}

//从队尾加入新元素
int Add_Queue(Queue* queue,ElemType elem){
    if((queue->rear+1)%queue->MaxSize == queue->front) return 0;
    queue->elem_array[queue->rear] = elem;
    queue->rear = (queue->rear+1)%queue->MaxSize;
    return 1;

}

//从队首剔除元素
ElemType Delete_Queue(Queue* queue){
    if(queue->rear == queue->front) return ElemType_Error;
    ElemType FrontElem = queue->elem_array[queue->front];
    queue->front = (queue->front+1)%queue->MaxSize;
    return FrontElem;
}

#define ElemType int /*Type of Elem*/

//树的定义
typedef struct Tree{
    ElemType elem;
    struct Tree *left;
    struct Tree *right;
}Tree;

int cmp(const void* e1,const void*e2){
    ElemType a = *(ElemType*)e1;
    ElemType b = *(ElemType*)e2;
    return a-b;
}

//在树中添加结点
Tree* Add_Tree(Tree *tree, ElemType elem ,int (*cmp)(const void* e1,const void*e2)){
    if(tree){
        if(cmp(&elem,&tree->elem)==0) { //元素不重复版本
            return tree;
        }else {
            if( cmp(&elem,&tree->elem) < 0 ) tree->left = Add_Tree(tree->left, elem,cmp);
            else tree->right = Add_Tree(tree->right, elem,cmp);
            return tree;
        }
    }else{  //空树 或 空结点
        Tree *new_tree = (Tree *) malloc(sizeof (Tree));
        new_tree->right = new_tree->left = NULL;
        new_tree->elem = elem;
        return new_tree;
    }
}

//在树中查找元素
int Find_Tree(Tree *tree ,ElemType key ,int (*cmp)(const void* e1,const void*e2)){
    while(tree){
        if( cmp(&key,&tree->elem) == 0 ) return 1;
        else if( cmp(&key,&tree->elem) < 0 ) tree = tree->left;
        else tree = tree->right;
    }
    return 0;
}

//删除树中结点
Tree* Delete_Tree(Tree *tree,ElemType key ,int (*cmp)(const void* e1,const void*e2)){
    if(tree) {
        if( cmp(&key,&tree->elem) == 0 ) {
            if (tree->left && tree->right) {  //左右结点均非空
                ElemType temp;
                Tree *op_tree = tree->right;
                while (op_tree->left) op_tree = op_tree->left;
                temp = tree->elem;
                tree->elem = op_tree->elem;
                op_tree->elem = temp;
                tree->right = Delete_Tree(tree->right, temp , cmp);
                return tree;
            } else if (tree->left || tree->right) {  //左右结点有一个不空
                Tree *op_tree = (tree->left == NULL) ? (tree->right) : (tree->left);
                free(tree);
                return op_tree;
            } else {  //左右结点均空（叶节点）
                free(tree);
                return NULL;
            }
        }else if( cmp(&key,&tree->elem) < 0) tree->left = Delete_Tree(tree->left, key, cmp);
        else tree->right = Delete_Tree(tree->right, key,cmp);
    }
    return tree;
}

//求树高
int Height_Tree(Tree *tree){
    if(!tree) return 0;
    int h_left = Height_Tree(tree->left);
    int h_right= Height_Tree(tree->right);
    return (h_left > h_right ? h_left : h_right ) + 1;
}

//前序遍历
void PreOrderTraversal(Tree *tree){
    if(tree){
        printf("%d ",tree->elem);
        PreOrderTraversal(tree->left);
        PreOrderTraversal(tree->right);
    }
}

//中序遍历
void InOrderTraversal(Tree *tree){
    if(tree){
        InOrderTraversal(tree->left);
        printf("%d ",tree->elem);
        InOrderTraversal(tree->right);
    }
}

//后序遍历
void PostOrderTraversal(Tree *tree){
    if(tree){
        PostOrderTraversal(tree->left);
        PostOrderTraversal(tree->right);
        printf("%d ",tree->elem);
    }
}

//层序遍历
void LevelOrderTraversal(Tree *tree){
    if(!tree) return;  //空树返回
    typedef struct Q{Tree *elem_T; struct Q *next;}Q;

    Q *q_head = (Q *)malloc(sizeof(Q));
    q_head->elem_T = NULL;  //Create_Queue()

    q_head->next = (Q *)malloc(sizeof(Q));
    q_head->next->elem_T = tree;
    q_head->next->next = NULL;  //Add_Queue(tree)

    Q *q_rear = q_head->next;

    Tree *T;
    while(q_head->next){
        printf("%d ",q_head->next->elem_T->elem);

        Q *q_off = q_head->next;
        q_head->next = q_head->next->next;
        T = q_off->elem_T;
        free(q_off);  //Delete_Queue(q_off)
        if(!q_head->next) q_rear=q_head;

        if(T->left){
            q_rear->next = (Q*) malloc(sizeof (Q));
            q_rear = q_rear->next;
            q_rear->elem_T = T->left;
            q_rear->next = NULL;  //Add_Queue(T->left)
        }
        if(T->right){
            q_rear->next = (Q*) malloc(sizeof (Q));
            q_rear = q_rear->next;
            q_rear->elem_T = T->right;
            q_rear->next = NULL;  //Add_Queue(T->right)
        }
    }
}

#define ElemType int /*Type of Elem*/
#define M_For_ElemType -1 /* limit of ElemType */  //作哨兵，但好像没用（to be checked）
#define ElemType_Error -1 /* untouchable num */
typedef struct Heap{
    ElemType *elem_array;
    int size;
    int MaxSize;
}Heap;
int cmp(const void *e1, const void *e2){ //最大堆用e1-e2 ；最小堆反之 ；注意double
    return *(ElemType*)e1 - *(ElemType*)e2;
}

Heap* Create_Heap(Heap *heap ,int MaxSize){
    heap=(Heap*) malloc(sizeof (Heap));
    heap->elem_array = (ElemType*) malloc((MaxSize+1)*sizeof (ElemType));
    heap->MaxSize = MaxSize;
    heap->size = 0;
    heap->elem_array[0] = M_For_ElemType; //哨兵，但好像没用（to be checked）
    return heap;
}

int AddInTail_Heap(Heap *heap, ElemType elem){
    if(heap->size < heap->MaxSize){
        heap->elem_array[++heap->size] = elem;
        return 1;
    }
    return 0;
}

int Insert_Heap(Heap *heap, ElemType elem, int (*cmp)(const void *e1,const void *e2)) {
    if (heap->size == heap->MaxSize) return 0; 
    int i = ++heap->size;
    while ( i>1 && cmp(&elem, &heap->elem_array[i/2]) > 0 ) { //类似插入排序原理
        heap->elem_array[i] = heap->elem_array[i/2];
        i /= 2;
    }
    heap->elem_array[i] = elem;
    return 1;
}

void PrecDown_Heap(Heap* heap, int subscript, int (*cmp)(const void *e1,const void *e2)){
// PrecDown -> Precolate(过滤) Down
    for (int i = subscript; 2*i <= heap->size; ) { //确保左子树存在
        int next_subscript; // subscript --> 下标
        if(2*i+1 > heap->size) next_subscript = 2*i; //右子树不存在时
        else next_subscript = ( cmp(&heap->elem_array[2*i],&heap->elem_array[2*i+1]) > 0 ) ? (2*i) : (2*i+1);
        if( cmp(&heap->elem_array[next_subscript],&heap->elem_array[i]) > 0 ){
            ElemType temp = heap->elem_array[next_subscript];
            heap->elem_array[next_subscript] = heap->elem_array[i];
            heap->elem_array[i] = temp;
            i = next_subscript;
        }else break;
    }
}

ElemType PopM_Heap(Heap *heap, int (*cmp)(const void *e1,const void *e2)){
    if(!heap->size) return ElemType_Error; //堆空返回error
    else{
        ElemType M_Elem = heap->elem_array[1];
        heap->elem_array[1] = heap->elem_array[heap->size];
        heap->size--;
        PrecDown_Heap(heap,1,cmp);
        return M_Elem;
    }
}

void Build_Heap(Heap *heap, int (*cmp)(const void *e1,const void *e2)){
    for (int i = heap->size/2; i > 0; --i) { //从最后一个非叶结点的位置开始往前下滤
        PrecDown_Heap(heap,i,cmp);
    }
}

#define ElemType int /*Type of Elem*/

int cmp(const void* e1,const void* e2){ //升序用 e1-e2
    return *(ElemType*)e1 - *(ElemType*)e2;
}
void merge(ElemType* A,ElemType* TempA,int l,int r,int REnd,int (*cmp)(const void* e1,const void* e2)){
//数组 A 由左右两段有序数列组成，此函数将 A 的左右两端归并
    int LEnd = r - 1;
    int n = REnd - l + 1;
    int subscript = l;
    while(l<=LEnd && r<=REnd) {
        if ( cmp(&A[l], &A[r])>0 ) TempA[subscript++] = A[r++];
        else TempA[subscript++] = A[l++];
    }
    while(r<=REnd) TempA[subscript++] = A[r++];
    while(l<=LEnd) TempA[subscript++] = A[l++];
    for (int i = 0; i < n; ++i,REnd--) A[REnd] = TempA[REnd];
}
void merge_pass(ElemType* A,ElemType* TempA,int n,int length,int (*cmp)(const void* e1,const void* e2)){
//对 A 的每两个连续的长为 length 的子段归并
    int i;
    for ( i = 0; i <= n-2*length; i+=2*length) {
        merge(A,TempA,i,i+length,i+2*length-1,cmp);
    }
    if(i+length < n) merge(A,TempA,i,i+length,n-1,cmp);
    else for (int j = i; j < n; ++j) TempA[j] = A[j];
}

void mergesort(ElemType* A,int n,int (*cmp)(const void* e1,const void* e2)){ //主体函数
    int length = 1;
    ElemType *TemA = (ElemType*)malloc((n)*sizeof (ElemType));
    if(TemA){
        while (length < n){ //相互交替覆盖
            merge_pass(A,TemA,n,length,cmp);
            length <<= 1;
            merge_pass(TemA,A,n,length,cmp);
            length <<= 1;
        }
        free(TemA);
    }else perror("error: malloc fault");
}

#define ElemType int /*Type of Elem*/
int cmp(const void* e1,const void* e2){ //升序
    return *(ElemType*)e1 - *(ElemType*)e2;
}
void PrecDown(ElemType* a, int subscript, int n, int (*cmp)(const void *e1,const void *e2)){
// PrecDown -> Precolate(过滤) Down
    for (int i = subscript; 2*i <= n ;) { //确保左子树存在
        int next_subscript;
        if( 2*i+1 > n ) next_subscript = 2*i; //右子树不存在时
        else next_subscript = (cmp(&a[2*i],&a[2*i+1])>0) ? (2*i) : (2*i+1);
        if(cmp(&a[next_subscript],&a[i])>0){
            ElemType temp = a[next_subscript];
            a[next_subscript] = a[i];
            a[i] = temp;
            i = next_subscript;
        }else break;
    }
}
void heapsort(ElemType* a,int n,int (*cmp)(const void* e1,const void* e2)){
    a--; //使 a[1] 存放第一个元素，与堆的存放规律匹配
    for (int i = n/2; i > 0 ; --i) { //建堆
        PrecDown(a,i,n,cmp);
    }
    ElemType temp;
    while(n > 1){
        temp = a[1];
        a[1] = a[n];
        a[n] = temp;
        n--;
        PrecDown(a,1,n,cmp);
    }
    a++;
}

#define Elemtype int /*Type of Elem*/
#define CutOff 10 /* 当数组长度 < CutOff时，进行简单插入排序 ！CutOff必须大于3 ！ */
int cmp(const void* e1, const void* e2){ //升序用 e1-e2;降序反之
    return *(Elemtype*)e1 - *(Elemtype*)e2;
}
void swap(Elemtype* a,Elemtype *b){
    Elemtype temp = *a;
    *a = *b;
    *b = temp;
}
Elemtype Pivot_Get(Elemtype* a,int n,int (*cmp)(const void* e1, const void* e2)){
    // n>=2
    int mid = (n-1)/2;
    if( cmp(&a[0],&a[mid])>0 ) swap(&a[0],&a[mid]);
    if( cmp(&a[0],&a[n-1])>0 ) swap(&a[0],&a[n-1]);
    if( cmp(&a[mid],&a[n-1])>0 ) swap(&a[mid],&a[n-1]);
    // a[0] <= a[mid] <= a[n-1] 保证pivot具有一定的随机性
    swap(&a[mid],&a[n-2]); // a[n-1]一定>=pivot，减少运算量
    return a[n-2];
}
void quicksort(Elemtype* a, int n ,int (*cmp)(const void* e1, const void* e2)){
    if(n > CutOff){
        int pivot = Pivot_Get(a,n,cmp);
        Elemtype *i = a;
        Elemtype *j = &a[n-3];
        for (;;) {
            while (cmp(i, &pivot) < 0) i++;
            while (cmp(j, &pivot) > 0) j--;
            if(i<=j) swap(i++, j--);
            else break;
        }
        swap(&a[n-2],i);
        quicksort(a,(int)(i-a),cmp);
        quicksort(i+1,(int)(&a[n-1]-i),cmp);
    } else{
        for (int j ,i = 1; i < n; ++i) { //插入排序
            Elemtype hold=a[i];
            for (j = i-1; j >= 0 ; --j) {
                if( cmp(&hold,&a[j])<0 ) a[j+1]=a[j];
                else break;
            }
            a[j+1]=hold;
        }
    }
}

void radixsort(int *a,int n,int up_or_down,int radix,int data_max){ 
//!!只能排正整数!!
//up_or_down == 1 为升序，up_or_down == 0 为降序 ; radix为基数(radix进制) ; data为数据最大值
    int Temp[n]; //备用数组
    int *bucket = (int*)malloc(radix*sizeof(int)); // 桶
    int p = 1 ,cycle_num = 0; // p = radix^cycle;
    int *temp1 = Temp ,*temp2 = a; // 两个数组指针交替使用
    
    while( p>0 && data_max / p ){ // p>0 : 防止 p 超过 2^31-1 爆 int
        memset(bucket,0,radix*sizeof(int));
        for (int i = 0; i < n; ++i) {
            int k = (temp2[i]/p)%radix;
            bucket[k]++; //记录桶中元素的个数
        }
        
        if(up_or_down) for (int i = 1; i < radix; ++i) bucket[i] += bucket[i-1];
        else for (int i = radix-2; i >=0 ; --i) bucket[i] += bucket[i+1];
        //利用 bucket[] 记录元素位置
        
        for (int i = n-1; i >= 0 ; --i) { //倒序保证有序性
            int k = (temp2[i]/p)%radix;
            temp1[--bucket[k]] = temp2[i];
        }

        int *swap = temp1;
        temp1 = temp2;
        temp2 = swap; //交换数组指针指代的位置

        cycle_num++;
        p *= radix;
    }
    if( cycle_num & 1 ) memcpy(a,Temp,n*sizeof(int)); //奇数次循环需要将结果转移至 a[]中
    free(bucket);
}

typedef struct AvlTree{
    int value;
    int height; //树高
    struct AvlTree* left;
    struct AvlTree* right;
}AvlTree;

int GetHeight(AvlTree* avlTree){ //取得结点树高（为了统一NULL的情况）
    if(!avlTree) return 0;
    else return avlTree->height;
}

int Max(int a,int b){return a>b?a:b;}

AvlTree* L_Rotate(AvlTree* avlTree){ //左旋
    AvlTree* root = avlTree->right;
    avlTree->right = root->left;
    root->left = avlTree;
    avlTree->height = Max(GetHeight(avlTree->left), GetHeight(avlTree->right)) + 1;
    root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
    return root;
}
AvlTree* R_Rotate(AvlTree* avlTree){ //右旋
    AvlTree* root = avlTree->left;
    avlTree->left = root->right;
    root->right = avlTree;
    avlTree->height = Max(GetHeight(avlTree->left), GetHeight(avlTree->right)) + 1;
    root->height = Max(GetHeight(root->left), GetHeight(root->right)) + 1;
    return root;
}
AvlTree* RL_Rotate(AvlTree* avlTree){  //右_左旋
    avlTree->right = R_Rotate(avlTree->right);
    avlTree = L_Rotate(avlTree);
    return avlTree;
}
AvlTree* LR_Rotate(AvlTree* avlTree){  //左_右旋
    avlTree->left = L_Rotate(avlTree->left);
    avlTree = R_Rotate(avlTree);
    return avlTree;
}

AvlTree* Add_AvlTree(AvlTree* avlTree,int value){ 
    if(!avlTree){ //空树
        AvlTree *newTree = (AvlTree*) malloc(sizeof (AvlTree));
        newTree->value = value;
        newTree->left = newTree->right = NULL;
        newTree->height = 1;
        return newTree;
    }else{
        if(value < avlTree->value){
            avlTree->left = Add_AvlTree(avlTree->left,value);
            if(GetHeight(avlTree->left) - GetHeight(avlTree->right) == 2){
                if(value < avlTree->left->value) avlTree = R_Rotate(avlTree); //左左型用左旋
                else avlTree = LR_Rotate(avlTree); //左右型用左右旋
            }
        }else if(value > avlTree->value){
            avlTree->right = Add_AvlTree(avlTree->right,value); 
            if(GetHeight(avlTree->right) - GetHeight(avlTree->left) == 2){
                if(value > avlTree->right->value) avlTree = L_Rotate(avlTree); //右右型用左旋
                else avlTree = RL_Rotate(avlTree); //右左型用右左旋
            }
        }
        avlTree->height = Max(GetHeight(avlTree->right), GetHeight(avlTree->left))+1;
        //更新树高
        return avlTree;
    }
}

AvlTree* Delete_Avltree(AvlTree* avlTree,int value){
    if(avlTree){
        if(avlTree->value == value) {
            if (avlTree->left && avlTree->right) {  //左右结点均非空
                int temp;
                AvlTree *op_tree = avlTree->right;
                while(op_tree->left) op_tree=op_tree->left;
                temp = op_tree->value;
                op_tree->value = value;
                avlTree->value = temp;
                avlTree = Delete_Avltree(avlTree,value); //不直接更新avlTree->right是为了保证能够持续地在标红的else里递归旋转AVL树
            } else if (avlTree->left || avlTree->right) {  //左右结点有一个不空
                AvlTree *op_tree = (avlTree->left == NULL) ? (avlTree->right) : (avlTree->left);
                free(avlTree);
                return op_tree;
            } else {  //左右结点均空（叶节点）
                free(avlTree);
                return NULL;
            }
        }else {
            if (value > avlTree->value) {
                avlTree->right = Delete_Avltree(avlTree->right, value);
                if(GetHeight(avlTree->left) - GetHeight(avlTree->right) == 2){
                    if( avlTree->right && GetHeight(avlTree->left->left) == 1){
                    //右子树存在 && avlTree->left->left 为叶结点
                        avlTree = LR_Rotate(avlTree);
                    }else avlTree = R_Rotate(avlTree);
                }
            } else { //与if相反
                avlTree->left = Delete_Avltree(avlTree->left, value);
                if(GetHeight(avlTree->right) - GetHeight(avlTree->left) == 2){
                    if(avlTree->left && GetHeight(avlTree->right->right) == 1){
                        avlTree = RL_Rotate(avlTree);
                    }else avlTree = L_Rotate(avlTree);
                }
            }
            avlTree->height = Max(GetHeight(avlTree->left), GetHeight(avlTree->right)) + 1;
            //更新树高
        }
    }else return avlTree;
}

enum State {
        dft,    // default
        SgSlash,// /
        DbSlash,// //
        Mt1,    // /*
        Mt2,    // /**
        SgQt,   // '
        DbQt,   // "
};
enum State s = dft;
void judge(int ch){ //读取的字符
    switch (s) {
        case dft:
            if (ch == '/') {
                s = SgSlash;
            }else if (ch == '\''){
                s = SgQt;
            }else if (ch=='\"'){
                s = DbQt;
            }
            break;
        case SgSlash:
            if (ch == '*') {
                s = Mt1;
            } else if (ch == '/') {
                s = DbSlash;
            }else{
                s = dft;
            }
            break;
        case DbSlash:
            if (ch=='\n'){
                s = dft;
            }
            break;
        case Mt1:
            if(ch=='*'){
                s = Mt2;
            }
            break;
        case Mt2:
            if(ch=='/'){
                s = dft;
            }else if(ch == '*'){
                s = Mt2;
            }else{
                s = Mt1;
            }
            break;
        case SgQt:
            if(ch=='\''){
                s = dft;
            }
            break;
        case DbQt:
            if(ch=='\"'){
                s = dft;
            }
            break;
        default:
            break;
    }
}