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