实现手机通讯录的新建、插入、删除与查询（要求用排序顺序表、排序单链表两种存储结构都要完成）

好的，我来为您讲解一下如何实现手机通讯录的新建、插入、删除与查询，并分别使用排序顺序表和排序单链表两种存储结构来完成。

首先，我们需要明确通讯录中每个联系人的信息包括姓名、电话号码、电子邮箱等。我们可以定义一个结构体来表示每个联系人的信息：

struct Contact {
    string name;
    string phone;
    string email;
};

接下来，我们就可以使用排序顺序表和排序单链表来实现通讯录的功能了。

## 排序顺序表

在排序顺序表中，我们可以定义一个结构体来表示通讯录，其中包含一个动态数组存储联系人信息，并且每个联系人信息都按照姓名的字典序排序。

struct ContactList {
    Contact* data;  // 动态数组
    int size;       // 当前存储的联系人数量
    int capacity;   // 动态数组的容量

    // 构造函数
    ContactList(int initialCapacity = 10) {
        data = new Contact[initialCapacity];
        size = 0;
        capacity = initialCapacity;
    }

    // 析构函数
    ~ContactList() {
        delete[] data;
    }

    // 新建联系人
    void createContact(Contact contact) {
        if (size >= capacity) {
            // 扩容
            capacity *= 2;
            Contact* newData = new Contact[capacity];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            delete[] data;
            data = newData;
        }

        // 插入新联系人
        int i = size - 1;
        while (i >= 0 && data[i].name > contact.name) {
            data[i + 1] = data[i];
            i--;
        }
        data[i + 1] = contact;
        size++;
    }

    // 删除联系人
    void deleteContact(string name) {
        int i = 0;
        while (i < size && data[i].name != name) {
            i++;
        }
        if (i == size) {
            // 没有找到联系人
            return;
        }
        for (int j = i + 1; j < size; j++) {
            data[j - 1] = data[j];
        }
        size--;
    }

    // 查询联系人
    Contact* findContact(string name) {
        int left = 0, right = size - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (data[mid].name == name) {
                // 找到了联系人
                return &data[mid];
            } else if (data[mid].name < name) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 没有找到联系人
        return NULL;
    }
};

注意，在新建联系人和删除联系人时，我们要保持联系人信息按照姓名的字典序排序。同时，在删除联系人时，我们可以使用数组的平移操作来实现。

在查询联系人时，由于我们已经按照姓名的字典序排序，可以使用二分查找算法来实现。这样可以将查询联系人的时间复杂度从 $O(n)$ 降为 $O(\log n)$。

## 排序单链表

在排序单链表中，我们可以定义一个结构体来表示每个节点，其中包含一个联系人的信息以及一个指向下一个节点的指针。同时，我们需要对每个节点的联系人信息按照姓名的字典序排序。

struct ListNode {
    Contact contact;
    ListNode* next;

    ListNode(Contact contact) {
        this->contact = contact;
        next = NULL;
    }
};

struct ContactList {
    ListNode* head; // 链表的头节点

    // 构造函数
    ContactList() {
        head = NULL;
    }

    // 析构函数
    ~ContactList() {
        ListNode* p = head;
        while (p != NULL) {
            ListNode* q = p->next;
            delete p;
            p = q;
        }
    }

    // 新建联系人
    void createContact(Contact contact) {
        ListNode* newNode = new ListNode(contact);
        if (head == NULL || head->contact.name > contact.name) {
            newNode->next = head;
            head = newNode;
        } else {
            ListNode* p = head;
            while (p->next != NULL && p->next->contact.name <= contact.name) {
                p = p->next;
            }
            newNode->next = p->next;
            p->next = newNode;
        }
    }

    // 删除联系人
    void deleteContact(string name) {
        if (head == NULL) {
            // 链表为空
            return;
        }
        if (head->contact.name == name) {
            ListNode* p = head;
            head = head->next;
            delete p;
        } else {
            ListNode* p = head;
            while (p->next != NULL && p->next->contact.name != name) {
                p = p->next;
            }
            if (p->next != NULL) {
                ListNode* q = p->next;
                p->next = q->next;
                delete q;
            }
        }
    }

    // 查询联系人
    Contact* findContact(string name) {
        ListNode* p = head;
        while (p != NULL && p->contact.name != name) {
            p = p->next;
        }
        if (p != NULL) {
            // 找到了联系人
            return &(p->contact);
        } else {
            // 没有找到联系人
            return NULL;
        }
    }
};

注意，在新建联系人和删除联系人时，我们要保持链表中每个节点的联系人信息按照姓名的字典序排序。同时，在删除联系人时，由于我们没有办法直接访问链表中前一个节点，因此需要使用单链表的删除节点操作。

在查询联系人时，我们可以使用链表的顺序查找算法来实现。由于链表中的每个节点的联系人信息都是按照姓名的字典序排序的，因此可以将查询联系人的时间复杂度从 $O(n)$ 降为 $O(\log n)$。

以上就是使用排序顺序表和排序单链表实现手机通讯录的新建、插入、删除与查询的方法。