在双向链表数据结构 class 实验项目中实现 append 和 insertAt 函数
Implementing append and insertAt functions in Doubly Linked List Data Structures class lab project
我已经在这个项目上工作了一个星期，但似乎无法使这个项目获得我需要通过这个实验室的预期输出。下面是本文提到的两个函数的脚手架post:
lab04.cpp（具有前置条件和 post 条件的空白脚手架）：
#include <ostream>
#include <cassert>
#include "linkedlistd.h"
namespace DS {
// Precondition: cursor is not NULL
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor->next
// The new node prev points to cursor
// The cursor->next prev points to the new node
// The cursor next points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::appendAt (const value_type& newdatum,node* cursor) {
}
// Precondition: none
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor
// The new node prev points to cursor->prev
// The cursor->prev next points to the new node
// The cursor prev points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::insertAt (const value_type& newdatum,node* cursor) {
}
} // end namespace
以下代码是我的文件版本，其中包含我尝试解决这两个函数的尝试：
#include "linkedlistd.h"
namespace DS {
// Precondition: cursor is not NULL
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor->next
// The new node prev points to cursor
// The cursor->next prev points to the new node
// The cursor next points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::appendAt(const value_type& newdatum, node* cursor) {
node* new_node = new node();
if (cursor->next() != nullptr) {
node* next_node = cursor->next();
new_node->setData(newdatum);
cursor->setNext(new_node);
new_node->setPrev(cursor);
new_node->setNext(next_node);
next_node->setPrev(new_node);
return next_node;
}
else {
new_node->setPrev(cursor);
cursor->setNext(new_node);
new_node->setNext(nullptr);
return new_node;
}
}
// Precondition: none
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor
// The new node prev points to cursor->prev
// The cursor->prev next points to the new node
// The cursor prev points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::insertAt(const value_type& newdatum, node* cursor) {
node* new_node = new node(newdatum);
if (cursor == nullptr) {
tail->setPrev(new_node);
new_node->setNext(tail);
new_node->setPrev(tail->prev());
return new_node;
}
if (cursor == head) {
new_node->setNext(head);
head->setPrev(new_node);
head = new_node;
return new_node;
}
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(cursor);
return new_node;
}
} // end namespace
但是当我运行项目时，我没有输出。
我应该得到的输出是：
->[5]->[10]->[20]--X
X--[20]<-[10]<-[5]<-
--X
->[30]->[5]->[10]->[20]->[7]->[2]--X
X--[2]<-[7]<-[20]<-[10]<-[5]<-[30]<-
->[1]->[2]->[4]->[8]->[16]->[32]->[16]->[8]->[4]->[2]->[1]--X
X--[1]<-[2]<-[4]<-[8]<-[16]<-[32]<-[16]<-[8]<-[4]<-[2]<-[1]<-
请帮助我完成这个项目，因为我对双向链表的理解和通过这个 class 取决于它。请用这两个函数的正确实现来回复，并解释为什么你编写了你为解决问题所做的事情。实验室的项目文件完整包含在下面。非常感谢您提前帮助我，我期待着阅读您的回复。
linkedlistd.h
#ifndef LINKEDDLIST_H
#define LINKEDDLIST_H
#include <cstdlib>
#include <iostream>
#include "node_dll.h"
namespace DS {
class linkedList
{
public:
typedef int value_type;
typedef DSDLL::node<value_type> node;
linkedList();
virtual ~linkedList();
node* appendAt(const value_type&, node*);
node* insertAt(const value_type&, node* = nullptr);
void insertItem(value_type);
void makeList(const value_type[], const size_t& count);
void deleteList();
//The following two assessors are for testing purpose and implemented inline
//Therefore, you do not need to implement in the cpp file
node* getHead() { return head; };
node* getTail() { return tail; };
//The following friend function is implemented in lablinklist.cpp
friend std::ostream& operator<<(std::ostream&, const linkedList&);
friend std::ostream& operator>>(std::ostream&, const linkedList&);
private:
node* head;
node* tail;
};
} //end namespace
#endif /* linkedList_H_ */
node_dll.h
#ifndef NODE_DLL_H_
#define NODE_DLL_H_
namespace DSDLL {
template <typename T>
class node
{
public:
typedef T value_type;
node(value_type d = value_type(), node* n = nullptr, node* p = nullptr) : data_field(d), next_ptr(n), prev_ptr(p) {}
//Assessor/Getters
const value_type& getData() const { return data_field; }
node const* getPrev() const { return prev_ptr; }
node const* getNext() const { return next_ptr; }
//Mutators/Setters
void setData(const value_type& d) { data_field = d; }
void setPrev(node* new_link) { prev_ptr = new_link; }
void setNext(node* new_link) { next_ptr = new_link; }
//Other
value_type& data() { return data_field; }
node*& prev() { return prev_ptr; }
node*& next() { return next_ptr; }
private:
value_type data_field;
node* next_ptr;
node* prev_ptr;
};
} /* namespace DSDLL */
#endif /* NODE_DLL_H_ */
lablinklist.cpp
#include <iostream>
#include "linkedlistd.h"
using namespace std;
using namespace DS;
int main() {
linkedList list1;
linkedList::node* tn1, * tn2;
//Test of adding items out of order
list1.insertItem(5);
list1.insertItem(20);
list1.insertItem(10);
cout << list1 << endl;
cout >> list1 << endl;
//Test of deleting entire list
list1.deleteList();
cout << list1 << endl;
//Add items again using insertAt and appendAt
list1.insertAt(5);
tn1 = list1.appendAt(10, list1.getHead());
tn2 = list1.appendAt(7, list1.getTail());
list1.appendAt(20, tn1);
list1.insertAt(30, list1.getHead());
list1.appendAt(2, tn2);
//Output forwards
cout << list1 << endl;
//Output reverse
cout >> list1 << endl;
//Now replace list with a new one in a specific order
int pow2[] = { 1,2,4,8,16,32,16,8,4,2,1 };
list1.makeList(pow2, sizeof(pow2) / sizeof(int));
cout << list1 << endl;
cout >> list1 << endl;
//Returning a non-zero number, if not 3, then we know it seg-faulted
return 3;
}
namespace DS {
/*
The following is provided so that everybody can easily get the same exact output
*/
std::ostream& operator<<(std::ostream& os, const linkedList& srcList) {
//Set a current-pointer to the "head".
const linkedList::node* cursor = srcList.head;
//While current-pointer is not NULL
while (cursor != nullptr)
{
//Print the data member ("datum") of the current node
os << "->[" << cursor->getData() << "]";
//Set the current-pointer to the "next" node in the list.
cursor = cursor->getNext();
}
//Print out a basic termination symbol
std::cout << "--X" << std::endl;
return os;
}
std::ostream& operator>>(std::ostream& os, const linkedList& srcList) {
//Set a current-pointer to the "head".
const linkedList::node* cursor = srcList.tail;
if (cursor == nullptr)
return os;
//Print out a start symbol
os << "X--[" << cursor->getData() << "]";
cursor = cursor->getPrev();
//While current-pointer is not NULL
while (cursor != nullptr)
{
//Print the data member ("datum") of the current node
os << "<-[" << cursor->getData() << "]";
//Set the current-pointer to the "next" node in the list.
cursor = cursor->getPrev();
}
//Print out a basic termination symbol
std::cout << "<-" << std::endl;
return os;
}
}
linkedlistd.cpp
#include <ostream>
#include <cassert>
#include "linkedlistd.h"
namespace DS {
linkedList::linkedList() {
head = tail = nullptr;
}
linkedList::~linkedList() {
deleteList();
}
void linkedList::insertItem(value_type newdatum) {
node* ccursor = head;
node* pcursor = nullptr;
if (head == NULL) {
insertAt(newdatum, ccursor);
}
else {
while (ccursor != NULL && newdatum > ccursor->getData()) {
pcursor = ccursor;
ccursor = ccursor->next();
}
appendAt(newdatum, pcursor);
}
}
void linkedList::makeList(const value_type items[], const size_t& count) {
deleteList();
if (count == 0) return;
insertAt(items[0]);
node* ccursor = head;
for (size_t i = 1; i < count; ++i) {
ccursor = appendAt(items[i], ccursor);
}
}
void linkedList::deleteList() {
node* dcursor;
while (head != nullptr) {
dcursor = head;
head = head->next();
delete dcursor;
}
head = tail = nullptr;
}
} //end of DS namespace
我认为您的以下代码语句不正确：
if (cursor == nullptr) {
tail->setPrev(new_node);
new_node->setNext(tail);
new_node->setPrev(tail->prev());
return new_node;
}
...
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(cursor);
return new_node;
请参阅下文进行更正。
情况一：当光标为nullptr时，即new_node必须插入到'last'处，因为没有找到匹配的位置中间的某个地方。这假设 'tail' 是你的最后一个元素（应该按照命名约定）：
if (cursor == nullptr){
tail->setNext(new_node);
new_node->setPrev(tail);
tail = new_node;
return new_node;
}
情况2：当光标指向中间某处时。它不是空的。 new_node 添加在 cursor.
之前
...
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(new_node);
return new_node;
我已经在这个项目上工作了一个星期，但似乎无法使这个项目获得我需要通过这个实验室的预期输出。下面是本文提到的两个函数的脚手架post:
lab04.cpp（具有前置条件和 post 条件的空白脚手架）：
#include <ostream>
#include <cassert>
#include "linkedlistd.h"
namespace DS {
// Precondition: cursor is not NULL
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor->next
// The new node prev points to cursor
// The cursor->next prev points to the new node
// The cursor next points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::appendAt (const value_type& newdatum,node* cursor) {
}
// Precondition: none
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor
// The new node prev points to cursor->prev
// The cursor->prev next points to the new node
// The cursor prev points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::insertAt (const value_type& newdatum,node* cursor) {
}
} // end namespace
以下代码是我的文件版本，其中包含我尝试解决这两个函数的尝试：
#include "linkedlistd.h"
namespace DS {
// Precondition: cursor is not NULL
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor->next
// The new node prev points to cursor
// The cursor->next prev points to the new node
// The cursor next points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::appendAt(const value_type& newdatum, node* cursor) {
node* new_node = new node();
if (cursor->next() != nullptr) {
node* next_node = cursor->next();
new_node->setData(newdatum);
cursor->setNext(new_node);
new_node->setPrev(cursor);
new_node->setNext(next_node);
next_node->setPrev(new_node);
return next_node;
}
else {
new_node->setPrev(cursor);
cursor->setNext(new_node);
new_node->setNext(nullptr);
return new_node;
}
}
// Precondition: none
// Postcondition: A new node is created with the datum of newdatum.
// The new node next points to cursor
// The new node prev points to cursor->prev
// The cursor->prev next points to the new node
// The cursor prev points to the new node
// Returns a pointer to the new node
linkedList::node* linkedList::insertAt(const value_type& newdatum, node* cursor) {
node* new_node = new node(newdatum);
if (cursor == nullptr) {
tail->setPrev(new_node);
new_node->setNext(tail);
new_node->setPrev(tail->prev());
return new_node;
}
if (cursor == head) {
new_node->setNext(head);
head->setPrev(new_node);
head = new_node;
return new_node;
}
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(cursor);
return new_node;
}
} // end namespace
但是当我运行项目时，我没有输出。
我应该得到的输出是：
->[5]->[10]->[20]--X
X--[20]<-[10]<-[5]<-
--X
->[30]->[5]->[10]->[20]->[7]->[2]--X
X--[2]<-[7]<-[20]<-[10]<-[5]<-[30]<-
->[1]->[2]->[4]->[8]->[16]->[32]->[16]->[8]->[4]->[2]->[1]--X
X--[1]<-[2]<-[4]<-[8]<-[16]<-[32]<-[16]<-[8]<-[4]<-[2]<-[1]<-
请帮助我完成这个项目，因为我对双向链表的理解和通过这个 class 取决于它。请用这两个函数的正确实现来回复，并解释为什么你编写了你为解决问题所做的事情。实验室的项目文件完整包含在下面。非常感谢您提前帮助我，我期待着阅读您的回复。
linkedlistd.h
#ifndef LINKEDDLIST_H
#define LINKEDDLIST_H
#include <cstdlib>
#include <iostream>
#include "node_dll.h"
namespace DS {
class linkedList
{
public:
typedef int value_type;
typedef DSDLL::node<value_type> node;
linkedList();
virtual ~linkedList();
node* appendAt(const value_type&, node*);
node* insertAt(const value_type&, node* = nullptr);
void insertItem(value_type);
void makeList(const value_type[], const size_t& count);
void deleteList();
//The following two assessors are for testing purpose and implemented inline
//Therefore, you do not need to implement in the cpp file
node* getHead() { return head; };
node* getTail() { return tail; };
//The following friend function is implemented in lablinklist.cpp
friend std::ostream& operator<<(std::ostream&, const linkedList&);
friend std::ostream& operator>>(std::ostream&, const linkedList&);
private:
node* head;
node* tail;
};
} //end namespace
#endif /* linkedList_H_ */
node_dll.h
#ifndef NODE_DLL_H_
#define NODE_DLL_H_
namespace DSDLL {
template <typename T>
class node
{
public:
typedef T value_type;
node(value_type d = value_type(), node* n = nullptr, node* p = nullptr) : data_field(d), next_ptr(n), prev_ptr(p) {}
//Assessor/Getters
const value_type& getData() const { return data_field; }
node const* getPrev() const { return prev_ptr; }
node const* getNext() const { return next_ptr; }
//Mutators/Setters
void setData(const value_type& d) { data_field = d; }
void setPrev(node* new_link) { prev_ptr = new_link; }
void setNext(node* new_link) { next_ptr = new_link; }
//Other
value_type& data() { return data_field; }
node*& prev() { return prev_ptr; }
node*& next() { return next_ptr; }
private:
value_type data_field;
node* next_ptr;
node* prev_ptr;
};
} /* namespace DSDLL */
#endif /* NODE_DLL_H_ */
lablinklist.cpp
#include <iostream>
#include "linkedlistd.h"
using namespace std;
using namespace DS;
int main() {
linkedList list1;
linkedList::node* tn1, * tn2;
//Test of adding items out of order
list1.insertItem(5);
list1.insertItem(20);
list1.insertItem(10);
cout << list1 << endl;
cout >> list1 << endl;
//Test of deleting entire list
list1.deleteList();
cout << list1 << endl;
//Add items again using insertAt and appendAt
list1.insertAt(5);
tn1 = list1.appendAt(10, list1.getHead());
tn2 = list1.appendAt(7, list1.getTail());
list1.appendAt(20, tn1);
list1.insertAt(30, list1.getHead());
list1.appendAt(2, tn2);
//Output forwards
cout << list1 << endl;
//Output reverse
cout >> list1 << endl;
//Now replace list with a new one in a specific order
int pow2[] = { 1,2,4,8,16,32,16,8,4,2,1 };
list1.makeList(pow2, sizeof(pow2) / sizeof(int));
cout << list1 << endl;
cout >> list1 << endl;
//Returning a non-zero number, if not 3, then we know it seg-faulted
return 3;
}
namespace DS {
/*
The following is provided so that everybody can easily get the same exact output
*/
std::ostream& operator<<(std::ostream& os, const linkedList& srcList) {
//Set a current-pointer to the "head".
const linkedList::node* cursor = srcList.head;
//While current-pointer is not NULL
while (cursor != nullptr)
{
//Print the data member ("datum") of the current node
os << "->[" << cursor->getData() << "]";
//Set the current-pointer to the "next" node in the list.
cursor = cursor->getNext();
}
//Print out a basic termination symbol
std::cout << "--X" << std::endl;
return os;
}
std::ostream& operator>>(std::ostream& os, const linkedList& srcList) {
//Set a current-pointer to the "head".
const linkedList::node* cursor = srcList.tail;
if (cursor == nullptr)
return os;
//Print out a start symbol
os << "X--[" << cursor->getData() << "]";
cursor = cursor->getPrev();
//While current-pointer is not NULL
while (cursor != nullptr)
{
//Print the data member ("datum") of the current node
os << "<-[" << cursor->getData() << "]";
//Set the current-pointer to the "next" node in the list.
cursor = cursor->getPrev();
}
//Print out a basic termination symbol
std::cout << "<-" << std::endl;
return os;
}
}
linkedlistd.cpp
#include <ostream>
#include <cassert>
#include "linkedlistd.h"
namespace DS {
linkedList::linkedList() {
head = tail = nullptr;
}
linkedList::~linkedList() {
deleteList();
}
void linkedList::insertItem(value_type newdatum) {
node* ccursor = head;
node* pcursor = nullptr;
if (head == NULL) {
insertAt(newdatum, ccursor);
}
else {
while (ccursor != NULL && newdatum > ccursor->getData()) {
pcursor = ccursor;
ccursor = ccursor->next();
}
appendAt(newdatum, pcursor);
}
}
void linkedList::makeList(const value_type items[], const size_t& count) {
deleteList();
if (count == 0) return;
insertAt(items[0]);
node* ccursor = head;
for (size_t i = 1; i < count; ++i) {
ccursor = appendAt(items[i], ccursor);
}
}
void linkedList::deleteList() {
node* dcursor;
while (head != nullptr) {
dcursor = head;
head = head->next();
delete dcursor;
}
head = tail = nullptr;
}
} //end of DS namespace
我认为您的以下代码语句不正确：
if (cursor == nullptr) {
tail->setPrev(new_node);
new_node->setNext(tail);
new_node->setPrev(tail->prev());
return new_node;
}
...
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(cursor);
return new_node;
请参阅下文进行更正。
情况一：当光标为nullptr时，即new_node必须插入到'last'处，因为没有找到匹配的位置中间的某个地方。这假设 'tail' 是你的最后一个元素（应该按照命名约定）：
if (cursor == nullptr){
tail->setNext(new_node);
new_node->setPrev(tail);
tail = new_node;
return new_node;
}
情况2：当光标指向中间某处时。它不是空的。 new_node 添加在 cursor.
...
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(new_node);
return new_node;