版权声明：您好，转载请留下本人博客的地址，谢谢 https://blog.csdn.net/hongbochen1223/article/details/44682285
不多说直接上代码。
注意：其中的Exception类请参考我的博客《使用C++实现的单向链表》
#ifndef CIRCULARCHAIN_H
#define CIRCULARCHAIN_H
#include "Exception.h"
#include
using namespace std;
template
class Chain;
template
class ChainNode{
friend class Chain;
private:
T data;
ChainNode* next;
};
template
class Chain{
public:
Chain(){
head = new ChainNode();
head->data = NULL;
head->next = head;
}
~Chain();
int Length();
bool isEmpty(){return head->next == head;}
bool Find(int k,T& x) const;
int Search(const T& x);
Chain& Delete(int k,T& x);
Chain& Insert(int k,const T& x);
void print();
private:
ChainNode* head;
};
template
Chain::~Chain()
{
if(head->next == head)
return;
ChainNode* current = head->next;
while(current != head){
head->next = current->next;
delete current;
current = head->next;
}
}
template
int Chain::Length()
{
int index = 0;
ChainNode *current = head;
while(current->next != head){
index++;
current = current->next;
}
return index;
}
template
bool Chain::Find(int k, T &x) const
{
if(k < 1)
throw OutOfBounds();
if(head->next == head)
throw OutOfBounds();
ChainNode* current = head->next;
for(int i = 1;i < k && current != head; i++){
current = current->next;
}
if(current == head)
return false;
x = current->data;
return true;
}
template
int Chain::Search(const T &x)
{
if(head->next == head)
return -1;
ChainNode* current = head->next;
int index = 1;
while(current->next != head && current->data != x){
current = current->next;
index++;
}
if(current == head)
return -1;
return index;
}
template
Chain& Chain::Delete(int k, T &x)
{
if(k < 1 || head->next == head)
throw OutOfBounds();
ChainNode* p = head->next;
ChainNode* q = head;
for(int i = 1;i < k && p != head; i++){
q = p;
p = p->next;
}
if(p == head)
throw OutOfBounds();
q->next = p->next;
x = p->data;
delete p;
return *this;
}
template
Chain& Chain::Insert(int k, const T &x)
{
if(k < 0)
throw OutOfBounds();
if(k > 0 && head->next == head)
throw OutOfBounds();
ChainNode* temp = new ChainNode();
temp->data = x;
ChainNode* p = head;
int i;
for(i = 0;i < k && p->next != head;i++){
p = p->next;
}
if(i < k-1)
throw OutOfBounds();
if(k == 0){
temp->next = head->next;
head->next = temp;
}else{
temp->next = p->next;
p->next = temp;
}
return *this;
}
template
void Chain::print()
{
if(head->next == head)
return;
ChainNode* current = head->next;
while(current != head){
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
#endif // CIRCULARCHAIN_H
AI 代码解读
