实现比较简单。

只需在二叉树节点内加入一个bool hasdata成员，表示此节点包含有效位串。

在插入时,遍历位串每一位，如果为1,则二叉树向右，如为0,则向左，在遍历位完成时，设置当前节点hasdata值为true。

最后的中序遍历更为简单

普通中序遍历原型为 middleOrder(currentNode)

代码为

判断 NODE不为NULL;

midlleOrder(currentNode->left);

printKey(currentNode);

middleOrder(currentNode->right);

基数树只需要加个形参即可。

原型 middleOrder(currentNode, string pre = string())

代码：

判断NODE不为NULL

   middleOrder(currentNode->left, pre +"0");

  if (currentNode->hasData)

      print(string);

  middleOrder(currentNode->right, pre +"1");

调用：

middleOrder(Tree)

代码有点混乱，C/C++不分，主要集中在createtree的 int &size形参上，其实最好是建个类存储当前层的SIZE，或者其他办法。因时间问题，不再更改。

#include <iostream>
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  findSecond
 *  Description:  算法导论练习 9.1-1
 *  证明：在最坏情况下，利用n + lgn -2次比较，，即可找到n个元素中的第2个小元素
 *  （提示：同时找最小元素）
 *  限制：需要支持随机迭代
 *  思路：起先想到用分治算法，但设计不出，还是忍不住看了算法导论的答案：
 *
 * To find the smallest element construct a tournament as follows:
 * Compare all the numbers in pairs.
 * Only the smallest number of each pair is potentially the
 smallest of all so the problem is reduced to size n/2 .
 * Continuing in this fashion until there is only one left clearly solves the problem.
 * Exactly n − 1 comparisons are needed since the tournament can be drawn as an n-leaf binary
tree
  which has n − 1 internal nodes (show by induction on n).
 * Each of these nodes correspond to a comparison.
 * We can use this binary tree to also locate the second
 * smallest number. The path from the root to the smallest element
 * (of height lg n ) must contain the second smallest element. Conducting
 * a tournament among these uses lg n − 1 comparisons.
 * The total number of comparisons are: n − 1 + lg n − 1 = n + lg n − 2.
 * =====================================================================================
 */

bool compInt(const int &a, const int &b)
{
  return a < b;
}

template <typename T>
class findSecondNode {
public:
  findSecondNode() : element(0), compareElement(0), child(0) { }
  findSecondNode(const T *elementArg, const T *compareElementArg, const findSecondNode<T> *childArg)
    : element(elementArg), compareElement(compareElementArg), child(childArg) { }
  const T *element;          /* 本元素指针 */
  const T *compareElement;   /* 与本元素比较的元素指针 */
  const findSecondNode<T> *child;            /* 二叉树子节点，与本元素同值 */
};

template <typename T, typename compFunc>
const findSecondNode<T> *createTree(const findSecondNode<T> *array, int &size, compFunc func);

template <typename T, typename compFunc>
const T *findSecond(T *array, int size, compFunc func);

#include <iostream>
#include <vector>
#include "find2nd.h"

// 如果失败，返回0值。
template <typename T, typename compFunc>
const findSecondNode<T> *createTree(const findSecondNode<T> *array, int &size,
compFunc func)
{
  if (size <= 0) {
    size = 0;
    return static_cast<findSecondNode<T> *>(0);
    }
  if (size == 1){
    size = 0;
    return array;
    }

  bool isEvenSize;
  int rowSize;
  if ((size % 2) != 0) {
    isEvenSize = false;
    rowSize = size / 2 + 1;
  } else {
    isEvenSize = true;
    rowSize = size / 2;
  }

  findSecondNode<T> *row = new findSecondNode<T>[rowSize];
  int i;
  for (i = 0; i < size -1; i += 2)
    if (func(*(array[i].element), *(array[i + 1].element))) {
      row[i / 2] = findSecondNode<T>(array[i].element, array[i + 1].element, array + i);
    } else {
      row[i / 2] = findSecondNode<T>(array[i + 1].element, array[i].element, array
+ i + 1);
    }

  if (!isEvenSize) {
    row[rowSize - 1] = findSecondNode<T>(array[i].element,
static_cast<T *>(0), array +
i - 1);
  }
  size = rowSize;
  return row;
}

template <typename T, typename compFunc>
const T *findSecond( T *array, int size, compFunc func)
{
  if (size <= 1)
    return 0;
  if (size == 2)
    return func(array[0], array[1]) ? array : array + 1;
  findSecondNode<T> *row;

  bool evenNumSize;
  int rowSize;
  if ((size % 2) != 0) {
    evenNumSize = false;
    rowSize = size / 2 + 1;
  } else {
    evenNumSize = true;
    rowSize = size / 2;
  }

  row = new findSecondNode<T>[rowSize];

  int i;
  for (i = 0; i < size -1; i += 2)
    if (func(array[i], array[i + 1])) {
      row[i / 2] = findSecondNode<T>(array + i, array +i + 1,
static_cast<findSecondNode<T> *>(0));
    } else {
      row[i / 2] = findSecondNode<T>(array + i + 1, array + i,
static_cast<findSecondNode<T> *>(0));
    }

  if (!evenNumSize)
    row[rowSize -1] = findSecondNode<T>(array + i, static_cast<T *>(0),
static_cast<findSecondNode<T> *>(0));

  std::vector<const findSecondNode<T> *> destructor;
  destructor.push_back(row);
  const findSecondNode<T> *ptr = row;

  while ((ptr = createTree(ptr, rowSize, func)) !=
         static_cast<const findSecondNode<T> *>(0))
      destructor.push_back(ptr);
  destructor.pop_back();
  ptr = destructor.at(destructor.size() - 1);
  const T *maySecond = ptr->compareElement;
  const T *tmp;
  while (ptr->child) {
    tmp = ptr->child->compareElement;
    if (tmp != 0 && func(*tmp, *maySecond))
      maySecond = tmp;
    ptr = ptr->child;
  }
  for (int i = destructor.size() - 1; i >= 0; i--)
    delete [] destructor.at(i);
  return maySecond;
}

//最好不要比较double值，不精确，此处只是展示
bool compDouble(const double &a, const double &b)
{
  return a < b;
}
int main ( int argc, char *argv[] )
{

  int a[10] = {90, 234, 234, 11, 5435, 89, 2423, 122, 99, 99};

  const int *tmp = findSecond(a, 10, compInt);
  std::cout << *tmp << std::endl;

  double b[9] = {23.33, 2342.22, 12.33, 2134.222, 5555.33, 242.2, 888,
                 1.333, 2342.222};

//最好不要比较double值，不精确，此处只是展示
  const double *tmpDouble = findSecond(b, 9, compDouble);
  std::cout << *tmpDouble << std::endl;
  return 0;
}       /* ----------  end of function main  ---------- */

本想模板编程，无奈基本没使用过，最后出来个四不像。。。。既不简单明了，又不高聚合低耦合的。。。

过几天再修改，将所有算法都尽量做成模板性质。。

#include <iostream>

int intFunc(int *number, void *)
{
  return *number;
}
// intbit 获取整数的第dbit位
int intbit(int *number, void *dbit);
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  CountingSort
 *  Description:  计数排序计数提供了O(N)的排序算法。
 *  但受限于整数的Range，是一个用空间换取时间的算法。
 *  rangeArr的依次相加获取数组位置是为了稳定排序，适用于各种可由正整数排序的结构。
 *  限制：必须是0开始的有range的正整数（可以通过func转换为此，再进行排序)
 * =====================================================================================
 */
template <typename T>
struct PosWithPointer {
  int posValue;
  T *pointer;
};

template <typename T>
void CountingSort(T *array, int size, int range, int(*func)(T *element, void *), void *arg = 0)
{
     PosWithPointer<T> *rangeArr = new PosWithPointer<T>[range +1];
     for (int i = 0; i <= range; i++) {
          rangeArr[i].posValue = 0;
          rangeArr[i].pointer = 0;
     }
     for (int i = 0;  i < size; i++) {
          ++rangeArr[func(array + i, arg)].posValue;
          rangeArr[func(array +i, arg)].pointer = array + i;
     }

     for (int i = 1; i <= range; i++) {
          rangeArr[i].posValue += rangeArr[i - 1].posValue;
     }

     T *sortArray = new T[size];
     for (int i = size - 1; i >= 0; --i) {
          // 注意此处要 -1,因为最小的数据位置为1,而数组初始为0.
          sortArray[rangeArr[func(array + i, arg)].posValue - 1] = array[i];
          --rangeArr[func(array +i, arg)].posValue;
     }
     for (int i = 0; i < size; i++) {
          array[i] = sortArray[i];
     }
     delete [] rangeArr;
     delete [] sortArray;

}

int tenPow(int basePow)
{
  int result = 1;
  for (int i = 1; i <= basePow; i++)
    result *= 10;
  return result;
}

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  RadixSort
 *  Description:  借助于计数排序的RaDixSort;
 *  算法复杂度：线性 O(dbit(size+ 10)), 10为每一位可能的取值
 * =====================================================================================
 */
// Dgit为数字的最大位数
void RadixSort(int *array, int size, int dbit)
{
  for (int i = 1; i <= dbit; i++)
    CountingSort(array, size, tenPow(dbit), intbit, static_cast<void *>(&i));
}

int intbit(int *number, void *dbit)
{
  if (*number < 0)
    return 0;
 
  int *bit = static_cast<int *>(dbit);
  return *number / tenPow(*bit - 1) % 10;
}

int main(int argc, char **argv)
{
     int a[10] = {3, 5, 3, 2, 8, 984, 223, 82, 9234, 10};
     std::cout << "计数排序数组" << std::endl;
     CountingSort(a, 10, 9235, intFunc, 0);
     for (int i = 0; i < 10; i++) {
          std::cout << a[i] << "\t";
     }

     std::cout << "\n使用基数排序，底层用计数排序实现" << std::endl;
     int b[10] = {3, 5, 3, 2, 8, 984, 223, 82, 9234, 10};
     RadixSort(b, 10, 4);
     for (int i = 0; i < 10; i++) {
          std::cout << b[i] << "\t";
     }

     return 0;
}

 

最大/最小优先级的结构代码不再赘述，需要考虑C/C++编程中0为初始，从而在代码上修改即可。

如有需要，我会给出我的。。。

问题：6.5-8

给出一个时间为O(nlgk)，用来将k个已排序链表合并为一个排序链表的算法。n为所有输入链表中元素的总数。（提示：用一个最小堆来做k路合并）

答案：

所有比较以多路链表首元素为基数，并以此来建立最小优先级队列。

总是弹出根节点链表的首元素。每次弹出后，如果根节点已经0元素，就extract-min()，否则minHeapify()下移根节点（有可能仍是最小元素，不必小移）。

问题： 6-5

Young氏矩阵：

答案：

（1）Extract-Min()

将第一个元素保存，最后返回。

Y[m,n]（最大的）与第一个元素交换，并比较最大元素的行/列两个临近元素，取小的值与最大值交换。注意边界，递归。

(2)排序：

将每个元素放入y[m,n]，然后运行Extract-Min

n^2个元素需要2n^3的运行时间。

(3)查找：

总是与最右上角比较，如果等于，则返回。

如果大于，去除这一行

如果小于，去除这一列。。

我是个业余小菜，入门偏上级别，并不是小牛小虾之类。。。。只是有几次碰巧和几位大牛结缘，看客不要误解先。。。

1, 我碰到一个GNU软件很偶尔的一次崩溃，当时某大牛和我在同一个聊天室，我向其随便一说。

大牛让我详细描述事件发生情况，我说我用的是Ubuntu ALPHA版，出现问题很正常，可能是系统原因，而非软件本身，可能不重要。（其实我心里也觉得 免费开源的东东，为这Alpha系统里出现的软件崩溃大费周章挺费力）

大牛不乐意，硬是坚持，说“重要不重要我说了算……” 后来没有找到具体原因，崩溃环境无法再现，大牛让我以后再有此类问题的话注意下比告知他。

这一点可能是认真

2, 我接了某大牛一个微不足道的GUI程序，功能并不复杂，基本都实现后交给了某大牛，让其看还要做什么改进。

乖乖，从UI界面的简单快捷，到按钮文字前加图片，线程化的 各个要求都出来了。。。。。为一个不起眼的软件，所做的一点也不会少。。

这一点可能是细致

3, 某大项目的牛人，只在网上见过名字，没接触过。我看到一篇非常好的大项目的WIKI译文，把链接发到了IRC上。

此牛以为译文作者是我，立刻问我，为什么不把这译文放到WIKI的中文版面上。。。。。在知道作者不是我后，在译文后留言表达这个想法

其实，这个项目可能被母公司砍出去了。。。。。大牛或者不负责这个项目了，或者他本人已经跳槽，最起码来说，这个项目暂时也是下坡路的，个人收益和开发人员数量都不会很乐观了……

我想，这是爱。。。。。

fcitx-table-editor

1. 软件介绍

fcitx-table-editor为一款fcitx专用码表管理工具，遵守GPL V2及以上版本协议。

开发者文档

2. 功能介绍

(1)， 读取并解析码表文件，编辑、修改、删除条目以及配置项。
(2)， 对码表中的同键多值行列，保持读取与编辑修改时的顺序。
(3)， 可对码表的键值，进行前缀、通配符、正则匹配过滤，以显示有用内容。

3. 联系我们

如果你对于该软件有任何不解或者建议的地方: wengxt@gmail.com sd44sd44@yeah.net

4. 项目地址

HomePage SourceCode

星海 Image Batcher是一个基于QT4/GM的批量图片处理软件，为功能强大，具有极高效率 的 graphicsmagick，（以下简称GM）界面前端。GM中的Magick++ API，采用OpenMP多线程库处理图片，并支持近百种图片格式，如DPX、GIF、 JPEG、JPEG-2000、PNG、PDF、PNM和TIFF，RAW等格式，还有各种特效，被称为 图片处理领域的瑞士军刀。

本软件尽量以转换后的图片质量为第一要求，虽然速度也不满

在软件设计过程中，参考了Converseen的界面，力求简洁明快。

感谢Converseen的作者.faster3ck@gmail.com 感谢Q3ACN老坛友们从我开始学编程一直以来的支持，By Quakers， For Quakers！
技术方面，感谢 irc://irc.freenode.net 中 #kde-cn 聊天室的大牛们， 尤其感谢kde-cn中csslayer, yuyichao, wanggjGhost 等大牛的鼎力相助 -__-。

最感谢的，还是爸爸、妈妈、老婆、小墨墨。。。。聚少离多，相聚时也把大部 份放在了编程上。。。

如有使用问题或更好建议，与我联系
sd44sd44@yeah.net
我的主页： http://sd44.is-programmer.com
项目主页： http://sd44.github.com

昨日在IRC #kde-cn频道，就几个问题询问了nihui老大和csslayer老大，两位老大给予了很大的帮助。。（虽然他们应该都比我小-___-)

与QT有关的，是Designer设计师里对于Layout的“错乱”

问题：因为添加这个，那个layout，常导致布局错乱。

讨论：

[nihui] 可以布局掌控的
[vic__] 布局 只是管理空间排列的方式的把
[nihui] 参考优先级 fixed-geometry > expanding > preferred > minimum > layoutstretch > layout

[nihui] sd44: 设计师的思路和手写是相反的

[nihui] 手写的时候是先创建设定好 layout,然后往 layout 加东西

[nihui] 设计师是先创建好东西,然后ctrl+鼠标选中这些东西,用某个 layout 排列
[csslayer]: 嗯,建好layout再改有时候很难做。如果想换layout或者添加,一般还是先break掉layout,然后再重新组合

之前csslayer老大也提到了多建立（适度）layout的解决方法，但我没有足够的功力去领悟 或者说 没有总结到。

最后的解决方法：

全局，容纳其他Widget的容器，如GroupBox，tabWidget,在相关组件建立好后，都建立一个layout。。。

这只是现在我能做到的较好的解决方法了，应该还有些地方需要注意，

如果你有更好的办法，留言或者mailme

最近在用GM API编程，采用了CMAKE作为构建系统

CMAKE自带ImageMagick的Find module，但是缺少GraphisMagick的

碰巧我在使用GM，所以找了下网上的GM module，最早的也是15个月前的，且稍稍有点问题。

于是我结合FINDIMAGEMAGICK MODULE代码，稍稍修改了下GraphisMagick。

以支持WINDOWS和LINUX双系统（只是搜索Magick API和Magick++ API)

内容如下：

#-*-cmake-*-
#
# Test for GraphicsMagick libraries, unlike CMake's FindGraphicsMagick.cmake which
# tests for GraphicsMagick's binary utilities
#
# Once loaded this will define
#  MAGICK_FOUND        - system has GraphicsMagick
#  MAGICK_INCLUDE_DIR  - include directory for GraphicsMagick
#  MAGICK_LIBRARY_DIR  - library directory for GraphicsMagick
#  MAGICK_LIBRARIES    - libraries you need to link to
#
#  MAGICK++_FOUND        - system has GraphicsMagick
#  MAGICK++_INCLUDE_DIR  - include directory for GraphicsMagick
#  MAGICK++_LIBRARY_DIR  - library directory for GraphicsMagick
#  MAGICK++_LIBRARIES    - libraries you need to link to
#

SET(MAGICK_FOUND   "NO" )
SET(MAGICK++_FOUND "NO" )

FIND_PATH( MAGICK_INCLUDE_DIR
  NAMES magick.h
  PATHS
  "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GraphicsMagick\\Current;BinPath]/include"
  "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GraphicsMagick\\Current;BinPath]/include/magick"
  /usr/include/GraphicsMagick/magick
  "$ENV{MAGICK_LOCATION}/magick"
  "$ENV{MAGICK_LOCATION}/include"
  "$ENV{MAGICK_LOCATION}/include/GraphicsMagick"
  "$ENV{MAGICK_LOCATION}/include/magick"
  "$ENV{MAGICK_HOME}/include/magick"
  /usr/include/magick
  /usr/include/
  /usr/local/include
  /usr/local/include/GraphicsMagick/magick
  /usr/local/include/GraphicsMagick/
  /opt/local/include/GraphicsMagick/magick
  /opt/local/include/GraphicsMagick
  )

FIND_PATH( MAGICK++_INCLUDE_DIR
  NAMES Magick++.h
  PATHS
  "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GraphicsMagick\\Current;BinPath]/include"
  "$ENV{MAGICK++_LOCATION}/Magick++"
  "$ENV{MAGICK++_LOCATION}/include/"
  "$ENV{MAGICK_LOCATION}/Magick++"
  "$ENV{MAGICK_LOCATION}/include/Magick++"
  "$ENV{MAGICK_LOCATION}/include/GraphicsMagick"
  "$ENV{MAGICK_LOCATION}/include/"
  "$ENV{MAGICK_HOME}/include/"
  /usr/include/GraphicsMagick
  /usr/include/Magick++
  /usr/include/
  /usr/local/include
  /usr/local/include/GraphicsMagick
  /opt/local/include/GraphicsMagick/Magick++
  /opt/local/include/GraphicsMagick
  )

FIND_LIBRARY( Magick
  NAMES GraphicsMagick CORE_RL_magick_
  PATHS 
  "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GraphicsMagick\\Current;BinPath]/lib"
  "$ENV{MAGICK_LOCATION}/magick/.libs"
  "$ENV{MAGICK_LOCATION}/lib"
  "$ENV{MAGICK_HOME}/lib"
  /usr/lib64
  /usr/local/lib64
  /opt/local/lib64
  /usr/lib
  /usr/local/lib
  /opt/local/lib
  DOC   "GraphicsMagick magic library"
  )


FIND_LIBRARY( Magick++
  NAMES GraphicsMagick++ CORE_RL_Magick++_
  PATHS 
  "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GraphicsMagick\\Current;BinPath]/lib"
  "$ENV{MAGICK++_LOCATION}/.libs"
  "$ENV{MAGICK_LOCATION}/.libs"
  "$ENV{MAGICK++_LOCATION}/lib"
  "$ENV{MAGICK_LOCATION}/lib"
  "$ENV{MAGICK_HOME}/lib"
  /opt/local/lib64
  /usr/lib64
  /usr/local/lib64
  /opt/local/lib
  /usr/lib
  /usr/local/lib
  DOC   "GraphicsMagick Magick++ library"
  )


SET(MAGICK_LIBRARIES ${Magick} )
SET(MAGICK++_LIBRARIES ${Magick++} )


IF (MAGICK_INCLUDE_DIR)
  IF(MAGICK_LIBRARIES)
    SET(MAGICK_FOUND "YES")
    GET_FILENAME_COMPONENT(MAGICK_LIBRARY_DIR ${Magick}   PATH)
  ENDIF(MAGICK_LIBRARIES)
ENDIF(MAGICK_INCLUDE_DIR)

IF (MAGICK++_INCLUDE_DIR)
  IF(MAGICK++_LIBRARIES)
    SET(MAGICK++_FOUND "YES")
    GET_FILENAME_COMPONENT(MAGICK++_LIBRARY_DIR ${Magick++} PATH)
  ENDIF(MAGICK++_LIBRARIES)
ENDIF(MAGICK++_INCLUDE_DIR)


IF(NOT MAGICK_FOUND)
  # make FIND_PACKAGE friendly
  IF(NOT Magick_FIND_QUIETLY)
    IF(Magick_FIND_REQUIRED)
      MESSAGE(FATAL_ERROR
        "GraphicsMagick required, please specify it's location with MAGICK_HOME, MAGICK_LOCATION or MAGICK++_LOCATION")
    ELSE(Magick_FIND_REQUIRED)
      MESSAGE(STATUS "GraphicsMagick was not found.")
    ENDIF(Magick_FIND_REQUIRED)
  ENDIF(NOT Magick_FIND_QUIETLY)
ENDIF(NOT MAGICK_FOUND)


#####

MODEL继承自QAbstractTableModel，

VIEW使用的QTABLEVIEW。

就列的显示大小和弹簧问题，做了很多尝试。

现在基本可以达到满意效果。

    tableView = new QTableView;
    tableView->horizontalHeader()->setStretchLastSection(true);
    tableView->horizontalHeader()->setResizeMode(QHeaderView::ResizeToContents);
    tableView->horizontalHeader()->setResizeMode(4, QHeaderView::Stretch);
    tableView->setSizePolicy(QSizePolicy::Expanding, QSizePolicy::Expanding);
    tableView->setModel(model);