C++链表实现通讯录设计

本文将详细讲解如何使用C++语言实现一个基本的通讯录系统，该系统使用链表数据结构来保存联系人信息，并能够实现基本的增、删、查、改功能。本文的目标读者是具有一定C++基础的初学者。

实现思路

我们使用链表这种数据结构来存储联系人信息，每个节点表示一个联系人，可以存储该联系人的姓名、电话、住址等信息。每个节点不仅保存着联系人信息，还保存着指向前一个节点和后一个节点的指针，这样就可以在列表中轻松地插入和删除联系人了。

具体地，我们设计一个Person结构体来表示每个联系人，然后设计一个LinkedList类来表示整个通讯录系统。LinkedList类有以下几个成员函数：

• void addPerson()：添加一个新联系人；
• void deletePerson()：根据姓名删除联系人；
• void searchPerson()：根据姓名查找联系人；
• void printList()：打印整个通讯录；
• void saveList()：将通讯录保存到文件。

实现步骤

定义Person结构体

struct Person {
    string name;    // 姓名
    string phone;   // 电话
    string address; // 住址
    Person* prev;   // 前一个联系人的指针
    Person* next;   // 后一个联系人的指针
};

定义LinkedList类

class LinkedList {
public:
    LinkedList();
    ~LinkedList();
    void addPerson();
    void deletePerson();
    void searchPerson();
    void printList();
    void saveList();
private:
    void insertAtBegin(Person*);
    void insertAtEnd(Person*);
    void insertAtMiddle(Person*, Person*);
    void deleteNode(Person*);
    void deleteList();
    void sortList();
    Person* head;
};

其中，head变量表示链表的头指针。在类的构造函数中，将头指针初始化为空指针。

实现通讯录系统

首先，我们来完整地实现LinkedList类的定义。下面的代码中，我们省略了一部分具体实现，只给出了函数声明和注释，以便于直观地理解算法。

class LinkedList {
public:
    // 构造函数和析构函数
    LinkedList();
    ~LinkedList();

    // 添加、删除、查询联系人
    void addPerson();
    void deletePerson();
    void searchPerson();

    // 打印整个通讯录
    void printList();

    // 将通讯录保存到文件
    void saveList();

private:
    Person* head;

    // 在链表的头部插入联系人
    void insertAtBegin(Person*);

    // 在链表的尾部插入联系人
    void insertAtEnd(Person*);

    // 在链表的中间插入联系人
    void insertAtMiddle(Person*, Person*);

    // 删除一个联系人
    void deleteNode(Person*);

    // 删除整个通讯录
    void deleteList();

    // 对通讯录进行排序
    void sortList();
};

接下来，我们分别来实现各个函数。

1. 构造函数和析构函数

LinkedList::LinkedList() {
    head = nullptr;
}

LinkedList::~LinkedList() {
    deleteList();
}

在构造函数中，我们将头指针初始化为空指针。在析构函数中，我们调用了deleteList()函数来删除整个通讯录。

2. 添加联系人

void LinkedList::addPerson() {
    // 创建一个新的联系人
    Person* newPerson = new Person;
    cout << "请输入联系人姓名：";
    getline(cin, newPerson->name);
    cout << "请输入联系人电话号码：";
    getline(cin, newPerson->phone);
    cout << "请输入联系人地址：";
    getline(cin, newPerson->address);

    // 将新的联系人插入到链表中
    if (head == nullptr) {
        // 如果链表为空，则直接插入到头部
        insertAtBegin(newPerson);
    } else {
        // 否则，按照姓名进行排序，插入到合适的位置
        Person* curr = head;
        while (curr != nullptr && curr->name.compare(newPerson->name) < 0) {
            curr = curr->next;
        }
        if (curr == nullptr) {
            insertAtEnd(newPerson);
        } else {
            insertAtMiddle(newPerson, curr);
        }
    }

    cout << "联系人已经成功添加！" << endl;
}

在addPerson()函数中，我们先让用户输入新联系人的信息，然后将该联系人插入到链表中。如果链表为空，那么我们直接将该联系人插入到头部；否则，我们按照姓名进行排序，找到该联系人应该插入的位置，然后插入到链表中。

注意，我们在这里重新定义了一个插入函数insertAtMiddle()，它可以在链表的中间插入联系人。

3. 删除联系人

void LinkedList::deletePerson() {
    // 让用户输入要删除的联系人的姓名
    string name;
    cout << "请输入要删除的联系人的姓名：";
    getline(cin, name);

    // 在链表中查找该联系人
    Person* curr = head;
    while (curr != nullptr && curr->name != name) {
        curr = curr->next;
    }

    // 如果找到该联系人，则删除它
    if (curr != nullptr) {
        deleteNode(curr);
        cout << "联系人已经成功删除！" << endl;
    } else {
        cout << "未找到该联系人！" << endl;
    }
}

在deletePerson()函数中，我们让用户输入要删除的联系人的姓名，然后在链表中查找该联系人。如果找到了该联系人，那么我们调用deleteNode()函数来删除它。否则，我们就打印一条错误提示信息。

4. 查找联系人

void LinkedList::searchPerson() {
    // 让用户输入要查找的联系人的姓名
    string name;
    cout << "请输入要查找的联系人的姓名：";
    getline(cin, name);

    // 在链表中查找该联系人
    Person* curr = head;
    while (curr != nullptr && curr->name != name) {
        curr = curr->next;
    }

    // 如果找到了该联系人，则输出它的详细信息
    if (curr != nullptr) {
        cout << "姓名：" << curr->name << endl;
        cout << "电话：" << curr->phone << endl;
        cout << "地址：" << curr->address << endl;
    } else {
        cout << "未找到该联系人！" << endl;
    }
}

在searchPerson()函数中，我们让用户输入要查找的联系人的姓名，然后在链表中查找该联系人。如果找到了该联系人，则输出它的详细信息。否则，我们打印一条错误提示信息。

5. 打印整个通讯录

void LinkedList::printList() {
    // 遍历整个链表并打印每个联系人的信息
    if (head == nullptr) {
        cout << "通讯录为空！" << endl;
    } else {
        Person* curr = head;
        while (curr != nullptr) {
            cout << "姓名：" << curr->name << endl;
            cout << "电话：" << curr->phone << endl;
            cout << "地址：" << curr->address << endl;
            cout << "----------------------" << endl;
            curr = curr->next;
        }
    }
}

在printList()函数中，我们遍历整个链表并打印每个联系人的信息。如果链表为空，我们则打印一条错误提示信息。

6. 将通讯录保存到文件

void LinkedList::saveList() {
    // 让用户输入要保存的文件名
    string filename;
    cout << "请输入要保存的文件名：";
    getline(cin, filename);

    // 打开文件并写入通讯录内容
    ofstream outFile(filename);
    if (!outFile) {
        cout << "无法打开文件" << filename << "，保存失败！" << endl;
        return;
    }
    Person* curr = head;
    while (curr != nullptr) {
        outFile << curr->name << ','
                << curr->phone << ','
                << curr->address << '\n';
        curr = curr->next;
    }
    outFile.close();

    cout << "通讯录已成功保存到" << filename << "文件！" << endl;
}

在saveList()函数中，我们让用户输入要保存的文件名，然后将通讯录内容写入到文件中。如果打开文件失败，我们则打印一条错误提示信息。

7. 在链表头部插入联系人

void LinkedList::insertAtBegin(Person* newPerson) {
    newPerson->prev = nullptr;
    newPerson->next = head;
    if (head != nullptr) {
        head->prev = newPerson;
    }
    head = newPerson;
}

在insertAtBegin()函数中，我们将新联系人插入到链表头部。

8. 在链表尾部插入联系人

void LinkedList::insertAtEnd(Person* newPerson) {
    if (head == nullptr) {
        insertAtBegin(newPerson);
    } else {
        Person* curr = head;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        newPerson->prev = curr;
        curr->next = newPerson;
        newPerson->next = nullptr;
    }
}

在insertAtEnd()函数中，我们将新联系人插入到链表尾部。如果链表为空，我们则将其插入到头部；否则，我们找到链表的尾部，并将新联系人插入到尾部。

9. 在链表中间插入联系人

void LinkedList::insertAtMiddle(Person* newPerson, Person* curr) {
    newPerson->prev = curr->prev;
    newPerson->next = curr;
    curr->prev->next = newPerson;
    curr->prev = newPerson;
}

在insertAtMiddle()函数中，我们将新联系人插入到链表的中间位置。

10. 删除一个联系人

void LinkedList::deleteNode(Person* curr) {
    if (curr == head) {
        head = curr->next;
        if (head != nullptr) {
            head->prev = nullptr;
        }
    } else {
        curr->prev->next = curr->next;
        if (curr->next != nullptr) {
            curr->next->prev = curr->prev;
        }
    }
    delete curr;
}

在deleteNode()函数中，我们删除一个联系人，并且处理链表的前后指针。

11. 删除整个通讯录

void LinkedList::deleteList() {
    Person* curr = head;
    while (curr != nullptr) {
        head = curr->next;
        delete curr;
        curr = head;
    }
}

在deleteList()函数中，我们删除整个通讯录，并释放节点的内存。

12. 对通讯录进行排序

我们可以使用冒泡排序或快速排序来对通讯录进行排序。这里我们以冒泡排序为例。

void LinkedList::sortList() {
    if (head == nullptr) {
        return;
    }
    bool swapped = true;
    while (swapped) {
        swapped = false;
        Person* curr = head;
        while (curr->next != nullptr) {
            if (curr->name.compare(curr->next->name) > 0) {
                swap(curr, curr->next);
                swapped = true;
            }
            curr = curr->next;
        }
    }
}

void LinkedList::swap(Person* a, Person* b) {
    string tempName;
    string tempPhone;
    string tempAddress;
    tempName = a->name;
    tempPhone = a->phone;
    tempAddress = a->address;
    a->name = b->name;
    a->phone = b->phone;
    a->address = b->address;
    b->name = tempName;
    b->phone = tempPhone;
    b->address = tempAddress;
}

在sortList()函数中，我们使用冒泡排序对通讯录按照姓名进行排序。在本例中，我们以姓名的字母顺序为排序依据。

我们还需要定义交换函数swap()，用来交换两个联系人的信息。

示例说明

下面，我们来演示一下这个通讯录程序的使用。

例1：添加联系人

我们依次添加一些联系人：

请输入联系人姓名：Mark
请输入联系人电话号码：123456
请输入联系人地址：Beijing
联系人已经成功添加！

请输入联系人姓名：Tom
请输入联系人电话号码：987654
请输入联系人地址：Shanghai
联系人已经成功添加！

请输入联系人姓名：Lily
请输入联系人电话号码：234567
请输入联系人地址：Guangzhou
联系人已经成功添加！

例2：查询联系人

我们查询一个联系人：

请输入要查找的联系人的姓名：Mark
姓名：Mark
电话：123456
地址：Beijing

例3：删除联系人

我们删除一个联系人：

请输入要删除的联系人的姓名：Tom
联系人已经成功删除！

例4：打印整个通讯录

我们打印整个通讯录：

姓名：Lily
电话：234567
地址：Guangzhou
----------------------
姓名：Mark
电话：123456
地址：Beijing
----------------------

例5：将通讯录存储到文件

我们将通讯录保存到文件data.txt：

请输入要保存的文件名：data.txt
通讯录已成功保存到data.txt文件！

例6：从文件中读取通讯录

我们可以从文件中读取通讯录并载入内存。

```cpp

include

include

include

include "LinkedList.h"

using namespace std;

int main() {
LinkedList list;
ifstream inFile("data.txt");
if (!inFile) {
cout << "无法打开文件data.txt，程序将退出！" << endl;
return 1;
}
string line;
while (getline(inFile, line)) {
Person* newPerson = new Person;
string name, phone, address;
int pos1 = 0, pos2;
pos2 = line.find(',', pos1);
name = line.substr(pos1, pos2 - pos1);
pos1 = pos2 + 1;
pos2 = line.find(',', pos1);
phone = line.substr(pos1, pos2 - pos1);
pos1 = pos2 + 1;
address = line.substr(pos1);
newPerson->name = name;
newPerson->phone = phone;
newPerson->address = address;
list.insertAtEnd(newPerson);
}
inFile.close();
list.sortList();

while (true) {
    cout << "请选择功能：" << endl;
    cout << "1. 添加联系人" << endl;
    cout << "2. 删除联系人" << endl;
    cout << "3. 查找联系人" << endl;
    cout << "4. 打印整个通讯录" << endl;
    cout << "5. 保存通讯录到文件" << endl;
    cout << "0. 退出程序" << endl;
    cout << ">>> ";
    int choice;
    cin >> choice;
    cin.get();
    cout << endl;
    switch (choice) {
    case 1:
        list.addPerson();
        break;
    case 2:
        list.deletePerson();
        break;
    case 3:
        list.searchPerson();
        break;
    case 4:
        list.printList();
        break;
    case 5:
        list.saveList();
        break;
    case 0:
        return 0;
    default:
        cout << "无效的选择，请重新选择