排序的char *數組

Question

我有一個數據結構

struct record { 
    char cont[bufferSize]; 
    record *next; 
}; 

當我添加新記錄這種結構，我希望他們能夠按照字母順序排序。我做了這個功能，即在正確的位置（由字母）鏈接列表添加記錄：

record *start=NULL, *p, *x; 

void recAdd(char*temp) { 
     p = new record; 
     temp[strlen(temp)] = '\0'; 
     for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j]; 
     if (start==NULL) start=p; 
     else { 
      x=start; 
      int c=0; 
      while (recComp(x->cont,p->cont) <= 0 && x->next != NULL) { 
        x=x->next; 
        c++; 
      } 
      if (c == 0) { 
       p->next=start; 
       start=p; 
      } 
      else { 
       x=start; 
       for (int i=0;i<c;i++) x=x->next; 
       p->next=x->next; 
       x->next=p; 
      } 
     } 
     for (int j=0;j<bufferSize;j++) temp[j] = NULL; 
    }; 

但不知何故，它不排序正確的事情。我的功能有什麼問題？

Answer 1

你的代碼亂七八糟。有許多語義和邏輯問題，但基本上決定插入新節點的邏輯是最有缺陷的。將其更改爲這個（注意在else塊我的新代碼）：

void recAdd(const char*t) { 
     char temp[bufferSize]; 
     strcpy(temp, t); 
     p = new record; 
     temp[strlen(temp)] = '\0'; 
     for (int j=0;j<bufferSize;j++) p->cont[j] = temp[j]; 
     if (start==NULL) { start=p; start->next = 0; } 
     else { 
      record* x = start; 
      record* prev = 0; 
      while(x && recComp(x->cont, p->cont) <= 0) 
      { 
       prev = x; 
       x = x->next; 
      } 

      // p is a new node. p, x and prev are arranged thusly: 
      // prev -> p -> x 
      // if prev is null, p is a new head 
      // if x is null, p is a new tail 
      // otherwise, p is inserted between prev and x 

      if(!prev) 
      { 
       p->next = start; 
       start = p; 
      } 
      else if(!x) 
      // note this block and the next one could be combined. 
      // done this way for clarity. 
      { 
       prev->next = p; 
       p->next = 0; 
      } 
      else 
      { 
       p->next = x; 
       prev->next = p; 
      } 
     } 
     for (int j=0;j<bufferSize;j++) temp[j] = NULL; 
    }; 

但事實上，你有足夠的困難，編寫這些代碼，你會問那麼用於幫助修復它說明了一個重要的觀點：最好的代碼是你永遠不必寫的代碼。你已經寫了一個鏈表式類型結構（它可能是裸露的骨骼）和一個排序算法。兩者都有缺陷，並且都有可用的工作，測試和高效版本，作爲標準C++庫的一部分。你應該使用它們。使用字符串而不是char * s。使用矢量而不是鏈接列表。使用sort而不是您的手滾排序算法。總之，所有的代碼可以通過這個來代替：

vector<string> records; 

// this for block just populates the vector with random strings 
for(int i = 0; i < 10; ++i) 
{ 
    string s; 
    for(int j = 0, jx = 3+(rand()/(RAND_MAX/10)); j < jx; ++j) 
     s += 'A'-1+(rand()/(RAND_MAX/26)); 
    cout << s << endl; 
    records.push_back(s); 
} 

sort(records.begin(), records.end()); 
copy(records.begin(), records.end(), ostream_iterator<string>(cout, " ")); 

爲什麼手工捲了一堆東西，暴露自己的缺陷不計其數時，你可以使用你想要的東西已經工作，並做工具？

Answer 2

也許我沒有回答你的問題，但你爲什麼不使用STL？它會爲你排序;這些日子你不應該寫這樣的排序例程。

Answer 3

一些提示：

• 使用strcmp使用指針寧願char你的結構裏面比較字符串
• 。這可以讓你盲目地分配他們沒有將其複製並不會浪費你struct
• 內部空間，如果你真的需要複製它們使用strdup分配新的字符串兩個電流元素而不是隻是一個
• 跟蹤，這將避免計算你有多少走到這一步，並辦理列表兩次，當你找到合適的位置

Answer 4

你可以讓你在這裏的生活輕鬆了許多，如果你實現一個簡單的插入排序使用STL向量（矢量有一個成員'插'）。

該代碼將尋找的例子在那裏，你會發現它有用的乾淨多了太:)

查找cplusplus.com。

Answer 5

正如其他人已經建議的那樣，STL讓生活變得更加輕鬆。看起來你需要的是一個分類的字符串容器：

#include <iostream> 
#include <set> 
#include <string> 

int main() 
{ 
    std::set<std::string> words; 
    words.insert("hello"); 
    words.insert("beautiful"); 
    words.insert("world"); 

    for (std::set<std::string>::const_iterator it = words.begin(); it != words.end(); ++it) 
    { 
     std::cout << *it << std::endl; 
    } 
}