带头结点的双循环链表- C/C++ - 软晨网（RuanChen.com）

struct DouCirListNode{
int data;
DouCirListNode *prior, *next;

public:
DouCirListNode():prior(NULL),next(NULL){}
DouCirListNode(int elem, DouCirListNode *first=NULL,DouCirListNode *back=NULL):data(elem),prior(first),next(back){}
~DouCirListNode(){prior=NULL; next=NULL;}
};

class DouCirList{
private:
DouCirListNode *first;
public:
DouCirList():first(new DouCirListNode()){
  first->prior=first;
  first->next=first;
}
~DouCirList(){
  MakeEmpty();
  delete first;
}
bool MakeEmpty();
int ListLength();
bool IsEmpty();
DouCirListNode* Find(int location);
DouCirListNode* FindData(int elem);
    bool Insert(int location, int elem);
void Remove(int location);
bool RemoveAll(int elem);
int GetData(int location);
void ShowList();
};

bool DouCirList::MakeEmpty(){
DouCirListNode *ptem=first->next, *pdel;
while(ptem!=first){
  pdel=ptem;
  ptem=pdel->next;
  delete pdel;
}
first->next=first;
first->prior=first;
return 1;
}

bool DouCirList::IsEmpty(){
return first->next==first;
}

int DouCirList::ListLength(){
DouCirListNode *ptem=first;
int count=0;
while(ptem->next!=first){
ptem=ptem->next;
count++;
}
return count;
}

int DouCirList::GetData(int location){
if(location<0){
  cout<<"sorry! the location must be over zero!"<<endl;
}
DouCirListNode *ptem=first;
int i=0;
while(ptem->next!=first&&i<location){
  i++;
  ptem=ptem->next;
}
if(ptem==first)
  cout<<"sorry! can't get the data of the location!"<<endl;
return ptem->data;
}

DouCirListNode* DouCirList::Find(int location){
if(location<0){
  cout<<"sorry! can't find the node of the location!"<<endl;
  return NULL;
}
DouCirListNode *ptem=first->next;
int i=0;
while(ptem!=first&&i<location){
  i++;
  ptem=ptem->next;
}
if(ptem==first){
  cout<<"sorry! can't find the node of the location!"<<endl;
  return NULL;
}
return ptem;
}

DouCirListNode* DouCirList::FindData(int elem){
DouCirListNode *ptem=first->next;
while(ptem->data!=elem){
  if(ptem==first){
   cout<<"sorry! can't find the elem!"<<endl;
   return NULL;
   break;
  }
   ptem=ptem->next;
}
return ptem;
}

bool DouCirList::Insert(int location, int elem){
if(location<0){
  cout<<"sorry! the location must be over 0!"<<endl;
  return 0;
}
DouCirListNode *ptem=first;
int i=0;
while(ptem->next!=first&&i<location){
  ptem=ptem->next;
  if(ptem==first){
   cout<<"sorry! can't find the correct location to insert!"<<endl;
   return 0;
   break;
  }
}
DouCirListNode *newnode=new DouCirListNode(elem);
newnode->next=ptem->next;
ptem->next->prior=newnode;
    newnode->prior=ptem;
ptem->next=newnode;
return 1;
}

void DouCirList::Remove(int location){
if(location<0){
  cout<<"The n is out of boundary"<<endl;
  exit(1);
}
DouCirListNode *pmove=first,*pdel;
for(int i=0;i<location;i++){   //find the position for delete
  pmove=pmove->next;
  if(pmove==first){
   cout<<"The n is out of boundary"<<endl;
   exit(1);
  }
}
pdel=pmove;
pmove->prior->next=pdel->next;
pmove->next->prior=pdel->prior;
delete pdel;

/*if(location<0){
  cout<<"can't remove a node that not exist!"<<endl;
  return 0;
}
DouCirListNode *ptem=first, *pdel;
for(int i=0;i<location;i++){
  ptem=ptem->next;
  if(ptem==first){
   cout<<"can't remove!"<<endl;
   return 0;
  }
}
pdel=ptem;
ptem->prior->next = pdel->next;
ptem->next->prior = pdel->prior;
delete pdel;
return 1;*/
}

bool DouCirList::RemoveAll(int elem){
DouCirListNode *ptem = first->next, *pdel;
while(ptem->next!=first){
  if(ptem->data==elem){
   pdel=ptem;
   ptem->prior->next=ptem->next;
   ptem->next->prior=ptem->prior;
   delete pdel;
  }
  ptem=ptem->next;
}
return 1;
}

void DouCirList::ShowList(){
DouCirListNode *ptem=first;
cout<<"first-->";
while(ptem->next!=first){
  ptem=ptem->next;
  cout<<"-->";
  cout<<ptem->data;
}
cout<<"-->over"<<endl;
}

int main(){
return 0;

}

C/C++ 中的带头结点的双循环链表

评论 (0) All

C/C++ 中的 带头结点的双循环链表

评论 (0) All

C/C++ 中的带头结点的双循环链表