单链表、堆排序、模版、操作符重载综合练习

   最近在复习C语言，做一些练习，看一些笔试题，顺便学点别人的思想。更重要的是实践下C++，之前也看了书，所以理解下，不会了再回头学习。

  看了下百度的笔试题，有个关于单链表（100万个结点），需要找出属于同一个组的Top10，主要就是排序然后定义一个node_t top[10] 去找到这10个结点就OK了。其中要求不用太多空间又要高效，所以就用堆排序，堆排序不是很熟练，还是理解的，SO拿来主义---虽然不太好！

  顺带练习了下模版，其实在其中模版不应该使用的，因为结构体定义没有通用性，just为了练习下，因此就练习吧。当然还有操作符的重载，学习是永无止尽的。如果自己想得到一个更高的发展，基础应该很重要，我的基础不是很好，能做出来东西，但是质量不会，这点需要像很多高手学习才好。不说了，好好努力吧！

/*
file:     node.h
author: hl
date:   2012-08-07
*/
#ifndef NODE_H
#define NODE_H

typedef struct node_t{
     int value;                    /* 节点排序字段 */
     int group;                    /* 组号: 0,1,2,3,4,5,6,7,8,9 */
     struct node_t *pnext;   /* 下个节点的指针 */
}node_t;
/*Here 我想将成员变量改为template，这样一切变化尽在掌握之中*/
template <typename T, typename W>
struct node_b{
     T value;
     W group;
     struct node_b *next;
};

//没用~
class cmp{
public:
     cmp(){}
     cmp(int& a, int& b) //适合没返回值的operator函数，调用的时候直接new cmp(a, b)就可以完成排序之类的操作；
     {
          swap(a, b);
     }
public:
     inline bool operator () (int a, int b)     //比较函数()重载
     {
          return a > b;
     }
     void swap (int& a, int& b)
     {
               a = a ^ b;
               b = a ^ b;
               a = b ^ a;
     }
};

//重载swap
namespace BAIDU
{
     template <typename T>
     class swap_p{
     public:
          void operator () (T& a, T& b)
          {
               T temp;
               temp = a;
               a = b;
               b = temp;
          }
     };
};

template <typename T>
class NodeOperate{
public:
     NodeOperate()
     {
          //you can add initial code here
     }
public:
     void nodeInitial(T *head);
     void nodeInsert(T *head, T& node);
     void nodeCreate(T *head, T arr[], int nodeNumber);
     //调整堆,每次选取一个较大的子节点替换父节点,然后继续处理该较大的子节点！
     inline void heapadjust(T top[], int root, int len)
     {
          int i = root;
          while(2 * i + 1 < len)
          {
               //获取较大的儿子节点,左孩子(2 * i + 1),右孩子(2 * i + 2)
               int child = 2 * i + 1;
               if(child + 1 < len && top[child].value < top[child + 1].value)
               {
                    child = child + 1; //如果右孩子大，令child等于右孩子的索引
               }

               if(top[child].value > top[i].value)
               {
                    this->swap(top[i], top[child]); //子节点的值大于父节点, 交换父子节点
                    i = child;//以子节点为重新调整的起点！
               }
               else
               {
               break;
               }
          }
     }
     void nodeArrSort(T top[], int topN);
     void nodeFilter(T *head, T top[], int topN, int groupId);
     void nodePrint(T *head);
public:
     T head;
     BAIDU::swap_p<T> swap;
};

#endif


/*
file:     node.cpp
author: hl
date:   2012-08-07
*/
#include <iostream>
#include <assert.h>
#include "node.h"
using namespace std;

template <typename T>
void NodeOperate<T>::nodeInitial(T *head)
{
     head->value = 0;
     head->group = 0;
     head->pnext = NULL;
}

template <typename T>
void NodeOperate<T>::nodeInsert(T *head, T& node)
{
     assert (head != NULL);
     T *p = head;
     T *pre = head;
     while(p)
     {
          pre = p;
          p = p->pnext;
     }
     pre->pnext = &node;
     node.pnext = NULL;
}

template <typename T>
void NodeOperate<T>::nodeCreate(T *head, T arr[], int nodeNumber)
{
     assert (head != NULL);
     for (int i = 1, j = 0; i < nodeNumber; ++i, ++j)
     {
          arr[j].group = (i%10);
          arr[j].value = i;
          this->nodeInsert(head, arr[j]);
     }
}

template <typename T>
void NodeOperate<T>::nodeArrSort(T top[], int topN)
{
     //将数组调整为最大堆
     for(int i = topN / 2; i >= 0; i--)
     {
               this->heapadjust(top, i, topN);
     }

     //不断缩小无序区
     for(int j = topN - 1; j > 0; j--)
     {
          this->swap(top[0], top[j]);
          this->heapadjust(top, 0, j)     ;
     }
}

template <typename T>
void NodeOperate<T>::nodeFilter(T *head, T top[], int topN, int groupId)
{
     assert (head != NULL);
     T *p = head;
     int flag = 1;
     int i = 0;
     do
     {
          if (groupId == p->group && flag)
          {
               top[i] = *p;
               if (9 == i)
               {
                    flag = 0;
                    break;
               }
               i++;
          }
     }while(p = p->pnext);
     //比较之前先排序top[]数组（从小到大）
     this->nodeArrSort(top, topN);
     //开始做比较, p之前已经存在，然后到i == 9以后就break, 因此只需要判断下一个是否存在，存在则继续比较；
     while(p = p->pnext)
     {
          if (p->group == groupId)
          {
               if (p->value > top[0].value)
               {
                    top[0].value = p->value;
                    //重新排序top[]数组（从小到大）
                    this->nodeArrSort(top, topN);
               }
          }
     }
}

template <typename T>
void NodeOperate<T>::nodePrint(T *head)
{
     assert (head != NULL);
     T *p = head;
     while(p)
     {
          cout << "group id is " << p->group;
          cout << " value is " << p->value << endl;
          p = p->pnext;
     }
}
/*
file:     main.cpp
author: hl
date:   2012-08-07
*/
#include <iostream>
#include "node.cpp"     //for template
#include "node.h"

using namespace std;

#define RMD(a, b) (a/b)   //求余数宏

//辅助打印结构体数组
void printArr(node_t nd[], int num)
{
     for (int i = 0; i < num; ++i)
          cout << nd[i].group << "  " << nd[i].value << endl;
}

int main(int argc, char** argv)
{
     /*1st宏替换*/
#if 0
     cout << RMD(2 + 4, 2) << endl;   //答案是4？ Answer-->2 + 4/2;
     cout << RMD((2 + 4), 2) << endl; //答案是3？ Answer-->(2+4)/2；
#endif

     /*2nd单向链表排序输出Top10*/
#if 0
     cmp cmp_t;
     cout << (cmp_t(3, 2) ? (1) : (2)) << endl;
     int a = 4;
     int b = 5;
     cout << "a is " << a << endl << "b is " << b << endl;
     new cmp(a, b);
     cout << "a is " << a << endl << "b is " << b << endl;
#endif

     /*3td*/
     NodeOperate<node_t> no;
     no.nodeInitial(&no.head);
     //no.nodePrint(&no.head);
     /*
     node_t no_t1;
     no_t1.group = 1;
     no_t1.value = 1;
     node_t no_t2;
     no_t2.group = 2;
     no_t2.value = 2;
     //no_t1.pnext = NULL; //如果你没有初始化，并且Inser函数定义方式是void nodeInsert(T *head, T node)；
                                //而不是引用，那么打印的过程则是无法预料的；因为在此时传参方式下函数内部进行node.pnext = NULL;是无效的！
     no.nodeInsert(&no.head, no_t1);
     no.nodeInsert(&no.head, no_t2);
     */
     /*
     struct node_b<int, int> node_b; //使用带模版的节点，看起来也不错；
     node_b.group = 1;
     node_b.value = 1;
     node_b.next = NULL;
     */

     node_t arr[10000]; //其实应该用指针数组比较好；
     //One:构造
     no.nodeCreate(&no.head, arr, 10000);
     //no.nodePrint(&no.head);
     /*Two:筛选出每组Top10 思路：
     *          取出group为0的前10个数，然后排序（从小到大），
     *          然后对后面的group为0的数与新排序的最小的数（就是第一个数）比较，
     *          如果小于就继续往后找，否则替换第一个，然后重新排序(排序如果要求高性能，要用最快的排序方式)；
     */
     node_t top[10];
     no.nodeFilter(&no.head, top, 10, 0);
     printArr(top, 10);

     system("pause");
     return 0;
}

我运行了还行，没报错，唉，对了，忘记了是不是还需要释放内存啊，如果可以改进的话我想尝试下shared_ptr“智能指针”，GoGo Study!