galgorithm and data struct

learn.c

#include<stdio.h>
#include<stdlib.h>

struct LinkNode {
    int val;
    struct LinkNode *prev;
    struct LinkNode *next;
};

struct LinkNode *InitDNode(struct LinkNode *head)
{
    struct LinkNode *new_node = (struct LinkNode *)calloc(1, sizeof(struct LinkNode));
    new_node->prev = new_node->next = new_node;
}

void FreeALLDnode(struct LinkNode *head)
{
    struct LinkNode *q, *p = head->next;
    while (p ! = head) {
        q = p->next;
        free(p);
        p = q;
    }
    free(head);
    head = NULL;
}

void ClearDnode(strut LinkNode *head)
{
    struct LinkNode *p, *q = head->next;
    while (p != head) {
        q = p->next;
        free(p);
        p = q;
    }
    head->prev = head->next = head;
}

int EmptyDnode(struct LinkNode *head)
{
    if (head->prev == head && head->next == head) return 1;
    return 0;
}

struct LinkNode *CreateNode(struct LinkNode *head, int val)
{
    if (head == NULL) {
        struct LinkNode *new_node = (struct LinkNode *)calloc(1, sizeof(struct LinkNode));
        new_node->val = val;
        new_node->next = NULL;
        head = new_node;
        return head;
    }
    struct LinkNode *new_node = (struct LinkNode *)calloc(1, sizeof(struct LinkNode));
    new_node->val = val;
    new_node->next = head;
    head = new_node;
    return head; 
}

void printf_list(struct LinkNode *head)
{
    if (head == NULL) {
        return ;
    }
    struct LinkNode *head_bk = head;
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
    head = head_bk;    
}

void SwapLinkNode(struct LinkNode *x, struct LinkNode *y)
{
    int tmp;
    tmp = x->val;
    x->val = y->val;
    y->val = tmp;
}

struct LinkNode *ReverseNode(struct LinkNode *head)
{
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct LinkNode *next = NULL;
    struct LinkNode *pre = NULL;    
    while (head) {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}
void MergeLinkNode(struct LinkNode *a, struct LinkNode *b)
{
    if (a == NULL || b == NULL) return ;
    struct LinkNode *bak = a;
    while (a) {
        if (a->next == NULL) {
            a->next = b;
            break;
        }
        a = a->next;
    }
    a = bak;
}

void BubbleSortLinkNode(struct LinkNode *head)
{
    if (head == NULL) {
        return ;
    }
    int flag = 1, swap_val;
    struct LinkNode *new_head;
    struct LinkNode *tmp = NULL;
    while (flag) {
        flag = 0;
        new_head = head;
        while (new_head->next != tmp) {
            if (new_head->val > new_head->next->val) {
                swap_val = new_head->val;
                new_head->val = new_head->next->val;
                new_head->next->val = swap_val;
                flag = 1;
            }
            new_head = new_head->next;
        }
        tmp = new_head;
    }
}

void printf_arr(int *arr, int len)
{
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void swap(int *x, int *y)
{
    int t = *x;
    *x = *y;
    *y = t;
}

int FreeAllNode(struct LinkNode *head)
{
    if (head == NULL) return 0;
    struct LinkNode *tmp = NULL;
    while(head) {
        tmp = head->next;
        free(head);
        head = tmp;
    }
    if (head) return 0;
    return 1;
}

struct LinkNode *FreeNodeByVal(struct LinkNode *head, int val)
{
    if (head == NULL) return NULL;
    struct LinkNode *p = head->next;
    struct LinkNode *pre;
    while (p->val != val) {
        pre = p;
        p = p->next;
    }
    pre->next = p->next;
    free(p);
    return head;
}

int *QuickSort(int *arr, int start, int end)
{
    if (start >= end) return NULL;
    int mid = arr[end];
    int left = start;
    int right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right) left++;
        while (arr[right] >= mid && left < right) right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end]) {
        swap(&arr[left], &arr[end]);
    } else {
        left++;
    }
    if (left) QuickSort(arr, start, left - 1);
    QuickSort(arr, left + 1, end);
    return arr;
}

int *BubbleSort(int *arr, int len)
{
    int i=0, j =0, tmp =0;
    for (i = 0; i < len -1; i++) {
        for (j =0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }            
        }
    }
    return arr;
}

int *ReverseArr(int *arr, int len)
{
    int i=0, j=0;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1 - i; j++) {
            swap(&arr[j], &arr[j+1]);
        }
    }
    return arr;
}

int FindMaxVal(int *arr, int len)
{
    arr = QuickSort(arr, 0, len - 1);
    return arr[len - 1];
}

int howmanyone(int val)
{
    int cnt = 0;
    while (val) {
        if (val & 1)
            cnt++;
        val >>= 1;
    }
    return cnt;
}
int howmanybit(int val)
{
    int cnt = 0;
    while(val) {
        val >>= 1;
        cnt++;
    }
    return cnt;
}
int howmanyzero(int val)
{
    return howmanybit(val) - howmanyone(val);
}

int main(int argc, char *argv[])
{
    #define ValueTest 10
    struct LinkNode *head = NULL, *head1 = NULL;
    int arr[ValueTest];
    for (int i = 0; i < ValueTest; i++) {
        int rnum = rand() % ValueTest;
        head = CreateNode(head, rnum);
        head1 = CreateNode(head1, rand() % 10000);
        arr[i] = rnum;
    }
    printf("oringin list: ");
    printf_list(head);
    FreeNodeByVal(head, 3);
    printf("merge List ");
    MergeLinkNode(head, head1);
    printf_list(head);
    printf("Reverse List: ");    
    BubbleSortLinkNode(head);
    //head = ReverseNode(head);
    printf_list(head);
    printf("FreeAllNode: %d\n", FreeAllNode(head));
    printf("sort in c\n");
    printf("origin: ");
    printf_arr(&arr[0], ValueTest);

    BubbleSort(&arr[0], ValueTest);
    printf("bubblesort: ");
    printf_arr(&arr[0], ValueTest);
    printf("QuickSort: ");
    QuickSort(&arr[0], 0, ValueTest - 1);
    printf_arr(&arr[0], ValueTest);
    printf("ReverseArr: ");
    ReverseArr(&arr[0], ValueTest);
    printf_arr(&arr[0], ValueTest);
    printf("FindMaxVal: ");
    printf("%d\n", FindMaxVal(&arr[0], ValueTest));    
    printf("bit in 1000: %d, one in 1000: %d, zero in 1000: %d\n", howmanybit(ValueTest), howmanyone(ValueTest), howmanyzero(ValueTest));
    return 0;
}