汉诺塔的递归实现
汉诺塔问题简介: http://zh.wikipedia.org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94
其递归实现的函数原型为: 'void hanoi(int n, char a, char b, char c);'. 其中字符变量'a', 'b', 'c'分别表示从杆子a, 杆子b, 杆子c, 整数变量'n'表示汉诺塔问题的阶数(即杆子a上有n个待移动到杆子c的圆盘, 杆子b作为临时杆子).
其递归实现的步骤为:
1. 如果n==1, 则直接将唯一的圆盘从杆子a移动到杆子c, 问题解决.
2. 否则, 将杆子a上的(n-1)个圆盘移动到杆子b(通过递归实现),
然后将杆子a上剩余的最大的圆盘移动到杆子c,
最后将杆子b上的(n-1)个圆盘移动到杆子c(通过递归实现), 问题解决.
其递归实现的C代码为:
#include<stdio.h>
void hanoi(int, char, char, char);
int main(void)
{
int n=3;
printf("输入数字n:\n");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
void hanoi(int n, char a, char b, char c)
{
if(n==1) {
printf("%c->%c\n", a, c);
} else {
hanoi(n-1, a, c, b);
printf("%c->%c\n", a, c);
hanoi(n-1, b, a, c);
}
}
之前在笔试中遇到的, 记录一下.
C 数据类型转换
看一下段代码, 分析for循环的循环体会执行多少次:
#include<stdio.h>
int main(void)
{
int i;
for(i=-1; i < sizeof(int); i++) {
printf("%d, ", i);
}
return 0;
}
实验表明, 在不同的编译器下, 这个循环的实现也不一样:
1. 在gcc下, 由于'sizeof(int)'的返回值是'unsigned long int'类型的, 但'i'的类型是'signed int'类型的, 二者在做比较时要将i从'signed int'转换成'unsigned long int', 但由于i原来是有符号的'-1', 转换后变为无符号的'0xffffffff', 当然比'sizeof(int)'大, 结果for循环体一次也没有执行.
2. 在Turbo C下, 由于'sizeof(int)'的返回值是'signed int'类型的(注意: 这不符合C标准的规定), 所以与'i'比较是没有类型转换, for循环体会执行5次.
严重注意: 有些东西了解就行, 以便在出现问题时知道如何解决, 但尽量不要在自己的代码中尝试那些东西.
C语言 char型也是分有符号数和无符号数的
unsigned char型表示无符号数, 取值范围是 0~255.
signed char型表示无符号数, 取值范围是 -128~127.
在x86平台上, gcc规定不带'unsigned'或'signed'关键字的char是有符号的. 参见以下代码 :
#include<stdio.h>
int main(void)
{
printf("(signed char)200: %d\n", (signed char)200);
printf("(unsigned char)200: %d\n", (unsigned char)200);
printf("(char)200: %d\n", (char)200); // gcc定义char型是有符号的。
return 0;
}
打印结果为:
(signed char)200: -56
(unsigned char)200: 200
(char)200: -56
利用objdump工具对其进行反汇编, 观察向printf函数传递的第二个参数, 节选部分汇编代码:
printf("(signed char)200: %d\n", (signed char)200);
80483cd: b8 e0 84 04 08 mov $0x80484e0,%eax
80483d2: c7 44 24 04 c8 ff ff movl $0xffffffc8,0x4(%esp)
80483d9: ff
80483da: 89 04 24 mov %eax,(%esp)
80483dd: e8 12 ff ff ff call 80482f4 <printf@plt>
printf("(unsigned char)200: %d\n", (unsigned char)200);
80483e2: b8 f6 84 04 08 mov $0x80484f6,%eax
80483e7: c7 44 24 04 c8 00 00 movl $0xc8,0x4(%esp)
80483ee: 00
80483ef: 89 04 24 mov %eax,(%esp)
80483f2: e8 fd fe ff ff call 80482f4 <printf@plt>
printf("(char)200: %d\n", (char)200); // gcc定义char型是有符号的。
80483f7: b8 0e 85 04 08 mov $0x804850e,%eax
80483fc: c7 44 24 04 c8 ff ff movl $0xffffffc8,0x4(%esp)
8048403: ff
8048404: 89 04 24 mov %eax,(%esp)
8048407: e8 e8 fe ff ff call 80482f4 <printf@plt>
还有一个问题需要注意, 从汇编代码可以看到, 实际上用了四个字节存储char类型的参量, 即: 像printf这种形参类型未知的函数, 调用函数时编译器会自动对相应的实参做Integer Promotion.
C 数组下标'[ ]'运算符
C语言是通过数组下标来引用数组的, 我们这样定义一个有十个元素的整型数组:
int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
然后可以通过数组arr的下标对其元素进行引用:
a[0] = a[1]+a[2];
实际上, 数组下标'[ ]'是一种运算符, 程序中用下标法引用数组元素的代码, 最终都被编译器自动转化为指针进行运算, 也就是说, 'a[i]'和'*(a+i)'在编译器看来, 是完全等价的.
由此, 可以理解以下代码:
#include<stdio.h>
int main(void)
{
struct hi {
int a;
int b;
};
struct hi test;
test.a=1;
test.b=2;
printf("%d, %d\n", test.a, test.b);
/* 真正写代码时, 请不要这样用: */
printf("%d, %d\n", ((int*)(&test))[0], ((int*)(&test))[1]);
return 0;
}
打印结果为:
1, 2
1, 2
结构体和动态内存分配实现的单向列表结构
好像贴出这么多代码来现丑有些不合适,不过我是博主, 我说了算:
#include<stdio.h>
#include<stdlib.h>
struct one_way_list{
int data;
struct one_way_list *next_node_pt;
}*head, *tail; //定义结构体, 单向列表的一个结点.
int counter=0; //计数器
//添加数据：
int app_data(int data) {
if(counter==0){
head=tail=(struct one_way_list *)malloc(sizeof(struct one_way_list));
if(head==NULL){
return(-1);
}
(*head).data=data;
} else {
(*tail).next_node_pt=(struct one_way_list *)malloc(sizeof(struct one_way_list));
if((*tail).next_node_pt==NULL){
return(-1);
}
tail=(*tail).next_node_pt;
(*tail).data=data;
}
counter++;
return(1);
}
//某数据是否存在：
int exists(int data) {
if(counter==0){
return(-1);
} else {
int i=0;
struct one_way_list *pt=head;
do{
if((*pt).data==data) {
return(i);
}
i++;
pt=(*pt).next_node_pt;
}while(pt != tail);
return(-1);
}
}
//查看计数器:
int count(void) {
return(counter);
}
//查看列表头：
int head_data(void) {
if(counter==0){
return(-1);
} else {
return((*head).data);
}
}
//查看列表尾：
int tail_data(void) {
if(counter==0){
return(-1);
} else {
return((*tail).data);
}
}
//查看第i个数据：
int ith_data(int numth) {
if(counter==0 || numth<0 || numth >= counter){
return(-1);
} else {
int i=0;
struct one_way_list tmp;
tmp=*head;
for(i=0; i!=numth; i++){
tmp=*tmp.next_node_pt;
}
return(tmp.data);
}
}
// 删除所有数据:
int delete_all(void) {
struct one_way_list *pt=head;
while(counter!=0) {
pt=head;
head=(*head).next_node_pt;
free(pt);
counter--;
}
return(1);
}
// 删除第i个数据:
int delete_ith(int numth) {
if(counter==0 || numth<0 || numth>= counter) {
return(-1);
} else if(numth==0) {
struct one_way_list *pt=head;
head=(*head).next_node_pt;
free(pt);
return(1);
} else {
int i=0;
struct one_way_list *pt_pr=head;
struct one_way_list *pt=(*head).next_node_pt;
for(i=1; i!=numth; i++) {
pt_pr=(*pt_pr).next_node_pt;
pt=(*pt).next_node_pt;
}
(*pt_pr).next_node_pt=(*pt).next_node_pt;
free(pt);
if(numth==counter) {
tail=pt_pr;
}
return(1);
}
}
//用于测试的主函数：
int main(void) {
if(app_data(1) == -1){
printf("Error1");
}
printf("counter: %d\n",counter);
if(app_data(2) == -1){
printf("Error2");
}
printf("counter: %d\n",counter);
if(app_data(3) == -1){
printf("Error3");
}
printf("counter: %d\n",counter);
if(app_data(4) == -1){
printf("Error4");
}
printf("counter: %d\n",counter);
if(exists(1)>=0){
printf("exits 1: %dth,\n", exists(1));
} else {
printf("1 not exits\n");
}
if(exists(9)>=0){
printf("exits 9: %dth,\n", exists(9));
} else {
printf("9 not exits\n");
}
printf("count: %d\nhead: %d\ntail_data: %d\n", count(), head_data(), tail_data());
printf("2th data:%d\n", ith_data(2));
delete_all();
printf("Just delete All.\n");
if(app_data(7) == -1){
printf("Error7");
} else {
printf("7 added\n");
}
printf("counter: %d\n",counter);
if(app_data(6) == -1){
printf("Error6");
} else {
printf("6 added\n");
}
printf("counter: %d\n",counter);
if(app_data(5) == -1){
printf("Error5");
} else {
printf("5 added\n");
}
printf("counter: %d\n",counter);
if(delete_ith(1) == -1){
printf("1th deleted error\n");
} else {
printf("1th deleted\n");
}
printf("1th: %d\n",ith_data(1));
printf("head: %d\ntail: %d\n", head_data(), tail_data());
return(0);
}
