以升序和降序打印鏈表

Question

我有一項任務，涉及使用菜單修改鏈接列表並能夠按照升序和降序打印。它是以前任務的擴展，我們必須將.dat文件加載到程序中並打印出來。我們的新指令是添加一個名爲before的新指針，該指針指向。我不知道如何以降序打印它。我們的教授說了一些關於使用循環的內容，但我很困惑這些都是如何工作的。該代碼現在有點馬虎，因爲我還沒有機會清理它。

#include <iostream> 
#include <iomanip> 
#include <fstream> 

using namespace std; 

struct Part 
{ 
    int number; 
    float price; 
    Part *next; 
    Part *before; 
}; 

class Inventory 
{ 
    protected: 
    Part *start; 
    public: 
    Inventory(void); 
    void link(Part); 
    string getFileName(void); 
    bool checkFileExistence(const string& filename); 
    void getFile(string filename, ifstream& file); 
    void PrintInventory (void); 
    void PrintDescending (void); 
    void AddPart(void); 
    void loadFile(void); 
    void DeleteItem(int); 
    void DeletePart(void); 
}; 

Inventory inven; 

Inventory::Inventory(void) 
{ 
    start = NULL; 
} 

void Inventory::link(Part item) 
{ 
    Part *p, *last, *here; 
    p = new Part; 

    p->number = item.number; 
    p->price = item.price; 

    if (start == NULL) 
    { 
    start = p; 
    start -> next = NULL; 
    } 
    else 
    { 
    here = start; 
    if(p->number < here->number) 
    { 
     p->next = here; 
     start = p; 
    } 
    else 
    { 
     while(p->number > here->number && here->next != NULL) 
     { 
     last = here; 
     here = here->next; 
     } 

     if (p->number < here->number) 
     { 
     last->next = p; 
     p->next = here; 
     } 
     else 
     { 
     here->next = p; 
     p->next = NULL; 
     } 
    } 
    } 
} 

void Inventory::PrintInventory() 
{ 
    Part *travel; 
    travel = start; 
    cout.setf(ios::fixed); 
    cout.precision(2); 

    if (travel != NULL) 
    { 
     cout << "\nPart #" << setw(13) << "Price" << endl; 
    } 

    while (travel != NULL) 
    { 
     cout << setw(5) << travel->number; 
     cout << setw(8) << '$' << setw(6) << travel->price << endl; 
     travel = travel->next; 
    } 
    cout << endl; 
} 

void Inventory::loadFile() 
{ 
    string filename; 
    filename = getFileName(); 
    Part thing; 
    cout << endl; 

    if (!checkFileExistence(filename)) 
    { 
     cout << "File '" << filename << "' not found." << endl; 
     return; 
    } 

    ifstream infile; 
    infile.open(filename.c_str()); 

    while(!infile.eof()) 
{ 
    infile >> thing.number; 
    infile >> thing.price; 
    inven.link(thing); 
} 

    cout << "\n Inventory File Loaded. \n\n"; 

} 

void Inventory::PrintDescending() 
{ 

} 

int main() 
{ 

char key; 
int res; 


    do{ 
     cout << "Menu:" << endl; 
     cout << "1) Load Inventory File" << endl; 
     cout << "2) Add Item to Inventory" << endl; 
     cout << "3) Remove Item from Inventory" << endl; 
     cout << "4) Print Inventory in Ascending Order" << endl; 
     cout << "5) Print Inventory in Descending Order" << endl; 
     cout << "6) Quit" << endl << endl; 
     cout << "Option Key: "; 
     cin >> key; 

     switch (key){ 
      case '2': 
       inven.AddPart(); 
       res = 1; 
       break; 
      case '3': 
       inven.DeletePart(); 
       res = 1; 
       break; 
      case '1': 
       inven.loadFile(); 
       res = 1; 
       break; 
      case '4': 
       inven.PrintInventory(); 
       res = 1; 
       break; 
      case '5': 
       inven.PrintDescending(); 
       res = 1; 
       break; 
      case '6': 
       res = 0; 
       break; 
      default: 
       res = 1; 
       break; 
     } 

    }while(res == 1); 
} 

我省去了添加和刪除項目的功能，因爲它們不是必需的。我們正在使用的.dat文件包含：

123 19.95 
46 7.63 
271 29.99 
17 .85 
65 2.45 
32 49.50 
128 8.25 

Answer 1

這是一種經典的數據結構算法。請參閱Double linked list。

但是：

之前試圖打印，您需要之前更新與新指針你的代碼。你也可以簡化這個，看看評論。 所以你鏈接功能：

if (start == NULL) 
    { 
    start = p; 
    start -> next = NULL; 
    // Here : 
    start->before = NULL; 
    } 
    else 
    { 
    here = start; 
    // You can remove this if... 
    if(p->number < here->number) 
    { 
     p->next = here; 
     start = p; 
    } 
    else 
    { 
     // ... Because your condition in the next while is enough. 
     while(p->number > here->number && here->next != NULL) 
     { 
     last = here; 
     here = here->next; 
     } 

     if (p->number < here->number) 
     { 
     // Here : TODO link with the previous one 
     last->next = p; 
     p->next = here; 
     } 
     else 
     { 
     // Here : TODO link with the previous one 
     here->next = p; 
     p->next = NULL; 
     } 
    } 
    } 
} 

，然後再打印，只要把你的PrintInventory功能，但之前使用解析。

希望它有幫助。