单链表的基本操作及应用

单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的基本操作包括：创建、插入、删除、查找和显示。下面是具体的实现步骤：

1. 创建单链表：定义一个 `Node` 结构体，用于表示链表的节点，其中包括一个数据元素和一个指向下一个节点的指针。然后定义一个 `LinkedList` 类，其中包括一个头节点指针，用于指向链表的头节点。链表的创建可以通过从头节点开始，依次插入新的节点来实现。

   struct Node {
       int data;
       Node* next;
   };
   
   class LinkedList {
   public:
       LinkedList() {
           head = new Node;
           head->next = nullptr;
       }
   
       void createList(int n) {
           Node* p = head;
           for (int i = 0; i < n; i++) {
               int data;
               cout << "请输入第" << i + 1 << "个节点的值：";
               cin >> data;
               Node* node = new Node;
               node->data = data;
               node->next = nullptr;
               p->next = node;
               p = node;
           }
       }
   
   private:
       Node* head;
   };

2. 插入节点：提供 `insertNode()` 方法，可以在链表中插入新的节点。需要考虑插入的位置和节点的值。比如，插入到链表的第三个位置，可以先找到链表的第二个节点，然后将新节点的指针指向第三个节点，第二个节点的指针指向新节点。

   void insertNode(int pos, int data) {
       Node* p = head;
       for (int i = 0; i < pos - 1; i++) {
           p = p->next;
       }
       Node* node = new Node;
       node->data = data;
       node->next = p->next;
       p->next = node;
   }

3. 删除节点：提供 `deleteNode()` 方法，可以删除链表中的指定节点。需要考虑被删除节点的前驱节点和后继节点的连接。比如，删除链表的第三个节点，可以先找到链表的第二个节点，然后将第二个节点的指针指向第四个节点，释放第三个节点的内存空间。

   void deleteNode(int pos) {
       Node* p = head;
       for (int i = 0; i < pos - 1; i++) {
           p = p->next;
       }
       Node* q = p->next;
       p->next = q->next;
       delete q;
   }

4. 查找节点：提供 `searchNode()` 方法，可以在链表中查找指定值的节点。需要遍历整个链表，依次比较节点的值。如果找到了目标节点，返回它的位置；否则返回 -1。

   int searchNode(int data) {
       Node* p = head->next;
       int pos = 1;
       while (p != nullptr) {
           if (p->data == data) {
               return pos;
           }
           p = p->next;
           pos++;
       }
       return -1;
   }

5. 显示链表：提供 `displayList()` 方法，可以将整个链表打印出来，方便查看和调试。需要遍历整个链表，依次输出每个节点的值。

   void displayList() {
       Node* p = head->next;
       while (p != nullptr) {
           cout << p->data << " ";
           p = p->next;
       }
       cout << endl;
   }

6. 通讯录设计（应用）：在 `Node` 结构体中增加姓名、电话等属性，实现通讯录的基本功能，比如添加联系人、删除联系人、查找联系人等。

   struct Node {
       string name;
       string phone;
       Node* next;
   };
   
   class AddressBook {
   public:
       AddressBook() {
           head = new Node;
           head->next = nullptr;
       }
   
       void addContact(string name, string phone) {
           Node* p = head;
           while (p->next != nullptr) {
               p = p->next;
           }
           Node* node = new Node;
           node->name = name;
           node->phone = phone;
           node->next = nullptr;
           p->next = node;
       }
   
       void deleteContact(string name) {
           Node* p = head;
           while (p->next != nullptr) {
               if (p->next->name == name) {
                   Node* q = p->next;
                   p->next = q->next;
                   delete q;
                   return;
               }
               p = p->next;
           }
           cout << "通讯录中不存在该联系人！" << endl;
       }
   
       void searchContact(string name) {
           Node* p = head->next;
           while (p != nullptr) {
               if (p->name == name) {
                   cout << "姓名：" << p->name << "，电话：" << p->phone << endl;
                   return;
               }
               p = p->next;
           }
           cout << "通讯录中不存在该联系人！" << endl;
       }
   
       void displayContacts() {
           Node* p = head->next;
           while (p != nullptr) {
               cout << "姓名：" << p->name << "，电话：" << p->phone << endl;
               p = p->next;
           }
       }
   
   private:
       Node* head;
   };