0
我有问题试图将INSERT函数转换为按字母顺序排列节点的函数。我写下了迄今为止我尝试过的内容......但它只检查第一个节点的名称，以查看它是否大于函数参数中新节点的给定名称。有人可以给我一个关于如何能够移动通过每个节点并且能够比较它们的键（名称）并相应地将它们左右放置的想法吗？下面是我在我的代码和我的INSERT功能到目前为止...将未排序的链接列表变成已排序的链接列表？ （C++）
// UnSortedLnkList.h
//----------------------------
#include <iostream>
#include <afxwin.h>
using namespace std;
#define new DEBUG_NEW
struct Node {
string m_name; // key
int m_age;
Node* m_next;
Node(const string& name, int age, Node* next = NULL);
};
ostream& operator<< (ostream&, const Node&);
class ULnkList {
friend ostream& operator<< (ostream&, const ULnkList&); // 1.5
public:
ULnkList();
// copy ctor
ULnkList(const ULnkList& existingList); // 5
~ULnkList(); // 4
bool IsEmpty() const;
int Size() const;
bool Insert(const string& name, int age); // 1
bool Delete(const string& name); // 3
bool Lookup(const string& name, int& age) const; // 2
ULnkList& operator =(const ULnkList& list2); // 6
bool Delete2(const string& name);
private:
Node* m_head; // points to head of the list
int m_num; // the number of entries in the list
// helper functions:
void Clear(); // 7
void Copy(const ULnkList& list2); // 8
};
// UnSortedLnkList.cpp
//----------------------------
#include "UnSortedLnkList.h"
#include <iostream>
#include <string>
using namespace std;
Node::Node(const string& name, int age, Node* next)
: m_name(name), m_age(age), m_next(next)
{}
ostream& operator<< (ostream& os, const Node& n) // cout << n;
{
os << "Name: " << n.m_name << "\tAge: " << n.m_age;
return os;
}
ULnkList::ULnkList()
: m_head(new Node("",-99,NULL)), m_num(0)
{
//m_head = new Node("",-99,NULL);
}
//
ULnkList::ULnkList(const ULnkList& existingList)
{
Copy(existingList);
}
void ULnkList::Copy(const ULnkList& existingList)
{
m_num = existingList.m_num;
// create dummy node
m_head = new Node("",-99,NULL);
// traverse existing list
Node *pe = existingList.m_head->m_next;
Node *pThis = m_head;
while(pe != 0)
{
// create a copy of the Node in OUR list
pThis->m_next = new Node(pe->m_name,pe->m_age,0);
// update pointers
pe = pe->m_next;
pThis = pThis->m_next;
}
}
void ULnkList::Clear()
{
Node *p = m_head->m_next;
Node *tp = m_head; // trail pointer
while(p != 0)
{
delete tp;
// update pointers
tp = p; //
p = p->m_next;
}
delete tp;
}
ULnkList& ULnkList::operator =(const ULnkList& list2) // list1 = list2;
{
// list1 = list1; // check for self-assignment
if(this != &list2)
{
this->Clear(); // normally Clear();
this->Copy(list2);
}
// l1 = l2 = l3;
return *this;
}
bool ULnkList::IsEmpty() const
{
return m_num == 0;
// return m_head->m_next == NULL;
}
int ULnkList::Size() const
{
return m_num;
}
//
ULnkList::Insert(const string& name, int age)
{
Node *current = m_head->m_next;
Node *previous = m_head;
if (m_head->m_next == NULL)
{
m_head->m_next = new Node(name,age,m_head->m_next);
m_num++;
return true;
}
if (name < m_head->m_next->m_name)
{
m_head->m_next = new Node(name,age,m_head->m_next);
m_num++;
return true;
}
return true;
}
//
ostream& operator<< (ostream& os, const ULnkList& list) // cout << list;
{
Node *p = list.m_head->m_next; // first node with data
while(p != 0)
{
cout << *p << endl; // ????
// update p
p = p->m_next;
}
cout << "--------------------------------------" << endl;
return os;
}
// input: name
//// output: age if found
bool ULnkList::Lookup(const string& name, int& age) const
{
// linear search
Node *p = m_head->m_next;
while(p != 0)
{
if(name == p->m_name)
{
// found it
age = p->m_age;
return true;
}
// update p
p = p->m_next;
}
return false;
}
//
bool ULnkList::Delete(const string& name)
{
Node *p = m_head->m_next;
Node *tp = m_head; // trail pointer
while(p != 0)
{
if(name == p->m_name)
{
// found it, so now remove it
// fix links
tp->m_next = p->m_next;
// delete the node
delete p;
return true;
}
// update pointers
tp = p; // tp = tp->m_next;
p = p->m_next;
}
return false;
}
bool ULnkList::Delete2(const string& name)
{
Node *p = m_head;
while(p->m_next != 0) // ?????
{
if(p->m_next->m_name == name)
{
Node *save = p->m_next;
// remove the node
// fix links
p->m_next = p->m_next->m_next;
// delete memory
delete save;
return true;
}
// update pointers
p = p->m_next;
}
return false;
}
//
ULnkList::~ULnkList()
{
Clear();
}
//
如果这是功课，请标记为这样。否则，不要使用链表来产生一个糟糕的'std :: set'模拟（好吧，我没有仔细观察 - 也许这是对std :: multiset的模仿）。哦，既然你没有编写模板，也可以从你的代码中删除'this->'。 –