由于找工作要惡補(bǔ)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，為了手撕代碼方便，寫了很多代碼并測試。都是些找工作常考的，現(xiàn)在貼上來，不定期更新部分代碼。

• 含有鏈表反轉(zhuǎn)，排序算法，查找算法和二叉樹的遍歷算法。
• 都是?？嫉氖炙捍a，建議找工作的童鞋使勁背。
• 里面每一段代碼都是經(jīng)過調(diào)試的。
• IDE建議使用CLion，個人感覺比較好用，沒有VS那么大，不想破解就下社區(qū)版，配置教程可以參考我另一篇文章Window10極簡CLion配置教程。

鏈表反轉(zhuǎn)

1. 結(jié)點(diǎn)定義

struct node{
    int node_data;
    struct node* next;
    node(int x) : node_data(x){}
};

2. 遞歸版

node* In_reverseList(node* head){
    if(head!=NULL && head->next != NULL){
        // l是新鏈表頭
        node* l = In_reverseList(head->next);
        head->next->next = head;
        head->next=NULL;
        return l;
    } else
        return head;
}

3. 非遞歸版

node* reverseList(node* head){
    if (head != NULL && head->next != NULL){
        node* p = head;
        node *q, *newNode=NULL;
        while (p!=NULL) {
            q = p->next;
            p->next=newNode;
            newNode=p;
            p=q;
        }
        return newNode;
    }
}

排序算法

1.冒泡排序法

// 冒泡排序
vector<int> bubblesort(vector<int> u_in)
{
    vector<int> unii = u_in;
    for (int i = 0; i < unii.size(); i++)
    {
        int tmp = 0;
        for (int j = i + 1; j < unii.size(); j++)
        {
            if (unii[i] > unii[j])
            {
                tmp = unii[i];
                unii[i] = unii[j];
                unii[j] = tmp;
            }
        }
    }
    return unii;
}

2.選擇排序法

// 選擇排序法
void selectsort(int *a, int n) {
    int min;
    for (int i = 0; i < n; i++) {
        min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}

3.快速排序法

// 快排，數(shù)組版
void quicksort(int *a, int left, int right)
{
    if (left >= right) return;
    int i = left;
    int j = right;
    int based = a[left];
    while (i < j) {
        while (i < j && a[j] >= based) j--;
        if (i < j) {
            a[i] = a[j];
            i++;
        }
        while (i < j && a[i] < based) i++;
        if (i < j) {
            a[j] = a[i];
            j--;
        }
        if (i >= j) break;
    }
    a[i] = based;
    quicksort(a, left, j - 1);
    quicksort(a, j + 1, right);
}

4.歸并排序法

// 歸并排序單元使用
void mergearr(int* a, int begin, int mid, int end, int *temp){
    int i=begin, j=mid+1;
    int m = mid, n = end;
    int k = 0;
    while (i <= m && j<= n){
        if (a[i]<a[j])
            temp[k++]=a[i++];
        else
            temp[k++]=a[j++];
    }
    while (i<=m)
        temp[k++]=a[i++];
    while (j<=n)
        temp[k++]=a[j++];
    for (i=0;i<k;i++){
        a[begin+i]=temp[i];
    }
}

// 歸并排序算子
void _merge_sort(int* a, int begin, int end, int *temp){
    if(begin<end) {
        int mid = (begin + end) / 2;
        _merge_sort(a, begin, mid, temp);
        _merge_sort(a, mid + 1, end, temp);
        mergearr(a, begin, mid, end,temp);
    }
}

// 歸并排序
int* MergeSort(int *a, int len){
    int *temp = new int[len];
    _merge_sort(a,0,len-1,temp);
    return temp;
}

查找算法

1.二分查找（遞歸版）

// 二分查找
int getkey (int* a, int key, int low, int high)
{
    int mid = (low+high)/2;
    if (low>high) return -1;
    if (a[mid]==key) return mid;
    else if (a[mid]<key)
        return getkey(a,key,mid+1,high);
    else
        return getkey(a,key,low,mid-1);
}
int main(){
    int a[8]={5,10,29,37,39,56,65,88};
    int key = 88;
    cout<<getkey(a,key,0,8);
    return 0;
}

二叉樹遍歷（非遞歸版）

由于遞歸版過于簡單，一般來說面試是不會考的，所以只放非遞歸版。

• 節(jié)點(diǎn)定義

// 二叉樹節(jié)點(diǎn)
struct binode{
    int val;
    binode* left;
    binode* right;
    explicit binode(int v){
        val=v;
        left=nullptr;
        right=nullptr;
    }
    binode(int v, binode* l, binode* r){
        val=v;
        left=l;
        right=r;
    }
    void setlrnode( binode* l, binode* r){
        left=l;
        right=r;
    }
    void setlnode( binode* l){
        left=l;
    }
    void setrnode( binode* r){
        right=r;
    }
};

1.先序遍歷

// 先序遍歷
void preorder(binode* root){
    if (root==nullptr) return;
    binode *p=root;
    stack<binode*> s;
    while (p!=nullptr || !s.empty()){
        while (p!= nullptr){
            cout<<p->val;
            s.push(p);
            p=p->left;
        }
        if (!s.empty()){
            p=s.top();
            s.pop();
            p=p->right;
        }
    }
}

2.中序遍歷

中序遍歷就是先序遍歷的cout放到if里面。

// 中序遍歷
void midorder(binode* root){
    if (root==nullptr) return;
    binode *p=root;
    stack<binode*> s;
    while (p!=nullptr || !s.empty()){
        while (p!= nullptr){
            s.push(p);
            p=p->left;
        }
        if (!s.empty()){
            p=s.top();
            cout<<p->val;
            s.pop();
            p=p->right;
        }
    }
}

3.后序遍歷

后續(xù)遍歷很容易出問題，之前的寫的會內(nèi)存泄露，現(xiàn)在修改了。

// 后序遍歷
void postorder(binode* root){
    if (root==nullptr) return;
    binode *p=root;
    stack<binode*> s;
    stack<binode*> t;
    while (p!=nullptr || !s.empty()){
        while (p!= nullptr){
            s.push(p);
            t.push(p);
            p=p->right;
        }
        if (!s.empty()){
            p=s.top();
            s.pop();
            p=p->left;
        }
    }
    while (!t.empty()) {
        p=t.top();
        t.pop();
        cout<<p->val;
    }
}

4.層序遍歷

層序遍歷即廣度優(yōu)先搜索，按照每一層的節(jié)點(diǎn)從左到右輸出，代碼非常簡單，用于計算二叉樹的高度（面試題，今天小米面試被問了，沒想起來）。

// 二叉樹層序遍歷
void layerorder(binode* root){
    if(root== nullptr)
        return;
    binode* p;
    queue<binode*> q;
    q.push(root);
    while (!q.empty()){
        p = q.front();
        q.pop();
        cout<<p->val;
        if(p->left!= nullptr){
            q.push(p->left);
        }
        if(p->right!= nullptr){
            q.push(p->right);
        }
    }
}

5.測試用例

// 二叉樹測試
int main()
{
    /* 假設(shè)有二叉樹
          1
         |  \
        2    3
       |  \
      4    5
     |  \
    6    7
  */
    binode* root = new binode(1);
    // 構(gòu)造二叉樹，這樣寫是為了MD可以正常顯示
    binode nd1(2);
    binode nd2(3);
    binode nd3(4);
    binode nd4(5);
    binode nd5(6);
    binode nd6(7);
    root->setlrnode(&nd1,&nd2);
    nd1.setlrnode(&nd3,&nd4);
    nd3.setlrnode(&nd5,&nd6);
    // 遍歷
    preorder(root);
    cout<<endl;
    midorder(root);
    cout<<endl;
    postorder(root);
    cout<<endl;
    layerorder(root);
    return 0;
}

測試結(jié)果如下：

測試結(jié)果圖

不定期繼續(xù)更新ing~