精华内容
下载资源
问答
  • #define N 10000 int a[N],b[N]; input(a,b); void input(int *p,int *q) ... n能不能传给下一个递归,不能的话就把n写进函数后面括号去 ... 可是我都试过了,不行,这...用递归怎么搞,且指针表达,不是调用函数数组
  • GC 原本一种“释放怎么都无法被引用的对象的机制”。那么人们自然而然地就会想到,可以让所有对象事先记录下“有多少程序引用自己”。让各对象知道自己的“人气指 数”,从而让没有人气的对象自己消失,这就是引用...

    GC 原本是一种“释放怎么都无法被引用的对象的机制”。那么人们自然而然地就会

    想到,可以让所有对象事先记录下“有多少程序引用自己”。让各对象知道自己的“人气指 数”,从而让没有人气的对象自己消失,这就是引用计数法(Reference Counting),它是 George E. Collins

    于 1960 年钻研出来的。

    引用计数法中引入了一个概念,那就是“计数器”。在对象头中增加了一个计数器属性,用来标识对象的被引用数量,也就是有多少程序引用了这个对象。

    本文代码使用C语言实现

    名词解释

    对象

    对象在GC的世界里,代表的是数据集合,是垃圾回收的基本单位。

    指针

    可以理解为就是C语言中的指针(又或许是handle),GC是根据指针来搜索对象的。

    mutator

    这个词有些地方翻译为赋值器,但还是比较奇怪,不如不翻译……mutator 是 Edsger Dijkstra 琢磨出来的词,有“改变某物”的意思。说到要改变什么,那就是 GC 对象间的引用关系。不过光这么说可能大家还是不能理解,其实用一句话概括的话,它的实体就是“应用程序”。

    mutator的工作有以下两种:生成对象

    更新指针mutator 在进行这些操作时,会同时为应用程序的用户进行一些处理(数值计算、浏览网页、编辑文章等)。随着这些处理的逐步推进,对象间的引用关系也会“改变”。伴随这些变化会产生垃圾,而负责回收这些垃圾的机制就是 GC。

    GC ROOTS

    GC ROOTS就是引用的起始点,比如栈,全局变量

    堆(Heap)

    堆就是进程中的一段动态内存,在GC的世界里,一般会先申请一大段堆内存,然后mutatar在这一大段内存中进行分配

    1460000022062600

    活动对象和非活动对象

    活动对象就是能通过mutatar(GC ROOTS)引用的对象,反之访问不到的就是非活动对象。

    准备工作

    在引用计数算法中,使用空闲链表(free-list)的内存分配策略

    空闲链表(free-list)内存分配

    空闲链表分配使用某种数据结构(一般是链表)来记录空闲内存单元的位置和大小,该数据结构即为空闲内存单元的集合。

    在需要分配内存时,顺序遍历每一个内存单元,找到第一个空闲的内存单元使用。

    在本文中,为了降低复杂度,只使用了最基本的free-list分配法,free-list数据结构如下图所示:

    1460000022062601

    为了实现简单,在本文代码中,每个单元只存储一个对象,不考虑单元拆分合并等问题。

    数据结构设计

    首先是对象类型的结构:

    为了动态访问“对象”的属性,此处使用属性偏移量来记录属性的位置,然后通过指针的计算获得属性typedef struct class_descriptor {

    char *name;//类名称

    int size;//类大小,即对应sizeof(struct)

    int num_fields;//属性数量

    int *field_offsets;//类中的属性偏移,即所有属性在struct中的偏移量

    } class_descriptor;

    然后是对象的结构,虽然C语言中没有继承的概念,但是可以通过共同属性的struct来实现:typedef struct _object {

    class_descriptor *class;//对象对应的类型

    int ref_cnt;//对象被引用的次数,"人气"

    } object;

    //继承

    //"继承对象"需和父对象object基本属性保持一致,在基本属性之后,可以定义其他的属性

    typedef struct emp {

    class_descriptor *class;//对象对应的类型

    int ref_cnt;//对象被引用的次数,"人气"

    int id;

    dept *dept;

    } emp;

    free-list结构设计struct _node {

    node *next;

    byte used;//是否使用

    int size;//单元大小

    object *data;//单元中的数据

    };

    有了基本的数据结构,下面就可以进行算法的实现了,以下执行GC前堆的状态图:

    1460000022062602

    算法实现

    在其他回收算法中,没有空闲内存分配时会调用GC,回收那些已经时垃圾的对象内存。

    然而在引用计数算法中并没有明确启动GC的地方。引用计数算法与mutator的执行关联性强,在mutator的处理过程中通过计数器的更新来进行内存管理;算是一种“实时”垃圾回收算法

    引用计数算法中,有两种情况会更新对象的计数器,分别是创建对象/更新对象引用

    创建对象&内存分配

    和标记-清除算法一样,需要先找到空闲的内存单元node *find_idle_node() {

    for (next_free = head; next_free && next_free->used; next_free = next_free->next) {}

    //还找不到就触发回收

    if (!next_free) {

    gc();

    }

    for (next_free = head->next; next_free && next_free->used; next_free = next_free->next) {}

    //再找不到真的没了……

    if (!next_free) {

    printf("Allocation Failed!OutOfMemory...\n");

    abort();

    }

    }

    然后在找到的空闲内存单元中分配新对象,并初始化object *gc_alloc(class_descriptor *class) {

    if (!next_free || next_free->used) {

    find_idle_node();

    }

    //赋值当前freePoint

    node *_node = next_free;

    //新分配的对象指针

    //将新对象分配在free-list的节点数据之后,node单元的空间内除了sizeof(node),剩下的地址空间都用于存储对象

    object *new_obj = (void *) _node + sizeof(node);

    new_obj->class = class;

    //初始化计数器

    new_obj->ref_cnt = 0;

    _node->used = TRUE;

    _node->data = new_obj;

    _node->size = class->size;

    for (int i = 0; i < new_obj->class->num_fields; ++i) {

    //*(data **)是一个dereference操作,拿到field的pointer

    //(void *)o是强转为void* pointer,void*进行加法运算的时候就不会按类型增加地址

    *(object **) ((void *) new_obj + new_obj->class->field_offsets[i]) = NULL;

    }

    next_free = next_free->next;

    return new_obj;

    }

    更新对象引用

    更新对象引用,就是将对象引用的对象将A更新为B,obj->ref_a = b/**

    * 修改引用

    * @param ptr 原指针,这个指针是引用的指针,pointer of pointer

    * @param obj 新对象指针

    */

    void gc_update_ptr(object **ptr, void *obj) {

    inc_ref_cnt(obj);

    dec_ref_cnt(*ptr);

    *ptr = obj;

    }

    虽然在 mutator 更新指针时程序会执行此函数,但事实上进行指针更新的只有最后一哈昂行的 *ptr = obj 部分,其他是进行内存管理的代码

    inc_ref_cnt是对指针 ptr 新引用的对象(obj)的计数器进行增加操作void inc_ref_cnt(object *obj) {

    if (!obj) {

    return;

    }

    obj->ref_cnt++;

    }

    dec_ref_cnt是对指针 ptr 之前引用的对象(*ptr)的计数器进行减少操作void dec_ref_cnt(object *obj) {

    if (!obj) {

    return;

    }

    obj->ref_cnt--;

    //如果计数器为0,则对象需要被回收,那么该对象引用的对象计数器都需要减少

    if (obj->ref_cnt == 0) {

    for (int i = 0; i < obj->class->num_fields; ++i) {

    dec_ref_cnt(*((object **) ((void *) obj + obj->class->field_offsets[i])));

    }

    //回收

    reclaim(obj);

    }

    }

    在dec_ref_cnt方法中,首先对引用指针原有的引用对象计数器进行减少的操作。如果计数器减少后为0,则该对象不可达了,没有任何引用成了垃圾,需要被回收。

    因为对象即将被回收,所以需要对这个对象所有的引用对象计数器也进行减少操作,并递归执行该逻辑。

    以上就是对引用计数算法的说明

    优点

    可以及时回收垃圾,当对象的计数器为0时,对象就会被回收;由于单次回收的对象单一,所以mutator需要暂停的时间会很短,对应用造成的影响比较小;在此算法中不用遍历对象图来查找存活对象

    缺点

    每次对象关系变化,都需要更新计数器,更新过于频繁;处理循环引用时较为麻烦(有些资料上说引用计数无法处理循环引用不太严谨,结合部分标记-清除算法就可以解决此问题)

    循环引用的例子:

    1460000022063257

    上图中,两个对象互相引用,计数器都为1;但对于GC ROOT都是不可达的,实际上应该是两个非存活对象,但由于互相引用,所以也会无法回收

    完整代码

    相关文章

    参考《垃圾回收的算法与实现》 中村成洋 , 相川光 , 竹内郁雄 (作者) 丁灵 (译者)

    《垃圾回收算法手册 自动内存管理的艺术》 理查德·琼斯 著,王雅光 译

    展开全文
  • C语言递归算法是怎么执行的<span style="font-size:12px;">#include <stdio.h> void net(int); int main() { net(1); return 0; } void net(int n) { printf("数字%d:n的地址是:%p\n", n, &...

    C语言递归算法是怎么执行的

    <span style="font-size:12px;">#include <stdio.h>
    
    void net(int);
    
    int main()
    {
    	    net(1);
    	    return 0;
    }
    
    void net(int n)
    {
    	    printf("数字%d:n的地址是:%p\n", n, &n);
    	    if(n<4)
    	    {
    		        net(n+1);
    		        printf("数字%d:n的地址是:%p\n", n, &n);
    	    }
    }</span>
    递归就是自己调用自己,例如你写的 net()函数,函数自己调用自己。
    它调用自己的时候,不管程序运行到了哪,见到自己直接跳转,进入到下一个自己中运行,直到不满足跳入下一个自己的条件时,运行完当前函数,然后回到前一个自己中,回到跳
    出位置,继续运行没有完事的部分,直到完成当前函数,然后回到上一个自己。。。。这样直到回到第一个自己,运行开始跳出时没有完成部分的程序。这就是递归;

    转载于:https://www.cnblogs.com/mingrigongchang/p/6246286.html

    展开全文
  • 递归调用

    2015-08-21 11:03:20
    可能有好多人会认为指针比较难,其实不是如此,指针只不过是C语言的一个语法概念,但是想理解递归却需要非常多的知识,下面咱们就来看看什么导致了递归调用那么难。 我给递归调用的理解分三个阶段。 1.透彻理解...

    C语言里最难的就是递归调用了。可能有好多人会认为指针比较难,其实不是如此,指针只不过是C语言的一个语法概念,但是想理解递归却需要非常多的知识,下面咱们就来看看是什么导致了递归调用那么难。

    我给递归调用的理解分三个阶段。

    1.透彻理解函数传参

    2.理解运行栈的机制

    3.把递归调用当成树来理解

    我带过的好多学生在学完C语言之后对函数传参都不怎么理解,也就是说大部分学生在大一大二甚至大三的时候都不怎么理解函数传参。

    至于运行栈,那跟不用说了,大部分学生都没听过这个概念。

    这两点都可以通过学习汇编语言来提高。

    至于第三点又需要一点数据结构树的概念,因此可以看出,想要完全理解递归是需要额外花费很多时间的。

    那么这篇文章就简单讲解一下这三点,希望对大家有所帮助。

    第一点,C语言里有值传递和指针传递两种参数传递方法,但本质上是相同的,即他们都是值传递。那么既然只有一种传递,如何能够学的透彻呢,这就必须靠调试来帮忙了,通过反复的看内存,慢慢的建立起一种概念,自然会理解为什么只有值传递。

    下面以两个例子稍作说明:

    void swap(int a, int b)
    {
    int tmp;
    tmp = a;
    a   = b;
    b   = tmp;
    },


    int main()
    {
    int a = 3;
    int b = 4;
    swap(a,b);


    return 0;
    }
    是研究值传递的一个极好的例子,为了理解的透彻,咱们说下运行栈,理解起来可以这样认为,运行栈是栈,是函数调用时将整个函数压栈和出栈的一种机制。


    记住一点,参数属于主调函数的栈,那么如何区分哪里是主调函数的栈和被调函数的栈呢,很容易,就看汇编代码里面哪里出现call 指令哪里就是分界线。

    先看看运行栈的大致样子



    再看看实际的内存中是什么样子的。




    这里有一句话,大家一定要记住:形参是实参的拷贝或者叫副本。

    从上图中可以看出,实参和形参的值是一样的但是所处的位置不同,而swap函数交换的是形参的值,和实参没有关系的。

    如果是指针传递呢

    void swap(int *p, int *q)
    {
    int tmp;
    tmp = *p;
    *p   = *q;
    *q   = tmp;
    }

    int main()
    {
    int a = 3;
    int b = 4;
    swap(&a,&b);

    return 0;
    }

    大家可以做个试验,这时传递的是a和b的地址,也就是说入栈的是a和b的地址。那么形参拿着地址就能取得主函数中a和b的值,进行交换自然也就能交换成功。


    第二点在第一点里基本上都说清楚了。

    说下第三点:有些情况下把递归当做树来理解是个不错的选择。

    int fn(int n)

    {
    if(n == 1)
    return 1;
    else
    return n*fn(n-1);
    }

    int main()
    {
    int b = fn(4);


    return 0;
    }

    这个可以理解成一颗下图的树:



    再看一个例子

    int fn(int n)     
    {
        if (n <= 1)
            return n;
        else
            return fn(n-1) + fn(n-2);
    }


    int main()
    {
    int b = fn(4);


    return 0;
    }

    这一个的图可以画成这样



    也就是说递归调用中调用自己一次那么就是一个单节点的树,调用自己两次,每个节点就有两个分支,调用自己三次,每个节点就有三个分支。

    当然过程是一个后续遍历树(不确定,我也搞不清楚),但是如果能把后续遍历直接看成层次遍历,我想你理解递归就容易的多了。


    愿大家早早脱离递归的苦海。。。。


    展开全文
  • C语言编程要点

    2017-09-18 00:10:37
    11.1. 如果我运行的程序挂起了,应该怎么办? 152 11.2. 如何检测内存漏洞(leak)? 157 11.3. 调试程序的最好方法什么? 158 11.4. 怎样调试TSR程序? 163 11.5. 怎样获得一个能报告条件失败的程序? 164 第12章 标准...
  • 首先看递归实现,由于递归将问题逐级分解,因此相对比较容易理解,但是需要消耗大量的栈空间,如果线程栈空间不够,那么就运行不下去了,而且函数调用开销也比较大。(1) 全排列:全排列表示把集合中元素的所有按照...

    首先看递归实现,由于递归将问题逐级分解,因此相对比较容易理解,但是需要消耗大量的栈空间,如果线程栈空间不够,那么就运行不下去了,而且函数调用开销也比较大。

    (1) 全排列:

    全排列表示把集合中元素的所有按照一定的顺序排列起来,使用P(n, n) = n!表示n个元素全排列的个数。

    例如:{1, 2, 3}的全排列为:

    123;132;

    213;231;

    312;321;

    共6个,即3!=321=6。

    这个是怎么算出来的呢?

    首先取一个元素,例如取出了1,那么就还剩下{2, 3}。

    然后再从剩下的集合中取出一个元素,例如取出2,那么还剩下{3}。

    以此类推,把所有可能的情况取一遍,就是全排列了,如图:

    116287456_1_20171115103748480.png

    知道了这个过程,算法也就写出来了:

    将数组看为一个集合,将集合分为两部分:0~s和s~e,其中0~s表示已经选出来的元素,而s~e表示还没有选择的元素。

    perm(set,s,e){顺序从s~e中选出一个元素与s交换(即选出一个元素)调用perm(set,s+1,e)直到s>e,即剩余集合已经为空了,输出set}

    c语言代码如下:

    voidperm(intlist[],ints,inte,void(*cbk)(intlist[])){inti;if(s>e){(*cbk)(list);}else{for(i=s;i<=e;i++){swap(list,s,i);perm(list,s+1,e,cbk);swap(list,s,i);}}}

    其中:

    voidswap(int*o,inti,intj){inttmp=o[i];o[i]=o[j];o[j]=tmp;}voidcbk_print(int*subs){printf("{");for(inti=0;i

    (2)组合:

    组合指从n个不同元素中取出m个元素来合成的一个组,这个组内元素没有顺序。使用C(n, k)表示从n个元素中取出k个元素的取法数。

    C(n, k) = n! / (k! * (n-k)!)

    例如:从{1,2,3,4}中取出2个元素的组合为:

    12;13;14;23;24;34

    方法是:先从集合中取出一个元素,例如取出1,则剩下{2,3,4}

    然后从剩下的集合中取出一个元素,例如取出2

    这时12就构成了一个组,如图。

    116287456_2_20171115103748714.png

    从上面这个过程可以看出,每一次从集合中选出一个元素,然后对剩余的集合(n-1)进行一次k-1组合。

    comb(set,subset,n,k){反向从集合中选出一个元素,将这个元素放入subset中。调用comb(set,subset,n-1,k-1)直到只需要选一个元素为止}

    C语言代码如下:

    voidcombine(ints[],intn,intk,void(*cbk)(int*subset,intk)){if(k==0){cbk(subset,k);return;}for(inti=n;i>=k;i--){subset[k-1]=s[i-1];if(k>1){combine(s,i-1,k-1,cbk);}else{cbk(subset,subset_length);}}}

    任何递归算法都可以转换为非递归算法,只要使用一个栈模拟函数调用过程中对参数的保存就行了,当然,这样的方法没有多少意思,在这里就不讲了。下面要说的是用其它思路实现的非递归算法:

    (1)全排列:

    首先来看一段代码:

    #include#includeusingnamespacestd;intmain(){intmyints[]={1,2,3};cout<

    这段代码是从STL Permutation上考下来的,要注意的是第10行,首先对数组进行了排序。

    第14行的next_permutation()是STL的函数,它的原理是这样的:生成当前列表的下一个相邻的字典序列表,里面的元素只能交换位置,数值不能改变。

    什么意思呢?

    123的下一个字典序是132,因为132比123大,但是又比其他的序列小。

    算法是:

    (1) 从右向左,找出第一个比右边数字小的数字A。

    (2) 从右向左,找出第一个比A大的数字B。

    (3) 交换A和B。

    (4) 将A后面的串(不包括A)反转。

    就完成了。

    好,现在按照上面的思路,写出next_permutation函数:

    templateboolnext_perm(T*start,T*end){//_asm{int 3}if(start==end){returnfalse;}else{T*pA=NULL,*pB;T tmp=*end;// find A.for(T*p=end;p>=start;p--){if(*p=start;p--){if(*p>*pA){pB=p;break;}}// swap A, B.tmp=*pA;*pA=*pB;*pB=tmp;// flip sequence after Afor(T*p=pA+1,*q=end;p

    (2)组合:01交换法

    使用0或1表示集合中的元素是否出现在选出的集合中,因此一个0/1列表即可表示选出哪些元素。

    例如:[1 2 3 4 5],选出的元素是[1 2 3]那么列表就是[1 1 1 0 0]。

    算法是这样的:

    comb(set,n,k){(1)从左到右扫描0/1列表,如果遇到“10”组合,就将它转换为”01”.(2)将上一步找出的“10”组合前面的所有1全部移到set的最左侧。(3)重复(1)(2)直到没有“10”组合出现。}

    代码如下:

    templatevoidcombine(Tset[],intn,intk,void(*cbk)(Tset[])){unsignedchar*vec=newunsignedchar[n];T*subset=newT[k];// build the 0-1 vector.for(inti=0;i

    至于其中的道理,n个位置上有k个1,按照算法移动,可以保证k个1的位置不重复,且覆盖n一遍。

    展开全文
  • 二叉树的创建及初始化 ...还有一个问题,在创建二叉树的时候,大部分算法都递归实现,实现起来简单,然而系统运行起来却很吃力,很占用系统资源。当我们在建立好二叉树之后我们需要频繁的查找某个单元,就得频.
  • 我觉得大家对于二叉树不平衡时的四种情况,以及要怎么调整为平衡二叉树应该都明白的,大家最疑惑的应该是运行程序时如何判断平衡因子不平衡。所以我在此着重讲解一下这个问题,此程序借助递归实现的,当插入的数据...
  • c语言,建立无向图进行广度优先遍历但是...这出问题的运行结果![图片说明](https://img-ask.csdn.net/upload/201906/30/1561872516_966750.png)https://img-ask.csdn.net/upload/201906/30/1561872516_966750.png
  • 探究:一个数据包在网络中到底是怎么游走的? 硬不硬你说了算!全图解被问千百遍的TCP三次握手和四次挥手面试题 硬核!30 张图解 HTTP 常见的面试题 如果面试再问GET和POST区别,就把这篇甩给他 计网 TCP/UDP 部分...
  • 2、 编写并调试一个求(n为整数)的递归函数,希望能在程序运行过程中动态地显示递归函数被调用的轨迹。 [分析讨论] 1、 针对以上实验内容写出相应的参数传递过程并分析结果。 2、 讨论参数的传递的几种形式。 ...
  • 11.1 如果我运行的程序挂起了,应该怎么办? 11.2 如何检测内存漏洞(leak)? 11.3 调试程序的最好方法什么? 11.4 怎样调试TSR程序? 11.5 怎样获得一个能报告条件失败的程序? 第12章 标准库函数 ...
  • VB课程设计俄罗斯方块

    热门讨论 2011-02-25 10:46:55
    然后将展示的形状复制到游戏窗体中进行摆放,在游戏窗体中用户就可以使用键盘的方向键来控制方块的运动,然后利用递归语句对每一行进行判断,如果有某行的方块满的,则消除这行的方块,并且使上面的方块自由下落,...
  • 易学C++,C++入门

    2009-12-06 14:30:11
     6.2.3 函数如何运行的   6.2.4 返回语句——return   6.2.5 关于主函数   6.2.6 同名同姓——参数定义   6.2.7 函数存在的意义   6.3 多功能“开瓶器”——函数重载   6.4 自动的“工具”  ...
  • 1 理解计算机是怎么运行程序的 2 运行一个已解释的程序 3 运行一个已编译的程序 4 C++在哪里 5 理解Visual c++中的程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...
  • 1 理解计算机是怎么运行程序的 2 运行一个已解释的程序 3 运行一个已编译的程序 4 C++在哪里 5 理解Visual c++中的程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...
  • 1 理解计算机是怎么运行程序的 2 运行一个已解释的程序 3 运行一个已编译的程序 4 C++在哪里 5 理解Visual c++中的程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...
  • 1 理解计算机是怎么运行程序的 2 运行一个已解释的程序 3 运行一个已编译的程序 4 C++在哪里 5 理解Visual c++中的程序文件 6 创建源代码文件 7 理解并创建头文件 第二章 结构和语法 8 理解计算机语言 9 理解计算机...
  • c++ 面试题 总结

    2009-09-16 08:44:40
    6.下面是C语言中两种if语句判断方式。请问哪种写法更好?为什么? int n; if (n == 10) // 第一种判断方式 if (10 == n) // 第二种判断方式 如果少了个=号,编译时就会报错,减少了出错的可能行,可以检测出是否少...
  • <div><p>这很久很久之前想写的东西,拖了五六个月,没有动笔,现今补齐,内容有些多,对初学者有用,错误之处,望指出。 理解作用域 理解作用域链Js编程中一个必须要...
  • 英特尔面试专项准备

    2020-12-09 13:46:46
    </li><li>关于平衡二叉树的平衡方式和堆排序是怎么排序的,时间和空间复杂度</li><li>列举线程函数库</li><li>线程同步</li><li> <p>fork &pthread_create </li><li> C语言编程 </li><li> <p>const </li>...

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

c语言递归是怎么运行的

c语言 订阅