具体实现代码@数据结构探险——链表

file:Node.hpp

#ifndef Node_hpp
#define Node_hpp

#include 

class Node{
public:
    Node();
    ~Node();
    void printData();

public:
    int data;
    Node *next;
    Node *prev;
};

#endif 

file:Node.cpp

#include "Node.hpp"
#include 

using namespace std;

Node::Node(){

}

Node::~Node(){

}

void Node::printData(){
    cout << data;
}

file:linkedList.hpp

#ifndef linkedList_hpp
#define linkedList_hpp

#include 
#include "Node.hpp"

class linkedList{
public:
    linkedList();
    ~linkedList();
    void ClearList();
    bool ListEmpty();
    int ListLength();
    bool getElem(int index,Node *pNode);
    int locateElem(Node *pNode);
    bool preElem(Node *pCurrentNode,Node *pPreNode);
    bool nextElem(Node *pCurrentNode,Node *pNextNode);
    void ListTraverse();
    bool ListInsert(int index,Node *pNode);
    bool ListDelete(int index,Node *pNode);
    bool ListInsertHead(Node *pNode);
    bool ListInsertTail(Node *pNode);
private:
    int m_iLength;
    Node *m_pList;
};

#endif 

file:linkedList.cpp

#include "linkedList.hpp"
#include 

using namespace std;

linkedList::linkedList(){
    m_pList = new Node;
    m_pList->data = 0;
    m_pList->next = NULL;
    m_iLength = 0;
}

bool linkedList::ListEmpty(){
    return m_iLength==0?true:false;
}

int linkedList::ListLength(){
    return m_iLength;
}

void linkedList::ClearList(){
    Node *CurrentNode = m_pList->next;
    while(CurrentNode != NULL){
 Node *temp = CurrentNode->next;
 delete CurrentNode;
 CurrentNode = temp;
    }
    m_pList->next = NULL;
    m_iLength = 0;
}

linkedList::~linkedList(){
    ClearList();
    delete m_pList;
    m_pList = NULL;
}

bool linkedList::ListInsertHead(Node *pNode){
    Node *temp = m_pList->next;
    Node *newNode = new Node;
    if(newNode == NULL){
 return false;
    }
    else{
 m_pList->next = newNode;
 newNode->data = pNode->data; 
 newNode->next = temp;

 m_iLength++;
 return true;
    }
}

bool linkedList::ListInsertTail(Node *pNode){
    Node *CurrentNode = m_pList;
    while(CurrentNode->next != NULL){
 CurrentNode = CurrentNode->next;
    }
    Node *newNode = new Node;
    if(newNode == NULL){
 return false;
    }
    else{
 CurrentNode->next = newNode;
 newNode->data = pNode->data;
 newNode->next = NULL;

 m_iLength++;
 return true;
    }
}

bool linkedList::ListInsert(int index, Node *pNode){
    if(index < 0 || index > m_iLength){
 return false;
    }
    else{
 Node *CurrentNode = m_pList;
 for(int k = 0;k < index;k++){
     CurrentNode = CurrentNode->next;
 }
 Node *newNode = new Node;
 if(newNode == NULL){
     return false;
 }
 else{
     newNode->data = pNode->data;
     newNode->next = CurrentNode->next;
     CurrentNode->next = newNode;

     m_iLength++;
     return true;
 }
    }
}

bool linkedList::ListDelete(int index, Node *pNode){
    if(index < 0 || index > m_iLength){
 return false;
    }
    else{
 Node *CurrentNode = m_pList;
 Node *CurrentNodePre = NULL;
 for(int k = 0;k < index;k++){
     CurrentNodePre = CurrentNode;
     CurrentNode = CurrentNode->next;
 }
 CurrentNodePre->next = CurrentNode->next;
 pNode->data = CurrentNode->data;
 delete CurrentNode;
 CurrentNode = NULL;
 m_iLength--;
 return true;
    }
}

bool linkedList::getElem(int index,Node *pNode){
    if(index < 0 || index > m_iLength){
 return false;
    }
    else{
 Node *CurrentNode = m_pList;
 Node *CurrentNodePre = NULL;
 for(int k = 0;k < index;k++){
     CurrentNodePre = CurrentNode;
     CurrentNode = CurrentNode->next;
 }
 pNode->data = CurrentNode->data;
 return true;
    }
}

int linkedList::locateElem(Node *pNode){
    Node *CurrentNode = new Node;
    int count = 0;
    while(CurrentNode->next != NULL){
 CurrentNode = CurrentNode->next;
 if(CurrentNode->data == pNode->data){
     return count;
 }
 else{
     count ++;
 }
    }
    return -1;
}

bool linkedList::preElem(Node *pCurrentNode,Node *pPreNode){
    Node *CurrentNode = m_pList;
    Node *tempNode = NULL;
    while(CurrentNode->next != NULL){
 tempNode = CurrentNode;
 CurrentNode = CurrentNode->next;
 if(CurrentNode->data == pCurrentNode->data){
     if(tempNode == m_pList){
  return false;
     }
     else{
  pPreNode->data = tempNode->data;
  return true;
     }
 }
    }
    return false;
}

bool linkedList::nextElem(Node *pCurrentNode,Node *pNextNode){
    Node *CurrentNode = m_pList;
    while(CurrentNode->next != NULL){
 CurrentNode = CurrentNode->next;
 if(CurrentNode->data == pCurrentNode->data){
     if(CurrentNode->next == NULL ){
  return false;
     }
     else{
  pNextNode->data = CurrentNode->next->data;
  return true;
     }
 }
    }
    return false;
}

void linkedList::ListTraverse(){
    Node *CurrentNode = m_pList;
    while(CurrentNode->next != NULL){
 CurrentNode = CurrentNode->next;
 CurrentNode->printData();
    }
    cout << endl;
}

file:demo.cpp

#include 
#include 
#include "linkedList.hpp"

using namespace std;

int main(void){
    Node node1;
    node1.data = 3;

    Node node2;
    node2.data = 4;

    Node node3;
    node3.data = 5;

    Node node4;
    node4.data = 6;

    linkedList *pList = new linkedList();

    cout << endl << "测试ListInsertHead:" << endl << endl;
    pList->ListInsertHead(&node1);
    pList->ListTraverse();

    pList->ListInsertHead(&node2);
    pList->ListTraverse();

    pList->ListInsertHead(&node3);
    pList->ListTraverse();

    pList->ListInsertHead(&node4);
    pList->ListTraverse();

    cout << endl << "测试ListInsertTail:" << endl << endl;
    pList->ListInsertTail(&node1);
    pList->ListTraverse();

    pList->ListInsertTail(&node2);
    pList->ListTraverse();

    pList->ListInsertTail(&node3);
    pList->ListTraverse();

    pList->ListInsertTail(&node4);
    pList->ListTraverse();

    cout << endl << "测试ListInsert:" << endl << endl;
    Node node5;
    node5.data = 0;
    pList->ListInsert(1, &node5);
    pList->ListTraverse();

    pList->ListInsert(2, &node5);
    pList->ListTraverse();

    pList->ListInsert(4, &node5);
    pList->ListTraverse();

    pList->ListInsert(11, &node5);
    pList->ListTraverse();

    cout << endl << "测试ListDelete:" << endl << endl;
    Node node;
    pList->ListDelete(1, &node);
    node.printData();
    cout << endl;
    pList->ListTraverse();

    pList->ListDelete(3, &node);
    node.printData();
    cout << endl;
    pList->ListTraverse();

    pList->ListDelete(5, &node);
    node.printData();
    cout << endl;
    pList->ListTraverse();

    cout << endl << "测试getElem:" << endl << endl;
    pList->getElem(1, &node);
    node.printData();
    cout << endl;

    pList->getElem(4, &node);
    node.printData();
    cout << endl;

    pList->getElem(6, &node);
    node.printData();
    cout << endl;

    pList->getElem(8, &node);
    node.printData();
    cout << endl;

    cout << endl << "测试nextElem:" << endl << endl;
    pList->ListTraverse();

    pList->nextElem(&node1, &node);
    node.printData();
    cout << endl;

    pList->nextElem(&node3, &node);
    node.printData();
    cout << endl;

    pList->nextElem(&node4, &node);
    node.printData();
    cout << endl;

    cout << endl << "测试preElem:" << endl << endl;
    pList->ListTraverse();

    pList->preElem(&node1, &node);
    node.printData();
    cout << endl;

    pList->preElem(&node3, &node);
    node.printData();
    cout << endl;

    pList->preElem(&node4, &node);
    node.printData();
    cout << endl;

    cout << endl << "测试locateElem:" << endl << endl;
    cout << pList->locateElem(&node1) << endl;
    cout << pList->locateElem(&node3) << endl;
    cout << pList->locateElem(&node4) << endl;

    cout << endl << "测试ListLength:" << endl << endl;
    cout << pList->ListLength() << endl;

    cout << endl << "测试ClearList:" << endl << endl;
    cout << pList->ListEmpty() << endl;
    pList->ClearList();
    pList->ListTraverse();
    cout << pList->ListLength() << endl;
    cout << pList->ListEmpty() << endl;

    delete pList;
    pList = NULL;
}