我在我的链接列表的排序方法有问题。我需要传送节点（节点的条目）的链接到一个双向链表节点进行排序。该方法停止由于在最后一个节点到nullptr。
我不知道如何解决这个问题。我尝试了很多变种，但没有一个是成功的。
#include "DlinkedList.h"
// Node constructor
Node::Node()
{
this->rhetorician = NULL;
this->prev = NULL;
this->next = NULL;
}
// Node destructor
Node::~Node()
{
}
// List constructor
DlinkedList::DlinkedList()
{
this->length = 0;
this->head = NULL;
}
// Method for adding node at the end
void DlinkedList::appendNode(Rhetorician* rhetorician)
{
if (this->head == NULL) {
Node *new_node = new Node();
new_node->rhetorician = rhetorician;
this->head = new_node;
}
else {
Node *last_node = NULL;
for (Node *node_ptr = this->head; node_ptr != NULL; node_ptr = node_ptr->next)
{
last_node = node_ptr;
}
Node *new_node = new Node();
new_node->rhetorician = rhetorician;
last_node->next = new_node;
new_node->prev = last_node;
}
this->length++;
}
// Method for printing nodes
void DlinkedList::printNodes()
{
for (Node *node_cur = this->head; node_cur != NULL; node_cur = node_cur->next)
{
node_cur->rhetorician->printer();
cout << "---------------------------------------------------------------------------------------------------" << endl;
}
cout << endl << "##################################################################################################\n" << endl;
}
// Method for getting length
int DlinkedList::getLenght()
{
return this->length;
}
// Method for deleting node
void DlinkedList::remove(string name)
{
Node* logout_node = NULL;
for (Node* node_cur = this->head; node_cur != NULL; node_cur = node_cur->next)
{
if (node_cur->rhetorician->name == name)
{
logout_node = node_cur;
}
}
if (this->head != NULL || logout_node != NULL)
{
if (this->head == logout_node)
{
this->head = logout_node->next;
}
if (logout_node->next != NULL)
{
logout_node->next->prev = logout_node->prev;
}
if (logout_node->prev != NULL)
{
logout_node->prev->next = logout_node->next;
}
delete logout_node->rhetorician;
delete logout_node;
this->length--;
}
}
// Method for finding node
void DlinkedList::find(string name)
{
bool ver = false;
Node *n = NULL;
for (Node* node_cur = this->head; node_cur != NULL; node_cur = node_cur->next)
{
if (node_cur->rhetorician->name == name)
{
ver = true;
n = node_cur;
}
}
if (ver)
{
n->rhetorician->printer();
}
else
{
cout << "Rhetorician was not found!";
}
}
// Method for sorting nodes
void DlinkedList::sort()
{
int count = this->getLenght();
Node *tmp, *current;
int i, j;
for (i = 1; i < count; i++)
{
current = this->head;
for (j = 0; j <= count - i - 1; j++)
{
Node *before, *after;
if (current->rhetorician->coefficient > current->next->rhetorician->coefficient)
{
before = current->prev;
after = current->next;
if (before != NULL) {
before->next = after;
}
current->next = after->next;
current->prev = after;
after->next = current;
after->prev = before;
}
tmp = current;
current = current->next;
}
}
}
// List destructor
DlinkedList::~DlinkedList()
{
Node *next_node = NULL;
for (Node *node_cur = this->head; node_cur != NULL; node_cur = next_node)
{
next_node = node_cur->next;
delete node_cur->rhetorician;
delete node_cur;
}
this->head = NULL;
this->length = 0;
}
主要：
#include <iostream>
#include "DlinkedList.h"
#include <fstream>
#include <vector>
#include <sstream>
// Namespace
using namespace std;
// Parser of line to vector array
vector<string> split(string strToSplit, char delimeter)
{
stringstream ss(strToSplit);
string item;
vector<string> splittedStrings;
while (getline(ss, item, delimeter))
{
splittedStrings.push_back(item);
}
return splittedStrings;
}
// File loader
void read_file(const char *name, DlinkedList *list)
{
// Variable for loading line
string line;
{
// Create relation
ifstream file(name);
// Check if file exists
if (file)
{
// Check if file is empty
if (!(file.peek() == ifstream::traits_type::eof()))
{
// Read data from file and put into LinkedList
while (getline(file, line)) {
list->appendNode(new Rhetorician(split(line, ';')[0], split(line, ';')[1],
split(line, ';')[2], stoi(split(line, ';')[3])));
}
}
// Close file
file.close();
}
}
}
// Main method
int main()
{
// Create instance of doubly linked list
DlinkedList *list = new DlinkedList();
// Read file and push data into list
read_file("seznam_enumat.txt", list);
// Print all loaded rhetoricians behind added own one
cout << "\nAll rhetoricians from file:" << endl;
cout << "##################################################################################################\n" << endl;
list->printNodes();
// Append other rhetoricians
list->appendNode(new Rhetorician("Cain", "Foster", "Structural and molecular virology", 7));
list->appendNode(new Rhetorician("Stacy", "Algar", "Dept of microbiology and immunology", 5));
list->appendNode(new Rhetorician("Oded", "Philander", "Experimental plasma physics", 3));
list->appendNode(new Rhetorician("Shay", "Rimon", "Experimental plasma physics", 10));
// Sort rhetoricians in list
list->sort();
// Delete rhetorician by name
//list->remove("Stacy");
// Finder of rhetorician
cout << "\nFound rhetorician:" << endl;
cout << "##################################################################################################\n" << endl;
list->find("Shay");
// Print all sorted rhetoricians
cout << "\nAll rhetoricians:" << endl;
cout << "##################################################################################################\n" << endl;
list->printNodes();
// Destruct list
delete list;
// Check if user click any key
getchar();
return 0;
}
雄辩：
#include "Rhetorician.h"
Rhetorician::Rhetorician(string name, string surname, string contribution, int coefficient)
{
this->name = name;
this->surname = surname;
this->contribution = contribution;
this->coefficient = coefficient;
}
void Rhetorician::printer()
{
// Name
cout << "Name:" << endl;
cout << this->name << endl;
// Surname
cout << "Surname:" << endl;
cout << this->surname << endl;
// Contribution
cout << "Contribution:" << endl;
cout << this->contribution << endl;
// Coefficient
cout << "Coefficient:" << endl;
cout << this->coefficient << endl;
}
主要的问题是在sort()。它不正确处理指针。就拿一个小例子，3 -> 2 -> 1，你会得到它。
下面是去除不需要的变量校正后的代码：
void DlinkedList::sort() {
int count = this->getLenght();
Node *current;
int i, j;
for (i = 1; i < count; i++) {
current = this->head;
for (j = 0; j <= count - i - 1; j++) {
Node *before, *after;
if (current->rhetorician->coefficient > current->next->rhetorician->coefficient) {
before = current->prev;
after = current->next;
if (before != nullptr) {
before->next = after;
} else {
// if before = null, it is the head node
this->head = after; // In case before pointer is null, after pointer should be the new head
}
current->next = after->next;
current->prev = after;
if (after->next != nullptr) {
after->next->prev = current; // prev pointer of after->next should be set to current.
}
after->next = current;
after->prev = before;
} else {
current = current->next; // Go to next node only if current->rhetorician->coefficient > current->next->rhetorician->coefficient condition is false.
}
}
}
}
向上排序列表正在超不过当我试图向下排序列表仅更改字符>为<它无法正常工作。节点之前和之后节点必须改变？
// Zero or one element, no sort required.
if (this->head == NULL) return;
if (this->head->next == NULL) return;
// Force initial entry.
int swapped = 1;
while (swapped) {
// Flag as last time, then do one pass.
swapped = 0;
this->current = this->head;
while (this->current->next != NULL) {
Node *before, *after;
if (current->rhetorician->coefficient > current->next->rhetorician->coefficient) {
swapped = 1;
before = current->prev;
after = current->next;
if (before != NULL) {
before->next = after;
}
else {
// if before = null, it is the head node
this->head = after; // In case before pointer is null, after pointer should be the new head
}
current->next = after->next;
current->prev = after;
if (after->next != NULL) {
after->next->prev = current; // prev pointer of after->next should be set to current.
}
after->next = current;
after->prev = before;
}
current = current->next;
}
}// Zero or one element, no sort required.
if (this->head == NULL) return;
if (this->head->next == NULL) return;
// Force initial entry.
int swapped = 1;
while (swapped) {
// Flag as last time, then do one pass.
swapped = 0;
this->current = this->head;
while (this->current->next != NULL) {
Node *before, *after;
if (current->rhetorician->coefficient > current->next->rhetorician->coefficient) {
swapped = 1;
before = current->prev;
after = current->next;
if (before != NULL) {
before->next = after;
}
else {
// if before = null, it is the head node
this->head = after; // In case before pointer is null, after pointer should be the new head
}
current->next = after->next;
current->prev = after;
if (after->next != NULL) {
after->next->prev = current; // prev pointer of after->next should be set to current.
}
after->next = current;
after->prev = before;
}
current = current->next;
}
}