这是数据结构的实验题,谁能帮我解一下,感激不尽哦
发布网友
发布时间：2022-05-13 08:27
共2个回答
热心网友
时间：2023-08-14 16:27
/*
作者：
学号：
题目：P50 2-3
时间：2010.3.24
说明：仅不带头结点的双循环链表类。提供一个迭代器类。
可以通过迭代器访问它指向的数据元素，迭代器可以向前/向后移动，可以被赋值，
可以判相等，可以删除迭代器指向的数据此元素。
思路：不带头结点需要特殊判断链表为空的情况，删除时要格外小心。
其他：注意迭代器不需要析构函数，它不申请额外空间
*/
#include <iostream>
#include <string>
using namespace std;
//线性表抽象类
template <class T>
class List{
public:
virtual ~List(){};
virtual void clear() = 0;
virtual int length() const = 0;
virtual void insert( int i, const T &x ) = 0;
virtual void remove( int i ) = 0;
virtual int search( const T& ) const = 0;
virtual T visit( int i ) const = 0;
virtual void traverse() const = 0;
};
class OutOfBound{
public:
OutOfBound(){
cout << "访问超出范围！" << endl;
system("pause");
}
};
class EraseError{
public:
EraseError(){
cout << "删除了不存在的结点，删除失败！" << endl;
system("pause");
};
};
class Exception{};
// 双链表类
template <class T>
class Linklist: public List<T>
{
private:
struct Node
{
T data;
Node *next, *prev;
Node( const T &x, Node *p = NULL, Node *n = NULL) { data = x; prev = p; next = n; }
Node(): next(NULL), prev(NULL){}
~Node(){}
};
public:
//迭代器类
class Iterator
{
friend bool operator == ( Iterator a, Iterator b ) {
return ( a.it == b.it ) ? true : false;
}
private:
Node *it;
public:
T visit(){ if ( it == NULL ) throw OutOfBound(); return it->data; }
//赋值迭代器
Iterator & operator = ( Iterator x ){
it = x.it;
return *this;
}
//自增、自减迭代器
Iterator & operator ++(){
if ( it == NULL || it->next == NULL ) throw OutOfBound();
it = it->next;
return *this;
}
Iterator operator ++ (int) {
if ( it == NULL || it->next == NULL ) throw OutOfBound();
Iterator v;
v.it = it;
it = it->next;
return v;
}
Iterator & operator --() {
if( it == NULL || it->next == NULL ) throw OutOfBound();
it = it->prev;
return *this;
}
Iterator operator --(int) {
if ( it == NULL || it->next == NULL ) throw OutOfBound();
Iterator v;
v.it = it;
it = it->prev;
return v;
}
Iterator(){ it = NULL; }
~Iterator() {}
friend class Linklist;
};
private:
Node *head, *tail;
int l;
//移动迭代器到指定结点
Node* move( int i ) const {
Node *p = head;
if ( i < 0 || i > l ) throw OutOfBound();
while (i--) p = p->next;
return p;
}
public:
Linklist();
~Linklist(){ clear(); delete head; delete tail; }
void clear();
int length() const { return l; }
int search( const T &x ) const;
void insert( int i, const T &x );
void remove( int i );
void traverse() const;
T visit( int i ) const;
void erase( Iterator v ){
//删除迭代器指定的结点
try{
v.it->prev->next = v.it->next;
v.it->next->prev = v.it->prev;
if ( v.it == head && l != 0 ) head = head->next;
delete v.it;
--l;
if ( l == 0 ){ head = NULL; tail = NULL; }
} catch ( Exception() ) { throw( EraseError()); };
}
//*
Iterator begin() const { Iterator v; v.it = head; return v; }
Iterator end() const { Iterator v; v.it = tail; return v; }
};
template <class T>
Linklist<T>::Linklist() {
head = NULL; tail = NULL; l = 0;
}
//清空链表
template <class T>
void Linklist<T>::clear() {
Node *p = head, *q;
for ( int i = 0; i < l; ++i ) {
q = p->next;
delete p;
p = q;
}
head = NULL; tail = NULL;
l = 0;
}
//插入链表
template <class T>
void Linklist<T>::insert( int i, const T &x ) {
Node *pos, *tmp;
if ( l == 0 ) {
head = new Node( x, NULL, NULL);
head->prev = head;
head->next = head;
tail = head;
} else {
pos = move(i-1);
tmp = new Node( x, pos, pos->next );
pos->next->prev = tmp;
pos->next = tmp;
if ( i == l ) tail = tmp;
}
++l;
}
//移除链表指定结点
template <class T>
void Linklist<T>::remove( int i )
{
try{
Node *pos;
pos = move(i);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
if ( i == 0 && l != 0 ) head = head->next;
delete pos;
--l;
if ( l == 0 ){ head = NULL; tail = NULL; }
} catch ( Exception() ) { throw( EraseError()); };
}
//搜寻指定结点
template <class T>
int Linklist<T>::search( const T &x ) const
{
Node *p = head;
int i = 0;
while ( i != l && p->data != x ) { p = p->next; ++i; }
if ( p->data == x ) return i; else return -1;
}
//访问结点
template <class T>
T Linklist<T>::visit( int i ) const
{
Node *p = move(i);
return p->data;
}
//遍历
template <class T>
void Linklist<T>::traverse() const
{
Node *p = head;
for ( int i = 0; i < l; ++i ){
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main(){
int i, n, x;
Linklist<int> a;
Linklist<int>::Iterator v1, v2;
//cin >> n;
cout << "这是一个自动范例，插入 1 2 3 4 5 " << endl;
n = 5;
for ( int i = 0; i != n; ++i ){
x = i + 1;
//cin >> x;
a.insert(i, x);
}
a.traverse();
cout << a.visit(3) << endl;
cout << a.length() << endl;
a.remove(3);
cout << a.search(x) << endl;
cout << a.search(0) << endl;
cout << a.visit(3) << endl;
a.traverse();
v1 = a.begin(); v2 = a.begin();
cout << "v1 == v2 " << (v1 == v2) << endl;
v1 = a.begin(); v2 = a.end();
cout << "v1 == v2 " << (v1 == v2) << endl;
for ( v1 = a.begin(); !(v1 == a.end()); ++v1 ){
cout << v1.visit() << endl;
a.erase(v1);
a.traverse();
}
system("pause");
return 0;
}
热心网友
时间：2023-08-14 16:27
