面试常考的写代码题

面试百度、腾讯、阿里的时候多多少少都问到些，要求在纸上写出。

以下代码是自己看数据结构书写出的总结。大家一定要自己动手写一写，画一画算法的过程图，毕竟自己写出来的才是属于自己的，切勿眼高手低啊 : )

 

//排序算法
void BubbleSort(int *a, int len){
    int i, j;
    for(i = 0; i < len - 1; i++){
        for(j = len - 1; j >= i; j--){
            if(a[j+1] < a[j]){
                swap(&a[j+1], &a[j]);
            }
        }
    }
}

void SelectSort(int *a, int len){
    int i, j;
    for(i = 0; i < len - 1; i++){
        for(j = i + 1; j < len; j++){
            if(a[j] < a[i]){
                swap(&a[i], &a[j]);
            }
        }
    }
}

void InsertSort(int *a, int len){
    int i, j, k;
    for(i = 2; i <= len; i++){
        a[0] = a[i];
        for(j = i - 1; a[j] > a[i]; j--);
        for(k = i - 1; k > j; k--){
            swap(&a[k+1], &a[k]);
        }
        a[j+1] = a[0];
    }
}

int Partition(int *a, int first, int last){
    int midkey = a[0];
    while(first < last){
        while(first < last && a[last] >= midkey)
            last--;
        a[first++] = a[last];
        while(first < last && a[first] <= midkey)
            first++;
        a[last--] = a[first];
    }
    a[first] = midkey;
    return first;
}

void QuickSort(int *a, int first, int last){
    if(first < last){
        int mid = Partition(a, first, last);
        QuickSort(a, first, mid - 1);
        QuickSort(a, mid + 1, last);
    }
}

int bisearch(int *a, int first, int last, int key){
    if(first <= last){
        int mid = (first + last)/2;
        if(key == a[mid]) return mid;
        else if(key > a[mid])
            return bisearch(a, mid + 1, last, key);
        else if(key < a[mid])
            return bisearch(a, first, mid - 1, key);
    }
    else
        return -1;
}

int bisearch_norecur(int *a, int first, int last, int key){
    int mid;
    while(first <= last){
        mid = (first + last)/2;
        if(key == a[mid]) return mid;
        else if(key < a[mid]) last = mid - 1;
        else if(key > a[mid]) first = mid + 1;
    }
    return -1;
}

//单双链表的基本操作
typedef struct node{
    int val;
    struct node *prev;
    struct node *next;
}node;

node *creatlist(int len){
    if(len == 0)
        return NULL;
    node *head = (node *)malloc(sizeof(node));
    head->next = NULL;
    head->prev = NULL;
    printf("请输入第1个节点的值：");
    scanf("%d", &head->val);
    node *p = head;
    int i;
    for(i = 1; i < len; i++){
        node *new_node = (node *)malloc(sizeof(node));
        new_node->next = NULL;
        new_node->prev = NULL;
        printf("请输入第%d个节点的值：", i+1);
        scanf("%d", &new_node->val);
        p->next = new_node;
        new_node->prev = p;
        p = new_node;
    }
    return head;
}

void showlist(node *head){
    if(!head)
        return;
    node *p = head;
    while(p){
        if(!p->next){
            printf("%d\t", p->val);
            break;
        }
        printf("%d\t", p->val);
        p = p->next;
    }
    printf("\nreverse\n");

    while(p){
        printf("%d\t", p->val);
        p = p->prev;
    }
    printf("\n");
}
node *delnode(node *head, int key){
    if(!head)
        return;
    node *p = head;
    node *tmp = NULL;
    while(p->val == key){
        if(p->next){
            p->next->prev = NULL;
            tmp = p;
            p = p->next;
            free(tmp);
        }
        else{
            free(p);
            return NULL;
        }
    }
    head = p;
    p = p->next;
    while(p){
        if(p->val == key){
            if(!p->next){
                p->prev->next = NULL;
                free(p);
                return head;
            }
            p->prev->next = p->next;
            p->next->prev = p->prev;
            tmp = p;
            p = p->next;

            free(tmp);
        }
        else{
            p = p->next;
        }
    }
    return head;
}

node *addnode(node *head, int key){
    node *new_node = (node *)malloc(sizeof(node));
    new_node->val = key;
    new_node->next = NULL;
    new_node->prev = NULL;
    if(!head)
        return new_node;
    if(key < head->val){
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
        return head;
    }
    node *p = head->next;
    while(p && key > p->val){
        if(!p->next){
            p->next = new_node;
            new_node->prev = p;
            return head;
        }
        p = p->next;
    }

    new_node->prev = p->prev;
    new_node->next = p;
    p->prev->next = new_node;
    p->prev = new_node;

    return head;
}


typedef struct node{
    int val;
    struct node *next;
}node;

node *createlist(int len){
    if(len == 0){
        return NULL;
    }

    node *head = (node *)malloc(sizeof(node));
    head->next = NULL;
    printf("请输入第1个节点的值：");
    scanf("%d", &head->val);
    node *p = head;
    int i;
    for(i = 1; i < len; i++){
        node *new_node = (node *)malloc(sizeof(node));
        new_node->next = NULL;
        printf("请输入第%d个节点的值：", i+1);
        scanf("%d", &new_node->val);
        p->next = new_node;
        p = new_node;
    }

    return head;
}

void showlist(node *head){
    if(!head)
        return;
    node *p = head;
    while(p){
        printf("%d\t", p->val);
        p = p->next;
    }
    printf("\n");
}

node *delnode(node *head, int key){
    if(!head)
        return NULL;
    node *p = head;
    node *tmp = NULL;
    while(p && p->val == key){
        tmp = p;
        p = p->next;
        free(tmp);
    }
    if(!p)
        return NULL;
    head = p;
    node *r = p->next;
    while(r){
        if(r->val == key){
            p->next = r->next;
            tmp = r;
            r = r->next;

            free(tmp);
        }
        else{
            p = r;
            r = r->next;
        }
    }

    return head;
}

node *addnode(node *head, int key){
    node *new_node = (node *)malloc(sizeof(node));
    new_node->next = NULL;
    new_node->val = key;
    if(!head)
        return new_node;
    if(key < head->val){
        new_node->next = head;
        head = new_node;
        return head;
    }
    node *p = head;
    while(p->next && key > p->next->val){
        p = p->next;
    }
    new_node->next = p->next;
    p->next = new_node;
    return head;
}

//链栈与链队列
typedef struct queue{
    node *head;
    node *tail;
}queue;

typedef struct stack{
    node *top;
    node *bottom;
}stack;

queue *insertqueue(queue *q, int x){
    if(!q)
        return NULL;
    node *new_node = (node *)malloc(sizeof(node));
    new_node->val = x;
    new_node->next = NULL;

    if(q->head == NULL){
        q->head = new_node;
        q->tail = new_node;
    }
    else{
        q->tail->next = new_node;
        q->tail = new_node;
    }
    return q;
}

queue *delqueue(queue *q){
    if(!q)
        return NULL;
    if(q->head == NULL){
        printf("队列中无节点\n");
        return q;
    }
    if(q->head == q->tail){
        free(q->head);
        q->head = q->tail = NULL;
    }
    else{
        node *tmp = q->head;
        q->head = q->head->next;
        free(tmp);
    }
    return q;
}

stack *pushstack(stack *s, int x){
    if(!s)
        return NULL;
    node *new_node = (node *)malloc(sizeof(node));
    new_node->val = x;
    new_node->next = NULL;
    if(s->top == NULL){
        s->top = s->bottom = new_node;
    }
    else{
        s->top->next = new_node;
        s->top = new_node;
    }
    return s;
}

stack *popstack(stack *s){
    if(!s)
        return NULL;
    if(s->top == NULL){
        printf("栈中没有元素\n");
        return s;
    }
    if(s->top == s->bottom){
        free(s->top);
        s->top = s->bottom = NULL;
    }
    else{
        node *p = s->bottom;
        while(p->next != s->top)
            p = p->next;
        free(s->top);
        s->top = p;
    }
    return s;
}