c++链表

  1 #include <iostream>
  2 #include <stdlib.h>
  3 
  4 using namespace std;
  5 
  6 class Node
  7 {
  8 public:
  9     Node(int item)
 10     {
 11         m_item = item;
 12         m_next = NULL;
 13     }
 14     
 15     ~Node();
 16     void display() const;//?????????why const
 17     
 18     int m_item;
 19     Node *m_next;
 20 };
 21 
 22 Node::~Node()
 23 {
 24     if (m_next != NULL)
 25         delete m_next;
 26 }
 27 
 28 void Node::display() const
 29 {
 30     cout << "Item" << m_item << endl;
 31 }
 32 
 33 class Link
 34 {
 35 public:
 36     Link();
 37     ~Link();
 38     
 39     void insert_node(Node *p);
 40     void traverse();
 41     Node *find_node(int data);
 42     void remove_node(Node *p);
 43 private:    
 44     Node *m_head;        
 45 };
 46 Link::Link()
 47 {
 48     m_head = NULL;
 49 }
 50 
 51 Link::~Link()
 52 {
 53     if (m_head != NULL)
 54     {
 55         delete m_head;
 56     }
 57 }
 58 
 59 void Link::insert_node(Node *p)
 60 {
 61     if(m_head == NULL)
 62         m_head = p;
 63     else
 64     {
 65         p->m_next = m_head;
 66         m_head = p;
 67     }
 68 }
 69 
 70 void Link::traverse()
 71 {
 72     Node *p = m_head;
 73     
 74     while(p != NULL)
 75     {
 76         cout << p->m_item << endl;
 77         p = p->m_next;
 78     }
 79 }
 80 
 81 Node *Link::find_node(int data)
 82 {
 83     Node *p = m_head;
 84     
 85     while(p != NULL)
 86     {
 87         if(p->m_item == data)
 88             return p;
 89         p = p->m_next;
 90     }
 91     return NULL;
 92 }
 93 
 94 void Link::remove_node(Node *p)
 95 {
 96     Node *p1 = m_head;
 97     if(p == m_head)
 98     {
 99         m_head = m_head->m_next;
100         p->m_next = NULL;
101         return;
102     } 
103     while (p1->m_next != NULL)
104     {
105         if (p1->m_next == p)
106         {
107             p1->m_next = p->m_next;
108             return;
109         }
110         p1 = p1->m_next;
111     }
112 }
113 
114 int main(void)
115 {
116     Link link;
117     
118     Node *node = new Node(11);
119     link.insert_node(node);
120     node =  new Node(2);
121     link.insert_node(node);
122     node =  new Node(31);
123     link.insert_node(node);
124     node =  new Node(14);
125     link.insert_node(node);
126     node =  new Node(-5);
127     link.insert_node(node);
128 
129     link.traverse();
130     node = link.find_node(-5);
131     
132     if (node == NULL)
133     {
134         cout << "can‘t find %d\n" << -5;
135     }else
136     {
137         cout << "Remove: " << node->m_item << endl;
138            link.remove_node(node);
139     }
140     
141     link.traverse();
142     return 0;
143 }

代码分析：

先创建一个和节点有关的类，在构造函数中传入节点的值。创建一个数据节点和一个存放同类型数据的指针。

class Node
{
public:
    Node(int item)
    {
        m_item = item;
        m_next = NULL;
    }
    
    ~Node();
    void display() const;//?????????why const
    
    int m_item;
    Node *m_next;
};

完善其中的构造和析构函数

Node::~Node()
{
    if (m_next != NULL)
        delete m_next;
}

void Node::display() const
{
    cout << "Item" << m_item << endl;
}

创建一个和链表有关的类：

 1 class Link
 2 {
 3 public:
 4     Link();
 5     ~Link();
 6     
 7     void insert_node(Node *p);
 8     void traverse();
 9     Node *find_node(int data);
10     void remove_node(Node *p);
11 private:    
12     Node *m_head;        
13 };

完善其中的函数：

Link::Link()
{
    m_head = NULL;
}

Link::~Link()
{
    if (m_head != NULL)
    {
        delete m_head;
    }
}

void Link::insert_node(Node *p)
{
    if(m_head == NULL)
        m_head = p;
    else
    {
        p->m_next = m_head;
        m_head = p;
    }
}

void Link::traverse()
{
    Node *p = m_head;
    
    while(p != NULL)
    {
        cout << p->m_item << endl;
        p = p->m_next;
    }
}

Node *Link::find_node(int data)
{
    Node *p = m_head;
    
    while(p != NULL)
    {
        if(p->m_item == data)
            return p;
        p = p->m_next;
    }
    return NULL;
}

void Link::remove_node(Node *p)
{
    Node *p1 = m_head;
    if(p == m_head)
    {
        m_head = m_head->m_next;
        p->m_next = NULL;
        return;
    } 
    while (p1->m_next != NULL)
    {
        if (p1->m_next == p)
        {
            p1->m_next = p->m_next;
            return;
        }
        p1 = p1->m_next;
    }
}

写主函数;

int main(void)
{
    Link link;
    
    Node *node = new Node(11);
    link.insert_node(node);
    node =  new Node(2);
    link.insert_node(node);
    node =  new Node(31);
    link.insert_node(node);
    node =  new Node(14);
    link.insert_node(node);
    node =  new Node(-5);
    link.insert_node(node);

    link.traverse();
    node = link.find_node(-5);
    
    if (node == NULL)
    {
        cout << "can‘t find %d\n" << -5;
    }else
    {
        cout << "Remove: " << node->m_item << endl;
           link.remove_node(node);
    }
    
    link.traverse();
    return 0;
}

 此外：写了一个和c语言差不多的c++的链表（最开始学习时候写的）

#include <iostream>
#include <stdlib.h>

using namespace std;

typedef struct Node
{
    int item;
    Node *next;
}Node;

Node *head = NULL;

Node *mkdir_node(int date)
{
    Node *p = new Node;
    p->item = date;
    p->next = NULL;
    
    return p;
}

void insert_node(Node *p)
{
    if(head == NULL)
        head = p;
    else
    {
        p->next = head;
        head = p; 
    }
}

void traverse()
{
    Node *p = head;
    while(p != NULL)
    {
        cout << p->item << endl;
        p = p->next;
    }    
}

int main(void)
{
    Node *p = mkdir_node(11); 
    
    insert_node(p);
    p = mkdir_node(12); 
    insert_node(p);
    traverse();
    
    return 0;
}