Sorting Linked Lists - move nodes or swap data members?

I have a simple question. I'm working on a C++ app that is a contact list app. It stores names, addresses, numbers, ages, etc for multiple people. I'm using stucts and linked lists (nodes). I'm building the sort list function, to alphabetize the list. I'm currently wondering if it's better to actually reorder the list by moving the structs as a whole or by swapping the data members inside each node. At first, I considered moving the nodes, but now swapping the data members seems more safe, as I don't have to reorder the list. At any rate, I don't know if either possesses any benefits over the other.

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

EDIT: Here's the source code I'm working on. Notice the sort function is incomplete. Also, I'm still a novice programmer, so the coding will probably have a ton of issues, from a professional standpoint. That, alongside the fact I'm not close to being done with it. I'm only writing it to practice coding over my summer break between programming classes.

编辑:这是我正在处理的源代码。请注意,排序功能不完整。此外,我仍然是一名新手程序员,因此从专业角度来看,编码可能会有很多问题。除此之外,我还没有接近完成它。我只是在编程课程的暑假期间编写它来练习编码。

#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);
}

5 个解决方案

#1

First - You're reordering the list in both cases.

首先 - 你在两种情况下重新排序列表。

Second - Swapping two nodes usually takes five operations:

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

1. Change the node one back from the first node to point to the second node.

将节点从第一个节点更改为指向第二个节点。

2. Change the node one back from the second node to point to the first node.

将节点1从第二个节点更改为指向第一个节点。

3. Store the first node's next pointer in a temporary pointer.

将第一个节点的下一个指针存储在临时指针中。

4. Change the first node's next pointer to the second node's next pointer.

将第一个节点的下一个指针更改为第二个节点的下一个指针。

5. Change the second node's next pointer to the temporary pointer.

将第二个节点的下一个指针更改为临时指针。

Swapping two variables takes at least three operations:

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

1. Store the first variable in a temporary variable.

将第一个变量存储在临时变量中。

2. Change the first variable to the second variable.

将第一个变量更改为第二个变量。

3. Change the second variable to the first variable.

将第二个变量更改为第一个变量。

But now multiply that by the number of struct members.

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

The struct should have at least 2 data members - a pointer and a payload - so off the bat you're looking at, at least, 6 operations. Which will increase by 3 for each member in the struct. So you're better off just swapping the nodes.

该结构应该至少有2个数据成员 - 一个指针和一个有效负载 - 所以你正在观察,至少6个操作。对于结构中的每个成员,这将增加3。所以你最好只是交换节点。

#2

No memory should be moving. The nodes in a linked list are not ordered in memory but only in relation to each-other via pointer(s) to the next/previous nodes in the list. your operation can be done with only a few pointer assignments.

没有记忆应该移动。链表中的节点不是在内存中排序,而是仅通过指向列表中下一个/上一个节点的指针相互关联。只需几个指针分配即可完成操作。

#3

Swapping the data is more costly and complex. For example, to swap the data, you will need to swap the name, address, numbers, ages etc.

交换数据更加昂贵和复杂。例如,要交换数据,您需要交换名称,地址,数字,年龄等。

On the other hand, swapping the node means just swapping two memory location address inside your list. So, swapping the nodes is highly preferable.

另一方面,交换节点意味着只需交换列表中的两个内存位置地址。因此,交换节点是非常可取的。

Secondly, if you add more metaData fields to your node, you won't have to change the sort code to swap the newly added data field.

其次,如果向节点添加更多元数据字段,则无需更改排序代码以交换新添加的数据字段。

#4

So you have a linked list that you want to sort. To do it correctly and efficiently you have to use the correct sorting algorithm which in this case is the Merge Sort. For sure you should not swap the nodes' data.

因此,您有一个要排序的链接列表。要正确有效地执行此操作,您必须使用正确的排序算法,在本例中为合并排序。确保您不应交换节点的数据。

Check this link: http://www.geeksforgeeks.org/merge-sort-for-linked-list/

请访问此链接:http://www.geeksforgeeks.org/merge-sort-for-linked-list/

#5

If node data size is larger, that time it's better to swap node's position rather than swap node's data (swapping data will be bad choice).

如果节点数据大小较大,那么最好交换节点的位置而不是交换节点的数据(交换数据将是不好的选择)。

Reasons of choosing moving the pointer implementation over swapping the data:

选择移动指针实现而不是交换数据的原因:

1. Let's suppose you want to add a new field to your contact list after some time. If you swap data, you will have to change your code every time you make changes to your contact list field.

   假设您想在一段时间后将新字段添加到联系人列表中。如果您交换数据,则每次更改联系人列表字段时都必须更改代码。

2. As fields in contact list increase, overhead for swapping the data will grow.

   随着联系人列表中的字段增加,交换数据的开销将增加。