44_递归的思想与应用（中）

关键词：单链表的转置、单向排序链表的合并、汉诺塔问题、全排列问题

0. 单链表的转置

/* 单链表的递归转置 */
struct Node_R
{
    int value;
    Node_R* next;
};

Node_R* create_list(int v, int len)
{
    Node_R* ret = NULL;
    Node_R* slider = NULL;

    for(int i=0; i<len; ++i)
    {
        Node_R* n = new Node_R();

        n->value = v++;
        n->next = NULL;

        if( slider == NULL )
        {
            slider = n;
            ret = n;
        }
        else
        {
            slider->next = n;
            slider = slider->next;
        }
    }

    return ret;
}

void print_list(Node_R* list)
{
    for(Node_R* node=list; node != NULL; node=node->next)
    {
        cout << node->value << "-->";
    }
    cout << "NULL" << endl;
}

void destory_list(Node_R* list)
{
    while(list != NULL)
    {
        Node_R* del = list;

        list = list->next;

        delete del;
    }
}

Node_R* reverse_list(Node_R* list)
{
    if( (list == NULL) || (list->next == NULL) )
    {
        return list;
    }
    else
    {
        Node_R* gurad = list->next;
        Node_R* ret = reverse_list(list->next);
        gurad->next = list;
        list->next = NULL;

        return ret;
    }
}

void test_list_r()
{
    Node_R* list = create_list(1, 5);

    print_list(list);

    Node_R* r_list = reverse_list(list);

    print_list(r_list);

    destory_list(r_list);
}

1. 单向排序链表的合并

Node_R* list_merge(Node_R* list1, Node_R* list2)
{
    if( list1 == NULL )
    {
        return list2;
    }
    else if(list2 == NULL )
    {
        return list1;
    }
    else if( list1->value < list2->value )
    {
//        Node_R* list1_ = list1->next;
//        Node_R* list = list_merge(list1_, list2);

//        list1->next = list;

//        return list1;
        // 用逗号表达式优化上面的代码
        return (list1->next = list_merge(list1->next, list2),
                list1);
    }
    else
    {
//        Node_R* list2_ = list2->next;
//        Node_R* list = list_merge(list2_, list1);

//        list2->next = list;

//        return list2;
        // 用逗号表达式优化上面的代码
        return (list2->next = list_merge(list1, list2->next),
                list2);
    }
}

2. 汉诺塔问题

问题描述

问题分解：

• 将n-1个木块借助C柱由A柱移动到B柱
• 将最底层的唯一木块直接移动到C柱
• 将n-1个木块借助A柱由B柱移动到C柱

/*
    汉诺塔问题
    a:起始地址
    b:中转站
    c:终止地址
 */
void hanoi_tower(int n, char a, char b, char c)
{
    if( n == 1 )
    {
        cout << a << "-->" << c << endl;
    }
    else
    {
        hanoi_tower(n-1, a, c, b);
        hanoi_tower(1, a, b, c);
        hanoi_tower(n-1, b, a, c);
    }
}

void test_hanoi_tower()
{
    hanoi_tower(3, 'a', 'b', 'c');
}

3. 全排列问题

/* 全排列问题 */
void permutation(char* s, char* e)
{
    if( *s == '\0' )
    {
        cout << e << endl;
    }
    else
    {
        int len = strlen(s);

        for(int i=0; i<len; ++i)
        {
            if( (i == 0) || (s[0] != s[i]) )
            {
                swap(s[0], s[i]);
                permutation(s+1, e);
                swap(s[0], s[i]);
            }
        }
    }
}

void test_permutation()
{
    char s[] = "abc";

    permutation(s, s);
}

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4