44_递归的思想与应用(中)
2018-07-17 本文已影响4人
编程半岛
关键词:单链表的转置、单向排序链表的合并、汉诺塔问题、全排列问题
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