以升序和降序打印链表

问题描述：

我有一项任务，涉及使用菜单修改链接列表并能够按照升序和降序打印。它是以前任务的扩展，我们必须将.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文件包含：

看起来你的列表是双向链接的（即有一个'next'和''before'指针）。但是在链接时你并没有使用这个逻辑。你只是连接下一个指针。用双向链表进行反向打印很容易，因为您只需从最后开始并按照“之前”指针。如果您想要反向打印单链表，您可以递归执行，也可以向前遍历列表两次（第一次，将其重新排序;第二次再次反转它，但在打印时按顺序打印每个节点）。 – paddy

答

这是一种经典的数据结构算法。请参阅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功能，但之前使用解析。

希望它有帮助。

以升序和降序打印链表

相关推荐