采用尾插法创建联系人链表

尾插法（Tail Insertion）是一种在链表结构中插入新节点的方法，特别适合于在链表的末尾添加元素。这种技术的特点在于，每次插入操作都直接将新节点链接到当前链表的最后一个节点之后，无需额外移动其他节点或改变已有的节点指针。

具体步骤如下：

1. **初始化**：如果你要插入第一个节点，链表为空，那么直接新建一个节点，并将其设置为头结点。

2. **插入操作**：对于后续的插入，首先创建一个新的节点，将它的 `next` 指针指向当前链表的最后一个节点。

3. **更新最后一个节点**：如果当前链表不为空，最后的节点会自动更新其 `next` 指向新插入的节点，这样新节点就成为了新的最后一个节点。

4. **重复**：如果链表还有更多元素要插入，重复上述过程，直到所有节点都插入完毕。

尾插法的时间复杂度通常是 O(1)，因为插入操作只涉及了对当前最后一个节点的修改，而不需要遍历整个链表。

相关问题

尾插法创建联系人链表

尾插法是一种在链表中高效插入新元素的方法，特别是在创建或修改已排序的动态联系人列表（如电话簿）时特别适用。它的基本思想是在链表的最后一个节点之后直接添加新节点，而无需遍历整个链表寻找插入位置。

以下是尾插法创建联系人链表的过程：

1. 初始化：如果链表为空，就创建一个新的节点作为头结点，并将其地址赋给链表指针。

2. 插入操作：对于每一个新的联系人，首先创建一个新的节点，存储联系人的信息（比如姓名、电话号码等）。然后，将这个新节点的`next`指针指向当前链表的最后一个节点。

3. 链表更新：每次添加一个节点后，都不用改变其他节点的指针，因为新节点自动成为了最后一个节点。

这种方法的优势在于时间复杂度为O(1)，无论链表大小如何，插入新节点几乎不增加查找和更新的时间。但需要注意的是，如果经常在链表头部插入，尾插法则不如头插法高效，因为它会频繁地移动节点。

用C语言编程，利用单链表的知识，编写一个通讯录储存姓名和电话号码，利用尾插法能够实现在尾部插入新记录

在C语言中，我们可以使用结构体（struct）定义一个联系人节点，包含姓名（char* name）和电话号码（char* phone）。然后通过单链表（如定义一个Node类型的指针变量作为头结点，指向第一个元素）来存储和管理这些联系人。尾插法（push_back in C++）在这里可以改写成动态添加新节点到链表的尾部。

下面是一个简单的示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义联系人结构体
typedef struct Contact {
    char* name;
    char* phone;
    struct Contact* next; // 指向下一个节点的指针
} Contact;

// 动态创建并初始化新的联系人节点
Contact* create_contact(char* name, char* phone) {
    Contact* new_node = (Contact*)malloc(sizeof(Contact));
    if (!new_node) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    new_node->name = strdup(name);
    new_node->phone = strdup(phone);
    new_node->next = NULL;
    return new_node;
}

// 尾插法插入新的联系人
void insert_contact_tail(Contact** head, char* name, char* phone) {
    Contact* new_node = create_contact(name, phone);

    if (*head == NULL) {
        *head = new_node;
    } else {
        Contact* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
}

// 打印整个联系人列表
void print_contacts(Contact* head) {
    Contact* current = head;
    while (current != NULL) {
        printf("Name: %s, Phone: %s\n", current->name, current->phone);
        current = current->next;
    }
}

int main() {
    Contact* contacts_list = NULL;
    
    // 插入一些联系人
    insert_contact_tail(&contacts_list, "Alice", "1234567890");
    insert_contact_tail(&contacts_list, "Bob", "9876543210");

    // 打印所有联系人
    print_contacts(contacts_list);

    return 0;
}