/* 链表： 1：链表的创建 2：链表的遍历 3：链表的元素个数的计算 4：链表的判空 5：链表的插入 6：链表的节点的删除 7：链表的清空 8：链表的倒序 9：链表的排序 */ #include <iostream> using namespace std;
typedef struct node{ int value; struct node *pNext; }List;
/*创建链表*/ void New_list(List* &Head,List* &End,int &NodeCount) { if (NodeCount <=0) return ; int NodeValue; for(int i=0 ;i< NodeCount;i++){ List *InsertNode = new List; cin>>NodeValue; InsertNode->value = NodeValue; InsertNode->pNext = NULL; if(Head == NULL){ Head = InsertNode; } else{ End->pNext = InsertNode; } End = InsertNode; } } /*遍历链表*/ void Traval_List(List* &Head,List* &End) { if(Head == NULL || End == NULL) return ; List* ptr = Head; while(ptr != End->pNext){ cout<<ptr->value<<" "; ptr = ptr->pNext; } cout<<endl; } /*获取链表的长度*/ void List_Length(List* &Head, List* &End,int &List_Count) { List_Count = 0; if(Head == NULL || End == NULL ) List_Count = 0; return ; List* ptr = Head; while(ptr != End->pNext){ List_Count++; ptr = ptr->pNext; } } /*链表判空*/ bool Is_Empty(List* &Head,List* &End){ if (Head == NULL || End == NULL) return true; return true; } /*链表的插入*/ void Insert_Node(List* &Head,List* &End,int &InsertPos,int &InsertValue) { if(Head == NULL || End == NULL || InsertPos <= 0 ) return ; int ListLength = 0; List_Length(Head,End,ListLength); if(InsertPos > ++ListLength) return ; List *insertnode = new List; insertnode->value = InsertValue; if(InsertPos == 1){ insertnode->pNext= Head; Head = insertnode; return ; } int pos = 1; List *ptr = Head; List *ptr_next = ptr->pNext; while(ptr_next != End->pNext){ pos++; if(pos == InsertPos) break; ptr = ptr->pNext; ptr_next = ptr->pNext; } if(InsertPos == pos){ insertnode->pNext = ptr_next; ptr->pNext = insertnode; } else{ End->pNext = insertnode; End = insertnode; } } /*删除链表的节点*/ void Del_Node(List* &Head,List* &End,int &DelPos) { if(Head == NULL || End == NULL || DelPos <= 0 ) return ; int ListLength = 0; List_Length(Head,End,ListLength); if(DelPos >= ++ListLength) return ; List *ptr = Head; if(DelPos == 1){ Head = Head->pNext; delete ptr; ptr = NULL; return ; } int pos = 1; List *ptr_next = ptr->pNext; while(ptr_next != End->pNext){ pos++; if(pos == DelPos) break; ptr = ptr->pNext; ptr_next = ptr->pNext; } ptr->pNext = ptr_next->pNext; if(ptr->pNext == NULL){ End = ptr; } delete ptr_next; ptr_next = NULL; } /*销毁链表*/ void Destroy(List* &Head,List* &End) { if (Head == NULL || End == NULL) return ; List *ptr = Head; List *ptr_next = ptr->pNext; while(ptr != End){ delete ptr ; ptr = ptr_next; ptr_next = ptr->pNext; } delete ptr ; ptr = NULL; ptr_next = NULL; Head = NULL; End = NULL; } /*单向链表倒序*/ void ReList(List* &Head ,List* &End) { if (Head == NULL || End == NULL) return ; List* ptr = Head; List* ptr_next ; while(ptr != End){ ptr_next = ptr->pNext; ptr->pNext = End->pNext; End->pNext = ptr; ptr = ptr_next; } ptr = Head; Head = End; End = ptr; } /*单向链表排序*/ void Sort(List* &Head, List* &End) { if(Head == NULL || End == NULL) return ; int listlength = 0; List_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; } }
int main() { List *Head = NULL ,*End = NULL; int NodeCount = 0,listlength = 0,insertpos =0 ,insertvalue=0,delpos =0; bool is_empty = false; /*创建链表*/ cin>>NodeCount; New_list(Head,End,NodeCount); Traval_List(Head,End); List_Length(Head,End,listlength); cout<<listlength<<endl; /*链表排序*/ Sort(Head,End); Traval_List(Head,End); List_Length(Head,End,listlength); cout<<listlength<<endl; /*链表插入节点*/ cin>>insertpos>>insertvalue; Insert_Node(Head,End,insertpos,insertvalue); Traval_List(Head,End); List_Length(Head,End,listlength); cout<<listlength<<endl; /*删除节点*/ cin>>delpos; Del_Node(Head,End,delpos); Traval_List(Head,End); List_Length(Head,End,listlength); cout<<listlength<<endl; /*链表倒序*/ ReList(Head,End); Traval_List(Head,End); List_Length(Head,End,listlength); cout<<listlength<<endl; /*销毁链表*/ Destroy(Head,End); List_Length(Head,End,listlength); cout<<listlength<<endl; /*链表判空*/ is_empty = Is_Empty(Head,End); if(is_empty = true){ cout<<"is_empty"<<endl; } else{ cout<<"is_not_enpty"<<endl; } system("pause"); return 0; }
