我写故我在

I write, therefore I am

Archive for the ‘技术’ Category

HuLu2012校园招聘笔试题

Posted by ieipi 于 九月 26, 2011

2011年9月23日中科院
70分钟,7张卷子,不得不说十分变态。。。

题目

此幻灯片需要JavaScript支持。

参考解答
 一.填空题
1. 11
2. 29
3. 
4. 1,3??
5. 11
6. 4
7. 32, 1
8. 9
9. 4
10. 141
11. 59
12. n(n+1)/2+1
13. 方块5
14. 9!
15. 5

二.编程题

三.附加题

Posted in 技术 | Tagged: | Leave a Comment »

创新工场2012校园招聘笔试题

Posted by ieipi 于 九月 25, 2011

创新工场笔试2011年9月19日中科院
一个小时。感觉答的不错,结果还是被鄙视了,没有收到面试通知。

题目

此幻灯片需要JavaScript支持。

参考答案
一.选择题
ACDDD BABCC
值得注意的是第7题:
首先:M个球放入N个箱子总共有C(M+N-1,N-1)中方法
方法一:
8个蓝球形成9个空格,放入5个红球共有C(5+9-1, 9-1)=C(13, 8);
若保证红球不相邻,则每个格子最多只能放一个,即C(9,5);
故:C(9,5)/ C(13, 8)=14/143
方法二:
5个红球8个蓝球放一列,相当于从13个球中选出5个(则剩下的8个已定),共有C(13,5)种;
要保证红球不相邻, 则每个红球边至少有一个蓝球,共消耗4个蓝球,剩下4个,相当于从9个球中选4个,则共有C(9,4)种;
故: C(9,4)/C(13,5) =14/143;

二.编程题
1.可以对P和R分别设一加权因子a,b,则对每一个应用,其待排序因素为a*P+b*R,转化为一个普通的一维序列,从而可以采用排序算法解决。
2.源代码如下:

int Fibonacci(int n)
{
	if(n<=0)
		return 0;
	if(n==1 || n==2)
		return 1;
	int first,second,third;//f(n-2),f(n-1),f(n);
	first = 1;
	second = 1;
	for(int i=2; i<=n; i++)
	{
		third = first + second;
		first = second;
		second = third;
	}
	return third;
}

3.约瑟夫环问题


Posted in 技术 | Tagged: | Leave a Comment »

程序员面试题集004

Posted by ieipi 于 九月 16, 2011

题目
输入一个整数和一颗二元树,打印出与输入整数相等的所有从根节点到叶子节点的路径.
思路
首先根据树的遍历算法很容易找到满足条件的叶子节点.
问题是如何打印出从根节点到该节点的路径?
进一步考虑,遍历通常用的是递归算法,从根节点到叶子节点的函数调用过程系统已经保存好了,用到的数据结构就是栈.
树中遍历的过程即是一个入栈和出栈的过程.所以我们同样可以采用一个栈来显式保存遍历的路径.
源代码
/**
 * @brief find the path whose sum equals the specified number.
 *
 * @param pNode root
 * @param expectedSum expected sum.
 * @param path the stack holds the path.
 * @param currentSum sum of the current path.
 */
    void
FindPath (struct BinaryTreeNode *pNode, int expectedSum, vector &path, int &currentSum  )
{
    if(pNode == NULL) {
        return;
    }
    currentSum += pNode->m_nValue;
    path.push_back(pNode->m_nValue);

    bool isLeaf = (pNode->m_pLeft == NULL)&&(pNode->m_pRight == NULL);
    if(currentSum == expectedSum && isLeaf) {
        vector::iterator itr = path.begin();
        for(; itr != path.end(); itr++) {
            cout << *itr << "\t";
        }
        cout << endl;
    }
    if(pNode->m_pLeft)
        FindPath(pNode->m_pLeft, expectedSum, path, currentSum);
    if(pNode->m_pRight)
        FindPath(pNode->m_pRight, expectedSum, path, currentSum);

    currentSum -= pNode->m_nValue;
    path.pop_back();
    return ;
}		/* -----  end of function FindPath  ----- */

 Reference

1.http://zhedahht.blog.163.com/blog/static/254111742007228357325/

Posted in 算法, 技术 | Tagged: , | Leave a Comment »

程序员面试题集003

Posted by ieipi 于 九月 14, 2011

题目

在O(n)的时间内求出一个输入数组的最大子段和

思路一

最笨的方法就是遍历.遍历所有的子数组,并比较它们的和,获得最大者.
但时间复杂度为O(n^3).
源代码

int MaxSubSum1(const int arr[], int len)
{
    //there is at least one positive value in the input array.
    int MaxSum = 0;

    for ( int i=0; i<len; i++) {
        //start index of the subsequence.
        for ( int j=i; j<len; j++){
            //end index of the subsequence.
            int SubSum = 0;
            //caculate the sum of the subsequence.
            for ( int k=i; k<=j; k++) {
                SubSum += arr[k];
            }
            if(SubSum > MaxSum)
                MaxSum = SubSum;
        }
    }
    return MaxSum;
}

思路二

上述算法可以优化,求子数组和时不必从头开始,可以直接利用上一次求和的结果,从而可以去掉一层循环.
时间复杂度可以降到O(n^2).
源代码

int MaxSubSum2(const int arr[], int len)
{
    int MaxSum = 0;

    for ( int i=0; i<len; i++){
        int SubSum = 0;
        for ( int j=i; j<len; j++) {
            //caculate the sum of the subsequence with help of the last SubSum.
            SubSum += arr[j];
            if ( SubSum > MaxSum ) {
                MaxSum = SubSum;
            }
        }
    }
    return MaxSum;
}

思路三
采用递归,现将输入数组分解为两个子数组,再递归处理两个子数组,最后将结果合并.即标准的Divide-Conquer-Combine模式.
时间复杂度可以进一步降到O(nlogn)
源代码

int MaxSubSumRec(const int arr[], int left, int right)
{
   //base case.
    if(left == right){
        //TODO:
        return arr[left];
    }
    //divide
    int center = (left+right)/2;
    //conquer
    int MaxLeftSum = MaxSubSumRec(arr, left, center);
    int MaxRightSum = MaxSubSumRec(arr, center+1,  right);
    //combine
    int MaxLeftBorderSum = 0; int LeftBorderSum = 0;
    for(int i=center; i>=left; i--){
        LeftBorderSum += arr[i];
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    int MaxRightBorderSum = 0; int RightBorderSum = 0;
    for(int i=center+1; i <= right; i++){
        RightBorderSum += arr[i];
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }
    int max = MaxLeftSum > MaxRightSum?MaxLeftSum:MaxRightSum;
    int LeftRightSum = MaxLeftBorderSum + MaxRightBorderSum;
    max = max>LeftRightSum?max:LeftRightSum;
    return max;
}
int MaxSubSum3(const int arr[], int len)
{
    return MaxSubSumRec(arr, 0, len-1);
}

思路四
输入数组中的若干个负数将数组划分为几个互补重合的子数组,我们只需分别求出这几个子数组的和并比较大小即可.
只需一次循环,时间复杂度为O(n).
源代码

int MaxSubSum4(const int arr[], int len)
{
   int MaxSum =0;
   int SubSum =0;
   for(int i=0; i<len; i++){
       SubSum += arr[i];
       if(SubSum>MaxSum)
           MaxSum = SubSum;
       else if (SubSum < 0 )
           SubSum = 0;
   }
   return MaxSum;
}

Posted in 算法 | Tagged: | Leave a Comment »

程序员面试题集002

Posted by ieipi 于 九月 14, 2011

题目
定义栈的数据结构,添加一个min函数,使之能在O(1)的时间内得到栈的最小元素.要求push,pop的时间复杂度都是O(1).
思路1
1.普通栈的push和pop操作都是O(1),但是min()操作为O(n);
2.尝试在每一次push操作时将最小值放在栈顶;但是此时不满足栈的LIFO特点;
3.继续尝试,设置一个minValue,记录当前栈的最小元素,每次push后更新该值,但是一旦该值被pop后,无法在O(1)内得到剩下元素的最小值;
4.继续尝试,可否用空间换取时间?Bingo!设置一个辅助栈,保存栈中当前元素的最小值.每次push,将最小值压栈,每次pop,也将栈顶最小元素出栈,
这样,栈顶元素既是当前元素的最小值.
源代码
/*
 * =====================================================================================
 *
 *       Filename:  MinStack-tmpl.cpp
 *
 *    Description:  Design a stack such that the getMinumun()operation will return the minimum
 *                  of the stack within O(1)time. And the push and pop operation will also run
 *                  in O(1)time.
 *
 *        Version:  1.0
 *        Created:  2011年09月14日 09时09分59秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>
#include	<iostream>
#include	<stack>
#include	"assert.h"
using namespace std;

template <class T>
class MinStack
{
    public:
        MinStack(){};
        ~MinStack(){};
        void push(T value);
        T pop();
        T min();

        stack<T> data;
        stack<T> minstack;
};
template <class T>
void MinStack<T>::push(T value)
{
    data.push(value);
    if(minstack.size() == 0){
        minstack.push(value);
    }else{
        T& min = minstack.top();
        if(value >= min){
            minstack.push(min);
        }else{
            minstack.push(value);
        }
    }
}
template <class T>
T MinStack<T>::pop()
{
    assert(data.size()>0);
    assert(minstack.size()>0);
    minstack.pop();
    T top = data.top();
    data.pop();
    return top;
}
template <class T>
T MinStack<T>::min()
{
    assert(data.size()>0);
    assert(minstack.size()>0);
    return minstack.top();
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    MinStack<int> stack;

    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(6);
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    cout << stack.min() << endl;
    stack.pop();
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

思路二
是否可以不要辅助栈,从而将空间复杂度也降低到O(1)呢?
接着思路一第三步,minValue保存当前最小值,但是栈内元素可以做手脚:
当入栈元素value>=minValue时,直接压栈;
但是当value<minValue时,需要特殊处理,我们将2*value-minValue入栈,
再更新minValue到当前最小值,即value 。
pop()操作也要做相应处理:
当top>=minValue时,说明栈顶元素即是原来压栈元素,直接弹出;
但是当top<minValue时,说明栈顶元素是做过手脚之后的结果,我们需要恢复,
此时minValue值即为原压栈元素,可以直接弹出,但是需要更新minValue=2*value-top
源代码

/*
 * =====================================================================================
 *
 *       Filename:  MinStack-tmpl.cpp
 *
 *    Description:  Without duplicate stack.min(),push(),and pop() are O(1); space is also O(1);
 *
 *        Version:  1.0
 *        Created:  2011年09月14日 09时09分59秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>
#include	<iostream>
#include	<stack>
#include	"assert.h"
using namespace std;

template <class T>
class MinStack
{
    public:
        MinStack(){};
        ~MinStack(){};
        void push(T value);
        T pop();
        T min();
        T top();

        stack<T> data;
        T minValue;
};
template <class T>
void MinStack<T>::push(T value)
{
    if(data.size() == 0){
        data.push(value);
        minValue = value;
    }else{
        if(value >= minValue){
            //push the actual value into stack.
            data.push(value);
        }else{
            //update minValue which is the new incomming data.
            //construct a new value_tmp to be pushed.
            T value_tmp = (value - minValue) + value;
            data.push(value_tmp);
            minValue = value;
        }
    }
}
template <class T>
T MinStack<T>::pop()
{
    assert(data.size()>0);
    T top = data.top();
    if(top >= minValue){
        //this is the actual member.
        data.pop();
        return top;
    }else{
        //minValue is the actual pushed data.
        //use top and minValue to restore the next minValue.
        top = minValue;
        minValue = 2*top - data.top();
        data.pop();
        return top;
    }
}
template <class T>
T MinStack<T>::min()
{
    assert(data.size()>0);
    return minValue;
}
template <class T>
T MinStack<T>::top()
{
    return data.top();
}
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    MinStack<int> stack;

    stack.push(10);
    stack.push(7);
    stack.push(3);
    stack.push(3);
    stack.push(5);
    stack.push(2);
    stack.push(6);

    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    cout << stack.min() << endl;
    cout << "\ttop:" << stack.top() << endl;
    stack.pop();
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

Reference
1.http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
2.http://stackoverflow.com/questions/1377222/min-value-from-stack?answertab=active#tab-top
3.http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 

Posted in 算法 | Tagged: , | Leave a Comment »

程序员面试题集001

Posted by ieipi 于 九月 10, 2011

题目

将一颗二叉搜索树变成排序的双向链表,要求只改动指针,不创建新的节点。

思路一

    对于二元查找树(Binary Search Tree),其中序遍历的结果即为排序的结果,只需将此结果用双链表表示即可。根据中序遍历的思想,
对于当前节点而言,其左子树已经成功转换,接下来先将当前节点插入链表尾部,再处理其右子树。

伪代码  

1.若当前节点为空,则处理结束,返回.
2.否则:
    2.1递归处理左子树;
    2.2将当前节点加入链表尾部;
    2.3递归处理右子树;

代码

/*
 * =====================================================================================
 *
 *       Filename:  bst2list.cpp
 *
 *    Description:  convert a BST into a sorted double linked list in place.
 *
 *        Version:  1.0
 *        Created:  2011年08月24日 19时54分33秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  XuDingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include	<stdlib.h>

#include	<stdio.h>
#include	<iostream>
using namespace std;

struct BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pLeft;
    BSTreeNode *m_pRight;
};
typedef BSTreeNode DoubleList;
DoubleList *pHead;
DoubleList *pListIndex;

void convertToDoubleList(BSTreeNode *pCurrent);
void addBSTreeNode(BSTreeNode *&pCurrent, int value);

/**
 * @brief add a new node to the current BST.
 *
 * @param pCurrent the root of the current BST.
 * @param value the data element of the new node.
 */
    void
addBSTreeNode (BSTreeNode *&pCurrent, int value  )
{

    if ( NULL == pCurrent ) {
        BSTreeNode *pBSTree = new BSTreeNode();
        pBSTree->m_pLeft = NULL;
        pBSTree->m_pRight = NULL;
        pBSTree->m_nValue = value;
        pCurrent = pBSTree;
    }
    else {
        if ( pCurrent->m_nValue > value ) {
            addBSTreeNode(pCurrent->m_pLeft, value);
        }
        else if(pCurrent->m_nValue < value){
            addBSTreeNode(pCurrent->m_pRight, value);
        }
        else {
            cout << "ignore duplicate node"  << endl;
        }
    }
    return ;
}		/* -----  end of function addBSTreeNode  ----- */

/**
 * @brief traverse the BST in inorder and form the double list accordingly.
 *
 * @param pCurrent the root of the current BST.
 */
    void
ergodicBSTree ( BSTreeNode *pCurrent  )
{
    if(NULL == pCurrent) {
        return;
    }
    if(NULL != pCurrent->m_pLeft){
        ergodicBSTree(pCurrent->m_pLeft);
    }
    convertToDoubleList(pCurrent);
    if(NULL != pCurrent->m_pRight) {
        ergodicBSTree(pCurrent->m_pRight);
    }
    return ;
}		/* -----  end of function ergodicBSTreeeNode  ----- */
/**
 * @brief add the current node into the doulbe list.
 *
 * @param pCurrent. the current node to be converted.
 */
    void
convertToDoubleList (BSTreeNode *pCurrent  )
{
    pCurrent->m_pLeft = pListIndex;
    if(NULL != pListIndex) {
        pListIndex->m_pRight = pCurrent;
    }else {
        pHead = pCurrent;
    }
    pListIndex = pCurrent;
    cout << pCurrent->m_nValue << endl;
    return ;
}		/* -----  end of function converToDoubleList  ----- */
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    BSTreeNode *pRoot = NULL;
    pHead = NULL;
    pListIndex = NULL;
    addBSTreeNode(pRoot, 10);
    addBSTreeNode(pRoot, 4);
    addBSTreeNode(pRoot, 6);
    addBSTreeNode(pRoot, 8);
    addBSTreeNode(pRoot, 12);
    addBSTreeNode(pRoot, 14);
    addBSTreeNode(pRoot, 15);
    addBSTreeNode(pRoot, 16);
    addBSTreeNode(pRoot, 1);
    addBSTreeNode(pRoot, 18);

    ergodicBSTree(pRoot);

    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

思路二

上述方法虽然本质上用的是递归,但是硬要跟树的遍历扯上关系,有点含混不清.何不直接用一个纯脆的递归方法呢?

伪代码

BST2Dlist(root):
if root=null
   then return null; #base case:null tree to null list.
   else preList=BST2Dlist(left[root]);
        postList=BST2Dlist(right[root]);
        combine preList, root, and postList to form one double list.

源代码

/*
 * =====================================================================================
 *
 *       Filename:  bst2list-3.cpp
 *
 *    Description:  convert a BST to sorted double list in place.
 *
 *        Version:  1.0
 *        Created:  2011年09月10日 00时41分00秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Xu Dingxin (xdxn), xdxn2010@gmail.com
 *        Company:  GUCAS
 *
 * =====================================================================================
 */

#include        <stdlib.h>

#include        <iostream>
using namespace std;

template <class T>
class Node
{
public:
    T data;
    Node *left;
    Node *right;

    Node(){
        data = 0;
        left = NULL;
        right = NULL;
    }
    Node(T data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

/**
 * @brief insert a new element to the BST.
 *
 * @param root reference to root of the BST.
 * @param data data field of the new element.
 *
 * @return
 */
    template <class T>
void TreeInsert(Node<T> *&root, T data)
{
    if(root == NULL){
        root = new Node<T>(data);
    }else{
        if ( data < root->data ) {
            TreeInsert(root->left, data);
        }else{
            TreeInsert(root->right, data);
        }
    }
}

/**
 * @brief traverse the BST in inorder.
 *
 * @param root
 */
template <class T>
    void
InorderTraverse (Node<T> *root)
{

    if ( root == NULL ) {
        return;
    }
    InorderTraverse(root->left);
    cout << root->data << "\t";
    InorderTraverse(root->right);
    return ;
}               /* -----  end of function InorderTraverse  ----- */
/**
 * @brief traverse the BST in preorder.
 *
 * @param root
 */
template <class T>
    void
PreOrderTraverse ( Node<T>* root )
{
    if(root == NULL)
        return;
    cout << root->data << "\t";
    PreOrderTraverse(root->left);
    PreOrderTraverse(root->right);
    return ;
}               /* -----  end of function PreOrderTraverse  ----- */
/**
 * @brief traverse the BST in postorder.
 *
 * @param root
 */
template <class T>
    void
PostOrderTraverse ( Node<T>* root )
{
    if(root == NULL)
        return;
    PostOrderTraverse(root->left);
    PostOrderTraverse(root->right);
    cout << root->data << "\t";
    return ;
}               /* -----  end of function PostOrderTraverse  ----- */
/**
 * @brief convert the BST to a sorted double list.
 *
 * @param root root of BST.
 *
 * @return pointer to the list head.
 */
template <class T>
   Node<T>*
BST2DList ( Node<T>* root )
{
    if(root == NULL)
        return NULL;
    Node<T>* left = BST2DList(root->left);
    Node<T>* right = BST2DList(root->right);

    Node<T>* listHead;
    if(left == NULL) {
        listHead = root;
    }else{
        //append root to the left list.
        listHead = left;
        Node<T>* tmp = listHead;
        while(tmp != NULL && tmp->right != NULL){
            tmp = tmp->right;
        }
        tmp->right = root;
        root->left = tmp;
    }

    if ( right != NULL ) {
        root->right = right;
        right->left = root;
    }
    return listHead;
}               /* -----  end of function BST2DList  ----- */
/**
 * @brief append bNode to aNode.
 *
 * @param aNode
 * @param bNode
 */
template <class T>
    static void
Join ( Node<T>*aNode, Node<T>* bNode )
{
    aNode->right = bNode;
    bNode->left = aNode;
    return ;
}               /* -----  end of function Join  ----- */
/**
 * @brief append bList to aList.
 *
 * @param aList
 * @param bList
 *
 * @return
 */
template <class T>
    static Node<T>*
ListJoin ( Node<T>* aList, Node<T>*bList )
{
    if(aList == NULL)
        return bList;
    if(bList == NULL)
        return aList;

    Node<T>* aLast = aList->left;
    Node<T>* bLast = bList->left;

    //append bList to aLast
    aLast->right = bList;
    bList->left = aLast;

    //link bLast to aList to form a circular list..
    bLast->right = aList;
    aList->left = bLast;
    return aList;
}               /* -----  end of function ListJoin  ----- */
/**
 * @brief convert a BST to a sorted double circular list.
 *
 * @param root
 *
 * @return
 */
template <class T>
    Node<T>*
BST2DCList ( Node<T>* root )
{
    if(root == NULL)
        return NULL;

    char tmp;
    Node<T>* left = BST2DCList(root->left);
    Node<T>* right = BST2DCList(root->right);

    //make the root node length-1 double circular list.
    root->left = root;
    root->right = root;

    //combine the left, root and right sub-list.
    left = ListJoin(left, root);
    left = ListJoin(left, right);
    return left;
}               /* -----  end of function BST2DCList  ----- */
/**
 * @brief print double list.
 *
 * @param list
 */
template <class T>
    void
PrintList ( Node<T>*list )
{
    if(list == NULL)
        return;
    Node<T> *tmp = list;
    while(tmp != NULL) {
        cout << tmp->data << "\t";
        tmp = tmp->right;
    }
    return ;
}               /* -----  end of function PrintList  ----- */
/**
 * @brief print double circular list.
 *
 * @param list
 */
template <class T>
    void
PrintDCList ( Node<T>* list )
{
    if(list == NULL)
        return;
    Node<T>* tmp = list;
    do{
        cout << tmp->data << "\t";
        tmp = tmp->right;
    }while(tmp != list);
    return ;
}               /* -----  end of function PrintDCList  ----- */
/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    Node<int> *root = new Node<int>(10);
    TreeInsert(root, 6);
    TreeInsert(root, 8);
    TreeInsert(root, 4);
    TreeInsert(root, 12);
    TreeInsert(root, 14);
    TreeInsert(root, 16);
    TreeInsert(root, 11);

    InorderTraverse(root);
    cout << endl;
    PreOrderTraverse(root);
    cout << endl;
    PostOrderTraverse(root);
    cout << endl;

    //Node<int>* list = BST2DList(root);
    //cout << "convertion result:" << endl;
    //PrintList(list);
    //cout << endl;

    Node<int>* dclist = BST2DCList(root);
    cout << "convertion result:" << endl;
    PrintDCList(dclist);
    cout << endl;
    return EXIT_SUCCESS;
}                               /* ----------  end of function main  ---------- */


在上述思路二中,提供了两种方法,即转换为普通双链表和带环双链表。
在普通双链表中,每次插入当前链表时需要遍历到链表尾端,耗时O(n);在带环双链表中,可以直接从头结点找到尾结点,耗时为
常数时间。

Reference

1.http://blog.csdn.net/v_JULY_v/article/details/6057286
2.http://cslibrary.stanford.edu/109/TreeListRecursion.html 

Posted in 算法, 技术 | Tagged: , | Leave a Comment »

SVN 使用笔记

Posted by ieipi 于 八月 31, 2011

1.设置svn:ignore 属性

svn会默认监测目录下的所有文件,这样当使用svn status时会遇到很多冗余信息。实际上,有很多文件,比如二进制文件,日志文件等是不需要加入svn 版本控制的。我们可以利用每个目录均有的svn:ignore属性来实现这一目的。
1)  设置.svnignore文件
在当前目录上新建.svnignore文件(文件名可行任意),并在其中编辑需要忽略的文件类型。例如

build/
dist/
*.class

2)  设置svn:ignore属性

svn propset svn:ignore –F .svnignore .

3)  其他
这种方法是局部设置,只对当前目录生效。还可以进行全局设置,对所有的svn workcopy均有效。

sudo vim /etc/subversion/config

找到global-ignores条目,在其后加上需要忽略的文件类型。

2.版本代码回滚

svn 本版库包含所有的历史信息,所以你可以回滚到任意历史版本。所有的修改可以看作是由一系列的修改及集组成。可以利用svn merge命令将一个或一组修改集应用当前工作拷贝。基本工作流程为:
1)    更新工作拷贝

svn update

2)    定位可疑目标

svn log test_rollback
svn diff –r 100:101 test_rollback

3)    撤销错误修改集

svn merge –r 101:100 test_rollback

4)    检查修改结果

svn diff test_rollback

5)    提交

svn commit –m"revert the wrong change from r101"

6)    其他
当提交更改后,r101的更改集已经从HEAD中删除。但是,r101版本仍然在版本库中。当直接从r101版本checkout时仍会得到错误更改。但是通常我们只对HEAD版本感兴趣,所以从HEAD删除已经足够好了。如果想从版本库中毁掉所有证据,并不容易。

Posted in 工具, 技术 | Tagged: | Leave a Comment »

悬挂指针(Dangling Pointer)

Posted by ieipi 于 五月 18, 2011

请看下段代码:

    int
main ( int argc, char *argv[] )
{
    unsigned int *pint = new unsigned int; 
    *pint = 5; 
    printf ( "before delete, pint = %p\n", pint );
    delete pint; 
    /*After delete the pointer, we should explicitly set it to NULL */
    /*pint = NULL; */
    printf ( "after delete, pint = %p\n", pint );

    long *plong = new long; 
    printf ( "plong = %p\n", plong );
    *plong = 10; 
    cout << "*pint = " << *pint << "; *plong = " << *plong  << endl; 
    *pint = 20; 
    cout << "*pint = " << *pint << "; *plong = " << *plong  << endl; 
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

其输出为:

before delete, pint = 0x8369008
after delete, pint = 0x8369008
plong = 0x8369008
*pint = 10; *plong = 10
*pint = 20; *plong = 20

分析
delete操作只是(让操作系统)解除pint和被分配的动态内存之间的关系.但是这块内存仍在,而且,该指针仍指向这块内存.像这种指向一块已经被释放的内存的指针被称为悬挂指针(dangling pointer).使用悬挂指针容易产生难以调试的运行时错误.
为了减少这种问题,可以在释放一个指针的内存后,强制将它赋值NULL.对NULL地址的操作会立即产生段错误.

Posted in 语言, 技术 | Tagged: , | Leave a Comment »

C 函数声明

Posted by ieipi 于 五月 15, 2011

国内有多少书声称函数必需先声明再调用? 比如<<程序员面试宝典>>P72例7. 那么实际情况呢?
Test 1: 同一个文件

int
main ( int argc, char *argv[] )
{
    double i1, i2;
    /*case 1: no declarations*/
    /*case 2: */
    //int fun1();
    /*case 3: */
    //double fun1();
    /*case 4: */
    //int fun1(int);
    i1 = fun1();
    i2 = fun1(i1);
    printf ( "i1=%d\n", i1);
    printf ( "i2=%d\n", i2);
    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */
fun1(int a, int b)
{
    double d = 3.1234567;
    printf ( "d=%.8f\n", d);
    return d;
}

结果:
case1 和 case2 输出结果相同,均为:

d=3.12345670
d=3.12345670
f1=3.00000000
f2=3.00000000

case3 和 case4 编译错误.
分析:
1).函数名是external object,默认具有全局(global)可见性. 函数原型声明只用于帮助编译器进行类型检查.
2).对于变量,编译器必需进行类型检查,所以必需”先声明后使用”.对于函数可以关闭类型检查(老版C 语言).
3).编译器如果遇到一个事先未声明的标示符,并且紧跟着一个左半括号(即形如”foo(“的语句),就把它默认处理为函数名.并且默认返回类型为int,形参表则不做任何假设.(即默认扩展为函数声明int foo();).
4).对于形参表为空的声明(例如 double atof(); ),编译器将关闭对形参表的类型检查,但是对于返回类型,仍将进行类型检查.
5).一个最简单的函数定义为:

foo() {}

问题:调用此函数的返回结果是多少?
Test 2: 两个文件

/*foo.c*/
foo()
{
    double d = 3.1234567; 
    printf ( "d=%.8f\n", d);
    return d; 
}
/* main.c*/
    int
main ( int argc, char *argv[] )
{
    double f1; 
    /* case 1: no declaration */
    f1 = foo(3, 4); 
    printf ( "f1 = %.8f\n", f1 );

    /* case 2: declaration */
    /*int foo(); */
    /*f1 = foo(); */
    /*printf ( "f1 = %.8f\n", f1 );*/

    /* actually incompatible prototype declaration. */
    /*double foo(int, int); */
    /*f1 = foo(3, 4); */
    /*printf ( "f1 = %.8f\n", f1 );*/

    return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

结果(编译时必需同时编译foo.c和main.c):
case1 和case2 的结果相同

d=3.12345670
f1 = 3.00000000

case3 的结果为:

d=3.12345670
f1 = -nan

分析:
1).编译器的编译检查只能局限在同一个源文件范围类,涉及到多个源文件的情况由连接器解决.
2).链接时只检查函数名,而不检查参数表和返回值(所以c中函数无法重载)
3).注意case3的结果输出为NaN,这是因为foo函数默认返回int型,而该int型的二进制表示恰好不符合浮点数的表示规则.
总结
1.”函数需要先声明后使用”,是一个好的编程规范,但并不是语言特性所要求的.
2.函数声明只用来帮助编译器进行类型检查.若函数定义和声明在同一个文件中,则可以检查定义,声明和调用是否匹配;
若定义和声明不在同一个文件,则只需函数声明和调用保持一致,并且与定义同名.

Posted in 语言, 技术 | Tagged: | Leave a Comment »

C Programming Language (1)

Posted by ieipi 于 四月 21, 2011

好吧,传说中的C语言圣经,我直到现在才看。然知耻而后勇,不亦乐乎!周末抢着看完了,不愧是经典,短小精悍,无以复简。

Chap0: History

本书初版于1978年,再版于1988,时至今日,日久弥新。
C语言由贝尔实验室的Dennis Ritchie于1969~1973年创建。C的名称由来是因为它从早期的B语言中借鉴很多特性。C语言与Unix的诞生相辅相成。1973年,Unix内核用C语言重写,从此一发而不可收拾。1978年,本书第一版诞生,成为C语言的非正式标准文档,被亲切地称为K&R。1983年,ANSI设立了一个专门委员会,致力于建立C标准。1989年,该标准发布,通常被称为ANSI C,或C Standard, 或C89。自此,C语言大致保持不变,1990年代陆续加入了少许新特性,这导致C99的诞生。

Chap1: Tutorial Introduction

Chap2:Types,Operators and Expressions

这些是程序设计语言的基本要素。

2.1 Variable Names

  1. 变量名由字母和数字组成,第一个字符不能是数字。下划线”_”也是字母,但是一般不用做变量的首字母,因为通常库函数会以下划线开头。
  2. 对于internal names,至少前31个字符是有效的;但是对于external names, the standard guarantees uniqueness only for 6 characters and a single case.(???) 。这是因为,外部变量可能会被汇编器和加载器用到,而语言对于这两者是无法控制的。

2.2 Data Types and Sizes

  1. C的语言类型基本为两种:整型和浮点型。前者包括char,short,int,long等,后者包括单精度和双精度。两种都包括有符号和无符号。
  2. C标准对于类型的大小没有明确的规定。编译器只需保证short和int至少16位,long至少32位并且short不大于int,int不大于long。
  3. 浮点类型数据大小同样与硬件平台有关。
  4. 标准库中的和包含相关信息。

2.3 Constants

  1. 字面整常量(literal integer constants, e.g. 1234)为(signed)int。加上后缀U和L后分别可表示unsigned和long。
  2. 字面浮点常量默认为double类型。可加后缀F表示float。
  3. 整形值可用八进制(037=31)或16进制(0x1F=037=31)表示。用这种表示法可以方便看出数值的二进制比特级位表示。
  4. 字符常量本质上是一个整型数值(numerical value)。但是其具体值由机器的character set 决定。采用’0’形式的字符表示,而不直接采用其对应的数值(48 in ASCII)一是因为可读性好,二是与特定字符集无关,增强可移植性。
  5. 某些特殊字符(无法显示)可以用转义序列表示。
  6. 字符串常量:以”/null/0结尾的字符数组。
  7. 枚举常量VS #define ???

2.4 Declarations

  1. 所有的变量在使用前都必须先申明(declared),但是有些声明可以根据上下文隐式地给出(???)。
  2. 初始化:对于external variable和static variable,会默认初始化为0;如果对其显示初始化,则该表达式必须是常量,并且初始化操作只在程序实际运行之前执行一次。 对于automatic variable,应该显性初始化,否则默认值是undefined garbage value。如果对其显性初始化,表达式可以是任意表达式,且初始化操作在程序每次进入该函数或块时都会执行一次。

2.5 Arithmetic Operations

  1. 对于负数,/(截断的方向)和%(余数的符号)运算的结果是与机器相关的。

2.6 Relational and Logical Operators

  1. 对于逻辑操作符&&和||,expressions are evaluated from left to right, and the evaluation stops as soon as the truth or falsehood of the result is known.

2.7 Type Conversions

  1. 当操作数涉及到不同数据类型时,需要进行类型转换。一般而言,低精度到高精度的转换(不会丢失信息) 会自动进行(没有warning?)。高精度到低精度会丢失信息,编译器会给出warning信息,但是不会报错,仍然合法。
  2. 对于char到int的转换,结果有无符号未定,与平台相关。
  3. 基本上算术运算中的隐式类型转换结果满足预期,但是涉及到无符号数时必须小心。这是因为signed与unsigned的比较与机器相关。例如-1L<1u(1u会首先转换成signed>1UL(-1L首先转换成unsigned long).(另据CSAPP2.2.5,如果一个运算数是有符号另一个是无符号,C语言会强制将有符号转换为无符号???)
  4. cast:强制类型转换,它是一个一元操作符,优先级属于第一级(最高一级)。
  5. 函数调用时的类型转换。

2.8 Increment and Decrement Operators

2.9 Bitwise Operators

  1. <<左移位操作的结果是确定的——低位补0;但是右移位>>的结果未定。逻辑右移高位补0,算术右移高位符号扩展。

2.10 Assignment Operators and Expressions

  1. “=”也是一个操作符,其运算结果是其左值执行完赋值操作以后的结果。

2.11 Conditional Expressions

  1. expr1 ? expr2:expr3是条件表达式,和其他表达式效果一样。特别的, int n = 1, float f = 1.0f, (n<0)>

2.12 Precedence and Order of Evaluation

  1. 运算符优先级及结合型如右图。
  2. C语言没有规定同一个运算符的多个操作数的求值顺序。例如x = f() + g()这个表达式中,f和g谁先被调用是不确定的。
  3. 函数的参数求值顺序也是未定的。例如:printf(“%d%d\n”,++n,power(2,n))的结果是未定的。

Chap3: Control Flow

Posted in 语言, 技术 | Tagged: | Leave a Comment »