单列表插入到列表结尾 [英] Singly-list insert to end of list
本文介绍了单列表插入到列表结尾的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我试图，不使用ListIterator，定义和实现一个名为insert_back的新操作，它接受单个模板对象，并将该对象插入列表的末尾。没有改变这个操作或任何其他的意义，我需要修改一个List的表示，并改变任何必要的方法使insert_back在固定时间运行：O（1）。
$ b $
我想创建另一个名为INSERTBACK的菜单选项，它将在列表的末尾插入一个新对象
p>LIST.H
#ifndef LIST_H
#define LIST_H
#include< iostream>
#includeListNode.h
#includeListIterator.h
namespace cs20 {
template< class Object>
class List {
public：
List（）;
List（const List& rhs）;
〜List（）;
bool isEmpty（）const;
bool isIncreasing（）const;
void makeEmpty（）;
ListIterator< Object> zeroth（）const;
ListIterator< Object> first（）const;
void insert（const Object& data，
const ListIterator< Object>& iter）;
void insert（const Object& data）;
void insert_back（const Object& data）;
ListIterator< Object> findPrevious（const Object& data）const;
void remove（const Object and amp; data）;
const列表& operator =（const List& rhs）;
const List& operator<<（const List& rhs）;
private：
ListNode< Object> *头;
ListNode< Object> * 尾巴;
};
}
#endif
LIST.CPP
#ifndef LIST_CPP
#define LIST_CPP
#includeList.h
namespace cs20 {
template< class Object>
List< Object> :: List（）{
head = new ListNode< Object>
tail-> nextIsNull（）;
}
template< class Object>
List< Object> :: List（const List< Object>& rhs）{
head = new ListNode< Object>
tail-> nextIsNull（）;
* this = rhs;
}
template< class Object>
List< Object> ::〜List（）{
makeEmpty（）;
delete head;
}
template< class Object>
bool List< Object> :: isEmpty（）const {
return（head-> nextIsNull（））;
}
template< class Object>
void List< Object> :: makeEmpty（）{
while（！isEmpty（））{
remove（first（）。retrieve（））;
}
tail = NULL;
}
template< class Object>
ListIterator< Object> List< Object> :: zeroth（）const {
return（ListIterator< Object>（head））;
}
template< class Object>
ListIterator< Object> List< Object> :: first（）const {
return（ListIterator< Object>（head-> getNext（）））;
}
template< class Object>
void List< Object> :: insert（const Object& data，
const ListIterator< Object& iter）{
if（iter.isValid（））{
ListNode< ; object> * newnode = new ListNode< Object>（data，iter.current-> getNext（））;
iter.current-> setNext（newnode）;
}
}
template< class Object>
void List< Object> :: insert（const Object& data）{
ListNode< Object> * newnode = new ListNode< Object>（data，head-> getNext（）） ;
head-> setNext（newnode）;
}
template< class Object>
void List< Object> :: insert_back（const Object& data）{
ListNode< Object> * newnode = new ListNode< Object>（data，tail-> getNext（））;
if（tail！= NULL）
{
tail-> setNext（newnode）;
}
tail = newnode;
if（head-> getNext（）== NULL）{
head-> setNext（newnode）;
}
}
template< class Object>
ListIterator< Object> List< Object> :: findPrevious（const Object& data）const {
ListNode< Object> * node = head;
while（node-> getNext（）！= NULL&& node-> getNext（） - > getElement（）！= data）{
node = node-> getNext ）;
}
if（node-> getNext（）== NULL）{
node = NULL;
}
return ListIterator< Object>（node）;
}
template< class Object>
bool List< Object> :: isIncreasing（）const {
ListNode< Object> * node = head;
while（node-> getNext（）！= NULL）
{
if（node-> getNext（） - > getElement（）< = node-> getElement ））
return false;
node = node-> getNext（）;
}
return true;
}
template< class Object>
void List< Object> :: remove（const Object& data）{
ListIterator< Object> iter = findPrevious（data）;
if（iter.isValid（））{
ListNode< Object> * node = findPrevious（data）.current;
if（node-> getNext（）！= NULL）{
ListNode< Object> * oldNode = node-> getNext（）;
node-> setNext（node-> getNext（） - > getNext（））; // Skip oldNode
delete oldNode;
}
}
}
//链表的深拷贝
template< class Object>
const List< Object>& List< Object> :: operator =（const List< Object>& rhs）{
if（this！=& rhs）{
makeEmpty（）;
ListIterator< Object> rightiter = rhs.first（）;
ListIterator< Object> myiterator = zeroth（）;
while（rightiter.isValid（））{
insert（rightiter.retrieve（），myiterator）;
rightiter.advance（）;
myiterator.advance（）;
}
}
return（* this）;
}
}
#endif
实施
LISTMENU.CPP
// Menu.cpp：定义控制台应用程序的入口点。
//
#include< iostream>
#includeList.h
#includeListNode.h
#includeListIterator.h
#includeList.cpp
#include ListNode.cpp
#includeListIterator.cpp
using namespace std;
using namespace cs20;
枚举选择{MAKEEMPTY，REMOVE，ISEMPTY，FINDPREVIOUS，INSERT，QUIT，PRINT};
选择菜单（）;
void printList（const List< int>& l）;
int main（int argc，char * argv []）{
int value;
List< int>列表;
ListIterator< int> iter;
选择选择;
do {
choice = menu（）;
switch（choice）{
case MAKEEMPTY：
list.makeEmpty（）;
break;
case ISEMPTY：
if（list.isEmpty（））{
cout< list is empty< endl;
}
else {
cout<< list is not empty< endl;
}
break;
case REMOVE：
cout<< 请提供int以删除：;
cin>>值;
list.remove（value）;
break;
case INSERT：
cout<< 请提供int插入：;
cin>>值;
list.insert（value）;
break;
case FINDPREVIOUS：
cout<< 请提供int找到：;
cin>>值;
iter = list.findPrevious（value）;
if（iter.isValid（））{
cout<< previous element =<< iter.retrieve（）<< endl;
}
else {
cout<< 未找到数据元素！ << endl;
}
break;
case PRINT：
printList（list）;
break;
case QUIT：
break;
}
} while（choice！= QUIT）;
return（0）;
}
int sample（）{
cout<< 形成列表<< endl;
int one = 1，two = 2;
List< int> l1 = List< int>（）;
List< int> l2 = List< int>（）;
l1.insert（one）;
l1.insert（two）;
cout<< print l1<< endl;
printList（l1）;
cout<< l2 = l1<< endl;
l2 = l1;
cout<< print l2< endl;
printList（l2）;
cout<< l1.remove（one）< endl;
l1.remove（one）;
cout<< print l1<< endl;
printList（l1）;
cout<< print l2< endl;
printList（l2）;
cout<< findPrevious 1 in l2< endl;
ListIterator< int> iter = l2.findPrevious（one）;
if（iter.isValid（））{
cout<< --iter valid< endl;
cout<< iter.retrieve（）<< endl;
}
else {
cout<< --iter not valid< endl;
}
cout<< findPrevious 2 in l2< endl;
iter = l2.findPrevious（two）;
if（iter.isValid（））{
cout<< --iter valid< endl;
cout<< iter.retrieve（）<< endl;
}
else {
cout<< --iter not valid< endl;
}
cout<< findPrevious 1 in l1< endl;
iter = l1.findPrevious（one）;
if（iter.isValid（））{
cout<< --iter valid< endl;
cout<< iter.retrieve（）<< endl;
}
else {
cout<< --iter not valid<< endl;
}
cout<< findPrevious 2 in l1< endl;
iter = l1.findPrevious（two）;
if（iter.isValid（））{
cout<< --iter valid< endl;
cout<< iter.retrieve（）<< endl;
}
else {
cout<< --iter not valid< endl;
}
cout<< print l1<< endl;
printList（l1）;
//你可以删除任何你想要的，不管它是否存在
cout<< l1.remove（one）< endl;
l1.remove（one）;
cout<< print l1<< endl;
printList（l1）;
return（0）;
}
void printList（const List< int>& l）{
if（l.isEmpty（））
cout< 空列表<< endl;
else {
ListIterator< int> iter = l.first（）;
while（iter.isValid（））{
cout<< iter.retrieve（）<< - >;
iter.advance（）;
}
cout<< 空值;
cout<< endl;
}
}
选择菜单（）{
char choice;
选择结果;
cout<< （M）akeEmpty I（s）Empty（R）emove（I）nsert（F）indPrevious（P）rint（Q）uit：< endl;
cin>>选择;
switch（choice）{
case'M'：
case'm'：
result = MAKEEMPTY;
break;
case'S'：
case's'：
result = ISEMPTY;
break;
case'R'：
case'r'：
result = REMOVE;
break;
case'I'：
case'i'：
result = INSERT;
break;
case'F'：
case'f'：
result = FINDPREVIOUS;
break;
case'Q'：
case'q'：
result = QUIT;
break;
case'P'：
case'p'：
result = PRINT;
break;
}
return（result）;
}
EDIT ：添加了ListNode.cpp
ListNode.CPP
#ifndef LISTNODE_CPP
#define LISTNODE_CPP
#includeListNode.h
namespace cs20 {
template< class Object>
ListNode< Object> :: ListNode（const Object& theElement，
ListNode< Object> * node）{
element = theElement;
next = node;
}
template< class Object>
bool ListNode< Object> :: nextIsNull（）const {
return（next == NULL）;
}
模板< class Object>
const Object& ListNode< Object> :: getElement（）const {
return（element）;
}
template< class Object>
ListNode< Object> * ListNode< Object> :: getNext（）const {
return（next）;
}
template< class Object>
void ListNode< Object> :: setNext（ListNode< Object> * node）{
next = node;
}
}
#endif
解决方案
您当前定义的链接列表称为单链表，因为您有一个指针（下一个），并且只存储一个指向列表头的指针。将一个名为tail的额外指针添加到您的列表容器，并将其指向最后一个元素。
另一种方法是将列表转换为带有（下一个，上一个）列表的双链表，指针，然后你可以保持head-> previous指向你的列表的尾部（一个双链接，循环列表）。
第三种方式是使单向链接列表循环，但将指针存储为上一个和下一个指针的异或（请参阅： http：/ /en.wikipedia.org/wiki/XOR_linked_list ）。
以下是您需要的一些更改的示例要添加一个'tail'成员到你的列表，并使用它来创建一个insert_back操作。
你列表的实现似乎添加一个新的节点，列表。
将成员添加到您的List.h定义中，
void insert_back（const Object& data）;
ListNode< Object> * head;
ListNode< Object> * tail; //添加尾部
您的列表实现甚至在空列表上创建一个ListNode。不知道你打算这样做。无论如何，在你的构造函数中，初始化尾部（这通常是NULL，也许你想初始化到你放在列表中的浪费节点。）
code> List< Object> :: List（）{
head = new ListNode< Object>
tail = NULL; //或= head
}
您还有列表分配，除了你对你分配给的列表中的节点做了什么（你不调用makeEmpty），但是你需要在尾部做一些事情 - 但是由于你只是分配，我将设置tail = NULL，提醒你做一些事情，
List< Object> :: List（const List< Object> ; rhs）{
head = new ListNode< Object> ;;
tail = NULL; //或= head
* this = rhs; //刚刚分配的列表节点丢失了
}
尾必须清空，
void List< Object> :: makeEmpty（）{
while（！isEmpty （））{
remove（first（）。retrieve（））;
}
tail = NULL;
}
您的现有插入方法需要在列表为空时初始化尾部，一个练习，
你将需要一个insert_back方法，它只需要在新节点（如果有一个尾部）指向tail-> next，然后设置tail到新节点，
template< class Object>
void List< Object> :: insert_back（const Object& data）{
//在尾节点之后插入
ListNode< Object> * newnode = new ListNode< Object> - > getNext（））;
if（tail！= NULL）// not empty，point tail-> next at newnode
{
tail-> setNext（newnode）;
}
tail = newnode;
if（head-> getNext（）== NULL）//空，newnode是头和尾
{
head-> setNext（newnode）;
}
}
I am trying to, without using a ListIterator, define and implement a new operation called insert_back which takes a single template Object and inserts the Object at the end of the list. Without changing the meaning of this operation or any other, I need to modify the representation of a List and alter whatever methods are necessary to make insert_back run in constant time: O(1).
I am totally stumped at implementing this.
I want to make another menu option named INSERTBACK that will insert a new object at the end of the list
LIST.H
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "ListNode.h"
#include "ListIterator.h"
namespace cs20 {
template <class Object>
class List {
public:
List();
List( const List& rhs );
~List();
bool isEmpty() const;
bool isIncreasing() const;
void makeEmpty();
ListIterator<Object> zeroth() const;
ListIterator<Object> first() const;
void insert( const Object& data,
const ListIterator<Object> &iter );
void insert( const Object& data );
void insert_back( const Object& data );
ListIterator<Object> findPrevious( const Object& data ) const;
void remove( const Object& data );
const List& operator =( const List& rhs );
const List& operator <<( const List& rhs );
private:
ListNode<Object> * head;
ListNode<Object> * tail;
};
}
#endif
LIST.CPP
#ifndef LIST_CPP
#define LIST_CPP
#include "List.h"
namespace cs20 {
template <class Object>
List<Object>::List() {
head = new ListNode<Object>;
tail->nextIsNull();
}
template <class Object>
List<Object>::List( const List<Object>& rhs ) {
head = new ListNode<Object>;
tail->nextIsNull();
*this = rhs;
}
template <class Object>
List<Object>::~List() {
makeEmpty();
delete head;
}
template <class Object>
bool List<Object>::isEmpty() const {
return( head->nextIsNull() );
}
template <class Object>
void List<Object>::makeEmpty() {
while (!isEmpty()) {
remove( first().retrieve() );
}
tail = NULL;
}
template <class Object>
ListIterator<Object> List<Object>::zeroth() const {
return( ListIterator<Object>( head ) );
}
template <class Object>
ListIterator<Object> List<Object>::first() const {
return( ListIterator<Object>( head->getNext() ) );
}
template <class Object>
void List<Object>::insert( const Object& data,
const ListIterator<Object> &iter ) {
if (iter.isValid()) {
ListNode<Object>* newnode = new ListNode<Object>( data, iter.current->getNext() );
iter.current->setNext( newnode );
}
}
template <class Object>
void List<Object>::insert( const Object& data ) {
ListNode<Object>* newnode = new ListNode<Object>( data, head->getNext() );
head->setNext( newnode );
}
template <class Object>
void List<Object>::insert_back( const Object& data ) {
ListNode<Object>* newnode = new ListNode<Object>( data, tail->getNext() );
if( tail != NULL )
{
tail->setNext( newnode );
}
tail = newnode;
if( head->getNext() == NULL ) {
head->setNext(newnode);
}
}
template <class Object>
ListIterator<Object> List<Object>::findPrevious( const Object& data ) const {
ListNode<Object>* node = head;
while( node->getNext() != NULL && node->getNext()->getElement() != data ) {
node = node->getNext();
}
if (node->getNext() == NULL) {
node = NULL;
}
return ListIterator<Object>( node );
}
template <class Object>
bool List<Object>::isIncreasing() const {
ListNode<Object>* node= head;
while (node->getNext() != NULL)
{
if (node->getNext()->getElement() <= node->getElement())
return false;
node = node->getNext();
}
return true;
}
template <class Object>
void List<Object>::remove( const Object& data ) {
ListIterator<Object> iter = findPrevious( data );
if (iter.isValid()) {
ListNode<Object>* node = findPrevious( data ).current;
if (node->getNext() != NULL) {
ListNode<Object> *oldNode = node->getNext();
node->setNext( node->getNext()->getNext() ); // Skip oldNode
delete oldNode;
}
}
}
// Deep copy of linked list
template <class Object>
const List<Object>& List<Object>::operator =( const List<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
ListIterator<Object> rightiter = rhs.first( );
ListIterator<Object> myiterator = zeroth();
while( rightiter.isValid() ) {
insert( rightiter.retrieve(), myiterator );
rightiter.advance();
myiterator.advance();
}
}
return( *this );
}
}
#endif
IMPLEMENTATION LISTMENU.CPP
// Menu.cpp : Defines the entry point for the console application. //
#include <iostream>
#include "List.h"
#include "ListNode.h"
#include "ListIterator.h"
#include "List.cpp"
#include "ListNode.cpp"
#include "ListIterator.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, REMOVE, ISEMPTY, FINDPREVIOUS, INSERT, QUIT, PRINT };
CHOICE menu();
void printList( const List<int>& l );
int main(int argc, char* argv[]) {
int value;
List<int> list;
ListIterator<int> iter;
CHOICE choice;
do {
choice = menu();
switch( choice ) {
case MAKEEMPTY:
list.makeEmpty();
break;
case ISEMPTY:
if (list.isEmpty()) {
cout << "list is empty" << endl;
}
else {
cout << "list is not empty" << endl;
}
break;
case REMOVE:
cout << "Please provide int to remove: ";
cin >> value;
list.remove( value );
break;
case INSERT:
cout << "Please provide int to insert: ";
cin >> value;
list.insert( value );
break;
case FINDPREVIOUS:
cout << "Please provide int to find: ";
cin >> value;
iter = list.findPrevious( value );
if (iter.isValid()) {
cout << "previous element = " << iter.retrieve() << endl;
}
else {
cout << "data element was not found!" << endl;
}
break;
case PRINT:
printList( list );
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
int sample() {
cout << "Forming Lists" << endl;
int one = 1, two = 2;
List<int> l1 = List<int>();
List<int> l2 = List<int>();
l1.insert( one );
l1.insert( two );
cout << "print l1" << endl;
printList( l1 );
cout << "l2 = l1" << endl;
l2 = l1;
cout << "print l2" << endl;
printList( l2 );
cout << "l1.remove(one)" << endl;
l1.remove( one );
cout << "print l1" << endl;
printList( l1 );
cout << "print l2" << endl;
printList( l2 );
cout << "findPrevious 1 in l2" << endl;
ListIterator<int> iter = l2.findPrevious( one );
if (iter.isValid()) {
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else {
cout << "--iter not valid" << endl;
}
cout << "findPrevious 2 in l2" << endl;
iter = l2.findPrevious( two );
if (iter.isValid()) {
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else {
cout << "--iter not valid" << endl;
}
cout << "findPrevious 1 in l1" << endl;
iter = l1.findPrevious( one );
if (iter.isValid()) {
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else {
cout << "--iter not valid" << endl;
}
cout << "findPrevious 2 in l1" << endl;
iter = l1.findPrevious( two );
if (iter.isValid()) {
cout << "--iter valid" << endl;
cout << iter.retrieve() << endl;
}
else {
cout << "--iter not valid" << endl;
}
cout << "print l1" << endl;
printList( l1 );
// you can remove whatever you want, whether it exists or not
cout << "l1.remove(one)" << endl;
l1.remove( one );
cout << "print l1" << endl;
printList( l1 );
return( 0 );
}
void printList( const List<int>& l ) {
if (l.isEmpty())
cout << "Empty list" << endl;
else {
ListIterator<int> iter = l.first();
while (iter.isValid()) {
cout << iter.retrieve() << " -> ";
iter.advance();
}
cout << "NULL";
cout << endl;
}
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty (R)emove (I)nsert (F)indPrevious (P)rint (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'F':
case 'f':
result = FINDPREVIOUS;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
}
return( result );
}
EDIT: Added ListNode.cpp ListNode.CPP
#ifndef LISTNODE_CPP
#define LISTNODE_CPP
#include "ListNode.h"
namespace cs20 {
template <class Object>
ListNode<Object>::ListNode( const Object& theElement,
ListNode<Object> * node ) {
element = theElement;
next = node;
}
template <class Object>
bool ListNode<Object>::nextIsNull() const {
return( next == NULL );
}
template <class Object>
const Object& ListNode<Object>::getElement() const {
return( element );
}
template <class Object>
ListNode<Object>* ListNode<Object>::getNext() const {
return( next );
}
template <class Object>
void ListNode<Object>::setNext( ListNode<Object> * node ) {
next = node;
}
}
#endif
解决方案
The linked list you currently have defined is called a single-linked list, as you have a single pointer (next), and you only store a pointer to the head of the list. Add to your List container an additional pointer called tail, and point it at the last element. You will need to adjust your List methods to properly assign tail and address it.
Another approach could be to convert your list to a double linked list with (next, previous) pointers, and you could then maintain head->previous to point to the tail of your list (a double-linked, circular list).
A third way would be to make your single-linked list circular, but store pointers as XOR of the previous and next pointer (see: http://en.wikipedia.org/wiki/XOR_linked_list).
Here are examples of some changes you need to make to add a 'tail' member to your List, and use it to create an insert_back operation.
You list implementation seems to add a new node even to an empty list.
Add the member to your List.h definition,
void insert_back( const Object& data );
ListNode<Object>* head;
ListNode<Object>* tail; //add a tail
Your list implementation creates a ListNode even on an empty list. Not sure you intend to do that. Anyway, in your constructor, initialize the tail (which is usually NULL, maybe you want to init to the wasted node you place in the list).
List<Object>::List() {
head = new ListNode<Object>;
tail = NULL; //or = head
}
You also have list assignment, which is fine except that what do you do with the node(s) in the list you are assigning to (you don't call makeEmpty), but you will need to do something sane with tail here -- but since you are just assigning, I'll set tail=NULL, to remind you do do something sane,
List<Object>::List( const List<Object>& rhs ) {
head = new ListNode<Object>;
tail = NULL; //or = head
*this = rhs; //the list node you just assigned is lost here
}
When you makeEmpty, your tail will need to be emptied,
void List<Object>::makeEmpty() {
while (!isEmpty()) {
remove( first().retrieve() );
}
tail = NULL;
}
Your existing insert methods need to initialize tail when the list is empty, left as an exercise,
You will need an insert_back method, which only needs to point tail->next at the new node (if there is a tail), and then set tail to the new node,
template <class Object>
void List<Object>::insert_back( const Object& data ) {
// insert after the tail node
ListNode<Object>* newnode = new ListNode<Object>( data, tail->getNext() );
if( tail != NULL ) //not empty, point tail->next at newnode
{
tail->setNext( newnode );
}
tail = newnode;
if( head->getNext() == NULL ) //empty, newnode is head and tail
{
head->setNext(newnode);
}
}
这篇关于单列表插入到列表结尾的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
