创建有序链表时缺少节点?
Missing nodes in creation of ordered linked list?
我正在尝试通过遍历其节点并通过 add_ordered()
添加它们来从现有链表中创建一个有序双向链表,但是当我打印有序列表时,很少有节点丢失。
list.h
:
#ifnded LIST_H
#define LIST_H
struct Node {
// data member
std::string value;
// constructors
Node (std::string v) : value(v) { }
Node (const Node& src) : value(src.value) { }
// overloaded operators
friend std::ostream& operator<< (std::ostream& os, const Node& g);
friend bool operator< (const Node& lhs, const Node& rhs);
friend bool operator> (const Node& lhs, const Node& rhs);
};
//====================================================================================
// doubly linkes list accepting any object type as its data member (value)
template<class T>
class Link {
public:
// public data member
T value;
// constructor
Link<T> (T v, Link<T>* p = 0, Link<T>* s = 0) : value(v), prev(p), succ(s) { }
// copy constructor
Link<T> (const Link<T>& l) : value(l.value), prev(l.next()), succ(l.previous()) { }
// non-modifying members
Link<T>* next () const { return succ; }
Link<T>* previous () const { return prev; }
// modifying members
Link<T>* insert (Link<T>* n);
Link<T>* add (Link<T>* n);
Link<T>* add_ordered (Link<T>* n);
private:
// private data members
Link<T>* prev;
Link<T>* succ;
};
#include "list.cpp"
#endif
list.cpp
:
std::ostream& operator<<(std::ostream& os, const Node& g) {
os << g.value ;
return os;
}
bool operator< (const Node& lhs, const Node& rhs) {
return lhs.value < rhs.value;
}
bool operator> (const Node& lhs, const Node& rhs) {
return lhs.value > rhs.value;
}
//=======================================================================================
// It inserts the node passed as a parameter before the node currently pointed to by this.
template<class T>
Link<T>* Link<T>::insert (Link<T>* n) {
if (!n) return this;
if (!this) return n;
n->succ = this;
n->prev = prev;
if (prev) prev->succ = n;
prev = n;
return n;
}
// It inserts the node passed as a parameter after the node currently pointer to by this.
template<class T>
Link<T>* Link<T>::add (Link<T>* n) {
if (!n) return this;
if (!this) return n;
// n->succ = nullptr;
n->succ = succ;
n->prev = this;
succ = n;
return n;
}
/*
It inserts the new node such that
current node and new node in
lexicographical order; returns
pointer to last node.
First node in ordered list contains the
lexicographically smaller value.
It assumes argument is the tail.
*/
template<class T>
Link<T>* Link<T>::add_ordered (Link<T>* n) {
if (!n) return this;
if (!this) { std::cout <<"new node first\n"; return n; }
Link<T>* tail = this;
if (n->value > tail->value) {
std::cout <<"new node largest \n";
add(n); // add after current (last) node
return n;
}
Link<T>* current_node = this;
while (current_node) {
if (n->value > current_node->value) {
std::cout <<"new node spliced \n";
add(n);
return tail;
}
std::cout <<"advance to head\n";
current_node = current_node->previous();
}
insert(n); // insert before current (first) node
std::cout << "new node smallest\n";
return tail;
}
main.cpp
:
#include <iostream>
#include <string>
#include <list.h>
template<class T>
void create_ordered_list (Link<T>* src, Link<T>*& dest) {
while (src){
Link<T> l(src->value, nullptr, nullptr);
dest = dest->add_ordered(new Link<T>(l));
src = src->next();
}
}
template<class T>
void print(Link<T>* n) {
Link<T>* tail = n;
if (tail->next()) {
std::cout <<"[";
while (tail) {
std::cout << tail->value;
if (tail = tail->next()) std::cout <<"\n";
}
std::cout <<"]";
} else if (tail->previous()) {
std::cout <<"[";
while (tail) {
std::cout << tail->value;
if (tail = tail->previous()) std::cout <<"\n";
}
std::cout <<"]";
}
getchar();
}
//===============================================================
int main () {
Link<Node>* head = new Link<Node>(Node("Zeus"));
head = head->insert(new Link<Node>(Node("Hera")));
head = head->insert(new Link<Node>(Node("Athena")));
head = head->insert(new Link<Node>(Node("Ares")));
head = head->insert(new Link<Node>(Node("Poseidon")));
print<Node>(head);
std::cout <<"\nOrdered lists\n";
Link<Node>* ordered_list = nullptr;
create_ordered_list(head, ordered_list);
print(ordered_list);
}
排序后的输出:
[Zeus
Hera
Athena]
预期输出:
[Zeus
Poseidon
Hera
Athena
Ares]
首先你必须更正add()
函数:
template<class T>
Link<T>* Link<T>::add (Link<T>* n) {
...
n->succ = succ;
n->prev = this;
succ = n;
if (n->succ) n->succ->prev = n; ///!!!
return n;
}
然后你必须在add_ordered()
函数中插入一些add()
和insert()
并调整一些returns:
template<class T>
Link<T>* Link<T>::add_ordered (Link<T>* n) {
if (!n) return this;
if (!this) { std::cout <<"new node first\n"; return n; }
Link<T>* tail = this;
if (n->value > tail->value) {
std::cout <<"new node largest \n";
return insert(n); // No: you need to insert before current node !!!
}
Link<T>* current_node = this;
while (current_node) {
if (n->value > current_node->value) {
std::cout <<"new node spliced \n";
add(n);
return this;
}
std::cout <<"advance to head\n";
current_node = current_node->previous();
}
add(n); // no: here we have to add at the end !
std::cout << "new node smallest\n";
return this;
}
那么它应该可以工作:live demo。
我正在尝试通过遍历其节点并通过 add_ordered()
添加它们来从现有链表中创建一个有序双向链表,但是当我打印有序列表时,很少有节点丢失。
list.h
:
#ifnded LIST_H
#define LIST_H
struct Node {
// data member
std::string value;
// constructors
Node (std::string v) : value(v) { }
Node (const Node& src) : value(src.value) { }
// overloaded operators
friend std::ostream& operator<< (std::ostream& os, const Node& g);
friend bool operator< (const Node& lhs, const Node& rhs);
friend bool operator> (const Node& lhs, const Node& rhs);
};
//====================================================================================
// doubly linkes list accepting any object type as its data member (value)
template<class T>
class Link {
public:
// public data member
T value;
// constructor
Link<T> (T v, Link<T>* p = 0, Link<T>* s = 0) : value(v), prev(p), succ(s) { }
// copy constructor
Link<T> (const Link<T>& l) : value(l.value), prev(l.next()), succ(l.previous()) { }
// non-modifying members
Link<T>* next () const { return succ; }
Link<T>* previous () const { return prev; }
// modifying members
Link<T>* insert (Link<T>* n);
Link<T>* add (Link<T>* n);
Link<T>* add_ordered (Link<T>* n);
private:
// private data members
Link<T>* prev;
Link<T>* succ;
};
#include "list.cpp"
#endif
list.cpp
:
std::ostream& operator<<(std::ostream& os, const Node& g) {
os << g.value ;
return os;
}
bool operator< (const Node& lhs, const Node& rhs) {
return lhs.value < rhs.value;
}
bool operator> (const Node& lhs, const Node& rhs) {
return lhs.value > rhs.value;
}
//=======================================================================================
// It inserts the node passed as a parameter before the node currently pointed to by this.
template<class T>
Link<T>* Link<T>::insert (Link<T>* n) {
if (!n) return this;
if (!this) return n;
n->succ = this;
n->prev = prev;
if (prev) prev->succ = n;
prev = n;
return n;
}
// It inserts the node passed as a parameter after the node currently pointer to by this.
template<class T>
Link<T>* Link<T>::add (Link<T>* n) {
if (!n) return this;
if (!this) return n;
// n->succ = nullptr;
n->succ = succ;
n->prev = this;
succ = n;
return n;
}
/*
It inserts the new node such that
current node and new node in
lexicographical order; returns
pointer to last node.
First node in ordered list contains the
lexicographically smaller value.
It assumes argument is the tail.
*/
template<class T>
Link<T>* Link<T>::add_ordered (Link<T>* n) {
if (!n) return this;
if (!this) { std::cout <<"new node first\n"; return n; }
Link<T>* tail = this;
if (n->value > tail->value) {
std::cout <<"new node largest \n";
add(n); // add after current (last) node
return n;
}
Link<T>* current_node = this;
while (current_node) {
if (n->value > current_node->value) {
std::cout <<"new node spliced \n";
add(n);
return tail;
}
std::cout <<"advance to head\n";
current_node = current_node->previous();
}
insert(n); // insert before current (first) node
std::cout << "new node smallest\n";
return tail;
}
main.cpp
:
#include <iostream>
#include <string>
#include <list.h>
template<class T>
void create_ordered_list (Link<T>* src, Link<T>*& dest) {
while (src){
Link<T> l(src->value, nullptr, nullptr);
dest = dest->add_ordered(new Link<T>(l));
src = src->next();
}
}
template<class T>
void print(Link<T>* n) {
Link<T>* tail = n;
if (tail->next()) {
std::cout <<"[";
while (tail) {
std::cout << tail->value;
if (tail = tail->next()) std::cout <<"\n";
}
std::cout <<"]";
} else if (tail->previous()) {
std::cout <<"[";
while (tail) {
std::cout << tail->value;
if (tail = tail->previous()) std::cout <<"\n";
}
std::cout <<"]";
}
getchar();
}
//===============================================================
int main () {
Link<Node>* head = new Link<Node>(Node("Zeus"));
head = head->insert(new Link<Node>(Node("Hera")));
head = head->insert(new Link<Node>(Node("Athena")));
head = head->insert(new Link<Node>(Node("Ares")));
head = head->insert(new Link<Node>(Node("Poseidon")));
print<Node>(head);
std::cout <<"\nOrdered lists\n";
Link<Node>* ordered_list = nullptr;
create_ordered_list(head, ordered_list);
print(ordered_list);
}
排序后的输出:
[Zeus
Hera
Athena]
预期输出:
[Zeus
Poseidon
Hera
Athena
Ares]
首先你必须更正add()
函数:
template<class T>
Link<T>* Link<T>::add (Link<T>* n) {
...
n->succ = succ;
n->prev = this;
succ = n;
if (n->succ) n->succ->prev = n; ///!!!
return n;
}
然后你必须在add_ordered()
函数中插入一些add()
和insert()
并调整一些returns:
template<class T>
Link<T>* Link<T>::add_ordered (Link<T>* n) {
if (!n) return this;
if (!this) { std::cout <<"new node first\n"; return n; }
Link<T>* tail = this;
if (n->value > tail->value) {
std::cout <<"new node largest \n";
return insert(n); // No: you need to insert before current node !!!
}
Link<T>* current_node = this;
while (current_node) {
if (n->value > current_node->value) {
std::cout <<"new node spliced \n";
add(n);
return this;
}
std::cout <<"advance to head\n";
current_node = current_node->previous();
}
add(n); // no: here we have to add at the end !
std::cout << "new node smallest\n";
return this;
}
那么它应该可以工作:live demo。