再写LinkedList

为嘛是再写,其实关于Data Structure,我觉得自己真心已经疼爱过他们一次了,奈何学艺不精,所以一直想找机会再仔细看一次,这样既然再次有了疼爱他们的机会,那么也就认真的再爱一次。

C++ 与 C

C到C++,感觉像折翼的天使。好吧,其实问题的关键是在于不要流程化思维和硬想要的OOP思维。

另外,C++的野心太大:
template模板/通用编程 以及 语法糖 还有 编译重载有的时候让C++读起来显得吓人,晦涩难懂,特别是对于初学者。
还是不能一口吃掉一个大饼,还是先写类似C的C++,再来写像C++的C++.

Mac上编译C++11

$ clang++ -std=c++11 -stdlib=libc++ t.cpp

不谢

LinkedList_v1 (C style C++?)

struct node

struct node{
  int data;
  node* next;
}

insert node/val at head

值得注意的是: 如果要在头上插入node,这里传入的时node *&head
所谓的pass by reference,如果写C的话,那么估计应该写 node **head

// pass head by reference, since the head will be changed
void insertFront(node *&head, int n){
    node *tmp = new node;
    tmp->data = n;
    tmp->next = NULL;
    
    if (head == NULL) {
        head = tmp;
    } else {
        tmp->next = head;
        head = tmp;
    }
}

traverse 遍历的方法千千万

这里其实不引入curr变量应该也ok,因为传入的是node* head,把head这个pointer按值传入

void traverse(node* head){
    for (node* curr = head; curr != NULL; curr = curr->next)
        cout << curr->data << " ";
    cout << endl;
}

跟for循环异曲同工

void traverse2(node* head){
    while (head) {
        cout << head->data <<" ";
        head = head->next;
    }
    cout << endl;
}

用递归来traverse

void traverseRec(node* head){
    if (head == NULL) return;
    cout << head->data << " ";
    traverseRec(head->next);
}

来寻找一个值/node

bool findVal(node *head, int val){
    if (head == NULL) return false;
    if (head->data == val) return true;
    return findVal(head->next,val);
}

还可以返回值的地址
我调皮的打印发现NULL的地址是0x0;

node* find(node *head, int val){
    if (head == NULL) return NULL;
    if (head->data == val) return head;
    return find(head->next,val);
}

deleteNode或许可以优化


void deleteNode(node *&head, int n){
    //if not found, just return;
    if (!findVal(head,n)) return;
    
    node* prev = NULL;
    node* curr = head;
    // the delete node is at head
    if (head->data == n){
        head = head->next;
        delete curr;
    } else {
        while (curr->data != n) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = curr->next;
        delete curr;
    }
}

没有在这个上面花second thought,挑了一个方便走的方向就赶着走了出来,或许这个是可以优化的

reserveList才是真神作

void reverseList(node *&head){
    node* prev = NULL;
    node* curr = head;
    node* next = NULL;
    
    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}
void reverseListRec(node* &head){
    node* first;
    node* rest;
    
    if (head == NULL) return;
    
    first = head;
    rest = first->next;
    
    if (rest == NULL) return;
    
    reverseListRec(rest);
    
    first->next->next = first;
    
    first->next = NULL;
    head = rest;
    
}

无论是recursive还是loop类型的reverse linked list都让我感觉是真神作算法啊~

P.S. 太懒了,暂时就把代码折让扔着,然后等待更简洁,更可爱,更迷人,更可人的linkelist_v2吧(假装就是这样)

本文固定链接:

再写LinkedList

http://www.js-code.com/cpp/cpp_61185.html

80%的人都看过