c++ - 排序链接列表 - 移动节点或交换数据成员？

Question

我有一个简单的问题。我正在开发一个 C++ 应用程序，它是一个联系人列表应用程序。它存储多人的姓名、地址、号码、年龄等。我正在使用结构和链表(节点)。我正在构建排序列表功能，以按字母顺序排列列表。我目前想知道通过整体移动结构或通过交换每个节点内的数据成员来实际重新排序列表是否更好。起初，我考虑移动节点，但现在交换数据成员似乎更安全，因为我不必重新排序列表。无论如何，我不知道两者之间是否有任何优势。

编辑:这是我正在处理的源代码。请注意排序功能不完整。另外，我还是一个新手程序员，所以从专业的角度来看，编码可能会有很多问题。那，除了我还没有接近完成它的事实。我写它只是为了在编程课之间的暑假练习编码。

#include <iostream>
#include <fstream>
#include <string.h>//for functions in date function
#include <time.h> //for functions in date function
#include <sys/stat.h>//for mkdir functions
#include <unistd.h>//for usleep function
#include <ctype.h>//for toupper function in swap function

using namespace std;

struct PersonInfo
{
    char FirstName[20];
    char LastName[20];
    char Address[40];
    char PhoneNumber[20];

    int Age;

    PersonInfo *Link;
};

bool EmptyFileChecker(ifstream &FI, const char *P);
void AddPeopleToList(PersonInfo *&HeadPointer);
void RebuildOldList(ifstream &FI, PersonInfo *&HeadPointer, const char *P);
void DisplayList(PersonInfo *HeadPointer);
void SaveSettings(ofstream &FO, const PersonInfo *HeadPointer, const char *P);
void DisplayMenu(PersonInfo *&HeadPointer, const char *P, ifstream &FileIn, ofstream &FileOut);
void SortContacts(PersonInfo *&HeadPointer);
bool NamesInOrder(const char LastName1[], const char LastName2[]);
string Date();

//Delete Contact
//ENCRYPT LIST?

//Check for memory leaks in code and destructor?
//Return something - noun-like
//void adjective - like

int main()
{
    PersonInfo *HeadPointer;

    const char *Path = "/Users/josephlyons/Library/Application Support/The Lyons' Den Labs/TheLyons'DenContactInformation.txt";//code variable for username

    ifstream FileIn;
    ofstream FileOut;

    mkdir("/Users/josephlyons/Library/Application Support/The Lyons' Den Labs", ACCESSPERMS);//MODE??

    if (!EmptyFileChecker(FileIn, Path))
        AddPeopleToList(HeadPointer);

    else
        RebuildOldList(FileIn, HeadPointer, Path);

    DisplayMenu(HeadPointer, Path, FileIn, FileOut);

    //SortContacts(HeadPointer);

    SaveSettings(FileOut, HeadPointer, Path);
}

void DisplayMenu(PersonInfo *&HeadPointer, const char *P, ifstream &FileIn, ofstream &FileOut)
{
    short int MenuChoice;

    do
    {
        cout << "(1) Display Contact List\n";
        cout << "(2) Organize Contact List\n";//delete when done with program and automatically sort list before saving.
        cout << "(3) Add Contact/s\n";
        cout << "(4) Delete Contact/s\n";
        cout << "(5) Quit\n\n";

        cout << "Choice: ";
        cin >> MenuChoice;

        if (MenuChoice == 1)
            DisplayList(HeadPointer);

        else if (MenuChoice == 2)
            SortContacts(HeadPointer);

        else if (MenuChoice == 3)
            AddPeopleToList(HeadPointer);

        else if (MenuChoice == 4)
            cout << "choice 4";
    }
    while(MenuChoice != 5);
}

bool EmptyFileChecker(ifstream &FI, const char *P)//DONE
{
    FI.open(P);

    if (FI.fail())
        return false;

    else if (FI.eof())//return 0 if file doesnt exist or if file is empty
        return false;

    else
        return true;
}

void AddPeopleToList(PersonInfo *&HeadPointer)
{
    PersonInfo *CurrentPosition;

    char UserChoice;

    do
    {
        CurrentPosition = new PersonInfo;

        if (CurrentPosition == NULL)
        {
            cout << "Not enough memmory to make new contact.";
            return;
        }

        cout << "\nEnter First Name:   ";
        cin >> CurrentPosition->FirstName;
        CurrentPosition->FirstName[0] = toupper(CurrentPosition->FirstName[0]);//automatically capitalize first name

        cout << "Enter Last Name:    ";
        cin >> CurrentPosition->LastName;
        CurrentPosition->LastName[0] = toupper(CurrentPosition->LastName[0]);//automatically capitalize last name

        cin.ignore();//flushes a single newline left in input buffer from previous cin >>
        cout << "Enter Adress:       ";
        cin.getline(CurrentPosition->Address, 40);//using cin.get() to allow for spaces in address

        cout << "Enter Phone Number: ";
        cin.getline (CurrentPosition->PhoneNumber, 20);//using cin.get() to allow for spaces in number

        cout << "Enter Age:          ";
        cin >> CurrentPosition->Age;

        cout << "\nAdd another contact? Y/N: ";
        cin >> UserChoice;

        cout << "\n";

        CurrentPosition->Link = HeadPointer;

        HeadPointer = CurrentPosition;
    }
    while (UserChoice == 'y' || UserChoice == 'Y');

    SortContacts(HeadPointer);
}

void RebuildOldList(ifstream &FI, PersonInfo *&HeadPointer, const char *P)
{
    PersonInfo *TemporaryPersonPointer;
    char EndOfListChecker = 1;//initialized at a not 0 to allow entrance into loop

    while (EndOfListChecker != 0)
    {
        TemporaryPersonPointer = new PersonInfo;

        if (TemporaryPersonPointer == NULL)
            cout << "Not enough memory to generate the full list";

        FI >> TemporaryPersonPointer->FirstName;
        FI >> TemporaryPersonPointer->LastName;

        FI.ignore();//flushes a single newline from input
        FI.getline(TemporaryPersonPointer->Address, 40);

        FI.ignore();
        FI.getline(TemporaryPersonPointer->PhoneNumber, 20);

        FI >> TemporaryPersonPointer->Age;

        TemporaryPersonPointer->Link = HeadPointer;

        HeadPointer = TemporaryPersonPointer;

        FI.get(EndOfListChecker);

        while (EndOfListChecker == '\n')
        {
            FI.get(EndOfListChecker);
        }

        if (EndOfListChecker != 0)
            FI.putback(EndOfListChecker);
    }
}

void DisplayList(PersonInfo *HeadPointer)
{
    do
    {
        cout << "\nFirst Name:   ";
        cout << HeadPointer->FirstName << endl;

        cout << "Last Name:    ";
        cout << HeadPointer->LastName << endl;

        cout << "Adress:       ";
        cout << HeadPointer->Address << endl;

        cout << "Phone Number: ";
        cout << HeadPointer->PhoneNumber << endl;

        cout << "Age:          ";
        cout << HeadPointer->Age;

        cout << "\n\n";

        HeadPointer = HeadPointer->Link;

        usleep(75000);
    }
    while (HeadPointer != NULL);

    cout << "Press enter to go to main menu: ";

    cin.ignore(2);

    cout << "\n";
}

void SaveSettings(ofstream &FO, const PersonInfo *HeadPointer, const char *P)
{
    FO.open(P);

    if (FO.fail())
        cout << "Couldn't Open File\n";

    while (HeadPointer != NULL)
    {
        FO << HeadPointer->FirstName   << endl;
        FO << HeadPointer->LastName    << endl;
        FO << HeadPointer->Address     << endl;
        FO << HeadPointer->PhoneNumber << endl;
        FO << HeadPointer->Age         << endl << endl;

        HeadPointer = HeadPointer->Link;
    }

    FO << (char) 0 << endl;

    FO << "Date of Settings: " << Date() << endl;

    FO.close();
}

void SortContacts(PersonInfo *&HeadPointer)
{
    PersonInfo *MovingPointer1;//used to "crawl" down list
    PersonInfo *MovingPointer2;//used to "crawl" down list
    PersonInfo *StaticPointer;//always points at first node to give HeadPointer a way to link back to the list at end
    PersonInfo *TemporaryPointer;//holds a node during a swap

    bool ZeroSwapsOccured = false;//initialized at false to allow entrance into loop once

    MovingPointer1 = StaticPointer = HeadPointer;//set all to point at first node

    MovingPointer2 = HeadPointer->Link;

    while (ZeroSwapsOccured == false)
    {
        ZeroSwapsOccured = true;

        while (MovingPointer2->Link != NULL)
        {
            if (!NamesInOrder(MovingPointer1->LastName, MovingPointer2->LastName))
            {
                ZeroSwapsOccured = false;

                //Temp = MP1
                //MP1  = MP2
                //MP2  = TEMP

                MovingPointer1->Link = MovingPointer2->Link;
                MovingPointer2->Link = MovingPointer1;
                HeadPointer->Link = MovingPointer2;
            }
        }
    }

    HeadPointer = StaticPointer;//link HeadPointer back to list after sort
}

bool NamesInOrder(const char LastName1[], const char LastName2[])
{
    for (int i = 0; LastName1[i] || LastName2[i]; ++i)//go until you get to the end of the larger name
    {
        if(toupper(LastName1[i]) < toupper(LastName2[i]))
           return true;

        if(toupper(LastName1[i]) > toupper(LastName2[i]))
            return false;
    }

    return true;//this will only be used if same last name

    //build in fucntionality to then go to first name after last name, if both last names are the same
}

string Date()//not my code here - just modified it to read easier
{
    char Time[50];
    time_t now = time(NULL);
    strftime(Time, 50, "%b, %d, %Y", localtime(&now)); //short month name
    return string(Time);
}

Answer 1

首先 -在这两种情况下您都对列表进行了重新排序。

第二 - 交换两个节点通常需要五个操作:

1. 将节点 one 从第一个节点改回指向第二个节点。
2. 将节点 one 从第二个节点改回指向第一个节点。
3. 将第一个节点的next指针存储在一个临时指针中。
4. 将第一个节点的 next 指针更改为第二个节点的 next 指针。
5. 将第二个节点的next指针改为临时指针。

交换两个变量至少需要三个操作:

1. 将第一个变量存储在临时变量中。
2. 将第一个变量更改为第二个变量。
3. 将第二个变量更改为第一个变量。

但现在乘以结构成员的数量。

该结构应该至少有 2 个数据成员 - 一个指针和一个有效负载 - 所以你马上就会看到至少 6 个操作。对于结构中的每个成员，这将增加 3。所以你最好只交换节点。