我创建了自己的双向链接列表程序(我知道有一个列表库)。我的main.cc仅具有主要功能，该功能提供菜单来选择程序的各种选项并调用正确的功能/对象。然后，我有3个不同的头文件包含类文件，其中1个是我的双链列表函数的常规文件，另一个是将常规DLL函数转换为队列函数，最后一个是将DLL函数转换为堆栈函数。
main.cc
#include <iostream>
#include "doubly-linked-list.h"
#include "DLLstack.h"
#include "DLLqueue.h"
using namespace std
int choice=0,choice2=0;
int main()
{
int choice=0,choice2=0,i=0;
DoublyLinkedList<int> lst;
DLLstack stlist;
while(1)
{
choice2=0;
//ask user
cout<<"\n1. Create Simple (Unsorted) List\n2. Create Sorted List\n";
cout<<"3. Create LIFO Queue\n4. Create FIFO Queue(Stack)\n";
cout<<"5. Exit Program\n";
cout<<"Please choose an option\n";
cin>>choice;
while(choice==1)
{
//ask user 1.a
cout<<"\n1. Enter integer for insertion at head of list\n2. Enter integer for insertion at tail of list\n";
cout<<"3. Display and Delete integer at head\n4. Display and Delete integer at tail\n";
cout<<"5. Search for integer in list and delete that node\n6. Display Contents of list from head to tail in order\n7. Exit\n";
cout<<"Please choose an option\n";
cin>>choice2;
if(choice2==1)//1.1
{cout<<"Enter integer to add to head\n";
cin>>i;
lst.addToDLLHead(i);
}
if(choice2==2)//1.2
{
cout<<"Enter integer to add to tail\n";
cin>>i;
lst.addToDLLTail(i);
}
if(choice2==3)//1.3
{ try{
i=lst.deleteFromDLLHead ();
} catch(int error_code)
{
cerr<<"Error: "<<error_code<<endl;
switch(error_code)
{cout<<"Empty List\n";
return(1);
}
}
cout<<"The deleted int was "<<i<<endl;
}
if(choice2==4)//1.4
{ try{
i=lst.deleteFromDLLTail ();
} catch(int error_code)
{
cerr<<"Error: "<<error_code<<endl;
switch(error_code)
{case 1:
cout<<"Empty List\n";
return(1);
}
}
cout<<"The deleted int was "<<i<<endl;
}
if(choice2==5)//1.5
{
cout<<"Enter Integer to search for and delete"<<endl;
cin>>i;
try{
lst.searchdelete (i);
} catch(int error_code)
{
cerr<<"Error: "<<error_code<<endl;
switch(error_code)
{cout<<"Empty List\n";
return(1);
}
}
}
if(choice2==6)
{lst.printlist ();}
if(choice2==7) choice=0;
}
while(choice==2)
{
//ask user 2.b
cout<<"\n1. Enter integer for sorted insertion(increasing order) into list\n2. Display and delete integer if present in list\n";
cout<<"3. Display contents of sorted list of integers, in increasing order\n";
cout<<"4. Exit program\n";
cout<<"Please choose an option\n";
cin>>choice2;
if(choice2==1)//2.1
{cout<<"Enter integer to add to the sorted list"<<endl;
cin>>i;
lst.addSorted (i);
}
if(choice2==2)
{
cout<<"Enter Integer to search for and delete"<<endl;
cin>>i;
try{
lst.searchdelete (i);
} catch(int error_code)
{
cerr<<"Error: "<<error_code<<endl;
switch(error_code)
{cout<<"Empty List\n";
return(1);
}
}
}
if(choice2==3)
{lst.printlist ();}
if(choice2=4)
{choice=0;}
}
while(choice==3)
{
cout<<"\n1. ENQUEUE\n2. DEQUEUE\n";
cout<<"3. Print QUEUE\n";
cout<<"4. Exit program\n";
cout<<"Please choose an option\n";
cin>>choice2;
DLLQueue.qlst;
if(choice2==1)
{
cout<<"Enter number to place in Queue"<<endl;
cin>>i;
qlst.enqueue(i);}
if(choice2=2)
{try{qlst.dequeue();
} catch(int error_code)
{
cerr<<"Error: "<<error_code<<endl;
switch(error_code)
{cout<<"Empty List\n";
return(1);
}
}
}
if(choice2=3)
{lst.printlist ();}
if(choice2=4)
{choice=0;}
}
while(choice==4)
{
cout<<"\n1. Push\n2. Pop\n";
cout<<"3. Print STACK\n";
cout<<"4. Exit program\n";
cout<<"Please choose an option\n";
cin>>choice2;
if(choice2==1)
{cout<<"Please enter value to place in stack"<<endl;
cin>>i;
stlst.push(i);
}
if(choice2==2)
{stlst.pop();}
if(choice2==3)
{lst.printlist ();}
if(choice2==4)
{choice=0;}
}
} //original while
return 0;
}
双链表
#ifndef DOUBLY_LINKED_LIST
#define DOUBLY_LINKED_LIST
#include <iostream>
using namespace std;
const int EMPTY_LIST=1;
template<class T>
class DLLNode
{
friend class DoublyLinkedList;
friend class DLLQueue;
friend class DLLstack;
public:
DLLNode(){next=prev=NULL;}
DLLNode(const T& el, DLLNode *n=NULL, DLLNode *p=NULL)
{info=el;
next=n;
prev=p;
}
T info;
DLLNode<T> *next, *prev;
protected:
//T info;
//DLLNode<T> *next, *prev;
private:
};
template<class T>
class DoublyLinkedList
{
friend class DLLQueue;
friend class DLLstack;
public:
DoublyLinkedList() {head=tail=NULL;} //good
void addToDLLTail(const T&); //good
T deleteFromDLLTail(); //good
T isDLLEmpty() {return (head==NULL);} //good
void addToDLLHead(const T&); //added
T deleteFromDLLHead(); //added
void deleteDLLNode(const T&); //added
bool isInList(const T&) const; //added
void addSorted(const T&); //added
void printlist(); //added
T searchdelete(const T&);
protected:
private:
DLLNode<T> *head, *tail;
};
template<class T>
T DoublyLinkedList<T>::deleteFromDLLTail(){
if(head!=NULL){
T el=tail->info;
if(head==tail){
delete tail;
head=tail=NULL;
}
return el;
}
else throw(EMPTY_LIST);
}
template<class T>
void DoublyLinkedList<T>::addToDLLTail(const T& el) {
if(tail!=NULL){
tail=new DLLNode<T>(el,NULL,tail);
tail->prev->next=tail;
}
else head=tail= new DLLNode<T>(el);
}
template<class T>
void DoublyLinkedList<T>::addToDLLHead (const T& el) {
head = new DLLNode<T>(el,head);
if(tail==NULL) tail=head;
}
template<class T>
T DoublyLinkedList<T>::deleteFromDLLHead (){
if(head!=NULL)
{
int el=head->info;
DLLNode<T> *tmp=head;
if(head==tail)
{head=tail=NULL;}
else{head=head->next;}
delete tmp;
return(el);
}
else throw(EMPTY_LIST);
}
template<class T>
void DoublyLinkedList<T>::deleteDLLNode(const T& el) {
if(head!=NULL){
if(head==tail&&el==head->info) {
delete head;
head=tail=NULL;
}
else if(el==head->info){
DLLNode<T> *tmp=head;
head=head->next;
head->prev=NULL;
delete tmp;
}
else {
DLLNode<T> *pred, *tmp;
for(tmp=head->next;tmp!=NULL && tmp->info!=el;tmp=tmp->next);
if(tmp!=NULL){
pred=tmp->prev;
pred->next=tmp->next;
pred->next->prev=pred;
if(tmp==tail) {tail=tail->prev;}
delete tmp;
}
}
}
else throw(EMPTY_LIST);
}
template<class T>
bool DoublyLinkedList<T>::isInList(const T& el) const {
DLLNode<T> *tmp;
for(tmp=head;tmp!=NULL&&tmp->info !=el; tmp=tmp->next);
return (tmp !=NULL);
}
template<class T>
void DoublyLinkedList<T>::addSorted(const T& i) {
DLLNode<T> *tmp, *nxt;
for(tmp=head;tmp->info<i;tmp=tmp->next);
nxt=tmp->next;
tmp->next= new DLLNode<T> (i,nxt,tmp);
next->prev=tmp->next;
delete tmp;
delete nxt;
}
template<class T>
void DoublyLinkedList<T>::printlist() {
DLLNode<T> *tmp;
if(head!=NULL){
for(tmp=head;tmp->next!=NULL;tmp=tmp->next){
cout<<tmp->info<<endl;
}
}
}
template<class T>
T DoublyLinkedList<T>::searchdelete(const T& i)
{ DLLNode<T> *tmp;
for(;tmp->info!=i&&tmp!=NULL;tmp=tmp->next){}
delete DLLNode<T> (tmp);
return(cout<<"Value Deleted from List\n");
}
#endif // DOUBLY_LINKED_LIST
DLLstack.h
#ifndef _DLLSTACK_H_
#define _DLLSTACK_H_
#include <iostream>
using namespace std;
#include "doubly-linked-list.h"
class DLLstack
{
friend class<class T> DoublyLinkedList;
friend class<class T> DLLNode;
public:
DLLstack(){};
bool isEmpty() const
{return lst.isEmpty();}
void clear()
{
while(!list.isEmpty()){
lst.deleteFromDLLHead();}
}
int pop()
{return (lst.deleteFromHead();}
void push(const int& el);
{lst.addToDLLHead (el);}
int topEl()
{
int topelement;
topelement=lst.deleteFromDLLHead ();
lst.addToDLLHead (topelement);
return(topelement);
}
protected:
private:
DoublyLinkedList stlst;
};
#endif // _DLLSTACK_H_
DLLqueue.h
#ifndef _DLLQUEUE_H_
#define _DLLQUEUE_H_
#include <iostream>
using namespace std;
#include "doubly-linked-list.h"
template<class T>
class DLLQueue
{
friend <class T> class DoublyLinkedList
friend <class T> class DLLNode
public:
DLLQueue(){};
bool isEmpty() const
{ return lst.isEmpty();}
void enqueue(const T& el)
{ lst.addToDLLTail (el);}
T dequeue()
{ return {lst.deleteFromDLLHead ();}
T firstEl()
{
T front_el;
front_el=lst.deleteFromDLLHead ();
lst.addToDLLHead (front_el);
return(front_el);
}
~DLLQueue() {clear();}
protected:
private:
DoublyLinkedList qlst;
};
#endif // _DLLQUEUE_H_
现在我得到30个错误，但是我的主要问题(我认为)是它说我的DLLqueue.h文件和DLLstack.h文件中的 friend 函数声明是
DLLqueue.h:11:9:错误:“DLLstack.h:11:14:错误:“
以及堆栈和队列类中的第一个对象“未在此范围内声明”
doubly-linked-list.h:141:2:错误:在此范围内未声明“next”
还有更多错误，但我认为这些是造成主要问题的原因，我需要先解决这些问题才能继续。
如果您想知道我在Ubuntu的Ajuta IDE中编程
最佳答案
friend <class T> class DoublyLinkedList
应该
template <class U> friend class DoublyLinkedList;
要么
friend class DoublyLinkedList<T>;
取决于哪些实例实际上需要成为 friend ；其他 friend 声明也一样。
DoublyLinkedList qlst;
应该
DoublyLinkedList<T> qlst;
因为
DoublyLinkedList是模板，而不是类型。DLLStack::push中的函数体前不应有分号:void push(const int& el);
{lst.addToDLLHead (el);}
您有一个不需要的
(，但在)中没有匹配的DLLstack::pop:{return (lst.deleteFromDLLHead();}
还有
{中不需要的DLLQueue::deque:{ return {lst.deleteFromDLLHead ();}
拼写错误多种多样(例如，声明成员
stlst并将其分别称为lst和list)-编译器错误将直接将您指向这些错误。DoublyLinkedList::isDLLEmpty需要声明为const，因此可以从其他类的const成员函数中调用它(一旦您纠正了称为isEmpty的拼写错误)。在
DoublyLinkedList::searchdelete中，delete DLLNode<T>(tmp)应该只是delete tmp。您还需要修复被删除节点两侧的节点中的指针，并返回T类型的值(大概是i)，并修复循环的行为，以便它实际上搜索正确的节点(即，它会循环进行到最后，然后删除null指针，结果它什么也不做。最后，
~DLLQueue尝试调用不存在的DoublyLinkedList::clear。您应该实现它，或者实现DoublyLinkedList的析构函数(或同时实现两者)。实际上，该列表是内存泄漏。它还应该具有复制构造函数和赋值运算符(如果您不希望类可复制，则应将其简单声明为private)。另外，您不应使用保留名称(以下划线开头，例如
_DLLQUEUE_H_)作为包含保护。您也不应该将using namespace std;放在头文件中；头文件的用户可能不希望污染全局 namespace 。