/* 双向循环链表 1：双向循环链表创建 2：双向循环链表长度 3：双向循环链表正向遍历 4：双向循环链表反向遍历 5：双向循环链表节点插入 6：双向循环链表节点删除 7：双向循环链表倒序 8：双向循环链表判空 9：双向循环链表排序 10：双向循环链表销毁 */
#include <iostream> using namespace std; typedef struct node{ struct node *pFront; int value; struct node *pNext; }DCList; /*创建双向循环链表*/ void Create(DCList* &Head,DCList* &End,int &nodecount ) { if(nodecount <=0) return ; DCList *node = NULL; int nodevalue = 0; for(int i=0;i<nodecount;i++){ cin>>nodevalue; node = new DCList; node->value = nodevalue; node->pFront = node; node->pNext = node; if(Head == NULL){ Head = node; } else{ node->pNext = Head; End->pNext = node; node->pNext->pFront = node; node->pFront = End; } End = node; } } /*获取双向链表的长度*/ void Length(DCList* &Head,DCList* &End,int &length) { length = 1; DCList* ptr= Head; while(ptr != End){ length++; ptr = ptr->pNext; } } /*双向链表正向遍历*/ void Traval(DCList* &Head,DCList* &End) { if(Head == NULL || End == NULL) return ; DCList *ptr = Head; while(ptr != End){ cout<<ptr->value<<" "; ptr= ptr->pNext; } cout<<End->value<<endl; } /*双线循环链表的反向遍历*/ void ReTraval(DCList* &Head,DCList* &End){ if(Head == NULL || End == NULL) return ; DCList * ptr= End; while(ptr != Head){ cout<<ptr->value<<" "; ptr=ptr->pFront; } cout<<Head->value<<endl; } /*双向循环链表节点插入*/ void Insert(DCList* &Head,DCList* &End,int &InsertPos,int InsertValue) { if((Head == NULL || End == NULL) && InsertPos != 1) return ; int length =0 ; Length(Head,End,length); if(InsertPos <=0 && InsertPos > length+1) return ; DCList *insertnode = NULL; insertnode = new DCList; insertnode->value = InsertValue; int insertpos =1; DCList* insertfront = End; DCList* insertnext = Head; while(insertpos != InsertPos){ insertfront = insertfront->pNext; insertnext = insertfront->pNext; insertpos++; } insertnode->pNext = insertnext; insertnode->pNext->pFront = insertnode; insertfront->pNext = insertnode; insertfront->pNext->pFront = insertfront; if(InsertPos == 1){ Head = insertnode; } else if(InsertPos == length+1){ End = insertnode; } } /*双向循环链表节点删除*/ void Del(DCList* &Head,DCList* &End,int &DelPos) { if(Head == NULL || End == NULL) return ; int length =0; Length(Head,End,length); if(DelPos <= 0 || DelPos > length) return ; DCList * delfront = End; DCList * delnext =Head->pNext; int delpos = 1; while(delpos != DelPos){ delfront = delfront->pNext; delnext = delnext->pNext; delpos++; } DCList *ptr = delfront->pNext; delfront->pNext = delnext; delnext->pFront = delfront; delete ptr ; ptr = NULL; if(DelPos == 1){ Head = delnext; } else if(DelPos == length){ End = delfront; } } /*双向循环链表倒序*/ void Reverse(DCList* &Head, DCList* &End) { if(Head == NULL || End == NULL) return ; DCList* Head_New = NULL; DCList* End_New = NULL; DCList *ptr = End; DCList *ptr_front = NULL; while(ptr != Head){ ptr_front = ptr->pFront ; ptr->pFront = ptr; ptr->pNext = ptr; if(Head_New == NULL){ Head_New = ptr; } else{ ptr->pNext = Head_New; End_New->pNext = ptr; ptr->pNext->pFront = ptr; ptr->pFront = End_New; } End_New = ptr; ptr = ptr_front; } Head->pNext = Head_New; Head->pFront = End_New; Head_New->pFront = Head; End_New->pNext = Head; End_New = Head; Head = Head_New; End = End_New; } /*双向循环链表排序*/ void Sort(DCList* &Head,DCList* &End) { if(Head == NULL || End == NULL) return ; DCList *node = NULL; DCList* node_next = NULL; DCList* node_front = NULL; DCList* tmp = NULL; int length = 0; Length(Head,End,length); int nflag =0; for(int i=0;i<length;i++){ nflag = 0; node = Head; node_next = node->pNext; node_front = Head; for(int j=0;j<length-i-1;j++){ if(node->value > node_next->value){ node->pNext = node_next->pNext; node->pNext->pFront = node; node_next->pNext = node; node_next->pNext->pFront = node_next; if(node != Head){ node_front->pNext = node_next; node_next->pFront = node_front; } if(node == Head){ Head = node_next; node_next->pFront = NULL; } if(node_next == End){ End = node; } tmp = node; node = node_next; node_next = tmp; nflag = j+1; } node_front = node; node = node->pNext; node_next = node->pNext; } if(nflag == 0){ break; } i = length-nflag-1; } } /*双向链表销毁*/ void Destroy(DCList* &Head,DCList* &End){ if(Head == NULL || End == NULL) return ; DCList * ptr = Head; DCList* ptr_next = NULL; while(ptr != End){ ptr_next = ptr->pNext; delete ptr ; ptr = NULL; ptr = ptr_next; } delete End ; End = NULL; Head = NULL; } /*双向链表判空*/ bool m_is_empty(DCList* &Head,DCList* &End) { if(Head == NULL || End == NULL) return true; else return false; } int main(){ int length,nodecount,insertpos,insertvalue,delpos; DCList *Head = NULL ,*End = NULL; /*创建双循环链表*/ cin>> nodecount; Create(Head,End,nodecount); Traval(Head,End); ReTraval(Head,End); Length(Head,End,length); cout<<length<<endl; //cout<<End->pNext->value<<" "<<Head->pFront->value<<endl; /*双向循环链表节点插入*/ cin>> insertpos >> insertvalue; Insert(Head,End,insertpos,insertvalue); Traval(Head,End); ReTraval(Head,End); Length(Head,End,length); cout<<length<<endl; /*双向循环链表节点删除*/ cin>> delpos ; Del(Head,End,delpos); Traval(Head,End); ReTraval(Head,End); Length(Head,End,length); cout<<length<<endl; /*双向链表倒序*/ Reverse(Head,End); Traval(Head,End); ReTraval(Head,End); Length(Head,End,length); cout<<length<<endl; /*双向循环链表排序*/ Sort(Head,End); Traval(Head,End); ReTraval(Head,End); Length(Head,End,length); cout<<length<<endl; /*双向循环链表判空*/ bool m_empty = m_is_empty(Head,End); if(m_empty ){ cout<<"is_empty"<<endl; } else{ cout<<"is_not_empty"<<endl; } Destroy(Head,End); m_empty = m_is_empty(Head,End); if(m_empty ){ cout<<"is_empty"<<endl; } else{ cout<<"is_not_empty"<<endl; } system("pause"); return 0; }
