C++双向链表按字母顺序和值添加节点

Question

我的任务是创建双向链表并根据它们的数据对它们进行排序，如果新写入的节点数据等于我的双向链表中的节点数据之一，我应该按字母顺序对它们进行排序但我被困在函数 strcmp(temp->name, newnode->name) 中，例如，我正在尝试检查这些值是否按顺序输入

基督教 250
汤姆 200
亚历克斯 250

我排序的双向链表给出的输出为

亚历克斯 250
基督教 250
汤姆 200

这是我的代码示例

   struct node {
    int data;
    string name;
    node* left;
    node* right;

    node(int i = 0, string s = "", node* l = nullptr, node* r = nullptr) : data(i), name(s), left(l), right(r) {}
};

struct node* head = NULL;
struct node* tail = NULL;

在程序的顶部

void insert(int newdata, string name)  // Used for insertion at the end of the linked list and make 
{                                      // the connection for each of the node
    node* newnode = new node();
    node* nodehead = head;
    newnode->data = newdata;
    newnode->name = name;
    newnode->right = NULL;

    if( head == NULL)
    {
        newnode -> left = NULL;
        head = tail = newnode;
    }
    else 
    {
        while (nodehead->right != NULL)
        {
            nodehead = nodehead->right;     
        }
            nodehead->right = newnode; // make the connection for each of them
            newnode->left = nodehead;
            tail = newnode; // and newly created node is our tail

            sorting(newnode); // then go the function to sort them 
    }
   
    cout << "New node is added " << newnode->name << " " << newnode->data << endl;
}

然后根据他们的数据比较对它们进行排序，如果它们相等，我应该根据它们的字母顺序检查

 void sorting( node *  &newnode) // ı call sorting function in the insertion function
    {
        node* temp = head;
        node* temp2 = newnode;
    
        int numtemp;
    
        while (temp != nullptr)
        {
            node* temp2 = temp->right;
            while (temp2 != nullptr)
            {       
                if (temp2->data > temp->data) // comparison of their data if newnode's data is larger 
                {
                    string strtemp = "";
                    numtemp = temp->data; // Change their number
                    temp->data = temp2->data;
                    temp2->data = numtemp;
    
                    strtemp = temp->name; // Change their name
                    temp->name = temp2->name;
                    temp2->name = strtemp;
                }
                else if (temp2->data = temp->data) // if newly data is equal to linked list data
                {
                    int ret;
                    ret =  strcmp(temp2->name, temp->name); // i tried to check their string comparison but it did not work
                }
                temp2 = temp2->right;
            }
            temp = temp->right;
        }        
    }

Answer 1

我建议您在节点本身上定义一个比较，并将其用于排序。请记住，如果您通过指针进行比较，则需要取消引用（比较节点，而不是指针）。

标准库已经有了基于多个术语进行比较的方法。 https://en.cppreference.com/w/cpp/utility/tuple/tie

使用std::tie确保您满足https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

当然，我假设 std::string 的比较符合您对字母顺序的需要。如果不是这种情况，这可能需要小修整一周。

#include <string>
#include <iostream>

struct node {
    int data;
    std::string name;
    node* left;
    node* right;

    node(int i = 0, std::string s = "", node* l = nullptr, node* r = nullptr) 
        : data(i), name(s), left(l), right(r) 
    {}

    bool operator< (const node & rhs) {
        return std::tie(data, name) < std::tie(rhs.data, rhs.name);
    }
};

int main(){
    // simplistic demo
    node a { 21, "green" };
    node b { 21, "yellow" };
    node * p1 = &a;
    node * p2 = &b;
    bool less = (*p1) < (*p2);
    if (p1->data == p2->data) {
        if (*p1 < *p2) {
            std::cout << p1->name << " < " << p2->name << std::endl;
        } else {
            std::cout << p1->name << " >= " << p2->name << std::endl;
        }
    }
}

Answer 2

如果值相同并更改名称，基本上会添加 else if 部分，但显然它会更改整个数字列表

void sorting( node *  &newnode) 
{

    node* temp = head;
    node* temp2 = newnode;

    int numtemp;


    while (temp != nullptr)
    {
        node* temp2 = temp->right;
        while (temp2 != nullptr)
        {

            if (temp2->data > temp->data)
            {
                string strtemp = "";
                numtemp = temp->data; // num change
                temp->data = temp2->data;
                temp2->data = numtemp;

                strtemp = temp->name; // name change
                temp->name = temp2->name;
                temp2->name = strtemp;

            }
            else if (temp2->data == temp->data) // here is the change 
            {
               if(temp2->name > temp->name ) // make comparison but im not sure wheteris logical or not 
               {
                   string strtemp = "";
                   strtemp = temp->name; // name change
                   temp->name = temp2->name;
                   temp2->name = strtemp;
               
               }
                
                 
                
            }

            temp2 = temp2->right;
        }

        temp = temp->right;
    }

   

}

Answer 3

您的比较运算符错误：

              if(temp2->name < temp->name ) // make comparison but im not sure wheteris logical or not 
               {
                   string strtemp = "";
                   strtemp = temp->name; // name change
                   temp->name = temp2->name;
                   temp2->name = strtemp;
               
               }

应该是<.

C++双向链表按字母顺序和值添加节点

C++ Doubly linked list adding node in alphabetical order and value

c++

sorting

char

doubly-linked-list

alphabetical-sort