精华内容
下载资源
问答
  • c++内存地址以及如何访问
    千次阅读
    2016-11-19 17:09:14

    通过指针,可以简化一些c++编程任务的执行,还有一些任务,如动态内存分配,没有指针是无法执行的

    每一个变量都有一个内存位置,每一个内存位置都定义了可使用连字号(&)运算符访问的地址,它表示了内存中的一个地址

    下面的实例中,它将输出定义的变量地址

    #include <iostream>

    using namespace std;

    int main()

    {

    int var1;

    char var2[10];

    cout<<"var1变量的地址"<<&var1<<endl;

    cout<<"var2变量的地址"<<&var2<<endl;

    return 0;

    }

    编译和执行后i,会显示内存地址

    更多相关内容
  • 为了便于内存的分配和释放,AWorks提供了两种内存管理工具:堆和内存池。 本文为《面向AWorks框架和接口的编程(上)》第三部分软件篇——第9章内存管理——第1~2小节:堆管理器和内存池。 本章导...

    在程序运行过程中,可能产生一些数据,例如,串口接收的数据,ADC采集的数据。若需将数据存储在内存中,以便进一步运算、处理,则应为其分配合适的内存空间,数据处理完毕后,再释放相应的内存空间。为了便于内存的分配和释放,AWorks提供了两种内存管理工具:堆和内存池。

    本文为《面向AWorks框架和接口的编程(上)》第三部分软件篇——第9章内存管理——第1~2小节:堆管理器和内存池。

    本章导读

    在计算机系统中,数据一般存放在内存中,只有当数据需要参与运算时,才从内存中取出,交由CPU运算,运算结束再将结果存回内存中。这就需要系统为各类数据分配合适的内存空间。

    一些数据需要的内存大小在编译前可以确定。主要有两类:一类是全局变量或静态变量,这部分数据在程序的整个生命周期均有效,在编译时就为这些数据分配了固定的内存空间,后续直接使用即可,无需额外的管理;一类是局部变量,这部分数据仅在当前作用域中有效(如函数中),它们需要的内存自动从栈中分配,也无需额外的管理,但需要注意的是,由于这一部分数据的内存从栈中分配,因此,需要确保应用程序有足够的栈空间,尽量避免定义内存占用较大的局部变量(比如:一个占用数K内存的数组),以避免栈溢出,栈溢出可能破坏系统关键数据,极有可能造成系统崩溃。

    一些数据需要的内存大小需要在程序运行过程中根据实际情况确定,并不能在编译前确定。例如,可能临时需要1K内存空间用于存储远端通过串口发过来的数据。这就要求系统具有对内存空间进行动态管理的能力,在用户需要一段内存空间时,向系统申请,系统选择一段合适的内存空间分配给用户,用户使用完毕后,再释放回系统,以便系统将该段内存空间回收再利用。在AWorks中,提供了两种常见的内存管理方法:堆和内存池。

    9.1  堆管理器

    堆管理器用于管理一段连续的内存空间,可以在满足系统资源的情况下,根据用户的需求分配任意大小的内存块,完全“按需分配”,当用户不再使用分配的内存块时,又可以将内存块释放回堆中供其它应用分配使用。类似于C标准库中的malloc()/free()函数实现的功能。

    9.1.1  堆管理器的原理概述

    在使用堆管理器前,首先通过一个示例对其原理作简要的介绍,以便用户更加有效的使用堆管理器。例如,使用堆管理器对1024字节的内存空间进行管理。初始时,所有内存均处于空闲状态,可以将整个内存空间看作一个大的空闲内存块。示意图详见图9.1。

    图9.1 初始状态——单个空闲内存块

    内存分配的策略是:当用户申请一定大小的内存空间时,堆管理器会从第一个空闲内存块开始查找,直到找到一个满足用户需求的空闲内存块(即容量不小于用户请求的内存空间大小),然后从该空闲内存块中分配出用户指定大小的内存空间。

    例如,用户向该堆管理器申请100字节的内存空间,由于第一个空闲内存块的容量为1024,满足需求,因此,可以从中分配100字节的内存空间给该用户,分配后的内存示意图详见图9.2。

    图9.2 分配100字节——分割为两个内存块

    注:填充为阴影表示该块已被分配,否则,表示该块未被分配,处于空闲状态,数字表示该块的容量。

    同理,若用户再向该堆管理器连续请求三次内存空间,每次请求的内存空间容量分别为:150、250、200字节,则分配后的内存示意图详见图9.3。

    图9.3 再分配100、300、200字节内存空间——分割为五个内存块

    随着分配的继续,内存块可能越来越多。若用户的请求无法满足,则会分配失败,如果在图9.3的基础上,用户再请求400字节内存空间,由于仅有的一个空闲块,且容量为324字节,无法满足需求,此时,分配会失败,用户无法得到一段有效的内存空间。

    当用户申请的某一段内存不再使用时,应该将该内存块释放回堆中,以便回收再利用。

    回收的策略是:当用户将某一内存块释放回堆中时,首先,将该内存块变为空闲块,若该内存块相邻的内存块也为空闲块,则将它们合并为一个大的空闲内存块。

    例如,在图9.3的基础上,释放之前分配的250字节内存空间,则首先将该内存块变为空闲块,示意图详见图9.4。

    图9.4 释放一个内存块——相邻块不为空闲块

    由于该内存块前后均不为空闲块,因此,无需作合并操作。此时,释放了250字节的空闲空间,堆中共存在574字节的内存空间。但是,若用户此时向该堆管理器申请400字节的内存空间,由于第一个空闲块和第二个空闲块均不满足需求,因此,内存分配还是会失败。

    这里暴露出了一个堆管理器的缺点。频繁的分配和释放大小不一的内存块,将产生诸多内存碎片,即图9.4中被已分配内存块打断的空闲内存块,图中容量为250字节和容量为324字节的空闲内存块被一个已分配的容量为200字节的内存块打断,使得各个空闲块在物理上不连续,无法形成一个大的空闲块。这种情况下,即使请求的内存空间大小小于当前堆的空闲空间总大小,也可能会由于没有一个大的空闲块而分配失败。

    在图9.4的基础上,即使再释放掉第一次分配的100字节内存空间,使总空闲空间达到674字节,详见图9.5,同样无法满足一个400字节内存空间的分配请求。

    图9.5 释放容量为100字节内存块

    随着系统中大量内存块的分配和回收,内存碎片将越来越多,一些长时间不被释放的内存块,将始终分割着一些空闲内存块,造成内存碎片。这也告知用户,当不再使用某一内存块时,应尽快释放掉该内存块,以避免造成过多的内存碎片。

    在图9.5中,有3个空闲块,若用户在此基础上再请求一个280字节的内存空间,根据分配策略,堆管理器首先查看第一个空闲块,其容量为100字节,无法满足需求,接着查看第二个空闲块,其容量为250字节,同样无法满足需求,接着查看第三个空闲块,其容量为324字节,最终从该块中分配一段空间给用户,分配后的内存示意图详见图9.6。

    图9.6 再分配280字节内存空间

    在图9.6的基础上,若用户再释放200字节的内存块,首先,将其变为空闲块,示意图详见图9.7。

    图9.7 释放200字节的内存空间(1)——标记为空闲

    由于其左侧大小为250的内存块同样为空闲块,因此,需要将它们合并为一个大的内存块,即合并为一个大小为450的内存块,示意图详见图9.8。

    图9.8 释放200字节的内存空间(2)——与相邻空闲块合并

    此时,由于存在一个大小为450的空闲块,因此,若此时用户申请400字节的内存空间,则可以申请成功。与图9.5对比可知,虽然图9.5共计有674字节的空闲空间,而图9.8只有594字节的空闲空间,但图9.8却可以满足一个大小为400字节的内存空间请求。由此可见,受内存碎片的影响,总的空闲空间大小并不能决定一个内存请求的成功与否。

    申请400字节成功后的示意图详见图9.9。

    图9.9 再分配400字节内存空间

    在图9.9的基础上,若用户再释放280字节的内存块,同样,首先将其变为空闲块,示意图详见图9.10。

    图9.10 释放280字节的内存空间(1)——标记为空闲

    由于其左右两侧均为空闲块,因此,需要将它们合并为一个大的内存块,即合并为一个大小为374的内存块,示意图详见图9.11。

    图9.11 释放280字节的内存空间(2)——与相邻空闲块合并

    之所以要将相邻的空闲内存块合并,主要是为了避免内存块越来越多,越来越零散,如此下去,将很难再有一个大的空闲块,用户后续再申请大的内存空闲时,将无法满足需求。

    通过上面一系列内存分配和释放的示例,展示了堆管理器分配和释放内存的策略,使得用户对相关的原理有了一定的了解。

    实际上,在堆管理器的软件实现中,为了便于管理,各个内存块是以链表的形式组织起来的,每个内存块的首部会固定存放一些用于内存块管理的相关信息,示意图详见图9.12。

    图9.12 内存块(含空闲内存块和已分配内存块)链表

    图中展示了4个非常重要的信息:magic、used、p_next、p_prev。

    magic被称为魔数,会被赋值为一个特殊的固定值,它表示了该内存块是堆管理器管理的内存块,可以在一定程度上检查错误的内存操作。例如,若这个区域被改写,magic的值被修改为了其它值,表明存在非法的内存操作,可能是用户内存操作越界等,应及时处理;在释放一个内存块时,堆管理器会检查magic的值,若其值不为特殊的固定值,表明这并不是堆管理器分配的内存块,该释放操作是非法的。

    used用于表示该内存块是否已经被使用。若其值为0,则表示该内存块是空闲块;若其值为1,则表示该内存块已经被分配,不是空闲块。

    p_next和p_prev用于将各个内存块使用双向链表的形式组织起来,以便可以方便的找到当前内存块的下一个或上一个内存块,例如,在释放一个内存块时,需要查看相邻的内存块(上一个内存块和下一个内存块)是否为空闲块,以决定是否将它们合并为一个空闲块。

    此外,为了在分配内存块时,加快搜索空闲块的效率,信息中还会额外另外两个指针,用于将所有空闲块单独组织为一个双向链表。这样,在分配一个内存块时,只需要在空闲链表中查找满足需求的空闲块即可,无需依次遍历所有的内存块。示意图详见图9.13。

    图9.13 空间块链表

    对于用户来讲,其获得的内存空间为用户数据空间(获得的是直接指向用户数据空间的指针),存放在内存块首部的信息对用户是不可见的,用户不应该尝试访问、修改这些信息。

    需要用户注意的是,由于内存块的相关信息需要占用一定的内存空间(在32位系统中,通常为24字节),因此,每个内存块占用的实际大小会大于用户请求的内存空间大小,例如,用户请求一个100字节的内存空间,实际中,为了存储内存块的相关信息,会分配一个大小为124字节的内存块。基于此,用户实际可以使用的内存空间要略小于堆的总空间。

    9.1.2  堆管理器接口

    AWorks提供了堆管理器,用户通过相关接口使用即可。相关函数的原型详见表9.1。

    表9.1 堆管理器接口(aw_memheap.h)

    1.  定义堆管理器实例

    在使用堆管理器前,必须先使用aw_memheap_t类型定义堆管理器实例,该类型在aw_memheap.h中定义,具体类型的定义用户无需关心,仅需使用该类型定义堆管理器实例即可,即:

    其地址即可作为初始化接口中memheap参数的实参传递。

    在AWorks中,一个堆管理器用于管理一段连续的内存空间,一个系统中,可以使用多个堆管理器分别管理多段连续的内存空间。这就需要定义多个堆管理器实例,例如:

    如此一来,各个应用可以定义自己的堆管理器,以管理该应用中的内存分配与释放,使得各个应用之间的内存使用互不影响。

    如果所有应用使用一个堆,那么各个应用之间的内存分配将相互影响,某一应用出现内存泄漏,随着时间的推移,极有可能造成一个堆的空间被完全泄漏,这将影响所有应用程序。同时,所有应用共用一个堆,也造成在一个堆中的分配与释放更加频繁,分配的内存块大小更加不一致,更容易产生内存碎片。

    2.  初始化堆管理器

    定义堆管理器实例后,必须使用该接口初始化后才能使用,以指定其管理的内存空间,其函数原型为:

    其中,memheap为指向堆管理器实例的指针;name为堆管理器的名字,名字为一个字符串,仅用作标识;start_addr指定了其管理的内存空间首地址;size指定了其管理的内存空间大小(字节数)。

    函数的返回值为标准的错误号,返回AW_OK时,表示初始化成功;否则,表示初始化失败。

    初始化函数的核心在于指定其管理的内存空间,通常情况下,这段连续的内存空间可以通过定义一个全局的数组变量获得,其大小与实际应用相关,应根据实际情况决定。例如,使用堆管理器管理1KB的内存空间,则初始化堆管理器的范例程序详见程序清单9.1。

    程序清单9.1 初始化堆管理器范例程序

    程序中,定义了一个大小为1024字节的数组,用于分配一个1KB的内存空间,以便使用堆管理器进行管理。

    3.  分配内存

    堆管理器初始化完毕后,可以使用该接口为用户分配指定大小的内存块,内存块的大小可以是满足资源需求的任意大小。分配内存块的函数原型为:

    其中,heap为指向堆管理器的指针;size为内存块大小。返回值为分配内存块的首地址,特别地,若返回值为NULL,则表明分配失败。

    在分配内存块时,由于堆管理器并不知道分配的内存块用来存储何种类型的数据,因此,返回值为通用的无类型指针,即void *类型,代表其指向了某一类型不确定的地址。显然,分配的内存块用以存储何种类型的数据是由用户决定的,因此,用户在使用这段内存空间时,必须将其转换为实际数据类型的指针。

    例如,分配用以存储100个无符号8位数据的内存块,其范例程序详见程序清单9.2。

    程序清单9.2 分配内存块的范例程序

    程序中,将aw_memheap_alloc()的返回值强制转换为了指向uint8_t数据类型的指针。注意,使用aw_memheap_alloc()分配的内存中,数据的初始值是随机的,不一定为0。因此,若不对ptr指向的内存赋值,则其值可能是任意的。

    4.  重新调整内存大小

    有时候,需要动态调整之前分配的内存块大小,如果一开始分配了一个较小的内存块,但随着数据的增加,内存不够,此时,就可以使用该函数重新调整之前分配的内存块大小。其函数原型为:

    其中,heap为指向堆管理器的指针;ptr为使用aw_memheap_alloc()函数分配的内存块首地址,即调用aw_memheap_alloc()函数的返回值;new_size为调整后的内存块大小。返回值为调整大小后的内存空间首地址,特别地,若返回值为NULL,则表明调整大小失败。

    newsize指定的新的大小可以比原内存块大(扩大),也可以比原内存块小(缩小)。如果是扩大内存块,则新扩展部分的内存不会被初始化,值是随机的,但原内存块中的数据仍然保持不变。如果是缩小内存块,则超出new_size部分的内存会被释放,其中的数据被丢弃,其余数据保持不变。特别地,若newsize的值为0,则相当于不再使用ptr指向的内存块,此时,将会直接释放整个内存块,这种情况下,返回值同样为NULL。

    函数返回值与ptr的值可能不同,即系统可能重新选择一块合适的内存块来满足调整大小的需求,此时,内存首地址将发生变化。例如,当新的大小比原空间大时,系统先判断原内存块后是否还有足够的连续空间满足本次扩大内存的要求,如果有,则直接扩大内存空间,内存首地址不变,同样返回原内存块的首地址,即ptr的值;如果没有,则重新按照newsize分配一个内存块,并将原有数据原封不动的拷贝到新分配的内存块中,而后自动释放原有的内存块,原内存块将不再可用,此时,返回值将是重新分配的内存块首地址,与ptr将无直接关系。

    例如,首先使用aw_memheap_alloc()分配了一个100字节大小的内存块,然后重新将其调整为200字节大小的内存块。范例程序详见程序清单9.3。

    程序清单9.3 重新调整内存大小

    值得注意的是,重新调整内存空间的大小失败后,原内存空间还是有效的。因此,若采用程序清单9.3第9行的调用形式,若内存扩大失败,则返回值为NULL,这将会导致ptr的值被设置为NULL。此时,虽然原内存空间仍然有效,但由于指向该内存空间的指针信息丢失了,用户无法再访问到对应的内存空间,也无法释放对应的内存空间,造成内存泄漏。

    在实际使用时,为了避免调整内存大小失败时将原ptr的值覆盖为NULL,应该使用一个新的指针保存函数的返回值,详见程序清单9.4。

    程序清单9.4 重新调整内存大小(使用新的指针保存函数返回值)

    此时,即使扩大内存空间失败,指向原内存空间的指针ptr依然有效,依旧可以使用原先分配的内存空间,避免了内存泄漏。扩大内存空间成功时,则直接将ptr的值重新赋值为new_ptr,使其指向扩展完成后的内存空间。

    5.  释放内存

    当用户不再使用申请的内存块时,必须释放,否则将造成内存泄漏。释放内存的函数原型为:

    其中,ptr为使用aw_memheap_alloc()或aw_memheap_realloc()函数分配的内存块首地址,即调用这些函数的返回值。注意,ptr只能是上述几个函数的返回值,不能是其它地址值,例如,不能将数组首地址作为函数参数,以释放静态数组占用的内存空间。传入错误的地址值,极有可能导致系统崩溃。

    当使用aw_memheap_free()将内存块释放后,相应的内存块将变为无效,用户不能再继续使用。释放内存块的范例程序详见程序清单9.5。

    程序清单9.5 释放内存块的范例程序

    为了避免释放内存块后再继续使用,可以养成一个良好的习惯,每当内存释放后,都将相应的ptr指针赋值为NULL。

    9.1.3  系统堆管理

    在AWorks中,整个内存空间首先用于满足存放一些已知占用内存空间大小的数据,比如:全局变量、静态变量、栈空间、程序代码或常量等。

    全局变量和静态变量都比较好理解,其占用的内存大小通过数据的类型即可确定。需要注意的是,在介绍堆管理器时,定义一块待管理的内存空间同样使用了静态数组的方式,详见程序清单9.1的第6行:

    这也属于一种静态变量,其占用的内存大小是已知的。

    对于栈空间,在AWorks中,栈空间是静态分配的,类似于一个静态数组,其占用的内存空间大小由用户决定,同样是已知的。

    通常情况下,程序代码和常量都存储在ROM或FLASH等只读存储器中,不会放在内存中。但在部分平台中,出于效率或芯片架构的考虑,也可能将程序代码和常量存储在内存中。例如,在i.MX28x平台中,程序代码和常量也存储在DDR内存中。程序代码和常量占用的内存空间大小在编译后即可确定,占用的内存空间大小也是已知的。

    在满足这些数据的存储后,剩下的所有内存空间即作为系统堆空间,便于用户在程序运行过程中动态使用。

    为了便于用户使用,需要使用某种合适的方法管理系统堆空间。在AWorks中,默认使用前文介绍的堆管理器对其进行管理。出于系统的可扩展性考虑,AWorks并没有限制必须基于AWorks提供的堆管理器管理系统堆空间,如果用户有更加适合特殊应用场合的管理方法,也可以在特定环境下使用自有方法管理系统堆空间。为了保持应用程序的统一,AWorks定义了一套动态内存管理通用接口,便于用户使用系统堆空间,而无需关心具体的管理方法。相关函数原型详见表9.2。

    表9.2 动态内存管理接口(aw_mem.h)

    通过前文的介绍可知,在使用堆管理器前,需要定义堆管理器实例,然后初始化该实例,以指定其管理的内存空间,初始化完成后,用户才可向其请求内存。若是使用堆管理器管理系统堆空间(默认),那么,表9.2中的接口均可基于堆管理器接口实现。此时,系统中将定义一个默认的堆管理器实例,并在系统启动时自动完成其初始化操作,指定其管理的内存空间为系统堆空间。如此一来,系统启动后,用户可以直接向系统中默认的堆管理器申请内存块。例如,aw_mem_alloc()用于分配一个内存块,其直接基于堆管理器实现,范例程序详见程序清单9.6。

    程序清单9.6 aw_mem_alloc()函数实现范例

    其中,__g_system_heap为系统定义的堆管理器实例,已在系统启动时完成了初始化。程序清单9.6只是aw_mem_alloc()函数实现的一个简单范例,实际中,用户可以根据具体情况,使用最为合适的方法管理系统堆空间,实现AWorks定义的动态内存管理通用接口。

    下面,详细介绍各个接口的含义及使用方法。

    1.  分配内存

    aw_mem_alloc()用于从系统堆中分配指定大小的内存块,用法和C标准库中的malloc()相同,其函数原型为:

    参数size指定内存空间的大小,单位为字节。返回值为void *类型的指针,其指向分配内存块的首地址,特别地,若返回值为NULL,则表示分配失败。

    例如,申请用以存储一个int类型数据的存储空间,范例程序详见程序清单9.7。

    程序清单9.7 申请内存范例程序

    程序中,将aw_mem_alloc()的返回值强制转换为了指向int数据类型的指针。注意,使用aw_mem_alloc()分配的内存中,数据的初始值是随机的,不一定为0。因此,若不对ptr指向的内存赋值,则其值将是任意的。

    2.  分配多个指定大小的内存块

    除使用aw_mem_alloc()直接分配一个指定大小的内存块外,还可以使用aw_mem_calloc()分配多个连续的内存块,用法与C标准库中的calloc()相同,其函数原型为:

    该函数用于分配nelem个大小为size的内存块,分配的内存空间总大小为:nelem×size,实际上相当于分配一个容量为nelem×size的大内存块,返回值同样为分配内存块的首地址。与aw_mem_alloc()不同的是,该函数分配的内存块会被初始化为0。例如,分配用以存储10个int类型数据的内存,则范例程序详见程序清单9.8。

    程序清单9.8 分配10个用于存储int类型数据的内存块

    由于分配的内存空间会被初始化为0,因此,即使不对ptr指向的内存赋值,其值也是确定的0。

    3.  分配具有一定对齐要求的内存块

    有时候,用户申请的内存块可能用来存储具有特殊对齐要求的数据,要求分配内存块的首地址必须按照指定的字节数对齐。此时,可以使用aw_mem_align()分配一个满足指定对齐要求的内存块。其函数原型为:

    其中,size为分配的内存块大小,align表示对齐要求,其值是2的整数次幂,比如:2、4、8、16、32、64等。返回值同样为分配内存块的首地址,其值满足对齐要求,是align的整数倍。如align的值为16,则按照16字节对齐,分配内存块的首地址将是16的整数倍,地址的低4位全为0。程序范例详见程序清单9.9。

    程序清单9.9 分配具有一定对齐要求的内存块范例程序

    程序中,将分配的地址通过aw_kprintf()打印输出,以查看地址的具体值,实际运行可以发现,地址值是满足16字节对齐的。注意,该函数与aw_mem_alloc()分配的内存块一样,其中的数据初始值是随机的,不一定为0。

    在堆管理器中,并没有类似的分配满足一定对齐要求的内存块接口,只有普通的分配内存块接口:aw_memheap_alloc()。其分配的内存块,可能是对齐的,也可能是未对齐的。为了使返回给用户的内存块能够满足对齐要求,在使用aw_memheap_alloc()分配内存块时,可以多分配align - 1字节的空间,此时,即使获得的内存块首地址不满足对齐要求,也可以返回从内存块首地址开始,顺序第一个对齐的地址给用户,以满足用户的对齐需求。

    例如,要分配200字节的内存块,并要求满足8字节对齐,则首先使用aw_memheap_alloc()分配207字节(200 + 8 - 1)的内存块,假定得到的内存块地址范围为:3 ~ 209,示意图详见图9.14(a)。由于首地址3不是8的整数倍,因此其不是按8字节对齐的,此时,直接返回顺序第一个对齐的地址给用户,即:8。由于用户需要的是200字节的内存块,因此,对于用户来讲,其使用的内存块地址范围为 :8 ~ 207,显然,其在实际使用aw_memheap_alloc()获得的内存块地址范围内,用户获得的内存块是完全有效的,示意图详见图9.14(b)。

    图9.14 内存对齐的处理——多分配align-1字节的空间

    为什么要多分配align - 1字节的空间呢?在获得的实际内存块不满足对齐需求时,表明内存块首地址不是align的整数倍,即其对align取余数的结果(C语言的%运算符)不为0,假定其对align取余数的结果为N(N ≥1),则只要将首地址加上align-N,得到的地址值就是align的整数倍。该值也为从首地址开始,顺序第一个对齐的地址。由于在首地址不对齐时,必然有:N ≥1,因此:align - N ≤ align – 1,即顺序第一个对齐的地址相对于起始地址的偏移不会超过align - 1。基于此,只要在分配内存块时多分配align-1字节的空间,那么就可以在向用户返回一个对齐地址的同时,依旧满足用户请求的内存块容量需求。

    若不多分配align-1字节的内存空间,例如,只使用aw_memheap_alloc()分配200字节的内存块,得到的内存块地址范围为:3 ~ 203,示意图详见图9.15(a)。此时,若同样返回顺序第一个对齐的地址给用户,即:8。由于用户需要的是200字节的内存块,因此,对于用户来讲,其使用的内存块地址范围为 :8 ~ 208,显然,204 ~ 208 这段空间并不是通过分配得到的有效内存,使得用户得到了一段非法的内存空间,一旦访问,极有可能导致应用出错。示意图详见图9.15 (b)。

    图9.15 内存对齐的处理——未多分配align-1字节的空间

    实际中,由于align - 1的值往往是一些比较特殊的奇数值,例如:3、7、15、31等,经常如此分配容易把内存块的首地址打乱,出现很多非对齐的地址。因此,往往会直接多分配align字节的内存空间。

    同时,出于效率考虑,在AWorks中,每次分配的内存往往都按照默认的CPU自然对齐字节数对齐,例如,在32位系统中,默认分配的所有内存都按照4字节对齐,基于此,aw_mem_alloc()函数的实现可以更新为如程序清单9.10所示的程序。 

    程序清单9.10 aw_mem_alloc()函数分配的内存按照4字节对齐

    4.  重新调整内存大小

    有时候,需要动态调整分配内存块的大小,如果一开始分配了一个较小的内存块,但随着数据的增加,内存不够,此时,则可以使用该函数重新调整之前分配的内存块大小。其函数原型为:

    其中,ptr为使用aw_mem_alloc()、aw_mem_calloc()或aw_mem_align()函数分配的内存块首地址,即调用这些函数的返回值。new_size为调整后的大小。返回值为调整大小后的内存块首地址,特别地,若调整大小失败,则返回值为NULL。

    例如,首先使用aw_mem_alloc()分配了存储1个int类型数据的内存块,然后重新调整内存块的大小,使其可以存储2个int类型的数据。范例程序详见程序清单9.11。

    程序清单9.11 内存分配范例程序(重新调整内存大小)

    5.  释放内存

    前面讲解了4种分配内存块的方法,无论使用何种方式动态分配的内存块,在使用结束后,都必须释放,否则将造成内存泄漏。释放内存块的函数原型为:

    其中,ptr为使用aw_mem_alloc()、aw_mem_calloc()、aw_mem_align()或aw_mem_realloc()函数分配的内存块首地址,即调用这些函数的返回值。

    当使用aw_mem_free()将内存块释放后,相应的地址空间将变为无效,用户不能再继续使用。释放内存块的范例程序详见程序清单9.12。

    程序清单9.12 释放内存块的范例程序

    9.2  内存池

    堆管理器极为灵活,可以分配任意大小的内存块,非常方便。但其也存在明显的缺点:一是分配效率不高,在每次分配时,都要依次查找所有空闲内存块,直到找到一个满足需求的空闲内存块;二是容易产生大小各异的内存碎片。

    为了提高内存分配的效率,以及避免内存碎片,AWorks提供了另外一种内存管理方法:内存池(Memory Pool)。其舍弃了堆管理器中可以分配任意大小的内存块这一优点,将每次分配的内存块大小设定为固定值。

    由于每次分配的内存块大小为固定值,没有空间大小的限制,因此,在用户每次申请内存块时,分配其第一个空闲内存块即可,无需任何查找过程,同理,在释放一个内存块时,也仅需将其标志为空闲即可,无需任何额外的合并操作,这极大的提高了内存分配和释放的效率。

    同时,由于每次申请和释放的内存块都是同样的大小,只要存在空闲块,就可以分配成功,某几个空闲内存块不可能由于被某一已分配的内存块分割而导致无法使用。这种情况下,任一空闲块都可以被没有限制的分配使用,不再存在任何内存碎片,彻底避免了内存碎片。 

    但是,将内存块大小固定,会限制其使用的灵活性,并可能造成不必要的内存空间浪费,例如,用户只需要很小的一块内存空间,但若内存池中每一块内存都很大,这就会使内存分配时不得不分配出一块很大的内存,造成了内存浪费。这就要求在定义内存池时,应尽可能将内存池中内存块的大小定义为一个合理的值,避免过多的内存浪费。

    系统中可以存在多个内存池,每个内存池包含固定个数和大小的内存块。基于此,在实际应用中,为了满足不同大小的内存块需求,可以定义多种尺寸(内存池中内存块的大小)的内存池(比如:小、中、大三种),然后在实际应用中根据实际用量选择从合适的内存池中分配内存块,这样可以在一定程度上减少内存的浪费。

    9.2.1  内存池原理概述

    内存池用于管理一段连续的内存空间,由于各个内存块的大小固定,因此,首先将内存空间分为若干个大小相同的内存块,例如,管理1024字节的内存空间,每块大小为128字节。则共计可以分为8个内存块。初始时,所有内存块均为空闲块,示意图详见图9.16。

    图9.16 初始状态——8个空闲块

    在AWorks中,为便于管理,将各个空闲内存块使用单向链表的形式组织起来,示意图详见图9.17。

    图9.17 以单向链表的形式组织各个空闲块

    这就要求一个空闲块能够存放一个p_next指针,以便组织链表。在32位系统中,指针的大小为4个字节,因此,要求各个空闲块的大小不能低于4个字节。此外,出于对齐考虑,各个空闲块的大小必须为自然对齐字节数的正整数倍。例如,在32位系统中,块大小应该为4字节的整数倍,比如:4、8、12、6……而不能为5、7、9、13等。

    基于此,当需要分配一个内存块时,只需从链表中的取出第一个空闲块即可。例如,需要在图9.17的基础上分配一个内存块,可以直接从链表中取出第一个空闲块,示意图详见图9.18。

    图9.18 从链表中取出一个内存块

    此时,空闲块链表中,将只剩下7个空闲块,示意图详见图9.19。

    图9.19 剩余7个空闲块

    值得注意的是,虽然在空闲块链表中,各个内存块中存放了一个p_next指针,占用了一定的内存空间,但是,当该内存块从空闲链表中取出,分配给用户使用时,已分配的内存块并不需要组织为一个链表,p_next的值也就没有任何意义了,因此,用户可以使用内存块中所有的内存,不存在用户不可访问的区域,不会造成额外的空间浪费。

    而在堆管理器中,无论是空闲块还是已分配的内存块,头部存储的相关信息都必须保持有效,其占用的内存空间用户是不能使用的,对于用户来讲,这相当于造成了一定的内存空间浪费。

    当用户不再使用一个内存块时,需要释放相应的内存块,释放时,直接将内存块重新加入空闲块链表即可。示意图详见图9.20。

    图9.20 释放一个内存块

    释放后,空闲链表中将新增一个内存块,示意图详见图9.21。

    图9.21 释放后,新增一个内存块

    由此可见,整个内存池的分配和释放操作都非常简单。分配时,从空闲链表中取出一个内存块,释放时,将内存块重新加入空闲链表中。

    9.2.2  内存池接口

    AWorks提供了内存池软件库,用户通过相关接口使用即可。相关函数的原型详见表9.3。

    表9.3 内存池接口(aw_pool.h)

    1.  定义内存池实例

    在使用内存池前,必须先使用aw_pool_t类型定义内存池实例,该类型在aw_pool.h中定义,具体类型的定义用户无需关心,仅需使用该类型定义内存池实例即可,即:

    其地址即可作为初始化接口中p_pool参数的实参传递。

    一个内存池可以管理一段连续的内存空间,在AWorks中,可以使用多个内存池,以分别管理多段连续的内存空间。此时,就需要定义多个内存池实例,例如:

    为了满足各种大小的内存块需求,可以定义多个具有不同内存块大小的内存池。例如:定义小、中、大三种尺寸的内存池,它们对应的内存块大小分别为8、64、128。用户根据实际用量选择从合适的内存池中分配内存块,以在一定程度上减少内存的浪费。

    2.  初始化内存池

    定义内存池实例后,必须使用该接口初始化后才能使用,以指定内存池管理的内存空间,以及内存池中各个内存块的大小。其函数原型为:

    其中,p_pool指向待初始化的内存池,即使用aw_pool_t类型定义的内存池实例;p_pool_mem为该内存池管理的实际内存空间首地址;pool_size指定整个内存空间的大小;item_size指定内存池中每个内存块的大小。

    函数的返回值为内存池ID,其类型aw_pool_id_t,该类型的具体定义用户无需关心,该ID可作为其它功能接口的参数,用以表示需要操作的内存池。特别地,若返回ID的值为NULL,表明初始化失败。

    初始化时,系统会将pool_size大小的内存空间,分为多个大小为item_size的内存块进行管理。例如,使用内存池管理1KB的内存空间,每个内存块的大小为16字节,初始化范例程序详见程序清单9.13。

    程序清单9.13 初始化内存池

    程序中,将1024字节的空间分成了大小为16字节的内存块进行管理。注意,出于效率考虑,块大小并不能是任意值,只能为自然对齐字节数的正整数倍。例如,在32位系统中,块大小应该为4字节的整数倍,若不满足该条件,初始化时,将会自动向上修正为4字节的整数倍,例如,块大小的值设置为5,将被自动修正为8。用户可以通过aw_pool_item_size ()函数获得实际的内存块大小。

    3.  获取内存池中实际的块大小

    前面提到,初始化时,为了保证内存池的管理效率,可能会对用户传入的块大小进行适当的修正,用户可以通过该函数获取当前内存池中实际的块大小。其函数原型为:

    其中,pool_id为初始化函数返回的内存池ID,其用于指定要获取信息的内存池。返回值即为内存池中实际的块大小。

    例如,初始化时,将内存池的块大小设定为5,然后通过该函数获取内存池中实际的块大小。范例程序详见程序清单9.14。

    程序清单9.14 获取内存池中实际的块大小

    运行程序可以发现,实际内存块的大小为8。

    实际应用中,为了满足不同容量内存申请的需求,可以定义多个内存池,每个内存池定义不同的块大小。如定义3种块大小尺寸的内存池,分别为8字节(小)、64字节(中)、128字节(大)。范例程序详见程序清单9.15。

    程序清单9.15 定义多种不同块大小的内存池

    程序中,将三种类型内存池的总容量分别定义为了512、1024、2048。实际中,应根据情况定义,例如,小型内存块需求量很大,则应该增大对应内存池的总容量。

    4.  获取内存块

    内存池初始化完毕后,用户可以从内存池中获取固定大小内存块,其函数原型为:

    其中,pool_id为初始化函数返回的内存池ID,其用于指定内存池,表示从该内存池中获取内存块。返回值为void *类型的指针,其指向获取内存块的首地址,特别地,若返回值为NULL,则表明获取失败。从内存池中获取一个内存块的范例程序详见程序清单9.16。

    程序清单9.16 获取内存块范例程序

    5.  释放内存块

    当获取的内存块使用完毕后,应该释放该内存块,将其返还到内存池中。其函数原型为:

    其中,pool_id为初始化函数返回的内存池ID,其用于指定内存池,表示将内存块释放到该内存池中。p_item为使用aw_pool_item_get()函数获取内存块的首地址,即调用aw_pool_item_get()函数的返回值,表示要释放的内存块。

    返回值为aw_err_t类型的标准错误号,若值为AW_OK,表示释放成功,否则,表示释放失败,释放失败往往是由于参数错误造成的,例如,释放一个不是由aw_pool_item_get()函数获取的内存块。注意,内存块从哪个内存池中获取,释放时,就必须释放到相应的内存池中,不可将内存块释放到其它不对应的内存池中。

    当使用aw_pool_item_return()将内存块释放后,相应的内存空间将变为无效,用户不能再继续使用。释放内存块的范例程序详见程序清单9.17。

    程序清单9.17 释放内存块范例程序

                   </div>
                <!--<div class="side-box author-article">
                    <a href="/d/user/2671042/" target="_blank">
                            <h2 class="title">
                                周立功单片机
                                技术专区</h2>
                        </a>
                        
                    <ul class="txt-list">
                        <li><a href="/d/922003.html">E523.52—高集成度电机控制芯片</a></li><li><a href="/d/906380.html">智能门锁生命线!一“芯”当关,安全守护</a></li><li><a href="/d/905625.html">新一代车载T-Box集成以太网网关的控制方案解析</a></li><li><a href="/d/904695.html">电源模块的可靠性设计有何秘籍?</a></li><li><a href="/d/904646.html">ZLG72128数码管显示驱动及键盘扫描管理芯片</a></li>                    </ul>
                </div>-->
    
                <!-- 文章增加的调整 -->
                    <iframe id="iframe_tags" data-elecfans_trackid="article_detail" data-tag="内存,数据存储,管理器" src="/static/iframe/course.html" width="100%" height="170" style="border: none; margin: 20px 0px; display: none;"></iframe>
                    <div class="hudong clearfix">
                    </div>
                     <div class="wx_detail">
                                        <p>原文标题:AWorks软件篇 — 内存管理</p>
                                        <p>文章出处:【微信号:Zlgmcu7890,微信公众号:周立功单片机】欢迎添加关注!文章转载请注明出处。</p>
                                </div>
            </div>
    
    展开全文
  • 数值信息是有正负之分的,因此,在计算机中存储数值信息必须要有表示符号的方法。由于计算机内是采用二进制编码表示,因此,在一般情况下,我们用“0”表示正号,“1”表示符号,符号位数放在数的最高位。 例如,...

    1. 信息在计算机系统中的表示

    我们知道,信息在计算机系统中是以二进制的方式进行传送,存储的。那么信息在计算机系统中是如何表示的呢?在这里可分为数值信息和非数值信息两个方面进行讨论。

    数据信息分类示意图

     

    1.1 数值信息在计算机系统中的表示

    数值信息是有正负之分的,因此,在计算机中存储数值信息必须要有表示符号的方法。由于计算机内是采用二进制编码表示,因此,在一般情况下,我们用“0”表示正号,“1”表示符号,符号位数放在数的最高位。

    例如,比如我们有十进制数A= +91,B= -91,8位二进制数A=(+1011011),B=(-1011011),A和B可以在计算机中表示为:

    A和B在计算机中的表示
    A:0(符号位)1011011
    B:1(符号位)1011011

    可以看出,最左边一位代表符号位,它们连同数字本身一起作为一个数。数值信息在计算机内采用符号和数字化处理后,便可以识别和表示带符号的数值信息了,而根据对负数不同的编码方式,又可分为原码、反码、补码三种方式。

    1.1.1 原码

    同上所述,直接将符号位数字化为0或1,不再进行其他处理,然后将数的绝对值与符号一起编码,即所谓“符号—绝对值表示”的编码,我们称之为原码(未经过其他处理故我们称之为"原")。

    其实上面我们已经说了如何用原码表示一个带符号的整数,如上所述,如果用一个字节(8位)放一个整数,其原码表示如下:

    A= +91= +0101011   [A原] = 00101011 ;

    B= -91=  -0101011   [B原] = 10101011 ;

    这里的“原”就是机器数,就是存放在计算机里的实际二进制数字,前面带符号的二进制数我们称之为机器数相对应的真值

    那我们采用原码有什么好处呢?首先就是编码很简单,我们只需要将真值里面的符号数转为0或1就可以变为机器数,机器数和真值转换很方便,一看就懂。

    那采用原码表示有什么缺陷吗?还真有,第一个就是零的表示不唯一,我们知道,0是没有符号的,+0和-0都是一样的,没有区别的,那么问题来了,我们如何表示0呢?

    [+0] = 00000000                                 [-0]=100000000

    以上两个表示方式都对,所以[0]的表示就有了二义性,这就给机器判零带来了麻烦。

    第二个缺陷就是直接用原码进行四则运算时,符号位需要单独处理,且运算规则复杂,例如进行一个加法运算,若两数同号,那么要取两数相同的符号作为最终符号;若两数异号,则要用大数减去小树,再把大数的符号作为最终的符号。虽然我们看起来很好理解,但实际上这种操作对计算机来说是及其麻烦的,因此,人们找到了更好的编码方式来代替,那就是补码表示法。

    1.1.2 补码

    要说到补码,必须先介绍下什么是反码。反码是基于原码基础上按位取反的,但是需要注意的是符号位是不变的。也就是说:

    原码和补码
    A:+0101011
    A原:0101101

    1

    A反:0(不变)010010

    0

     和原码一样,反码对0的表示也不唯一。

    介绍完反码,我们就可以引出补码的概念,补码在原理上其实是运用了“模数”的概念,在模数系统中有这么一个概念:

    若一个数减去另一个数,或者说一个数加上一个负数,等价于第一个数加上第二个数的补数。

    比如,我们取模数为12,那么:

    8 + (-2) = 8 +10 (mod12) = 6

    为什么这么做呢?这样我们就把加上一个“负数”的“减法”运算变成了加法运算,也就弥补了之前我们原码所说的缺陷。

    补码的原理我们不必深究,有一个快速简洁求补码的方法我们需要记住:

    对于正数,不存在反码和补码,没有意义。因此,有些教材上说正数的反码补码形式相同是不对的,实际上,应该说正数没有反码补码更合适点。

    对于负数,其补码就是反码的最后一位 [加1] 所得。

    这里需要注意:最后一位若是0加1就是1,最后一位是1加1就进位变成0,看起来像取反一样,实际上进行的是操作.

     1.2 非数值信息在计算机系统中的表示

    在计算机内部,非数值信息也是采用0和 1 两个符号来进行编码表示的。

    ①字符的编码, ASCII码是“美国信息交换标准代码”的简称,在这种编码中,每个字符用 7 个二进制位表示,即从 0000000 到 1111111 可以给出 128 种编码,可用来表示 128 个不同的字符。一个字符的 ASCII码通常占用一个字节,由七位二进制数编码组成,故 ASCII 码最多可表示 128 个不同的符号。由于 ASCII码采用七位编码,来用到字节的最高位,故在计算机中一般保持为“0” ,在数据传输时可用作奇偶校验位。

    ② 汉字的编码,目前,我国使用的是“国家标准信息交换用汉字编码” ,该标准码是二字节码,用2个七位二进制数编码表示一个汉字,并收人了 6763 个汉字。汉字在计算机内的表示,有多种编码,如汉字输入码,输人码进人计算机后,必须转换成汉字内码,才能进行信息处理。为了最终显示、打印汉字,再由内码转换成汉字字形码。此外,为使不同的汉字处理系统之间能够交换信息,还必须设有汉字交换码。


     

    2. 内存地址和内存空间的简单理解

    2.1 理解内存地址和内存空间

    首先我们先来看这么一个代码

    
        int a =1,b=2;
        int main()
        {
            a++;
            b++;
            return 0;
        {

     

    这么一段简单的代码在计算机中如何执行呢?a和b在计算机中如何区分?要回答这个问题,必须要简单理解下计算机中的内存地址和内存空间。

    实际上,如果我们反汇编一下,就可以看到a++和b++分别对应的是:

        incl 0x80495f8              //把0x80495f8地址中的整数加1
        incl 0x80495fc              //把0x80495fc地址中的整数加1

    在这里,那0x80495f8地址和0x80495fc地址就叫做a和b在内存中的地址。要了解内存地址首先必须要知道的是,内存地址就只是一个编号,一个内存地址就代表一个内存空间。那么这个空间是多大呢?我们常说,计算机中存储器的容量是以字节为基本单位的。什么叫以字节为单位,就是说一个内存地址代表一个字节(1Byte 也就是 8bit)的存储空间,这就是我们说的字节Byte是计算机的基本单位的含义。

    1个内存地址 = 1个字节(Byte) = 8位(bit)

     我们还知道,int型是占据4个字节的(4字节Byte=32位bit),也就是说存储一个int型必须用4个字节,也就等价于至少占据4个内存地址,所以,int在计算机中存储是占据了4个内存地址的。我们在输入语句int a =1,b=2; 后,计算机就分别为a和b分配了4个内存地址来存储a和8,这一以来,我们只需要知道a和b的内存起始地址(首地址),再加4,就是a和b实际在计算机中的地址,如下图示:

    a和b在内存空间的地址

     再比如经常说32位的操作系统最多支持4GB的内存空间,也就是说CPU只能寻址2的32次方,即2的32次方个8bit单位,或者说最大只有2的32次方个内存地址。

                                                                  2的32次方Byte = 4GB =4 294 967 296Byte

    2.2 数据在内存的存储

    理解了内存地址和内存空间后,我们便能知道数据在计算机中到底最终是怎么存储的。

    学习编程,必须对内存的地址有一个透彻的理解。我们编程中的每一行代码,代码中用到的每个数据,都需要在内存上有其映射地址。当然,我们并不需要掌握内存是如何进行编址,那是计算机系中的另外一门课:操作系统的事了。

    内存地址:计算机把所有的信息都给数字化了,所以它知道自已把一个数据,一条命令记到了内存中的哪个(些)位置。

    看下面的例子,看计算机是如何在内存里记住变量a和变量b的:

    变量:(int) a = 4(int) b = 2
    内存地址:0x80495f80x80495f90x80495fa0x80495fb0x80495fc0x80495fd0x80495fe0x80495ff
    内存空间:2001H2002H2003H2004H2005H2006H2007H2008H
    内存数据:0000000000000000000000000000010000000000000000000000000000000010

     

    通过以上我们可以知道,int型变量a和b都占据了4个字节也就是4个内存空间,一个内存地址对应一个内存空间也对应一个字节即8个位。

    可以看到,(int) a 和 b 的确是由一串0、1组成的。更确切地,从图上可以看出它们分别都是由32位0和1组成。这32数都存放在4个内存地址里。所以,内存地址是内存当中存储数据的一个标识,并不是数据本身,通过内存地址可以找到内存当中存储的数据。

    展开全文
  • 图论(六)图的两种表示方法

    万次阅读 多人点赞 2017-01-17 17:56:55
    如果要用图来解决问题,首先我们必须采用某种数据结构来存储和表示“图”。...因此也就无法以数据元素在内存中的物理位置来表示元素之间的关系,也就是说,图不可能用数组这样简单的顺序存储结构来表示

    如果要用图来解决问题,首先我们必须采用某种数据结构来存储和表示“图”。相对于数组、链表等来说,图的存储结构就复杂的多了。

    • 首先,图上的任何一个顶点都可以被看作是第一个顶点,任意顶点的邻接顶点之间也不存在次序关系。还记得在《图论(一)基本概念》中的“同构图”吧,图的形状可以千变万化的。因此也就无法以数据元素在内存中的物理位置来表示元素之间的关系,也就是说,图不可能用数组这样简单的顺序存储结构来表示。
    • 其次,如果使用链表一样的链式存储结构,不同顶点的邻接顶点数量是不一样的,相差可能很大,如何在操作和效率之间寻求平衡是个大难题。

    不过不用担心,计算机科学界不缺乏牛人,前辈们早就为我们设计好了,而且方法不止一种,发明了大量的图表示法,甚至还有专门从事图表示法的研究员(Jeremy P.Spinrad),还写过一本书《Efficient Graph Representations》。
    这里写图片描述

    尽管有大量的图表示法可用,但我们需要掌握的,也是最常用的、最著名的,可用性和普及率都最高的,只有两类:邻接表法和邻接矩阵法。都带有“邻接”两字,这是数学语言,大白话的意思就是“邻居”。

    (1)邻接表

    邻接表的核心思想就是针对每个顶点设置一个邻居表。
    这里写图片描述
    以上面的图为例,这是一个有向图,分别有顶点a, b, c, d, e, f, g, h共8个顶点。使用邻接表就是针对这8个顶点分别构建邻居表,从而构成一个8个邻居表组成的结构,这个结构就是我们这个图的表示结构或者叫存储结构。

    a, b, c, d, e, f, g, h = range(8)
    N = [{b, c, d, e, f},  # a 的邻居表
         {c, e},  # b 的邻居表
         {d},  # c 的邻居表
         {e},  # d 的邻居表
         {f},  # e 的邻居表
         {c, g, h},  # f 的邻居表
         {f, h},  # g 的邻居表
         {f, g}]  # h 的邻居表

    这样,N构成了一个邻居节点集。可以通过N对图进行操作了。

    # 顶点f的邻居顶点
    print(N[f])
    # 顶点g是否是a的邻居顶点
    print(g in N[a])
    # 顶点a的邻居顶点个数
    print(len(N[a]))

    输出结果:

    {2, 6, 7}
    False
    5

    注意:每个顶点的邻居表都是一个集合(set),为什么用set,因为不能重复存储邻居顶点,这是一个非常自然的选择。那么,可不可以用list,当然可以。用字典呢,当然也可以,甚至在表示带权重值的图时,使用字典表示更合理。

    N = [{b: 1, c: 2, d: 1, e: 2, f: 3},  # a 的邻居表
         {c: 1, e: 2},  # b 的邻居表
         {d: 3},  # c 的邻居表
         {e: 1},  # d 的邻居表
         {f: 2},  # e 的邻居表
         {c: 1, g: 1, h: 1},  # f 的邻居表
         {f: 1, h: 2},  # g 的邻居表
         {f: 1, g: 2}]  # h 的邻居表
    
    # 边(a,f)的权重
    if f in N[a]:
         print(N[a][f])

    输出结果:

    3

    需要注意的是,不管邻居表是用set,list,还是dict,都是邻接表的各种变形,最终使用哪个取决于这个图本身是什么,我们要用这个图干什么。实际应用中我们可以针对图本身特点和我们要解决问题特点针对性的构建图的表示结构。

    (2)邻接矩阵

    邻接矩阵的核心思想是针对每个顶点设置一个表,这个表包含所有顶点,通过True/False来表示是否是邻居顶点。
    还是针对上面的图,分别有顶点a, b, c, d, e, f, g, h共8个顶点。使用邻接矩阵就是针对这8个顶点构建一个8×8的矩阵组成的结构,这个结构就是我们这个图的表示结构或存储结构。

    a, b, c, d, e, f, g, h = range(8)
    N = [[0, 1, 1, 1, 1, 1, 0, 0],  # a的邻接情况
         [0, 0, 1, 0, 1, 0, 0, 0],  # b 的邻居表
         [0, 0, 0, 1, 0, 0, 0, 0],  # c 的邻居表
         [0, 0, 0, 0, 1, 0, 0, 0],  # d 的邻居表
         [0, 0, 0, 0, 0, 1, 0, 0],  # e 的邻居表
         [0, 0, 1, 0, 0, 0, 1, 1],  # f 的邻居表
         [0, 0, 0, 0, 0, 1, 0, 1],  # g 的邻居表
         [0, 0, 0, 0, 0, 1, 1, 0]]  # h 的邻居表

    同样,可以对N进行图操作了,操作方式与邻接表方式有所不同。

    # 顶点g是否是a的邻居顶点
    print(N[a][g])
    
    # 顶点a的邻居顶点个数
    print(sum(N[a]))
    
    # 顶点a的邻居顶点
    neighbour = []
    for i in range(len(N[f])):
         if N[f][i]:
              neighbour.append(i)
    print(neighbour)

    输出结果:

    0
    5
    [2, 6, 7]

    在邻接矩阵表示法中,有一些非常实用的特性。

    • 首先,可以看出,该矩阵是一个方阵,方阵的维度就是图中顶点的数量,同时还是一个对称矩阵,这样进行处理时非常方便。
    • 其次,该矩阵对角线表示的是顶点与顶点自身的关系,一般图不允许出现自关联状态,即自己指向自己的边,那么对角线的元素全部为0;
    • 最后,该表示方式可以不用改动即可表示带权值的图,直接将原来存储1的地方修改成相应的权值即可。当然, 0也是权值的一种,而邻接矩阵中0表示不存在这条边。出于实践中的考虑,可以对不存在的边的权值进行修改,将其设置为无穷大或非法的权值,如None,-99999/99999等。

    最后总结下,邻接表和邻接矩阵两种表示方法各有特点,具体使用哪个应该针对具体问题具体分析。但事实上,如果不是特别巨大无比的图,用不着费劲思考,用哪种都可以的。

    展开全文
  • 如何查看进程发生缺页中断的次数?  用ps -o majflt,minflt -C program命令查看。  majflt代表major fault,... 这个数值表示一个进程自启动以来所发生的缺页中断的次数。 发成缺页中断后,执行了那些操作?
  • 关于内存地址的一些理解

    千次阅读 2018-10-11 14:33:28
    首先,必须要知道内存地址只是一个编号,如1000H,代表一个内存空间。在计算机中存储器的容量是以字节为基本单位的。也就是说一个内存地址代表一个字节(8bit)的存储空间。 例如经常说32位的操作系统最多支持4GB的...
  • 在这一篇博文中,我们主要讲解一些更灵活的定位内存地址方法和相关的编程方法。   and 和 or 指令 and 指令:逻辑与指令,按位进行与运算 例如指令: mov al, 01100011B and al, 00111011B 执行后:al = ...
  • 彻底搞懂虚拟内存,虚拟地址,虚拟地址空间

    千次阅读 多人点赞 2021-04-27 18:20:55
    程序经过编译后,变成了...现代操作系统采用的是虚拟地址,这也是本篇文章阐述的重点,但虚拟地址是由1~3阶段发展而来的,所以也有必要阐述1~3三访问方式。 直接访问 直接访问很好理解,程序经过编译后,生成了可执行
  • 内存地址的概念和理解

    万次阅读 多人点赞 2019-05-29 09:07:24
    1.内存地址用4位16进制和8位16进制表示的区别。例如经常可以看到某些书籍上写的内存地址0x0001,在另外一些书籍上写的内存地址又变成了0x00000001。都是表示的编号为1的内存地址,为什么一个是4位16进制表示,另外一...
  • 关于内存内存地址的详解

    千次阅读 2018-10-24 22:48:46
    内存地址用4位16进制和8位16进制表示的区别。例如经常可以看到某些书籍上写的内存地址0x0001,在另外一些书籍上写的内存地址又变成了0x00000001。都是表示的编号为1的内存地址,为什么一个是4位16进制表示,另外一个...
  • 关于内存地址内存空间的理解

    千次阅读 2019-08-28 09:39:47
    1.内存地址用4位16进制和8位16进制表示的区别。例如经常可以看到某些书籍上写的内存地址0x0001,在另外一些书籍上写的内存地址又变成了0x00000001。都是表示的编号为1的内存地址,为什么一个是4位16进制表示,另外一...
  • android 内存使用详情查询的几种方法

    千次阅读 2018-07-18 11:02:22
    一. /proc/meminfo android /proc/ 目录下为我们提供了操作系统几乎所有的状态信息,当然也包含系统的内存使用信息,下面列举.../proc/pid/maps pid 为进程号,显示当前进程所长用的虚拟地址 cat /proc/pid/statm ...
  • 内存单元的物理地址是由其所处的地址总线上的位置决定的,机器安装完成后,其物理地址是固定的、不变的,并不是由CPU分配的。 cpu只需要告诉控制器它要存取的内存单元地址;要找到这个地址单元则交给成组的地址译码...
  • c语言字符串数组的两种表示方法

    万次阅读 多人点赞 2017-09-21 00:31:56
    c语言字符串数组的两种表示方法
  • java优化占用内存的几种方法

    千次阅读 2018-08-07 21:07:40
    java做的系统给人的印象是什么?占 内存!说道这句话就会有N多人站出来为java辩护,并举出...个字,陋习。 (1)别用new Boolean()。 在很多场景中Boolean类型是必须的,比如JDBC中boolean类型的set与get都是通过...
  • 物理地址:这里说的物理地址内存中的内存单元实际地址,不是外部总线连接的其他电子元件的地址!物理地址属于比较好理解的,物理地址就是内存中每个内存单元的编号,这个编号是顺序排好的,物理地址的大小决定了...
  • 内存地址与低地址 https://zhidao.baidu.com/question/1900511789089474940/answer/3236761807.html 可以把主存看成一本空白的作业本,你现在要在笔记本上记录一些内容,他的页码排序是 第一页 : 0x0000001 第二页...
  • 操作系统内存地址映射

    千次阅读 2018-05-09 13:06:06
    内存是现代计算机的运行的中心,内存是由很大的一组字或者是字节组成的,每个字或者是字节都是有它们自己的地址,以及CPU会根据程序计数器(PC)的值从内存中提取指令,这些指令可能会引起进一步对特定内存地址的读取...
  • Hadoop YARN同时支持内存和CPU两种资源的调度(默认只支持内存,如果想进一步调度CPU,需要自己进行一些配置),本文将介绍YARN是如何对这些资源进行调度和隔离的。 在YARN中,资源管理由ResourceManager和...
  • 如何对JVM进行内存调优?调优需要遵从什么样的原则或者说方法? 下面我们来说叨说叨,希望能帮到大家,同时自己也学习、记录。
  • 1、[bx+idata] ...而[bx+idata]所表示的是一更加灵活的方式来定位内存地址,其表示的是段地址为DS,偏移地址为(bx)+idata的内存位置。通常idata为一个常量,表示一个固定的地址偏移量。如下面几条指令实际上
  • 如何查看进程发生缺页中断的次数?  用ps -o majflt,minflt -C program命令查看。  majflt代表major fault,... 这个数值表示一个进程自启动以来所发生的缺页中断的次数。 发成缺页中断后,执行了那些操作?
  • 如何查看进程发生缺页中断的次数?  用ps -o majflt,minflt -C program命令查看。 ... 这个数值表示一个进程自启动以来所发生的缺页中断的次数。 发成缺页中断后,执行了那些操作?
  • 内存地址存储,内存空间

    千次阅读 2018-05-13 11:56:37
    1.内存地址用4位16进制和8位16进制表示的区别。例如经常可以看到某些书籍上写的内存地址0x0001,在另外一些书籍上写的内存地址又变成了0x00000001。都是表示的编号为1的内存地址,为什么一个是4位16进制表示,另外一...
  • iOS 内存泄漏排查方法及原因分析

    千次阅读 2018-11-22 09:03:18
    内存泄漏排查方法(工具) 内存泄漏原因分析(解决方案) 在正式开始前,我们先区分个基本概念: 内存泄漏(memory leak):是指申请的内存空间使用完毕之后未回收。 一次内存泄露危害可以忽略,但若一直泄漏...
  • 逻辑地址、虚拟地址、物理地址以及内存管理

    万次阅读 多人点赞 2016-10-11 21:47:33
    本文涉及的硬件平台是X86,如果是其它平台,...——这个概念应该是这几个概念中最好理解的一个,但是值得一提的是,虽然可以直接把物理地址理解成插在机器上那根内存本身,把内存看成一个从0字节一直到最大空量逐字节的
  • 大小端模式以及两种判断方法

    千次阅读 2019-04-12 13:55:01
    - 大端:高尾端:数据的尾部(低位字节)放在内存的高位地址。 - 小端:低尾端:数据的尾部(低位字节)放在内存的地位地址
  • 3)应用使用过程中,越来越卡——CPU能力不足/内存泄露;4)应用页面卡顿——帧率较低、页面卡顿。因此,对开发的Android应用,必须对其进行性能测试,不然将会直接影响用户体验。Android应用性能测试通常包括:启动...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,202,541
精华内容 481,016
关键字:

内存地址的两种表示方法

友情链接: NUFFT_code.rar