海量數據 Top-K 問題：鏈表版從 N 個數選最大前 10 個完整實現

同樣解決「從 N 個數選最大前 10 個」問題，本文提供基於**有序鏈表**的實現。雖單次插入 O(K)，但 K=10 時常數極小，實測比堆版更快（0.014s vs 0.046s），適合極小 K 場景。

算法思想

• 維護長度固定 K=10 的降序鏈表（頭節點最大）
• 新數從頭遍歷，找到首個 新數 >= 節點值 的位置插入
• 超過 K 個截斷尾部
• 無需堆調整，邏輯極簡

完整代碼

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>
#include <strings.h>

#define BUFF_LEN (4096)

typedef struct queue_s { int data; struct queue_s *next; } queue_t;

static void generate_test_data(long n) {
    long i; int r, l = sizeof(int);
    srand(time(NULL));
    for(i=0; inext) fprintf(n ? stderr : stdout, "%d\n", q->data);
    if(n) printf("\n");
}

int main(int argc, char *argv[]) {
    int *sbuff;
    int i, j, n;
    queue_t *rbuff, **tmp, *t;
    
    #ifdef INFO
    int s_0, s_1, s_2;
    struct timeval begin, end;
    #endif
    
    if(argc < 2) {
        printf("Usage:\n 1. Gen: %s \n 2. Run: %s exec\n", argv[0], argv[0]);
        return 0;
    }
    if(strcmp(argv[1], "exec") != 0) {
        generate_test_data(atoi(argv[1]));
        return 0;
    }
    
    sbuff = malloc(1024*1024*4);
    rbuff = malloc(sizeof(queue_t) * 10);
    
    // 初始化鏈表：10 個節點，data=-1，串聯
    bzero(rbuff, sizeof(queue_t)*10);
    for(i=0; i<9; i++) {
        (rbuff+i)->next = rbuff+i+1;
        (rbuff+i)->data = -1;
    }
    (rbuff+9)->data = -1; (rbuff+9)->next = NULL;
    
    #ifdef INFO { s_0=s_1=s_2=0; gettimeofday(&begin,NULL); }
    
    while((n = read_input(STDIN_FILENO, sbuff, 1024*1024*4)) != 0) {
        #ifdef INFO { s_0++; s_2 += n/4; #endif
        j = n/4;
        for(i=0; i= (*tmp)->data; tmp = &(*tmp)->next) {
                #ifdef INFO s_0+=2; #endif
            }
            #ifdef INFO s_0++; #endif
            
            if(*tmp == rbuff) continue;  // 比最小還小，忽略
            
            // 插入：將新值存入頭節點，調整鏈表
            rbuff->data = *(sbuff+i);
            #ifdef INFO { s_1++; s_0++; #endif
            
            if(*tmp != rbuff->next) {  // 不在頭部，需移動節點
                t = rbuff;
                rbuff = rbuff->next;
                t->next = *tmp ? *tmp : NULL;
                *tmp = t;
                #ifdef INFO { s_1+=4; s_0++; #endif
            }
        }
    }
    
    #ifdef INFO { gettimeofday(&end,NULL); #endif
    dump_link(rbuff, 0);  // 輸出結果
    
    #ifdef INFO {
        fprintf(stderr, "總計[%d]個輸入\n總計比較[%d]次\n總計寫內存[%d]次\n總計耗時[%0.6fs]\n",
            s_2, s_0, s_1, (end.tv_sec*1000000+end.tv_usec-begin.tv_sec*1000000-begin.tv_usec)/1000000.0);
    }
    return 0;
}

關鍵技巧解析

鏈表初始化：哨兵節點法

for(i=0; i<9; i++) {
    (rbuff+i)->next = rbuff+i+1;
    (rbuff+i)->data = -1;
}
(rbuff+9)->next = NULL;

預分配 10 節點陣列，串成鏈表，data=-1 作為哨兵（比所有合法輸入小）。

插入邏輯：頭節點交換法

rbuff->data = new_val;  // 新值暫存頭節點
if(*tmp != rbuff->next) {  // 插入位置非頭部
    t = rbuff;           // 取下頭節點
    rbuff = rbuff->next; // 頭指針後移
    t->next = *tmp;      // 原頭節點接在插入位置前
    *tmp = t;            // 插入位置指向原頭節點
}

巧妙利用「頭節點總是可覆寫」特性，避免 malloc/free，O(1) 節點復用。

測試結果（100 萬輸入）

總計[1000000]個輸入
總計比較[2001654]次
總計寫內存[552]次
總計耗時[0.014687s]

✅ **比堆版快 3 倍**，寫內存極少（僅鏈表指針調整）。

複雜度對比

選擇建議

• K ≤ 20、極致效能、單線程 → 鏈表版
• K 較大、需並行、通用庫 → 堆版
• 教學演示堆原理 → 堆版

編譯運行

gcc -DINFO -o top10_list top10_list.c
./top10_list 1000000 2>data.bin
./top10_list exec < data.bin