21xrx.com
2024-09-20 00:38:22 Friday
登录
文章检索 我的文章 写文章
C++中链表的介绍和使用
2023-07-05 05:59:14 深夜i     --     --
链表 C++ 节点 指针 遍历

C++是一个面向对象的编程语言，具有高效、灵活、易用等优点，在实际的编程工作中广受程序员们的喜爱。在C++中，链表是一种常见的数据结构，可用于存储和管理一系列元素。本文将简要介绍C++中链表的概念、特点以及应用方法。

一、链表的概念和特点

链表是一种由节点集合构成的数据结构，节点包括两个部分：数据域和指针域。数据域用于存储节点的数据信息，指针域指向下一个节点，将一系列元素连接成一条链，故称之为“链表”。

链表的一个重要特点是可以动态地分配节点的空间，使得链表在空间利用上比较灵活，方便对元素的插入、删除等操作。此外，链表的访问时间通常是O(n)，也就是说，访问某个具体的元素需要进行整个链表的遍历，因此链表在一些应用场合几乎无法取代数组。

二、链表的实现方法

C++中链表的实现方法有多种，本文主要介绍两种：单链表和双向链表。

1. 单链表

单链表是最基本的链表形式，每个节点只有一个指针，指向下一个节点。对于单链表，需要维护头结点和尾节点的指针，便于向前或向后遍历链表。其实现方法如下：

class Node{          //节点类的定义

public:

  int data;         //节点数据域

  Node* next;        //节点指针域

  Node(int data, Node* next); //构造函数

};

Node::Node(int data, Node* next) //定义构造函数

  this->data = data;

  this->next = next;

class LinkedList{ //链表类的定义

public:

  LinkedList();         //构造函数

  ~LinkedList();         //析构函数

  void AddNode(int data);     //添加节点

  void DeleteNode(int data);   //删除节点

  void PrintList();        //输出链表

private:

  Node* head;           //头结点指针

  Node* tail;           //尾节点指针

};

LinkedList::LinkedList()     //定义构造函数

  head = tail = NULL;

LinkedList::~LinkedList()     //定义析构函数

{

  Node* p = head;

  while (p) {

    Node* q = p->next;

    delete p;

    p = q;

  }

  head = tail = NULL;

}

void LinkedList::AddNode(int data) //定义添加节点的函数

{

  Node* p = new Node(data, NULL);

  if (tail == NULL)

    head = tail = p;

  else

    tail->next = p;

    tail = p;

}

void LinkedList::DeleteNode(int data) //定义删除节点的函数

{

  Node* p = head, * q = NULL;

  while (p && p->data != data)

    q = p;

    p = p->next;

  if (p) {

    if (p == head)

      head = head->next;

    else if (p == tail)

      tail = q;

      q->next = NULL;

    else

      q->next = p->next;

    delete p;

  }

}

void LinkedList::PrintList() //定义输出链表函数

{

  Node* p = head;

  while (p)

    cout << p->data << " ";

    p = p->next;

}

2. 双向链表

双向链表是一种每个节点有两个指针的链表形式，指向前一个节点和后一个节点。相对于单链表，双向链表更易于对链表中元素进行双向遍历，在某些搜索问题中比单链表更加高效。其实现方法如下：

class DNode{           //双向链表节点类的定义

public:

  int data;          //节点数据域

  DNode* prev;        //指向前一个节点

  DNode* next;        //指向后一个节点

  DNode(int data, DNode* prev, DNode* next);

};

DNode::DNode(int data, DNode* prev, DNode* next) //定义构造函数

  this->data = data;

  this->prev = prev;

  this->next = next;

class DLinkedList {  //双向链表类的定义

public:

  DLinkedList();   //构造函数

  ~DLinkedList();  //析构函数

  void AddNode(int data);    //添加节点

  void DeleteNode(int data);   //删除节点

  void PrintList();       //输出链表

private:

  DNode* head;          //头结点指针

  DNode* tail;          //尾节点指针

};

DLinkedList::DLinkedList()     //定义构造函数

  head = tail = NULL;

DLinkedList::~DLinkedList()     //定义析构函数

{

  DNode* p = head;

  while (p) {

    DNode* q = p->next;

    delete p;

    p = q;

  }

  head = tail = NULL;

}

void DLinkedList::AddNode(int data) //定义添加节点函数

{

  DNode* p = new DNode(data, NULL, NULL);

  if (tail == NULL)

    head = tail = p;

  else

    tail->next = p;

    p->prev = tail;

    tail = p;

}

void DLinkedList::DeleteNode(int data) //定义删除节点函数

{

  DNode* p = head;

  while (p && p->data != data)

    p = p->next;

  if (p) {

    if (p == head)

      head = head->next;

      head->prev = NULL;

    else if (p == tail)

      tail = tail->prev;

      tail->next = NULL;

    else

      p->prev->next = p->next;

      p->next->prev = p->prev;

    delete p;

  }

}

void DLinkedList::PrintList() //定义输出链表函数

{

  DNode* p = head;

  while (p)

    cout << p->data << " ";

    p = p->next;

}

三、链表的应用

链表在编程中有着广泛的应用，可以用于数据的存储、排序、查找、垃圾回收等。下面介绍两个常见的例子。

1. 单链表实现栈

栈是一种后进先出的数据结构，常用于表达式求值、括号匹配等场合。通过单链表实现栈的代码如下：

class Stack{            //栈类的定义

public:

  Stack();           //构造函数

  bool IsEmpty();       //判断栈是否为空

  void Push(int data);      //向栈中压入一个元素

  void Pop();          //从栈中弹出一个元素

  int Top();           //取栈顶元素

private:

  Node* top;           //栈顶指针

};

Stack::Stack()       //定义构造函数

  top = NULL;

bool Stack::IsEmpty()    //定义判断栈是否为空的函数

{

  return (top == NULL);

}

void Stack::Push(int data)   //定义向栈中压入元素的函数

{

  Node* p = new Node(data, NULL);

  if (top == NULL)

    top = p;

  else

    p->next = top;

    top = p;

}

void Stack::Pop()     //定义从栈中弹出元素的函数

{

  if (top) {

    Node* p = top;

    top = top->next;

    delete p;

  }

  else

    cout << "The stack is empty!" << endl;

}

int Stack::Top()     //定义取栈顶元素的函数

{

  if (top)

    return top->data;

  else

    cout << "The stack is empty!" << endl;

    return -1;

}

2. 双向链表实现LRU缓存

LRU（Least Recently Used）是一种缓存淘汰策略，常用于缓存系统中，实现方式是：当缓存空间已满时，淘汰最久未被使用的缓存。我们可以通过双向链表实现LRU缓存功能，其中双向链表中的头节点表示最近使用的缓存，尾节点表示最久未被使用的缓存。该功能实现代码如下：

class CacheNode{          //缓存节点类的定义

public:

  int key;            //节点数据域

  int value;           //节点数据域

  CacheNode* prev;        //指向前一个节点

  CacheNode* next;        //指向后一个节点

  CacheNode(int key, int value, CacheNode* prev, CacheNode* next);

};

CacheNode::CacheNode(int key, int value, CacheNode* prev, CacheNode* next) //定义构造函数

  this->key = key;

  this->value = value;

  this->prev = prev;

  this->next = next;

class LRUCache{            //LRU缓存类的定义

public:

  LRUCache(int capacity);     //构造函数

  int Get(int key);        //获取缓存中的元素

  void Put(int key, int value);  //向缓存中添加元素

private:

  CacheNode* head;         //头结点指针

  CacheNode* tail;         //尾节点指针

  unordered_map cache; //哈希表记录缓存中的元素

  int size;             //缓存中元素的个数

  int capacity;          //缓存容量

};

LRUCache::LRUCache(int capacity){  //定义构造函数

  head = new CacheNode(0, 0, NULL, NULL); //创建头节点

  tail = new CacheNode(0, 0, head, NULL); //创建尾节点

  head->next = tail;           //头节点指向尾节点

  size = 0;

  this->capacity = capacity;

}

int LRUCache::Get(int key){      //定义获取缓存中元素的函数

  if (cache.count(key) == 0)     //如果缓存中没有该元素

    return -1;

  CacheNode* node = cache[key];

  node->prev->next = node->next;   //将该元素从链表中删除

  node->next->prev = node->prev;

  node->prev = head;         //将该元素插入到头节点后

  node->next = head->next;

  head->next->prev = node;

  head->next = node;

  return node->value;

}

void LRUCache::Put(int key, int value){ //定义向缓存中添加元素的函数

  if (cache.count(key) == 0) {     //如果缓存中没有该元素

    CacheNode* node = new CacheNode(key, value, NULL, NULL);

    cache[key] = node;

    node->prev = head;        //将该元素插入到头节点后

    node->next = head->next;

    head->next->prev = node;

    head->next = node;

    size++;

    if (size > capacity) {      //如果缓存已满，要删除最久未被使用的缓存

      CacheNode* temp = tail->prev;

      temp->prev->next = tail;

      tail->prev = temp->prev;

      cache.erase(temp->key);

      delete temp;

      size--;

    }

  }

  else {                //如果缓存中有该元素

    CacheNode* node = cache[key];

    node->value = value;

    node->prev->next = node->next;   //将该元素从链表中删除

    node->next->prev = node->prev;

    node->prev = head;         //将该元素插入到头节点后

    node->next = head->next;

    head->next->prev = node;

    head->next = node;

  }

}

结论：

链表是C++编程中广泛使用的数据结构之一，常用于数据存储、排序、查找等。本文介绍了C++中链表的概念、特点及两种实现方法：单链表和双向链表，并给出了两个链表应用的例子。当编写程序时，可以根据实际需要选择不同的链表形式，达到高效、灵活、易用的编程目的。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复