模板类链表
本次作业要求补写课本样例的链表模板
node.h (节点类模板)
#ifndef __NODE_H_
#define __NODE_H_
template<class tt>
class node
{
private :
node<tt> * next; //pointer to next
public :
tt data;// data space
node(const tt& data, node<tt> *next);
void insertAfter(node<tt> *p);//insert the same node after this node
node<tt> * deleteAfter();//delete the node after this node,return the address
node<tt> * nextNode(); //get the address after this node
};
template <class tt>
node<tt>::node(const tt& data, node<tt> * next):data(data), next(next){}
template <class tt>
void node<tt>::insertAfter(node<tt> *p)
{
p->next = next;
next = p;
}
template <class tt>
node<tt> * node<tt>::deleteAfter()
{
node<tt> * tempPtr = next;
if(next == 0)
return 0;
next = tempPtr->next;
return tempPtr;
}
template <class tt>
node<tt> * node<tt>::nextNode()
{
return next;
}
#endiflink.h (链表类模板)
#ifndef _LINK_H_
#define _LINK_H_
#include <bits/stdc++.h>
#include "node.h"
template <class tt>
class link
{
private:
node<tt> *front, *rear;//head and the end of the list
node<tt> *prePtr, *currPtr;//record the current pointer
int size, position;//the num of the element and record the list
node<tt> *newNode(const tt &item, node<tt> *preNext);
//create new node
void freeNode(node<tt> *p);//free node
void copy(const link<tt> &l);
//copy the list L to the current list
public:
link();
link(const link<tt> &l);
~link();
link<tt> &operator=(const link<tt> &l);
int getSize() const { return size; }
bool isEmpty() const { return size == 0; }
void reset(int pos);
//reset the pointer to special position
void next();
bool endOfList() const /*{ return position == size; }*/
{
// std::cout << "the last data: " << data() << std::endl;
return position == size;
}
//judge if the pointer move the end of the list
bool judgeEnd() const { return position == size - 1; }
//judge if the pointer move the end of the list
/*this is different from the former, this function is used to judge if the
current data is the last data, the former function is to judge if pointer
move the rear position*/
int currentPostion() const { return position; }
//pointer return to current position
void insertFront(tt &item);
//insert at the head of the list
void insertRear(tt &item);
//insert at the end of the list
void insertAt(tt &item);
//insert before the current node
void insertAfter(tt &item);
//insert after the current node
tt deleteFront();//delete head node
void deleteCurrent();//delete current node
tt &data() { return currPtr->data; }
//return current data of the member
const tt &data() const { return currPtr->data; }
//return current data of the member (const)
void clear();
//clear the list,free all the memory space
};
template <class tt>
void link<tt>::freeNode(node<tt> *p)
{
delete p;
}
template <class tt>
void link<tt>::copy(const link<tt> &l)
{
front = l.front;
rear = l.rear;
currPtr = l.currPtr;
prePtr = l.prePtr;
size = l.size;
position = l.position;
}
template <class tt>
link<tt>::link()
{
front = NULL;
rear = NULL;
currPtr = NULL;
prePtr = NULL;
size = 0;
position = 0;
}
template <class tt>
link<tt>::link(const link<tt> &l)
{
copy(l);
}
template <class tt>
link<tt>::~link()
{
clear();
delete prePtr;
delete currPtr;
}
template <class tt>
link<tt> &link<tt>::operator=(const link<tt> &l)
{
copy(l);
}
template <class tt>
void link<tt>::reset(int pos)
{
if (pos >= 0 && pos <= size)
{
position = 0;
currPtr = front;
prePtr = NULL;
while (pos--)
next();
}
else
{
position = pos;
currPtr = prePtr = NULL;
}
}
template <class tt>
void link<tt>::next()
{
++position;
prePtr = currPtr;
if (currPtr != NULL)
currPtr = currPtr->nextNode();
}
template <class tt>
node<tt> *link<tt>::newNode(const tt &item, node<tt> *preNext)
{
node<tt> *p = new node<tt>(item, preNext);
assert(p != NULL);
return p;
}
template <class tt>
void link<tt>::insertFront(tt &item)
{
front = newNode(item, front);
if (isEmpty())
rear = front;
++size;
reset(++position);
}
template <class tt>
void link<tt>::insertRear(tt &item)
{
node<tt> *p = newNode(item,currPtr);
if (isEmpty())
front = rear = p;
else
{
rear->insertAfter(p);
rear = p;
}
++size;
reset(position);
}
template <class tt>
void link<tt>::insertAt(tt &item)
{
if (currPtr != NULL)
{
node<tt> *p = newNode(item, currPtr);
if (prePtr != NULL)
prePtr->insertAfter(p);
else
front = rear = p;
++size;
reset(++position);
}
}
template<class tt>
void link<tt>::insertAfter(tt&item)
{
if(currPtr != NULL)
{
node<tt> *p = newNode(item, currPtr->nextNode());
currPtr->insertAfter(p);
++size;
reset(position);
}
}
template<class tt>
tt link<tt>::deleteFront()
{
assert(!isEmpty());
node<tt> *p = front;
front = front->nextNode();
if(--size == 0)
front = rear = NULL;
reset(--position);
tt item = p->data;
freeNode(p);
return item;
}
template<class tt>
void link<tt>::deleteCurrent()
{
node<tt> *tempPtr = currPtr;
prePtr->deleteAfter();
delete currPtr;
currPtr = prePtr;
size--;
/*there may be error in here, I forgot to link the currPtr with the
prePtr, this lead to the data after this node can't be showed*/
}
template<class tt>
void link<tt>::clear()
{
while(!isEmpty())
deleteFront();
}
#endifmain.cpp(主函数)
// #include<bits/stdc++.h>
#include "link.h"
using namespace std;
int main()
{
link<int> list;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
list.insertRear(x);
}
cout << "list:";
list.reset(0);
while (!list.endOfList())
{
cout << list.data() << ' ';
list.next();
}
cout << endl;
//search
int temp;
list.reset(0);
cout << "enter the data that you wanna search: ";
cin >> temp;
while (!list.endOfList())
{
if (list.data() == temp)
{
cout << "the result: " << list.data() << endl;
break;
}
else
{
if (list.judgeEnd())
{
cout << "not found\n";
break;
}
list.next();
}
}
//delete
list.reset(0);
cout << "enter the data that you wanna remove: ";
cin >> temp;
while (!list.endOfList())
{
if (list.data() == temp)
{
list.deleteCurrent();
break;
}
else
{
if(list.judgeEnd())
{
cout << "not found\n";
break;
}
list.next();
}
}
//output the linklist
cout << "list: ";
list.reset(0);
while (!list.endOfList())
{
cout << list.data() << ' ';
list.next();
}
cout << endl;
}