C语言链表节点Website字符串逐字符比较及插入排序实现问询

刚接触C语言就能尝试链表有序插入，已经很棒了！你的核心问题是如何比较两个节点的网站字符串来确定插入位置，其实有两种思路——用标准库函数快速解决，或者自己实现逐字符比较来加深理解，我都给你详细讲清楚：

第一步：定义链表节点结构 #

首先我们需要一个清晰的节点结构，包含网站名、用户名和指向下一个节点的指针：

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

typedef struct Node {
    char website[100];  // 预留足够空间存储网站名，可根据需求调整
    char username[50];  // 同理调整用户名长度
    struct Node *next;
} Node;

第二步：创建新节点的工具函数 #

每次输入一对网站和用户名，我们需要把它们封装成一个新节点：

Node* create_node(const char *website, const char *username) {
    Node *new_node = (Node*)malloc(sizeof(Node));
    if (!new_node) {  // 检查内存分配是否成功
        perror("Failed to allocate memory");
        exit(EXIT_FAILURE);
    }
    // 把输入内容复制到节点的字符数组中
    strcpy(new_node->website, website);
    strcpy(new_node->username, username);
    new_node->next = NULL;
    return new_node;
}

第三步：核心实现——有序插入 #

这里分两种方式实现，你可以根据需求选择：

方式1：用标准库strcmp快速比较 #

C标准库的strcmp函数已经帮我们完成了逐字符比较的工作：

• 返回负数：第一个字符串在字母序中排在第二个前面
• 返回0：两个字符串完全相等
• 返回正数：第一个字符串在字母序中排在第二个后面

利用这个函数，我们可以轻松找到插入位置：

Node* insert_sorted(Node *head, Node *new_node) {
    // 情况1：链表为空，或者新节点应该插在表头（比第一个节点的网站名靠前）
    if (head == NULL || strcmp(new_node->website, head->website) < 0) {
        new_node->next = head;
        return new_node;
    }

    // 情况2：遍历链表，找到第一个网站名比新节点靠后的节点的前一个位置
    Node *current = head;
    while (current->next != NULL && strcmp(current->next->website, new_node->website) < 0) {
        current = current->next;
    }

    // 插入新节点到current和current->next之间
    new_node->next = current->next;
    current->next = new_node;
    return head;
}

方式2：自己实现逐字符比较 #

如果想手动实现逐字符比较的逻辑，我们可以写一个自定义函数，模仿strcmp的返回规则：

// 自定义网站名比较函数，返回值规则和strcmp一致
int compare_website(const char *a, const char *b) {
    // 逐字符比较，直到其中一个字符串结束
    while (*a != '\0' && *b != '\0') {
        if (*a < *b) {
            return -1;  // a的字符更小，a排在前面
        } else if (*a > *b) {
            return 1;   // a的字符更大，a排在后面
        }
        // 当前字符相等，继续比较下一个
        a++;
        b++;
    }

    // 处理其中一个字符串先结束的情况（比如"app"和"apple"，短的排在前面）
    if (*a == '\0' && *b != '\0') {
        return -1;
    } else if (*a != '\0' && *b == '\0') {
        return 1;
    }
    return 0;  // 两个字符串完全相同
}

然后把插入函数里的strcmp换成这个自定义函数即可：

Node* insert_sorted_custom(Node *head, Node *new_node) {
    if (head == NULL || compare_website(new_node->website, head->website) < 0) {
        new_node->next = head;
        return new_node;
    }

    Node *current = head;
    while (current->next != NULL && compare_website(current->next->website, new_node->website) < 0) {
        current = current->next;
    }

    new_node->next = current->next;
    current->next = new_node;
    return head;
}

第四步：主函数与测试 #

最后我们写主函数来接收输入、插入节点、打印结果，还要记得释放内存避免泄漏：

// 打印链表内容，验证排序结果
void print_list(Node *head) {
    Node *current = head;
    printf("\nSorted Website-Username List:\n");
    while (current != NULL) {
        printf("Website: %-20s Username: %s\n", current->website, current->username);
        current = current->next;
    }
}

// 释放链表所有节点的内存
void free_list(Node *head) {
    Node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    Node *head = NULL;
    char website[100], username[50];

    printf("Please enter website and username (one pair per line, press Ctrl+D to finish):\n");
    // 循环接收输入直到EOF（Windows下是Ctrl+Z，Linux/macOS是Ctrl+D）
    while (scanf("%99s %49s", website, username) == 2) {
        Node *new_node = create_node(website, username);
        // 选择一种插入方式：用标准strcmp或自定义比较函数
        head = insert_sorted(head, new_node);
        // head = insert_sorted_custom(head, new_node);
    }

    print_list(head);
    free_list(head);  // 一定要释放内存！
    return 0;
}

关键注意事项 #

• 缓冲区溢出：用%99s而不是%s是因为我们的website数组大小是100，要留一个位置给字符串结束符'\0'，避免溢出。
• 内存泄漏：程序结束前一定要调用free_list释放所有节点的内存，这是C语言的好习惯。
• 排序规则：这里用的是ASCII码顺序，所以大写字母会排在小写字母前面（比如"Google"会在"apple"前面），如果想忽略大小写，可以把字符串转成小写后再比较（比如用tolower函数逐字符转换）。

内容的提问来源于stack exchange，提问作者Shaka Wright