C语言实现有序链表插入年份节点时程序卡顿问题求助

首先，先帮你定位当前程序卡顿无响应的核心问题，再逐步修复逻辑，最后给出大规模链表的处理方案。

1. 数组越界导致的未定义行为（大概率是死循环根源） #

你定义了int test[15] = {0};，数组的有效下标范围是0~14，但你的for循环写的是for (key = 0; key < 20 ; key++)，这意味着你会访问test[15]到test[19]——这些都是数组边界外的内存区域。这种越界访问属于未定义行为，可能会意外覆盖循环变量key或者其他内存数据，导致key永远无法达到20，循环无限执行，最终让虚拟机卡顿。

修复方法二选一：

• 调整数组大小到至少20，匹配循环次数：

  int test[20] = {10,25,7,5,30,40,3,4,98,0,4,14,23,16,35,6,0,0,0,0};
  

• 或者修改循环条件，匹配数组实际长度：

  for (key = 0; key < 15 ; key++)
  

2. 链表插入逻辑缺陷（导致大量节点丢失） #

你的原插入逻辑只处理了中间插入的极端情况，完全忽略了插入到链表末尾和**插入到头部（除了key==2的特殊情况）**的场景，导致大部分节点根本没被添加到链表中。比如当data比链表所有节点值都大时，循环结束后没有执行任何插入操作，节点直接丢失。

下面是修复后的完整插入逻辑，确保所有节点按升序正确插入：

for (key = 0; key < 15 ; key++) {
    data = test[key];
    // 提前创建新节点
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->key = key;
    new_node->data = data;
    new_node->next = NULL;

    // 空链表直接作为头节点
    if (head_countries == NULL) {
        head_countries = new_node;
        continue;
    }

    // 插入到头部（data比第一个节点小）
    if (data < head_countries->data) {
        new_node->next = head_countries;
        head_countries = new_node;
        continue;
    }

    // 寻找中间或末尾的插入位置
    struct node* curr = head_countries;
    while (curr->next != NULL && curr->next->data < data) {
        curr = curr->next;
    }
    // 插入到curr的后面
    new_node->next = curr->next;
    curr->next = new_node;
}

另外，你的struct node定义末尾多了一个node;，会创建一个全局的node变量，建议去掉，改成标准结构体定义：

struct node {
    int data;
    int key;
    struct node *next;
};

3. 大规模链表的处理建议 #

如果你的CSV文件数据量很大，链表逐个插入的O(n²)时间复杂度会变得低效，还可能带来内存压力，推荐以下优化方案：

• 先数组排序再构建链表：先把所有年份数据读取到数组中，用快速排序/归并排序等O(n log n)的高效算法排序，最后再一次性构建链表。这种方式比逐个插入链表快得多，适合大规模数据。
• 内存预分配：如果知道数据的大致数量，可以预先分配一块连续内存存储所有节点，减少频繁malloc的开销，提升性能。
• 分批处理：如果数据量极大到无法一次性加载到内存，可以分批次读取CSV，每批次排序后合并到已有的有序结构中（类似归并排序的合并步骤）。
• 添加内存释放逻辑：大规模链表一定要记得在程序结束时释放所有节点内存，避免内存泄漏：

  void freeList() {
      struct node* temp;
      while (head_countries != NULL) {
          temp = head_countries;
          head_countries = head_countries->next;
          free(temp);
      }
  }
  

  然后在main函数结束前调用freeList();即可。

先修复数组越界和插入逻辑的问题，你的程序应该就能正常运行了，再根据实际数据规模选择合适的优化方案。

内容的提问来源于stack exchange，提问作者Carlos Martins