链表

评分: 3.6/5 (1099 票)

一组相同类型的数据项，其中每个数据项指向（“链接到”）列表中的下一个数据项。数据项的顺序不是定义的一部分，因此我们不考虑顺序。顺序取决于用法。

注意： 由于元素序列不是链表定义的一部分，因此可以使用链表实现许多其他结构。
例如，如果数据项根据插入列表的顺序进行排序，这对应于堆栈，其中顶层数据项由列表的头指针指向。

头指针

列表头是指向列表中第一个数据项的特殊指针。
最后一个节点（尾部）指向一个NULL地址
在处理列表时，任何节点只能在访问了它之前的所有其他节点后才能访问。此属性也可以称为严格顺序访问 (SSA)。

// implementation of LinkedList
// the Node class will be given later
// Author: Ali Selcuk AKYUZ
// Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr
// Electrical and Electronics Engineering Department
// Middle East Technical University - ANKARA
// If any questions please send me an email

#include <iostream>
#include "Node.cpp"
using namespace std;
int main ()
{
  Node<char> *p,*q,*r;
  // Link the nodes with each other
  q = new Node<char>('B'); // here nxtptr is passed by a nullptr by default
  p = new Node<char>('A',q);
  r = new Node<char>('C');

  // modify the list
  q->InsertAfter(r);
  /*
  Call the InsertAfter method that belongs to the object pointed by q, as
  paramater, pass to it the address contained in r.
  */

  cout << "p:" << p->data << endl;                 // "A" will be printed out
  cout << "p_next:" << p->NextNode()->data << endl;  // "B" will be printed out
  cout << "q:" << q->data << endl;                 // "B" will be printed out
  cout << "q_next:" << q->NextNode()->data << endl;  // "C" will be printed out
  cout << "r:" << r->data << endl;                 // "C" will be printed out

  p = p->NextNode(); // p now points to the node coming after the node it was
                     // previously pointing to.
  cout << endl;
  cout << "p:" << p->data << endl;                 // "B" will be printed out

  r = q->DeleteAfter();        // copy to r the address of the node pointed by
  //the node pointed by the node pointed by q, and remove that node from the list

  Node<char> *head;
  head = GetNode('A',GetNode('B',GetNode('C')));
  /*
  Here above method, creates a list which has nodes having data A,B,C and each
  node pointing to the next one respectively.
  */
  delete q;
  delete p;
  delete r;
  return 0;
}


p:A
P_next:B
q:B
q_next:C
r:C

p:B

// Node.h
// Author: Ali Selcuk AKYUZ
// Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr
// Electrical and Electronics Engineering Department
// Middle East Technical University - ANKARA 
// If any questions please send me an email

#ifndef NODE_H
#define NODE_H
#include <iostream>

using namespace std;

template<class T>
class Node
{
    public:
        Node();
        Node(const T& item, Node<T>* ptrnext = NULL);
        T data;
        // access to the next node
        Node<T>* NextNode();
        // list modification methods
        void InsertAfter(Node<T>* p);
        Node<T>* DeleteAfter();
        Node<T> * GetNode(const T& item, Node<T>* nextptr = NULL);
    private:

        Node<T> * next;
};

#endif // NODE_H

// implementation of Node class
// Author: Ali Selcuk AKYUZ
// Mail: selcuk@retinarobotics.com || e174043@metu.edu.tr
// Electrical and Electronics Engineering Department
// Middle East Technical University - ANKARA 
// If any questions please send me an email

#include "Node.h"

template<class T>
Node<T>::Node()
{
    // default constructor
    // this is to allow us to create an object without any initialization

}


//  This constructor is just to set next pointer of a node and the data contained.
template<class T>
Node<T>::Node(const T& item,Node<T>* ptrnext)
{
    this->data = item;
    this->next = ptrnext;
}

template<class T>
Node<T>*Node<T>::NextNode()
{
    return this->next;
}

//  This methods inserts a node just after the node that the method belongs to 
//  TO-DO: Consider a better implementation
template<class T>
void Node<T>::InsertAfter(Node<T> *p)
{
    // not to lose the rest of the list, we ought to link the rest of the
    // list to the Node<T>* p first
    p->next = this->next;

    // now we should link the previous Node to Node<T> *p , i.e the Node that we are 
    //inserting after,
    this->next = p;
}

// Deletes the node from the list and returns the deleted node
template<class T>
Node<T>* Node<T>::DeleteAfter()
{
    // store the next Node in a temporary Node
    Node<T>* tempNode = next;
    // check if there is a next node
    if(next != NULL)
        next = next->next;

    return tempNode;
}
template<class T>
Node<T> * GetNode(const T& item, Node<T>* nextptr = NULL)
{
    Node<T>* newnode; // Local ptr for new node
    newnode = new Node<T>(item,nextptr);
    if ( newnode == NULL)
    {
        cerr << "Memory allocation failed." << endl;
        exit(1);
    }
    return newnode;
}

堆栈、队列属性

堆栈: 如果数据项根据插入列表的顺序进行排序，这对应于堆栈。换句话说，先进后出 (FILO) 或后进先出 (LIFO)
队列: 队列是一种数据结构，由一系列数据项以及指向列表“前端”和“后端”数据项的两个指针组成。数据项只能在尾部插入，只能在头部移除。即先进先出 (FIFO) 操作。