Danh sách liên kết đơn

_list_full.cpp

/* http://lvduit.com */

#include <iostream> 
#include <time.h> 
using namespace std; 
  
const int MIN = 1; 
const int MAX = 50; 
  
typedef struct dNode { 
    int value; 
    struct dNode * next; 
} NODE; 
  
typedef struct nList { 
    struct dNode * head, * tail; 
} LIST; 
  
  
    // node function  
    inline NODE * createNode(int x); 
  
    // list function 
    inline LIST * createList(); 
    inline void printList(LIST * L); 
    inline void deleteList(LIST * L); 
      
    // head function 
    inline void addHead(LIST * L, NODE * newNode); 
    inline void addHead(LIST * L, int x); 
    inline NODE * removeHead(LIST * L); 
    inline void deleteHead(LIST * L); 
  
    // tail function 
    inline void addTail(LIST * L, NODE * newNode); 
    inline void addTail(LIST * L, int x); 
    inline void deleteTail(LIST * L); 
  
    // middle function 
    inline void addAfterNode(NODE * currentNode, NODE * newNode); 
    inline NODE * removeAfterNode(LIST * L, NODE * currentNode); 
    inline void deleteAfterNode(NODE * currentNode); 
    inline void deleteNodeX(LIST * L, int x); 
      
    // brower list 
    inline NODE * searchNode(LIST * L, int x); 
        inline NODE * findAndRemoveMinNode(LIST * L); 
  
    // Sort algorithms 
    inline void selectionSort(LIST * &  L); 
  
    // addon function 
    inline void swap(int & a, int & b) { a ^= b ^= a ^= b; } 
     int getRand() { return rand() % (MAX - MIN + 1) + MIN; } 
  
  
     // list action  
     NODE * reverse(LIST * L) { 
        NODE * next; 
        NODE * curr = L->head; 
        NODE * prev = NULL; 
  
        while (curr != NULL) { 
            next = curr->next; 
            curr->next = prev; 
  
            prev = curr; 
            curr = next; 
        } 
  
        return prev; 
    } 
  
// -------------------------------------------------------------------------------------------------- 
int main() { 
    srand((unsigned int)time(0)); 
  
    LIST * L = createList(); 
  
    for (int i = 0; i < 20; i++) { 
        addTail(L, getRand()); 
    } 
      
    printList(L); 
    cout << endl; 
    //selectionSort(L); 
  
    L->head = reverse(L); 
  
    printList(L); 
  
    return 0; 
} 
  
// -------------------------------------------------------------------------------------------------- 
  
  
inline NODE * createNode(int x) { 
    NODE * newNode = new NODE; 
  
    newNode->value = x; 
    newNode->next = NULL; 
  
    return newNode; 
} 
  
inline LIST * createList() { 
    LIST * newList = new LIST; 
  
    newList->head = newList->tail = NULL; 
  
    return newList; 
} 
  
inline void printList(LIST * L) { 
    NODE * currentNode = L->head; 
  
    while (currentNode != NULL) { 
        cout << currentNode->value << " "; 
        currentNode = currentNode->next; 
    } 
} 
  
inline void deleteList(LIST * L) { 
    if (L->head == NULL) return; 
  
    while (L->head != NULL) deleteHead(L); 
  
    return; 
} 
  
inline void addHead(LIST * L, NODE * newNode) { 
    if (newNode == NULL) return; 
    if (L->head == NULL) { 
        L->head = L->tail = newNode; 
        return; 
    } 
  
    newNode->next = L->head; 
    L->head = newNode; 
      
    return; 
} 
  
inline void addHead(LIST * L, int x) { 
    NODE * newNode = createNode(x); 
      
    return addHead(L, newNode); 
} 
  
inline NODE * removeHead(LIST * L) { 
    if (L->head == NULL) { 
        return NULL; 
    } 
  
    NODE * newNode = L->head; 
    L->head = L->head->next; 
    newNode->next = NULL; // break link 
  
    return newNode; 
} 
  
inline void deleteHead(LIST * L) { 
    NODE * newNode = removeHead(L); 
    delete newNode; 
  
    return; 
} 
  
inline void addTail(LIST * L, NODE * newNode) { 
    if (newNode == NULL) { 
        return; 
    } 
    if (L->tail == NULL) { 
        L->head = L->tail = newNode; 
    } 
  
    L->tail->next = newNode; 
    L->tail = newNode; 
      
    return; 
}  
  
inline void addTail(LIST * L, int x) { 
    NODE * newNode = createNode(x); 
    if (newNode == NULL) { 
        return; 
    } 
  
    return addTail(L, newNode); 
} 
  
inline void deleteTail(LIST * L) { 
    if (L->tail == NULL) { 
        return; 
    } 
  
    if (L->head == L->tail) { 
        NODE * newNode = L->head; 
        L = createList(); 
        delete newNode; 
  
        return; 
    } 
  
    NODE * currentNode = L->head; 
    while (currentNode != NULL) { 
        if (currentNode->next == L->tail) { 
            return deleteAfterNode(currentNode); 
        } 
        currentNode = currentNode->next; 
    } 
  
    return; 
} 
  
inline void addAfterNode(NODE * currentNode, NODE * newNode) { 
    if (newNode == NULL) return; 
    if (currentNode == NULL) return; 
  
    newNode->next = currentNode->next; 
    currentNode->next = newNode; 
  
    return; 
} 
  
inline NODE * removeAfterNode(NODE * currentNode) { 
    if (currentNode == NULL) return NULL; 
      
    NODE * newNode = currentNode->next; 
    currentNode->next = newNode->next; 
    newNode->next = NULL; 
  
    return newNode; 
} 
  
inline void deleteAfterNode(NODE * currentNode) { 
    if (currentNode == NULL) return; 
    NODE * deletedNode = removeAfterNode(currentNode); 
    delete deletedNode; 
  
    return; 
} 
  
inline void deleteNodeX(LIST * L, int x) { 
    if (L->head == NULL) return; 
    NODE * beforeNode, * currentNode; 
  
    currentNode = L->head; 
    beforeNode = NULL; 
    while (currentNode != NULL && currentNode->value != x) { 
        beforeNode = currentNode; 
        currentNode = currentNode->next; 
    } 
  
    if (currentNode == NULL) return; 
    if (beforeNode != NULL) deleteAfterNode(beforeNode); 
    else deleteHead(L); // duyet chua het list, before lai bang null => before chac chan la head 
  
    return; 
} 
  
inline NODE * searchNode(LIST * L, int searchValue) { 
    if (L->head == NULL) return NULL; 
  
    NODE * currentNode = L->head; 
    while (currentNode != NULL && currentNode->value != searchValue) { 
        currentNode = currentNode->next; 
    } 
  
    return currentNode; 
} 
  
inline void selectionSort(LIST * & L) { 
    LIST * newList = createList(); 
    NODE * minNode; 
  
    while (L->head != NULL) { 
        minNode = findAndRemoveMinNode(L); 
        if (minNode != NULL) addTail(newList, minNode); 
    } 
  
    L = newList; 
} 
  
inline NODE * findAndRemoveMinNode(LIST * L) { 
    if (L->head == NULL) return NULL; 
  
    NODE * minNode, * preMinNode, * currentNode; 
    minNode = currentNode = L->head; 
    preMinNode = NULL; 
      
    while (currentNode != NULL) { 
        if (currentNode->next != NULL && currentNode->next->value < minNode->value) { 
            minNode = currentNode->next; 
            preMinNode = currentNode; 
        } 
        currentNode = currentNode->next; 
    } 
  
    if (preMinNode == NULL) return removeHead(L); 
  
    return removeAfterNode(preMinNode); 
}