C++ programming 高手请进来帮忙。

geekman

原帖由 1max1 于 19-9-2008 12:16 AM 发表

是咯，第一个printf会重复print 9次（1-9），因printnum(begin+1)funtion call。
但是第二个 printf 就没见得有任何repeat的funtion call，因该只是个9，怎么会从9 print 直1，9次。

你还是没弄明白 Recursive Function Call 是怎么一回事？

那你应该知道一般的 Function Call 是如何运作的吧？（不知道？我不感到意外，你的老师可能也不懂这些基础。。。现在的人都讲究速成。。。唉。。。）

当你呼叫一个 Function 时，你的程式会从现有运算流程“跳跃”（Jump，你如果有学过 Assembly language 就会知道所有的 Function call 都最后都会被 Compiler 编译成 jmp [address] 这个 Assembly Code）到你所呼叫 Function 的所在地址。当你呼叫的 Function 拥有 Arguments 的时候，它们会被“推”（push）进 stack 里面 - Stack 是一个记忆暂存区，相信又是一个你的老师没教的东西吧？ - 当进入 Function return 的时候，stack 里面的 Arguments 会被 Function “拉”（pull）回来。

当然这不是为何会出现 9-1 的原因。这里只是告诉你，recursive 的第一个最大隐藏陷阱。当你写出一个大量 recursive （比如说10000次 recursive call）的 program 时，你会把大量的数据推进 stack 里面，问题是，stack 是个容量十分小的暂存区，通常是几个 kilobyte 罢了。当你推进去的 Arguments 超过 stack 的容量，就会发生 stack overflow，电脑当机只是最轻的后果。

现在咱们来看看为何会出现 9-1 的问题。

首先，把你的程式解拆（unfold）开来，想象以下流程：

1. main()
   
2. |
   
3. |->calling printnum(0), begin = 0; calling first printf()
   
4.   |
   
5.   |->calling printnum(1), begin = 1; calling first printf()
   
6.     |
   
7.     |->calling printnum(2), begin = 2; calling first printf()
   
8.        |
   
9.        |->calling printnum(3), begin = 3; calling first printf()
   
10.          |
    
11.          |->calling printnum(4), begin = 4; calling first printf()
    
12.            |
    
13.            |->calling printnum(5), begin = 5; calling first printf()
    
14.              |
    
15.              |->calling printnum(6), begin = 6; calling first printf()
    
16.                |
    
17.                |->calling printnum(7), begin = 7; calling first printf()
    
18.                  |
    
19.                  |->calling printnum(8), begin = 8; calling first printf()
    
20.                    |
    
21.                    |->calling printnum(9), begin = 9;
    
22.                       since (begin < 9) == false， no more recursive call;
    
23.                       calling second printf() with begin = 9
    
24.                       |
    
25.                     function printnum(9) returns, back to begin = 8, calling second printf()
    
26.                     |                                                                                 
    
27.                   function printnum(8) returns, back to begin = 7, calling second printf()
    
28.                   |   
    
29.                 function printnum(7) returns, back to begin = 6, calling second printf()
    
30.                 |  
    
31.               function printnum(6) returns, back to begin = 5, calling second printf()
    
32.               |
    
33.             function printnum(5) returns, back to begin = 4, calling second printf()
    
34.             |
    
35.           function printnum(4) returns, back to begin = 3, calling second printf()
    
36.           |
    
37.         function printnum(3) returns, back to begin = 2, calling second printf()
    
38.         |
    
39.       function printnum(2) returns, back to begin = 1, calling second printf()
    
40.       |
    
41.     function printnum(1) returns, back to begin = 0, calling second printf()
    
42.     |
    
43. return to main()
    
44. |
    
45. End of Program.   

复制代码

这是recursive的另一个隐藏陷阱：argument pull from stack。我说过了，任何 function call，包括 recursive，都得收拾手尾的。

在你还没学会 program 如何运行，了解你的 program 的流程之前，为了你自己的安全，别使用 recursive，否则你会花费上百小时的时间寻找一个你百思不得其解的 bug。

[ 本帖最后由 geekman 于 19-9-2008 08:49 PM 编辑 ]

onlylonly

geekman ， 小弟真的不得不佩服你的耐心。

要我这样仔细写出整个的流程来解释我真的做不到。。

recursive call 在 call by value 上非常不推荐， 太浪费记忆体了。

每一次recursive call， 就必须复制出另一份variable 出来。 100 次 recursive 就要多复制100 份 variable。 overflow 是就够力了。

在 pass by reference 还可以考虑。

[ 本帖最后由 onlylonly 于 19-9-2008 06:14 PM 编辑 ]

geekman

为了让新手们能够了解整个流程和其中的危险性，没办法了

不过也幸好这个program不是很复杂，不然我也不会有耐心去写出整个流程。。。

geekman

原帖由 1max1 于 19-9-2008 11:38 AM 发表


pointer是address不是value，做么不直接newPtr->nextPtr =  newPtr;，previousPtr->nextPtr = currentPtr;？

newPtr->nextPtr = newPtr? 你是想做一个 deadlock link 吗？

如果想象，link list 就好像一群兄弟，previousPtr 就是哥哥，而nextPtr就是弟弟，如果小明就是 newPtr，
那么：小明的弟弟 = 小明？？

[ 本帖最后由 geekman 于 19-9-2008 09:01 PM 编辑 ]

糯米鸡

原帖由 geekman 于 19-9-2008 12:42 PM 发表


当你呼叫一个 Function 时，你的程式会从现有运算流程“跳跃”（Jump，你如果有学过 Assembly language 就会知道所有的 Function call 都最后都会被 Compiler 编译成 jmp [address] 这个 Assembly Code）到你所呼叫 Function 的所在地址。当你呼叫的 Function 拥有 Arguments 的时候，它们会被“推”（push）进 stack 里面 - Stack 是一个记忆暂存区，相信又是一个你的老师没教的东西吧？ - 当进入 Function return 的时候，stack 里面的 Arguments 会被 Function “拉”（pull）回来。

是call， 不是jmp

geekman

我说的是 assembly code
p/s: 我以前学的Assembly language 是Motorola 68000的，Intel 的没学过。当calling subroutine 时，function call 会被 unfold 为：

[calling address]
push [value],[stack pointer]
jmp [routine address]
...
(upon return)
jmp [calling address + 1]
pull [value],[stack pointer]
...

以上的是 pseudo code，太久没写 assembly 了，很多细节都忘了。

[ 本帖最后由 geekman 于 19-9-2008 09:18 PM 编辑 ]

糯米鸡

原帖由 geekman 于 19-9-2008 09:02 PM 发表
我说的是 assembly code
p/s: 我以前学的Assembly language 是Motorola 68000的，Intel 的没学过。当calling subroutine 时，function call 会被 unfold 为：

[calling address]
push [value],[stack pointer]
...

x86的是用call。jmp是单程的， 一jmp后就不能return回去caller那里。call会把caller的execution pointer放在stack里面， 然后ret(return)会用这个跑回去caller那里。

1max1

楼上两位不要请说这么深的东西。

晨天

深东西好呀， 可以学更多东西

geekman和糯米鸡 网友

你们 或 联合其他网有 可以开一个贴叫
＂老师没有教的东西＂

可以把所有lower level language and concept的东西放下去
或 programmer常犯的mistake
或 如何掌握problem solving skill
或 前途茫茫的大学IT生
等等...

1max1

很好！到时记得留个位给我，

liverpool07

我觉得在论坛里学这种相当初级的C programming 是很不effective的.
建议找个好老师详细给你讲两个小时的效果会更好.

tensaix2j

原帖由 糯米鸡 于 19-9-2008 09:25 PM 发表
x86的是用call。jmp是单程的， 一jmp后就不能return回去caller那里。call会把caller的execution pointer放在stack里面， 然后ret(return)会用这个跑回去caller那里。

这个我也有听说过。。
而且， 在function 里搞 buffer overflow的话 ，还可能把这个 return address overwrite掉， ret 后，搞到eip不懂指到哪里去。。 应该就是俗称的stack overflow吧。。

[ 本帖最后由 tensaix2j 于 21-9-2008 09:36 PM 编辑 ]

tensaix2j

原帖由 晨天 于 20-9-2008 02:30 PM 发表
深东西好呀， 可以学更多东西

geekman和糯米鸡 网友

你们 或 联合其他网有 可以开一个贴叫
＂老师没有教的东西＂

可以把所有lower level language and concept的东西放下去
或 programmer常犯的mistake
...

这位仁兄不是搞数学的吗？
什么风又把你吹到这边来。。。

晨天

原帖由 tensaix2j 于 21-9-2008 09:37 PM 发表

这位仁兄不是搞数学的吗？
什么风又把你吹到这边来。。。

如果天下武功出于少林
那么世界科技出于数理。。。。。。。。

我的正业是电脑
副业有搞 科学逻辑 天文地理 人文哲理 玄学术伦
全部都有一点点研究

~Lucifer~

上个sem才有拿structre and althorigm这科，里面讨论的都是c programming 的structre的各种用法，虽然有拿A，可是楼上几位讨论的已经超越我水准了。Malloc这东西我是死死记下来。这个sem学了assembly language过后，第一次了解到原来c programming是那么的user friendly，最少你电脑只需要有compiler去make sure你做的东西是对的，不必去了解其他的东西了。Assembly language还有去找microcontoller的stimulator，然后还要了解microcontoller的构照(internal ram,timer等等)，combine hardware和software，才可以写出assembly code。只不过好像过时很久了

[ 本帖最后由 ~Lucifer~ 于 22-9-2008 12:33 AM 编辑 ]

1max1

原帖由 ~Lucifer~ 于 22-9-2008 12:13 AM 发表
上个sem才有拿structre and althorigm这科，里面讨论的都是c programming 的structre的各种用法，虽然有拿A，可是楼上几位讨论的已经超越我水准了。Malloc这东西我是死死记下来。这个sem学了assembly language过 ...

你读那间学院？想来你学院报名。

~Lucifer~

原帖由 1max1 于 22-9-2008 12:34 AM 发表

你读那间学院？想来你学院报名。

欢迎欢迎 。现在在MMU拿着工程系，这里的工程系主要是专注在hardware的东西，programming很少吧了，拿了17科只有2科programming，也很容易score  ，你要专注在programming的话那么读IT系比较好，这里也有提供。

~Lucifer~

原帖由 geekman 于 19-9-2008 09:02 PM 发表
我说的是 assembly code
p/s: 我以前学的Assembly language 是Motorola 68000的，Intel 的没学过。当calling subroutine 时，function call 会被 unfold 为：

[calling address]
push [value],[stack pointer]
...

恰恰相反，我学的是intel uc of 8051 family ，多2个礼拜大考了。考完试好想自己design一些circuit来玩，觉得很有趣，第一次接触到hardware和software可以combine在一起的东西。只不过哥哥说assembly 已经过时了 ，因为有的uc已经可以support visual basic了，连c都不用。

1max1

原帖由 ~Lucifer~ 于 22-9-2008 03:22 AM 发表


欢迎欢迎 。现在在MMU拿着工程系，这里的工程系主要是专注在hardware的东西，programming很少吧了，拿了17科只有2科programming，也很容易score  ，你要专注在programming的话那么读IT系比较好，这里也有提供 ...

吾拿Computer Study的。

1max1

void AddQueue(Item_type item, Queue_type *queue_ptr)
{
    if (queue_ptr->count >= MAXQUEUE)
      Error(“Queue is full”);
            else
              {
        queue_ptr->count++;
queue_ptr->rear = (queue_ptr-> rear + 1) % MAXQUEUE;
queue_ptr->entry[queue_type->rear] = item;
      }
}

如queue_ptr->rear是0， MAXQUEUE是3：
queue_ptr->rear =（0+1）% 3；
                           = 0.333333

如queue_ptr->rear是1， MAXQUEUE是3：
queue_ptr->rear =（1+1）% 3；
                           = 0.666666

如果在array里 0.333333是1，
queue_ptr->entry[1]=item;
但0.666666也会变成1吗？