/* 1：创建单向循环链表 2：遍历单向循环链表 3：单向循环链表节点插入 4：单向循环链表节点删除 5：单向循环链表倒序 6：单向循环链表排序 7：单向循环链表销毁 8：获取单链表的长度 9：单向循环链表判空 */ #include <iostream> using namespace std; typedef struct node{ int value; struct node *pNext; }List; /*创建单向循环链表*/ void Create(List* &Head,List* &End,int &NodeCount) { if(NodeCount <= 0) return ; int nodevalue_ = 0; List* node = NULL; for(int i=0;i<NodeCount;i++){ cin>>nodevalue_; node = new List; node->value = nodevalue_; node->pNext = NULL; if(Head == NULL){ Head = node; } else{ End->pNext = node; } End = node; } End->pNext = Head; } /*遍历单项循环链表*/ void Traval(List* &Head,List* &End) { if (Head == NULL || End == NULL) return ; List* ptr = Head; while(ptr != End){ cout<< ptr->value<<" "; ptr = ptr->pNext; } cout<< ptr->value<<endl; } /*获取单向链表的长度*/ void Length(List* &Head,List* &End,int &Length) { if (Head == NULL || End == NULL) { Length = 0 ; return ; } Length = 1; List* ptr = Head; while(ptr != End){ Length++; ptr = ptr->pNext; } } /*单向循环链表节点插入*/ void Insert(List* &Head,List* &End,int &InsertPos,int &InsertValue) { if ((Head == NULL || End == NULL) && InsertPos != 1) return ; int length = 0; Length(Head,End,length); List* insertnode = new List; insertnode->value = InsertValue; insertnode->pNext = NULL; if (InsertPos == 1 || (InsertPos == (++length))) { insertnode->pNext = Head; End->pNext = insertnode; if(InsertPos == 1){ Head = insertnode; } else{ End = insertnode; } return ; } else{ int insertpos = 2; List* InsertPrior = Head; List* InsertNext = InsertPrior->pNext; while(insertpos != InsertPos){ insertpos++; InsertPrior = InsertPrior->pNext; InsertNext = InsertNext->pNext; } insertnode->pNext = InsertNext; InsertPrior->pNext = insertnode; } } /*单向循环链表节点删除*/ void Del(List* &Head,List* &End,int &DelPos) { int length; Length(Head,End,length); if (Head == NULL || End == NULL || DelPos <=0 || DelPos > length) return ; List* DelPrior = End; List* DelNext = Head->pNext; if (DelPos == 1 ){ End->pNext = DelNext; delete Head; Head = DelNext; } else { DelPrior = Head; DelNext = DelPrior->pNext->pNext; int delpos = 2; List* ptr = NULL; while(delpos != DelPos){ DelPrior = DelPrior->pNext; DelNext = DelPrior->pNext->pNext; delpos++; } ptr= DelPrior->pNext; DelPrior->pNext = DelNext; if (ptr == End){ End = DelNext; } delete ptr; ptr = NULL; } } /*单向循环链表倒序*/ void Reverse(List* &Head,List* &End) { if(Head == NULL || End == NULL) return ; List* ptr = Head,*ptr_next= NULL; End->pNext = NULL; while(ptr != End){ ptr_next = ptr->pNext; ptr->pNext = End->pNext; End->pNext = ptr; ptr = ptr_next; } ptr = Head; Head = End; End = ptr; End->pNext = Head; } /*单向循环链表排序*/ void Sort(List* &Head,List* &End) { if( Head == NULL || End == NULL) return ; End->pNext = NULL; int listlength = 0; Length(Head,End,listlength); List *node = Head,*node_pNext = node->pNext; List *tmp = NULL; List *node_prior = NULL; int nflag ; for(int i=0;i<listlength;i++){ nflag = 0; node = Head; node_pNext = Head->pNext; node_prior = Head; for(int j=0;j<listlength-i-1;j++){ if(node_pNext->value < node->value){ tmp = node_pNext; node->pNext = node_pNext->pNext; node_pNext->pNext = node; if(node != Head){ node_prior->pNext = node_pNext; } if(node == Head){ Head = node_pNext; } if (node_pNext == End){ End = node; } tmp = node; node = node_pNext; node_pNext = tmp; nflag = j+1; } node_prior = node; node = node->pNext; node_pNext = node->pNext; } if (nflag == 0 ){ break; } i = listlength - nflag - 1; } End->pNext = Head; } /*单向链表销毁*/ void Destroy(List* &Head,List* &End) { if(Head == NULL || End == NULL) return ; List* ptr = Head,*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(List* &Head,List* &End) { if(Head == NULL && End == NULL) return true; else return false; } int main() { List *Head = NULL ,*End = NULL; int length = 0,nodecount = 0,insertpos = 0,insertvalue = 0,delpos = 0; /*创建单向循环链表*/ cin>>nodecount; Create(Head,End,nodecount); Traval(Head,End); Length(Head,End,length); cout<<length<<endl; /*单向循环链表插入节点*/ cin>>insertpos >> insertvalue; Insert(Head,End,insertpos,insertvalue); Traval(Head,End); Length(Head,End,length); cout<<length<<endl; /*删除单向循环链表的节点*/ cin>>delpos; Del(Head,End,delpos); Traval(Head,End); Length(Head,End,length); cout<<length<<endl; /*单向循环链表的倒序*/ Reverse(Head,End); Traval(Head,End); Length(Head,End,length); cout<<length<<endl; /*单向循环链表排序*/ Sort(Head,End); Traval(Head,End); Length(Head,End,length); cout<<length<<endl; /*单向循环链表判空*/ bool b_empty = m_is_empty(Head,End); if(b_empty == true){ cout<<"is_empty"<<endl; } else{ cout<<"is_not_empty"<<endl; } /*销毁单向链表*/ Destroy(Head,End); if(Head == NULL && End == NULL){ cout<<"is_empty"<<endl; } else{ cout<<"not_empty"<<endl; } system("pause"); return 0; }
