效率與結構

我有以下結構效率與結構

struct scoreentry_node { 
    struct scoreentry_node *next; 
    int score; 
    int max; 
    char name[1];  
} 
; 
typedef struct scoreentry_node *score_entry;

而且我有建造我的構造函數add：

int max(int a, int b) {  
    if (a > b) return a; 
    return b; 
} 

score_entry add(int in, char* n, score_entry en) {  
    score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n)) 
    if (en == NULL){ r->max = in; } 
    else { r->max = max(in, en->max); } 
    r->score = in; 
    strcpy(r->name, n); 
    r->next = en; 
    return r; 
}

我有以下的功能，通過我的結構掃描搜索名稱併產生該名稱的最高分數：

int maxiscore(score_entry a, char* name) 
{  
int highestscore = -1000000000;  
    for (a; a != NULL; a = a->next) 
    { 
     if (strcmp(a->name, name) == 0 && a->score > highestscore) 
     { 
      highestscore = a->score;     
     } 
    } 
return highestscore; 
}

我是w如果我可以讓我的maxiscore函數在O（1）中運行[不需要掃描我的結構]？我正在考慮添加另一個字段到我的結構，但我必須考慮它需要根據具體的輸入名稱而有所不同。任何建議/提示？

來源

2012-03-31 Thatdude1

什麼是'char name [1];'？如果你想要一個字符，爲什麼不用'char名字;'？如果你希望它是以空字符結尾的字符串，那麼只有**空終止符將適合單字符數組。 – Imp 2012-03-31 22:20:12

使其成爲O（1）的唯一方法是不斷排序列表，這會比最大分數爲O（n）更大的浪費。 – 2012-03-31 22:20:28

使其成爲O（1）的唯一方法是將列表實現爲'priorityQueue'（即排序）或將列表實現爲'HashTable'。用你當前的設置'HashTable'選項需要基本上重做整個代碼。你可以實現一個'priorityQueue'。 – twain249 2012-03-31 22:22:11

您可以在scorelist類中包裝一組結構，其中score_entry指針指向包含的條目中第一個元素和最大分數（以及指向相關元素的指針）。您可以在add()上更新biggets得分並重寫指針。您將能夠訪問O（1）中得分最高的元素。

來源

2012-03-31 22:23:34 iehrlich

爲什麼我處理最小分數的你？以及我將如何「添加一個指向相關元素的指針」？ – Thatdude1 2012-03-31 22:38:15

Biggset當然:) – iehrlich 2012-03-31 22:40:56

你seemply **總是**保持一個指向最高分的元素。您可以通過add（）中的指針訪問此元素，如果添加的元素具有較大的分數，則可以重寫該指針。 – iehrlich 2012-03-31 22:44:25

正如一些評論者指出的，這基本上是一個算法/數據組織問題。您可以花時間創建「有組織的」數據結構，如每用戶評分表，散列值，平衡樹等等;您可以花費時間創建「有組織的」數據結構，如每用戶評分表，哈希值，平衡樹等等。或者你可以花時間搜索「混亂」的數據結構。甚至還有混合方法：根據需要創建它們「無組織」，然後根據需要即時組織它們（例如，展開樹）。

如果您已經掌握了有關您「盡最大努力」的信息，現在可以進行優化。否則，如果您希望稍後能夠進行優化，請確定您需要的功能類型，並提供特定功能以「做每件事」（添加一個帶有一組分數的名稱？用一個分數添加一個名稱？查找所有分數找到一個特定的名字？找到N個最高分數？找到一個特定名稱的N個最高分數？前面的任何/所有的？等等）。一旦它全部正常工作，就使用分析來找出時間的推移，然後選擇如何組織通過這些功能訪問的數據。

事實上，我認爲你的問題開始有點「太低級」，即「我已經擁有這套特殊的指甲，所以應該使用哪種錘子」，或許螺絲或膠水會更好。 :-)

來源

2012-03-31 22:39:07 torek

回答

相關問題