C++单链表的实现 |21xrx.com

C++单链表的实现

2023-07-05 10:06:02 深夜i 13 0

C++ 单链表实现

单链表是一种常见的数据结构，在C++中可以通过类的方式来实现单链表。下面是单链表的实现步骤及代码示例。

1. 定义链表节点结构体

链表的节点包括数据成员和指向下一个节点的指针成员。这里定义一个结构体来表示链表节点：

struct ListNode {
  int val;    // 节点的值
  ListNode* next; // 指向下一个节点的指针
};

2. 定义链表类

链表类包括数据成员和方法成员。数据成员包括链表的头节点指针和链表的长度，方法成员包括链表的初始化、插入、删除、查找和打印等。

class LinkedList {
public:
  LinkedList();      // 构造函数
  ~LinkedList();     // 析构函数
  void insertFront(int x);// 在头部插入一个节点
  void deleteFront();   // 删除头部节点
  bool search(int x);   // 查找节点是否存在
  void print();      // 打印链表
private:
  ListNode* head;     // 头节点指针
  int length;       // 链表长度
};

3. 实现链表类的方法

- 构造函数和析构函数

构造函数初始化头节点指针为NULL，链表长度为0。

析构函数遍历链表并释放每个节点的空间。

LinkedList::LinkedList()
  head = NULL;
  length = 0;
LinkedList::~LinkedList() {
  ListNode* curr = head;
  while (curr != NULL) {
    ListNode* temp = curr;
    curr = curr->next;
    delete temp;
  }
}

- 在头部插入一个节点

在头部插入一个节点需要先创建一个新的节点，把头节点的指针指向新节点，新节点的指针指向原来的头节点，然后更新链表长度。

void LinkedList::insertFront(int x) {
  ListNode* newNode = new ListNode;
  newNode->val = x;
  newNode->next = head;
  head = newNode;
  length++;
}

- 删除头部节点

删除头部节点需要先把头节点指针指向它下一个节点，然后释放头节点的空间，最后更新链表长度。

void LinkedList::deleteFront() {
  if (head == NULL) return;
  ListNode* temp = head;
  head = head->next;
  delete temp;
  length--;
}

- 查找节点是否存在

遍历链表查找每个节点的值是否等于给定的值，如果找到则返回true，否则返回false。

bool LinkedList::search(int x) {
  ListNode* curr = head;
  while (curr != NULL) {
    if (curr->val == x) return true;
    curr = curr->next;
  }
  return false;
}

- 打印链表

遍历链表打印每个节点的值。

void LinkedList::print() {
  ListNode* curr = head;
  while (curr != NULL)
    cout << curr->val << " ";
    curr = curr->next;
  
  cout << endl;
}

4. 测试链表类

定义一个LinkedList对象并执行一些插入、删除、查找和打印操作。

int main() {
  LinkedList list;
  list.insertFront(1);
  list.insertFront(2);
  list.insertFront(3);
  list.print(); // 3 2 1
  list.deleteFront();
  list.print(); // 2 1
  cout << list.search(3) << endl; // 0
  cout << list.search(2) << endl; // 1
  return 0;
}

以上就是在C++中实现单链表的完整过程。单链表虽然简单，但是在算法题中非常常见，理解单链表的实现原理能够帮助我们更好地理解和实现算法题目。

上一篇: idea打包java可执行jar包

下一篇: C++ 图片旋转的实现方法

评论区

相似文章