双链表基本操作

1.在头接点插入指定的值

template<class T>void InsertD(dnode<T>* &front,const T& value){ dnode<T>* prev = front->prev, *curr = front;

 dnode<T>* newNode = new dnode<T>(value);

 newNode->prev = prev; newNode->next = curr;

 prev->next = newNode; curr->prev = newNode;} 

 

2.显示所有接点数值

template<class T>void ShowD(dnode<T>* &front){ dnode<T>*p = front->next; while(p != front)   {     cout<<p->value <<"/n";     p = p->next;    }}

3. 删除接点

template<class T>void DeleteD(dnode<T>* &lhs){ dnode<T>*p = lhs->next;

 while(p != lhs) {  dnode<T>* front = p;  p = p->next;  delete front; }}

4。删除指定数据

//delete special elementtemplate<class T>void DeleteSpeValue(dnode<T>* &lhs,const T& value){ dnode<T>*p =lhs->next; dnode<T>*front =lhs;

 bool bfind = false;     while(p != lhs && !bfind) {        if(p->value == value)  {   front->next = p->next;   bfind = true;   delete p;  }  else  {   front = p;   p = p->next;  } }}

5.删除指定接点

template<class T>void DeleteNode(dnode<T>* &lhs){ if (lhs == lhs->prev)  throw;

 dnode<T>*prev = lhs->prev; dnode<T>*pNext = lhs->next; prev->next = pNext->next;

 delete lhs;

}

 

约瑟夫算法

void jose(int n,int m){ int i = 0,j = 0; dnode<int>*front = new dnode<int>(),*curr;

 //insert value to front for ( ; i < n; ++i) {  InsertD<int>(front,i); }

 //point to first element curr = front->next;

 for (i = 0; i < n; ++i) {  for (j = 0; j <m -1; ++j)  {   curr = curr->next;

   if (front == curr)    curr = curr->next;  }

  curr = curr->next;

  cout<<"delete value is "<<front->value <<"/n";  DeleteNode(curr->prev);

  if (curr == front)   curr = curr->next; } cout<<"last win value is"<<front->value;

 delete front; delete curr;}