简单的单链表排序 —— 学生管理程序

////////////////////////////////////////////////////////////////////////// // ListMgr 链表管理器类的具体实现 // #include "ListMgr.h" #include <iostream> #include <assert.h> using namespace std; /************************************************************************/ /* 函数说明：构造函数 /* 函数参数：无 /* 返 回 值：无 /* 备注信息：初始化头结点 /************************************************************************/ ListMgr::ListMgr() { first = 0; } /************************************************************************/ /* 函数说明：在单链表中插入一个元素 /* 函数参数：theStudent 元素指针 /* 返 回 值：无 /* 备注信息：无 /************************************************************************/ void ListMgr::Insert(Student *theStudent) { Node *newNode,*current,*previous; Student *currentStudent; newNode = new Node(theStudent); int newKey = theStudent->GetKey(); if( !newNode ) { cout<<"\n无法创建一个结点.\n"<<endl; return; } if (first == 0) { first = newNode; } else { int firstNode = true; current = first; while(current != 0) { currentStudent = current->GetStudent(); if(newKey < currentStudent->GetKey()) break; previous = current; current = current->GetNext(); firstNode = false; } // 如果是第一次插入，则将前一个节点指向这个新的节点 if(!firstNode) previous->SetNext(newNode); else first = newNode; // 将新的节点存放在当前链表中 newNode->SetNext(current); } } /************************************************************************/ /* 函数说明：在单链表中查找一个元素 /* 函数参数：searchNum 节点的关键字，即学生编号 /* 返 回 值：成功返回该节点的指针，否则返回0 /* 备注信息：无 /************************************************************************/ Student* ListMgr::Find(int searchNum) { Student *currentStudent; Node *current; current = first; while(current != 0) { currentStudent = current->GetStudent(); if(searchNum == currentStudent->GetKey()) return currentStudent; current = current->GetNext(); } return 0; } /************************************************************************/ /* 函数说明：在单链表中删除一个元素 /* 函数参数：searchNum 节点的关键字 /* 返 回 值：成功返回true，否则返回false /* 备注信息：无 /************************************************************************/ int ListMgr::Remove(int searchNum) { Student *currentStudent; Node *current,*previous,*next; if(first == 0) // 如果当前链表为空则直接返回 return false; int firstNode = true; current = first; while(current != 0) { currentStudent = current->GetStudent(); if(searchNum == currentStudent->GetKey()) break; previous = current; current = current->GetNext(); firstNode = false; // 不是头节点 } if(current == 0) // 没有找到该节点则返回 return false; if(!firstNode) { next = current->GetNext(); // 先获取该节点的后一个节点 previous->SetNext(next); } else first = current->GetNext(); // 将后一个节点设置为当前节点 // 这里内存释放有点问题，未调试完毕 // delete current->GetStudent(); // 删除学生对象的内存空间 // delete current; // 删除节点对象的内存空间 return true; // 成功删除某节点 } /************************************************************************/ /* 函数说明：在单链表中获取头节点元素 /* 函数参数：无 /* 返 回 值：Node* 头节点元素 /* 备注信息：无 /************************************************************************/ Node* ListMgr::GetFirst() { return first; } /************************************************************************/ /* 函数说明：比较大小函数 /* 函数参数：big==true 升序 ==false 降序可用来控制排序升序降序 /* 返 回 值：bool值 是否大于或小于 /* 备注信息：无 /************************************************************************/ bool ListMgr::Compare(int Left, int Right, bool big) { return big ? Left>Right : Left<Right; } /************************************************************************/ /* 函数说明：根据学生总分进行排序 /* 函数参数：asc true升序/\ false降序 /* 返 回 值：无 /* 备注信息：找最值然后与前面的交换 重复这样的过程 完成排序 /************************************************************************/ void ListMgr::Order(bool asc /*= true*/) { for (Node *pNodei=first; pNodei!=NULL; pNodei=pNodei->GetNext()) { Node* pNoteM = pNodei; Node *pNodej = pNodei->GetNext(); for (; pNodej!=NULL; pNodej=pNodej->GetNext()) { if(Compare(pNoteM->GetStudent()->GetTotal(), pNodej->GetStudent()->GetTotal(), asc)) { pNoteM = pNodej;//记录最值 } } SwapNode(pNodei, pNoteM);//交换本节点和最值 } } /************************************************************************/ /* 函数说明：交换两个结点的位置 /* 函数参数：无 /* 返 回 值：无 /* 备注信息：无 /************************************************************************/ void ListMgr::SwapNode(Node *pLeft,Node *pRight) { assert(pLeft!=NULL && pRight!=NULL); Student* temp = pLeft->GetStudent(); pLeft->SetStudent(pRight->GetStudent()); pRight->SetStudent(temp); } // end of file ListMgr.cpp //////////////////////////////////////////////////////////////////////////