c++ - 按升序和降序打印链表

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

这是一个经典的数据结构算法。见双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 函数，但使用 before 进行解析。

希望对您有所帮助。