c++ 高效编程：内存与性能优化 源码 代码 实例

#include "BookTools.h" #include <stdlib.h> #include <string.h> #include <stdio.h> #include <time.h> #include <fstream> #include <iomanip.h> #define MAXELEM 50000 class EmployeeInfo { public: unsigned long salaryCode; char *name; EmployeeInfo() {}; EmployeeInfo(char *s, unsigned long id) { name = new char[strlen(s)+1]; strcpy(name, s); salaryCode = id; }; void Setdata(char *s, unsigned long id) { name = new char[strlen(s)+1]; strcpy(name, s); salaryCode = id; } void Printdata() { cout << setw(8) << salaryCode << " " << name << endl; } unsigned long GetCode() { return(salaryCode); } friend int operator==(const EmployeeInfo &r, const EmployeeInfo &s); friend int operator==(const EmployeeInfo &r, const unsigned long id); friend int operator==(const unsigned long id, const EmployeeInfo &s); friend int operator<(const EmployeeInfo &r, const EmployeeInfo &s); friend int operator<(const EmployeeInfo &r, const unsigned long id); friend int operator<(const unsigned long id, const EmployeeInfo &s); friend int operator>(const EmployeeInfo &r, const EmployeeInfo &s); friend int operator>(const EmployeeInfo &r, const unsigned long id); friend int operator>(const unsigned long id, const EmployeeInfo &s); }; int operator==(const EmployeeInfo &r, const EmployeeInfo &s) { return(r.salaryCode == s.salaryCode); } int operator==(const EmployeeInfo &r, const unsigned long id) { return(r.salaryCode == id); } int operator==(const unsigned long id, const EmployeeInfo &s) { return(id == s.salaryCode); } int operator<(const EmployeeInfo &r, const EmployeeInfo &s) { return(r.salaryCode < s.salaryCode); } int operator<(const EmployeeInfo &r, const unsigned long id) { return(r.salaryCode < id); } int operator<(const unsigned long id, const EmployeeInfo &s) { return(id < s.salaryCode); } int operator>(const EmployeeInfo &r, const EmployeeInfo &s) { return(r.salaryCode > s.salaryCode); } int operator>(const EmployeeInfo &r, const unsigned long id) { return(r.salaryCode > id); } int operator>(const unsigned long id, const EmployeeInfo &s) { return(id > s.salaryCode); } // ************Binary Tree typedef enum {RED, BLACK} Colors; template <class T> class Node { public: Node *left; Node *right; T data; Node *parent; Colors color; }; template <class T> class Tree { public: Node<T> *root; ~Tree(); Tree() { root = NULL;}; virtual Node <T> *InsertNode(T data); virtual void DeleteNode(unsigned long id) { DeleteNode(FindNode(id)); } virtual void DeleteNode(T data) { DeleteNode(FindNode(data)); } virtual void DeleteNode(Node<T> *del); T FindData(unsigned long id) { return(FindData(root, id)); } T FindData(Node<T> *current, unsigned long id); Node <T>*FindNode(unsigned long id) { return(FindNode(root, id)); } Node <T>*FindNode(Node<T> *current, unsigned long id); Node <T>*FindNode(T data) { return(FindNode(root, data));} Node <T>*FindNode(Node<T> *current, T data); void InorderWalk() { InorderWalk(root); } void InorderWalk(Node<T> *current); void PreorderWalk() { PreorderWalk(root); } void PreorderWalk(Node<T> *current); void PostorderWalk() { PostorderWalk(root); } void PostorderWalk(Node<T> *current); private: void RemoveTree(Node<T> *current); void ReInsertTree(Node<T> *current) { ReInsertTree(root, current); } void ReInsertTree(Node<T> *entrance, Node<T> *current); }; template <class T> Tree<T>::~Tree() { RemoveTree(root); } template <class T> void Tree<T>::RemoveTree(Node<T> *current) { if (current != NULL) { if(current->right != NULL) RemoveTree(current->right); if(current->left != NULL) RemoveTree(current->left); delete current; } } template <class T> void Tree<T>::ReInsertTree(Node<T> *entrance, Node<T> *current) { if (current != NULL) { if(current->right != NULL) ReInsertTree(entrance, current->right); if(current->left != NULL) ReInsertTree(entrance, current->left); InsertNode(current->data); delete current; } } template <class T> T Tree<T>::FindData(Node<T> *current, unsigned long id) { while (current != NULL) { if (*(T) current->data == id) return (current->data); current = (id < *(T) current->data) ? current->left : current->right; } return(NULL); } template <class T> Node<T> *Tree<T>::FindNode(Node<T> *current, unsigned long id) { while (current != NULL) { if (*(T) current->data == id) return (current); current = (id < *(T) current->data) ? current->left : current->right; } return(NULL); } template <class T> Node<T> *Tree<T>::FindNode(Node<T> *current, T data) { while (current != NULL) { if (*(T) current->data == *(T)data) return (current); current = (*(T)data < *(T) current->data) ? current->left : current->right; } return(NULL); } template <class T> Node <T>*Tree<T>::InsertNode(T data) { Node<T> *current = root; Node<T> *newNode = NULL; Node<T> *oldNode = NULL; while(current != NULL) { if(*(T)data == *(T)current->data) return(current); oldNode = current; if(*(T)data < *(T)current->data) current = current->left; else current = current->right; } if ((newNode = (Node<T>*)malloc (sizeof(*newNode))) == NULL) return(NULL); newNode->right = NULL; newNode->left = NULL; newNode->data = data; newNode->parent = oldNode; if(root == NULL) root = newNode; else { if(*(T)data < *(T)oldNode->data) oldNode->left = newNode; else oldNode->right = newNode; } return(newNode); } template <class T> void Tree<T>::DeleteNode(Node <T> *del) { if(del != NULL) { if (del == root) { if (root->left != NULL) { root = root->left; ReInsertTree(root, del->right); } else root = root->right; } else { if (del->parent->left == del) del->parent->left = del->left; else del->parent->right = NULL; ReInsertTree(del->parent, del->right); } if (del == root) root = NULL; delete del; } } template <class T> void Tree<T>::InorderWalk(Node<T> *current) { if(current != NULL) { InorderWalk(current->left); current->data->Printdata(); InorderWalk(current->right); } } template <class T> void Tree<T>::PreorderWalk(Node<T> *current) { if(current != NULL) { current->data->Printdata(); PreorderWalk(current->left); PreorderWalk(current->right); } } template <class T> void Tree<T>::PostorderWalk(Node<T> *current) { if(current != NULL) { PostorderWalk(current->left); PostorderWalk(current->right); current->data->Printdata(); } } //****************** RedBlackTree template <class T> class RedBlackTree : public Tree <T> { public: RedBlackTree() { LEAF = new Node