精华内容
下载资源
问答
  • 第二行和第三行看不懂求详解说的越详细越好。谢谢!有用到指针吗?![图片说明](https://img-ask.csdn.net/upload/201509/10/1441878903_779729.png)
  • 数据结构中的一个c++工程,关于图的动态存储和基本操作的实现。
  • 数据结构动态存储

    2016-07-26 13:34:00
    1.堆:是程序中用来保存长期使用数据的地方,堆上的数据不会自动清除,因此堆是保存数据结构的绝佳场所(例如链表) 2.用堆进行动态存储:  用malloc()申请存储器(相当于储物柜),malloc()返回一个指针  ...

    1.堆:是程序中用来保存长期使用数据的地方,堆上的数据不会自动清除,因此堆是保存数据结构的绝佳场所(例如链表)

    2.用堆进行动态存储:

      用malloc()申请存储器(相当于储物柜),malloc()返回一个指针

      一旦申请了堆上的空间,这块空间就再也不能被分配出去,直到告诉C标准库已经用完了,堆存储器空间有限,如果在代码中不断申请堆空间,很快就会发生存储器泄露。

      用free()释放存储器

    3.用法:

    #include<stdlib.h>   //为了使用malloc()和free()函数
    mallocsizeof(island));  //表示“给我足够的空间来保存island结构指针” malloc()返回通用指针
    free(p);  //释放

     

     

    4.strdup()复制字符串到堆上

    例如:

    char *s = "MONA LISA";
    char *copy = strdup(s);

    注意:栈上的局部变量会被清除,但堆上的不会,所以记得要用free()释放空间

    指针不会建立自己的副本,要用strdup()函数

    数组会建立自己的副本,不用strdup()函数

    5.字符指针不限制字符串的大小

       字符数组需要提前决定字符串长度

    6.valgrind工具:发现存储器泄露

    7.数据结构

    练习

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct node
    {
        char *question;
        struct node *no;
        struct node *yes;
    }node;//二叉树
    
    int yes_no(char *question)
    {
        char answer[3];
        printf("%s?(y/n):",question);
        fgets(answer,3,stdin);
        return answer[0] == 'y';
    }
    
    node *create(char *question)//初始化
    {
        node *n = malloc(sizeof(node));
        n->question = strdup(question);
        n->no = NULL;
        n->yes = NULL;
        return n;
    }
    
    void release(node *n)//释放
    {
        if(n)
        {
            if(n->no)
                release(n->no);
            if(n->yes)
                release(n->yes);
            if(n->question)
                free(n->question);
            free(n);
        }
    }
    
    int main()
    {
        char question[80];
        char suspect[20];
        node *start_node = create("Does suspect have a mustache");
        start_node->no = create("Loretta Barnsworth");
        start_node->yes = create("Vinny the Spoon");
    
        node *current;
        do
        {
            current = start_node;
            while(1)
            {
                if(yes_no(current->question))
                {
                    if(current->yes)
                        current = current->yes;
                    else
                    {
                        printf("SUSPECT IDENTIFIED\n");
                        break;
                    }
                }
                else if(current->no)
                    current = current->no;
                else
                {
                    //Make the yes-node the new suspect name
                    printf("Who's the suspect?");
                    fgets(suspect,20,stdin);
                    node *yes_node = create(suspect);
                    current->yes = yes_node;
    
                    //Make the no-node a copy of this question
                    node *no_node = create(current->question);
                    current->no = no_node;
    
                    //Then replace this question with the new question
                    printf("Give me a question that is TRUE for %s but not for %s?",suspect,current->question);
                    fgets(question,80,stdin);
                    current->question = strdup(question);
    
                    break;
                }
            }
        }while(yes_no("Run again"));
        release(start_node);
        return 0;
    }

     

    转载于:https://www.cnblogs.com/syyy/p/5707161.html

    展开全文
  • 数据结构-动态存储管理

    千次阅读 2019-01-26 10:55:16
    边界标识法是操作系统中用以动态分区分配的一种存储管理方法,系统将所有空闲块连接在一个双重循环链表结构的可利用空间表中。特点在于: 每个内存区头部和底部设标识,标识该区域是占用块还是空闲块,使得在...

    内存回收系统做法

    1. 一种策略是系统继续从高地址的空闲块中进行分配,不理会已经分配给用户的内存区是否空闲,直到分配无法进行,系统才去回收所有用户不再使用的空闲块,并重新组织内存将所有空闲的内存区连接在一起成为一个大的空闲块
    2. 另一种策略是用户一旦运行结束,便将它所占的内存区释放成为空闲块,每当新的用户请求分配内存时,系统巡视整个内存区的空闲块,并从中找出一个合适的分配之。为此,系统需建立一张记录所有空闲块的“可利用空间表”
    3. 可利用空间表一般为链表或者目录表 ,目录表包括:初始地址、空闲块大小、使用情况三项,链表的每个表结点表示一个空闲块,每次分配回收即是在可利用空间表中删除或插入结点。

    可利用空间表及分配方法

    只讨论链表,可利用空间表可称为存储池,三种情况:

    1. 系统运行期间所有用户请求分配的存储量大小相同,通常在系统开始运行时将内存区分割为大小相同的块,然后用指针链接成一个可利用空间表,请求内存时将第一个结点分配给程序,回收内存时在表头插入结点即可。
    2. 系统运行期间用户请求分配的存储量有若干种大小的规格,通常建立若干个可利用空间表,表内结点大小相同。此时分配与回收与第一种类似,只是在各自的可利用空间表中进行。两种额外情况:
    • 如果结点大小与请求分配的内存大小相同的链表空了,查询结点较大的链表,取出一个结点分配一部分内存,再将剩下的部分插入相应的链表中
    • 如果对应结点大小和大结点的链表都为空,不一定是内存满了,而是有可能经过多次分配之后,空闲区变成了多个小结点在其他链表中,此时应当重整内存,即"内存紧缩"
    1. 系统运行期间用户请求分配的存储量大小不固定,就将整个内存空闲区作为结点,分配时割出一个结点,这种情况下结点应当指明自身的大小,即有一个结点大小域

    由于结点大小不同,故在分配时有一个问题,如果需要m大小的空间,可利用空间表中却有若干个不小于m的空闲块,该怎么分配:
    (1) 首次拟合 从表头指针查找,找到的第一个大小不小于m的结点的一部分分配给用户。
    (2) 最佳拟合 将可利用空间表中一个不小于m且最接近m的空闲块的一部分分配给用户,推荐按结点从小到大排序,回收时把释放的空闲块插入到合适的位置上区
    (3) 最差拟合 将可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户,此时结点应当从大到小排序,分配时只需从链表中删除第一个结点,并分配一部分给用户,剩余部分插入到合适位置。

    最佳拟合法适用于请求分配的内存大小范围较广的系统。最差拟合每次从最大结点分配,最终结点大小趋于一致,适用于内存大小范围较窄的系统。

    通过时间考虑:首次拟合分配时需查找可利用空间表,回收时插入到表头;最佳拟合无论分配回收都需要查找可利用空间表;最差拟合分配时直接表头分配,回收时查找

    边界标识法

    边界标识法是操作系统中用以动态分区分配的一种存储管理方法,系统将所有空闲块连接在一个双重循环链表结构的可利用空间表中。特点在于:

    1. 每个内存区头部和底部设标识,标识该区域是占用块还是空闲块,使得在回收用户释放的空闲块时易于判别在物理位置上与其相邻的内存内存区域是否为空闲块,以便合并空闲存储区

    可利用空间表的结构

    space指示存储单元,单元大小由head中的size域表示,以head和foot作为边界,head和foot中都有标志域tag,

    typedef struct WORD
    {
    	union{
    		WORD *llink;//指向前驱
    		WORD *uplink;//指向本结点头部
    	};
    	int tag;//空闲占用标识
    	int size;//块大小
    	WORD *rlink;//指向后继结点
    	OtherType other;//其他
    }WORD,head,foot,*Space;
    

    可利用空间表设置为双重循环链表,llink指向前驱,rlink指向后继,表中不设头节点,表头指针可以指向任意一个结点。

    分配算法

    首次拟合法,找到表头指针所指结点起在可利用空间表中查找,找到第一个容量不小于请求分配的存储量的空闲块就进行分配
    (1)如果待分配块容量为m个字,每次分配分配n个字给用户,剩余m-n大小的结点仍然留在链表中,这样的话会剩余容量极小的块,但设定一个e,m-n<e时,就将m整块分配给用户,反之分配高地址的n个字给用户(避免修改指针)
    (2) 如果每次分配都从表头指针开始找的话,会使得存储量小的结点密集在头指针附近,所以每次查找应当从不同结点开始查找,实现方法是使头指针指向刚分配过结点的后继结点

    Space AllocBoundTag(Space &pav, int n)
    {
    	for(p=pav;p&&p->size<n&&p->rlink!=pav;p;p->rlink)//查找空闲块
    		;
    	if(!p||p->size<n)
    		return nullptr;//找不到合适空闲块
    	else
    	{
    		f=Footloc(p);
    		pav=p->rlink;//让表头结点指向尾结点
    		if(p->size-n<=e)
    		{
    			if(pav==p)//分配后变为空表
    				pav=NULL;
    			else
    			{
    				pav->llink=p->llink;//p结点整个分配,删除p结点,
    				p->llink=p->rlink=pav;
    			}
    			p->tag=f->tag=1;//标识为使用块
    		}
    		else
    		{
    			f->tag=1;//分配块标识
    			p-=n;//减去分配块大小
    			f=Footloc(p);//切换到空闲块底部
    			f->tag=0;
    			f->uplink=p;
    			p=f+1;//分配块头部
    			p->size=n; p->tag=1;
    			
    		}
    		return p;
    	}
    }
    

    回收算法

    若释放块头部地址为p 则p-1为左侧紧邻块地址,p+p->size为右侧紧邻块地址,检查这两个地址中tag就知道是否为空闲块,故有四种情况

    (1) 左右均为占用块,即做简单插入

    p->tag=0;Footloc(p)->uplink=p;Footloc(p)->tag=0;//设置空闲标识
    if(!pav)
    {
    	pav=p->link=p->rlink=p;
    }
    else
    {//双向链表
    	q=pav->llink;
    	p->rlink=pav;
    	p->llink=q;
    	q->rlink=pav->llink=p;
    	pav=p;
    }
    
    p->tag=0;
    Footloc(p)->uplink=p;
    Footloc(p)->tag=0;
    if(!pav)
    	pav=p->llink=p->rlink=p;
    else
    {//插到pav前面
    	l=pav->llink;
    	l->rlink=p;
    	p->llink=l;
    	p->rlink=pav;
    	pav->llink=p;
    	pav=p;
    }
    
    

    (2) 左边为空闲块,右边为占用块,只需改变左邻结点的底部,重新设置size

    size=p->size;
    l=(p-1)->uplink;
    l->size+=size;
    bottom=p+n-1;
    bottom->tag=0;
    bottom->uplink=l;
    

    (3) 左边为占用块,右边空闲块,与右边合并之后,结点头指针改变了位置

    size=p->size;]
    p->tag=0;
    tmp=p+p->size;
    l=tmp->llink;
    p->llink=l;
    l->rlink=p;
    r=tmp->rlink;
    r->llink=p;
    p->rlink=r;
    Footloc(tmp)->uplink=p;
    

    (4) 左右邻均是空闲块,增加左邻的space容量,删去右邻结点

    n=p->size;
    r=p+p->size;
    l=(p-1)->uplink;
    l->size+=(n+r->size);
    r->rlink->llink=r->llink;
    r->llink->rlink=r->rlink;
    Footloc(r)->uplink=l;
    

    伙伴系统

    伙伴系统无论是占用块还是空闲块,大小均为2的kk次方,如当用户申请n个字的内存区时,分配的占用块大小为2k(2k1&lt;n&lt;2k)2^k(2^{k-1}&lt;n&lt;2^k)个字,

    可利用空间表的结构

    整个内存区为大小为2m2^m的空闲块,一段时间后被分成若干占用块和空闲块,将大小相同的空闲块建于一张子表中,每个子表是双重链表

    #define m 16//可利用空间总容量的幂次,子表个数m+1
    typedef struct WORD_b
    {
    	WORD_b *llink,*rlink;
    	int tag;
    	int kval;
    	OtherType other;
    }WORD_b,head;
    typedef struct HeadNode
    {
    	int nodesize;
    	WORD_b *first;
    }FreeList[m+1];
    

    分配算法

    提出大小为n的分配请求,在可利用表上寻找与n大小匹配的子表,子表非空,直接分配结点,子表为空,则从比结点更大的非空子表中查找,将空闲块的一部分分配给用户。
    如果2k1&lt;n&lt;=2k12^{k-1}&lt;n&lt;=2^k-1 k+1子表不为空,那么就删除此链表中第一个结点并分配给用户,若2k2&lt;n&lt;=2k112^{k-2}&lt;n&lt;=2^{k-1}-1 因为结点大小2k12^{k-1}的子表为空,需要从结点大小为2k2^k取出一块,将其中一半分配给用户,剩余一半空间作为新节点插在对应大小链表中

    WORD_b* alloc(FreeList &avali, int n)
    {
    	for(int k=0;k<=m&&(avali[k].nodesize<n+1||!avali[k].first))
    		;
    	if(k>m)
    		return nullptr;
    	else
    	{
    		first=avali[k].first;
    		pre=first->llink;
    		post=first->rlink;
    		if(post=first)
    			avali[k].first=nullptr;
    		else
    		{
    			avali[k].first=post;
    			pre->rlink=post;
    			post->llink=pre;
    		}
    		int i=1;
    		for(i=1;avali[k-i].nodesize>=n+1;i++)
    		{
    			pi=pa+2^(k-i);pi->rlink=pi;pi->llink=pi;
    			pi->tag=0;pi->kval=(k-i);avali[k-1].first=pi;
    		}
    		pa->tag=1;
    		pa->kval=k-(--i);//循环结束的时候多加了一次i
    	}
    	return pa;
    }
    

    回收算法

    回收空闲块,需要将新空闲块插入到可利用空间表中,并与其在之前分裂出来的伙伴块做合并,若伙伴块不为空闲块,只需简单插入到对应子表中,否则要找到伙伴结点,删除之并判断合并后的空闲块的伙伴是否是空闲块。

    起始地址为p,大小为2k2^k的内存块,其伙伴块的起始地址为

    buddy(p,k)=p+2kbuddy(p,k) = p+2^k
    (若pMOD2k+1=0p MOD 2^{k+1}=0)

    buddy(p,k)=p2kbuddy(p,k) = p-2^k
    (若pMOD2k+1=2kp MOD 2^{k+1}=2^k)

    无用单元收集

    无用单元是那些用户不再使用而系统没回收的结构和变量,如

    p=malloc(size);
    q=p;
    free(p);
    

    就使得指针变量q悬空,如果所释放的结点再被分配而继续访问q指向的结点,这种行为被称为悬挂访问

    对于使用广义表的程序,常常出现悬空指针问题(P207),解决方法是在程序的运行过程中对所有的链表结点,不管是否有用都不回收,直到可利用空间表为空,此时暂时中断执行程序,将所有当前不使用链接在一起,成为一个新的可利用空间表。只需对当前正在使用的指针变量出发,遍历链表,就可以标记正在使用的结点,其他的都可以释放了,步骤如下:
    (1) 对占用结点加上标志域,使用为1,空闲为0
    (2) 遍历可利用存储空间顺序,将所有标志域为0的结点链接成为一个新的可利用空间表

    第一步较为困难,因为此时存储空间几乎为0,
    (1)递归法:列表为空,无需遍历;若为一个数据元素,标志元素结点;若多个元素,先标志表结点,在分别遍历表头和表尾。
    该方法是递归法, 需要内存来保存递归栈,因为递归层次不定,所以需要较大的空间以防栈溢出
    (2) 非递归法:广义表结点分为表结点和元素结点,元素结点没有指针域,表结点有表头指针和表尾指针,所以很像二叉树的二叉链表,元素结点相当于二叉树的叶子结点,所以很容易按树的遍历的非递归算法写出广义表非递归算法
    (3) 利用表结点本身的指针域标记遍历路径,使用三个指针,p指向某个表结点时,t指向p的母表结点,q指向p的表头或者表尾。
    当q指向p的表头结点时:

    • p表头是元素结点,遍历表头仅需打上标志后再令q指向p的表尾
    • p表头为空表或者已经加上标志的子表,只需令q指向p的表尾
    • p的表头为未加标志的子表,需遍历表头子表,p赋q的值,t赋p的值,并令p所指结点的hp域为t tag域为0

    当q指向p的表尾结点时

    • p的表尾为未加标志的子表,遍历表尾子表,p赋q的值,t赋p的值,并令p所指结点的tp域为t
    • p表尾为空或已经加上标志的子表,p应退回到母表结点,t也后退一步
    void MarkList(GList &GL)
    {
    	t = nullptr;
    	p = GL;
    	finished = false;
    	while(!finished)
    	{
    		while(p->mark==0)
    		{
    			p->mark=1;
    			q=p->p.hp;//q指向p表头
    			if(q&&q->mark==0)
    			{
    				if(q->tag==0)
    					q->tag=1;
    				else
    				{
    					p->p.hp=t;
    					p->tag=0;
    					t=p;
    					p=q;//返回继续遍历
    				}
    			}
    		}
    		q=p->tp;
    		if(q&&q->mark==0)
    		{	
    			p->p.tp=t;
    			t=p;
    			p=q;		
    		}
    		else
    		{
    			while(t&&t->tag==1)
    			{
    				q=t;
    				t=q->p.tp;
    				q->p.tp=p;
    				p=q;
    			}
    			if(!t)
    				finished=true;
    			else
    			{
    				q=t;
    				t=p->p.hp;
    				q->p.hp=p;
    				p=q;
    				p->tag=1;
    			}
    		}
    	}
    }
    

    第三种算法不需要附加存储,但是每个表结点指针域的值都要做两次改变,时间上的开销相当大。而递归算法占用的空间较大,但是时间开销较小。总之无用单元 收集较为耗费时间,不能在实时处理的情况下应用。
    第一步对结点加标志,时间与结点数成正比,假设总占用节点数为NN 则标志过程所需时间为c1Nc_1N 第二步是从第一个结点起,链接未加标志的结点,假设可用空间MM个结点,所需时间为c2Mc_2M 收集总时间为c1N+c2Mc_1N+c_2M 收集的无用结点个数为MNM-N,显然,如果无用结点数少,则平均收集每个结点花费时间就多。

    存储紧缩

    之前介绍的都是建立无用结点组成的可利用空间表。现在采用另一种结构:可利用空间组织为地址连续的存储区,每次分配都是从这个空间中划出一块,即设立一个堆指针指向最高地址,每次用户请求分配,先将堆指针值拷贝给用户,随后堆指针移动请求的空间大小。因此分配算法很简单,但是回收就比较困难,因为必须将所释放的整个空闲块合并到堆上去(存储紧缩)
    (1) 第一种办法是一旦有用户释放存储就进行存储紧缩
    (2)另一种是直到堆指向最高地址或可利用空间不够分配时才进行存储紧缩

    步骤如下
    首先堆占用块进行标志

    1. 计算占用块的新地址,设立两个指针,分别指示占用块在紧缩之前和之后的源地址和新地址,因此在占用块的第一个存储单位,设立长度域和标志域和新地址域
    2. 修改用户的初始变量表,以便在存储紧缩后用户程序能继续正常运行
    3. 检查每个占用块中存储数据,若有指向其他存储块的指针,则做相应的修改
    4. 将所有占用块迁移到新地址去。

    在这里插入图片描述

    展开全文
  • 这是我上数据结构课时写的,在学线性表时,老师让我们写动态存储结构的线性表,所以我就写了这个链表
  • 7:数据结构动态存储:    一个结构根本不够!    本章内容:  1)如何用结构指针吧自定义数据类型连接成复杂的大型数据结构;通过创建链表探索其中的基本原理;  2)通过在堆上动态分配空间来学习如何...

     该系列文章系个人读书笔记及总结性内容,任何组织和个人不得转载进行商业活动!

    7:数据结构与动态存储:

     

     一个结构根本不够!

     

     本章内容:

     1)如何用结构指针吧自定义数据类型连接成复杂的大型数据结构;通过创建链表探索其中的基本原理;

     2)通过在堆上动态分配空间来学习如何让数据结构处理可变数量的数据,并在完成后释放空间;(如果嫌清理麻烦,可以学习一下使用valgrind)

     

     保存可变数量的数据:

         为了保存可变数量的数据,需要一样比数组更灵活的东西,即链表;

         链表是一连串的数据;

         链表是一种抽象数据结构;它是通用的,可以用来保存很多不同类型的数据,所以被称为抽象数据结构;

         链表保存了一条数据和一个链向另一条数据的链接;

         要知道链表从哪里开始,就可以遍历链表,可以从一条数据跳到另一条,直到链表的尾部;

     (P1)

     

     在链表中的插入数据:

         相比于数组,链表插入非常快;如果想在数组中插入一个值,就不得不将插入点后所有的数据后移一个位置;

         我们可以用链表来保存可变数量的数据;

     (P2)

     

     如何在C语言中创建链表?

     

     创建递归结构:

         链表中每个结构都需要与下一个结构相连;

         如果一个结构包含一个链向同种结构的链接,这种结构就称为递归结构;

         递归结构中含有指向同种结构的指针;

     场景:

         太平洋上诸多岛屿之间的飞机航线,受天气原因可能会临时变化,存储的结构可以设计如下:

     (Code7_1)

    /*
     *
     */
    
    #include <stdio.h>
    
    //island
    typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
        char * name;
        char * opens;//岛上机场的营业时间
        char * closes;
        struct island * next;//这里不能用别名 必须用结构体名
    }island;
    
    int main() {
        
        island island1 = {"A","09:00","17:00",NULL};
        island island2 = {"B","09:00","17:00",NULL};
        island island3 = {"C","09:00","17:00",NULL};
        island island4 = {"D","09:00","17:00",NULL};
        island island5 = {"E","09:00","17:00",NULL};
        
        island1.next = &island2;
        island2.next = &island3;
        island3.next = &island4;
        island4.next = &island5;
        
        //2、3之间插入一个岛
        island island_insert = {"E","09:00","17:00",NULL};
        
        island_insert.next = island2.next;
        island2.next = &island_insert;
        
        return 0;
    }

     这里要小心:

         递归结构要有名字;

         在递归结构中,需要包含一个相同类型的指针,C语言的语法不允许用typedef别名声明它,因此必须为结构起一个名字;

     

     接下来,参看Code7_1中实现的飞机航线上诸岛的链表示例:

         初始island的next字段值都设为NULL;C语言中,NULL的值实际上为0,NULL专门用来把某个指针设为0;

         我们需要小心地将每一个island的next变量设为下一个island的地址;

     

     在链表中插入值:

         通过修改指针就可以实现插入island,参看Code7_1;

         这里在中间位置声明了要插入的变量,这在C99和C11标准是可以的,在ANSI C中,必须在函数的顶部声明局部变量;

     

     示例:

         打印链表-航线上岛屿的名字;

     (Code7_2)

    /*
     *
     */
    
    #include <stdio.h>
    
    //island
    typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
        char * name;
        char * opens;//岛上机场的营业时间
        char * closes;
        struct island * next;//这里不能用别名 必须用结构体名
    }island;
    
    int display(island * start){
        island * il = start;
        int i;
        for (i = 0 ; il->next != NULL; il = il->next , i++) {
            printf("Island name:%s\nOpen-Close:%s-%s\n",il->name,il->opens,il->closes);
        }
        return i;
    }
    
    int main() {
        
        island island1 = {"A","09:00","17:00",NULL};
        island island2 = {"B","09:00","17:00",NULL};
        island island3 = {"C","09:00","17:00",NULL};
        island island4 = {"D","09:00","17:00",NULL};
        island island5 = {"E","09:00","17:00",NULL};
        
        island1.next = &island2;
        island2.next = &island3;
        island3.next = &island4;
        island4.next = &island5;
        
        printf("%i\n",display(&island1));
        
        return 0;
    }
    

     log:

     Island name:A

     Open-Close:09:00-17:00

     Island name:B

     Open-Close:09:00-17:00

     Island name:C

     Open-Close:09:00-17:00

     Island name:D

     Open-Close:09:00-17:00

     4

     

     我们打印了该线路上所经过的岛屿,同时返回了岛屿的数量(没有打印出目的地岛屿,可以使用do-while打印);

     

     注意:

         不同于J其他语言,如Java,它有内置链表;C语言没有内置数据结构,必须自己创建;

         链表想遍历只能从头开始;这一点不比数组;

         递归定义的结构中使用的是指向其他结构的指针,它不能换成一个递归定义的结构,因为结构在存储器中大小确定,如果递归地赋值自己,两条数据将不一样大;

     

     程序需要动态存储:

     场景:

         从一个不断更新的文件中读取各个岛的信息,比如一个每行只有一个 island name的文件;我们不知道这个文件有多大;

     

     分析:

         前面程序我们是为每个岛都声明了一个变量,但现在我们不知道文件大小,又怎么能知道有多少变量呢?

         我们需要在需要的时候分配新的存储空间;

     

     所以,需要以某种方法创建动态存储:

         到目前为止,我们写过的所有程序都使用静态存储;

         每当想保存一样东西,都在代码中添加一个变量,通常保存在栈中;(栈式存储器中专门用来保存局部变量的区域)

         如果编译时知道需要保存多少数据,那没问题,但程序在运行前往往不知道自己需要多少存储空间;

     

     用堆进行动态存储:

         程序运行时很难在栈上分配大量空间,所以需要堆;

         堆是程序中用来保存长期使用数据的地方;堆上的数据不会自动清除;是保存数据的好地方,比如保存我们的链表;

     

     首先,用malloc()获取空间:

         如果程序在运行时发现有大量数据要保存,要申请一个大容量的存储空间,可以用malloc()函数来申请;

         告诉malloc()需要多少个存储,他会要求操作系统在堆上分配空间;然后会返回一个指针,指向堆上新分配的空间;

         指针就好比这块存储空间的钥匙,可以用它来访问存储器,并跟踪这块区域的使用;

     

     有用有还:

         堆存储器的优点是可以占用很长时间,缺点同样是这个;

         使用栈的时候,无需操心归还存储器,因为这个过程是自动进行的;离开函数事,局部变量会从栈中清除;

         堆则不同,一旦申请就不能再分配,直到告诉C标准库,你已用完;

         堆的空间有限,不断堆积,会造成存储器泄漏,这种错误很常见,却也很难追踪;

     

     调用free()释放存储器:

         malloc()函数分配空间并给出一个指向这块空间的指针;你需要用这个指针访问数据,用完之后,需要用free()函数释放存储器;

     

     看看malloc()和free()如何工作:

     

     用malloc()申请存储器:

         memory allocation(存储器分配)的意思;

         malloc()接收一个参数:所需要的字节数;通常我们不知道确切的字节数,因此malloc()经常与sizeof运算符一起使用;

     像这样:

     #include <stdlib.h>//包含stdlib.h头文件,以使用malloc()和free()函数;

     ...

     malloc(sizeof(island));//表示“给我足够大的空间来保存island结构”

     

     siziof告知某种数据类型在系统中占了多少字节;这种数据类型可以是结构,也可以是int或double这样的基本数据类型;

     malloc()函数为你分配一块存储器,然后返回一个指针;指针中保存了存储器块的起始地址;malloc()返回的是通用指针,即void*类型的指针;

     

     用free()释放存储器:

         如果在一个地方用malloc()分配了存储器,就应该在后面用free()释放他;

         free()需要接收malloc()创建的存储器地址;只要告诉C标准库存储器块从哪里开始,他就能查阅记录,知道要释放多少存储器;

     island * p = malloc(sizeof(island));

     free(p);//表示释放分配的存储器,从堆地址p开始;

     (Code7_3)

    /*
     * 创建一条航线之后 打印输出
     */
    
    #include <stdio.h>
    #include <stdlib.h>//使用malloc()不要忘记导入头文件
    #include <string.h>
    
    //island
    typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
        char * name;
        char * opens;//岛上机场的营业时间
        char * closes;
        struct island * next;//这里不能用别名 必须用结构体名
    }island;
    
    int display(island * start){
        if (start == NULL) {
            return 0;
        }
        island * il = start;
        int i;
        for (i = 1 ; il->next != NULL; il = il->next , i++) {
            printf("Island name:%s  Open-Close:%s-%s\n",il->name,il->opens,il->closes);
        }
        printf("Island name:%s  Open-Close:%s-%s\n",il->name,il->opens,il->closes);
        return i;
    }
    
    island * create(char * name){
        island * i = malloc(sizeof(island));
        i->name = name;
        i->opens = "09:00";
        i->closes = "17:00";
        i->next = NULL;
        
        return i;
    }
    
    int main() {
        char name[80];
        island * start = NULL;
        island * current = NULL;
        
        puts("输入岛名:(输入S结束)");
        while (scanf("%79s",name) == 1) {
            if (strlen(name) == 1 && (name[0] - 'S' == 0)){
                break;
            }
            island * il = create(name);
            if (start == NULL) {
                start = il;
            }
            if (current != NULL) {
                current->next = il;
            }
            current = il;
            
            puts("输入岛名:");
        }
        
        printf("%i\n",display(start));
        
        //free all
        return 0;
    }

     这个程序中,我们定义了一个结构;一个遍历的方法;一个生成的方法;并在main函数中循环输入直到输入S;

     log:

     输入岛名:

     a

     a-输入岛名:

     b

     b-输入岛名:

     c

     c-输入岛名:

     d

     d-输入岛名:

     e

     e-输入岛名:

     f

     f-输入岛名:

     S

     S-Island name:S  Open-Close:09:00-17:00

     Island name:S  Open-Close:09:00-17:00

     Island name:S  Open-Close:09:00-17:00

     Island name:S  Open-Close:09:00-17:00

     Island name:S  Open-Close:09:00-17:00

     Island name:S  Open-Close:09:00-17:00

     6

     

     奇怪的事情发生了,我们用来存储name的字符数组在最后接收字符“S”之后,前面所有的岛的名字全都被莫名的修改了!

     

     问题在于:

         当代码记录岛名字的时候,并没有接收一份完整的name字符,而是记录了name字符串在存储器中的地址;

         这也导致,所有创建的岛都共享了同一个name字符串;一旦局部变量name更新了,前面的岛的名字也就没了;

     

     聚焦字符串复制:

         string.h头文件中创建了一个叫strdup()的函数,可以将字符串的所有字符复制到堆上;

         strdup()函数能够计算出字符串的长度,然后调用malloc()函数在堆上分配相应的空间;

         然后,strdup()函数把所有字符串复制到堆上的新空间;

         因为strdup()是把新字符串放在堆上,所以千万记得要用free()函数释放空间;

     

     用strdup()修改代码:

         i->name = name;    =>     i->name = strdup(name);

         opens和closes只所以不用修改,是因为他们根本就不会变;

     (Code7_4)

    /*
     * 创建一条航线之后 打印输出
     */
    
    #include <stdio.h>
    #include <stdlib.h>//使用malloc()不要忘记导入头文件
    #include <string.h>
    
    //island
    typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
        char * name;
        char * opens;//岛上机场的营业时间
        char * closes;
        struct island * next;//这里不能用别名 必须用结构体名
    }island;
    
    int display(island * start){
        if (start == NULL) {
            return 0;
        }
        island * il = start;
        int i;
        for (i = 1 ; il->next != NULL; il = il->next , i++) {
            printf("Island name:%s  Open-Close:%s-%s\n",il->name,il->opens,il->closes);
        }
        printf("Island name:%s  Open-Close:%s-%s\n",il->name,il->opens,il->closes);
        return i;
    }
    
    island * create(char * name){
        island * i = malloc(sizeof(island));
        i->name = strdup(name);
        i->opens = "09:00";
        i->closes = "17:00";
        i->next = NULL;
        
        return i;
    }
    
    void release(island * start) {
        island * i = start;
        island * next = NULL;
        for (; i != NULL; i = next) {
            next = i->next;
            free(i->name);//首先需要释放strdup()创建的name字符串
            free(i);
        }
        
    }
    
    int main() {
        char name[80];
        island * start = NULL;
        island * current = NULL;
        
        puts("输入岛名:(输入S结束)");
        while (scanf("%79s",name) == 1) {
            if (strlen(name) == 1 && (name[0] - 'S' == 0)){
                break;
            }
            island * il = create(name);
            if (start == NULL) {
                start = il;
            }
            if (current != NULL) {
                current->next = il;
            }
            current = il;
            
            puts("输入岛名:");
        }
        
        printf("%i\n",display(start));
        
        //free all
        release(start);
        
        return 0;
    }

     log:

     输入岛名:(输入S结束)

     a

     输入岛名:

     b

     输入岛名:

     c

     输入岛名:

     d

     输入岛名:

     e

     输入岛名:

     f

     输入岛名:

     S

     Island name:a  Open-Close:09:00-17:00

     Island name:b  Open-Close:09:00-17:00

     Island name:c  Open-Close:09:00-17:00

     Island name:d  Open-Close:09:00-17:00

     Island name:e  Open-Close:09:00-17:00

     Island name:f  Open-Close:09:00-17:00

     6

     

     上述示例中:

         使用字符指针相比于字符数组更好,因为字符数组需要提前决定字符串的长度;

     值得注意的是:

         我们添加了一个新的函数release(),用于链表的释放;

         其中,需要释放使用strdup()函数创建的name字符串;

         之后,再释放相应节点的结构;

         用完后调用释放存储器调用release(start);即可;

     

     有了动态分配存储器,就能在运行时创建需要的存储器,使用malloc()和free(),可以访问动态堆存储器;

     

     小结:

         堆之所以叫堆,因为计算机不会自动组织它,他只是一大堆数据而已;

         垃圾收集:一些语言会跟踪你在堆上分配的数据,当不再使用时,就释放它们;C语言是没有的;

         虽然操作系统会在程序结束时回收所有存储器,但最后显示的释放自己创建的每样东西;

     

     要点:

     -可以用动态数据结构保存可变数量的数据项;

     -可以很方便地在链表这种数据结构中插入数据项;

     -在C语言中,动态数据结构通常用递归结构来定义;

     -递归结构中有一个或多个指向相同结构的指针;

     -栈用来保存局部变量,他由计算机管理;

     -堆用来保存长期使用的数据,可以用malloc()分配堆空间;

     -sizeof运算符告诉你一个结构需要多少空间;

     -数据会一直留在堆上,直到用free()释放它;

     

     使用结构我们还可以创建很多其他形式的数据结构:

     (P3)

     

     数据结构很有用,但要小心使用:

         当用C语言创建这些数据结构时需要非常小心,如果没有记录好保存的数据,就可能把不同的数据留在堆上;时间久了,会消耗存储器,程序也会因为存储器错误而崩溃;

         我们可以使用valgrind工具追查代码中的存储器泄露:

             gcc -g xxx.c ... //-g开关会告诉编译器要记录要编译代码的行数

             valgrind --leak-check=full ./xxx

     

     C语言工具箱:

     -链表比数组更容易扩展;

     -在链表中插入数据很方便;

     -链表是动态数据结构;

     -动态数据结构使用递归结构;

     -递归结构包含一个或多个链向相同结构数据的链接;

     -malloc()在堆上分配存储器;

     -free()释放堆上的存储器;

     -与栈不同堆存储器不会自动释放;

     -栈用来保存局部变量;

     -strdup()会把字符串复制到堆上;

     -存储器内存泄漏是指存储器分配出去以后,你再也访问不到;

     -valgrind可以帮助跟踪存储器泄露;(可自行查阅)

     

     

    展开全文
  • 数据结构动态存储管理(C语言)

    千次阅读 2017-09-05 10:43:13
    2. 动态存储分配过程的内存状态系统运行一段时间后,有些程序的内存被释放,造成了上图(b)中的状态。假如此时又有新的程序请求分配内存,系统将如何做呢?通常有两种做法:一种策略是继续从高地址的空闲块中进行分配...

    一、 概述

    1. 占用块
    占用块:已分配给用户使用的地址连续的内存区
    可利用空间块:未曾分配的地址连续的内存区
    
    2. 动态存储分配过程的内存状态

    这里写图片描述

    系统运行一段时间后,有些程序的内存被释放,造成了上图(b)中的状态。假如此时又有新的程序请求分配内存,系统将如何做呢?
    
    通常有两种做法:一种策略是继续从高地址的空闲块中进行分配,而不考虑已经分配给用户的内存区是否已空闲,知道分配无法进行(即剩余的空闲块不能满足分配的请求)时,系统才回收所有用户不再使用的空闲块,并且重新组织内存,将所有空闲的内存区连接在一起成为一个大的空闲块。另一种策略是用户一旦运行结束,便将它所占内存区释放成为空闲区,同时,当用户请求新的内存分配时,系统需要检查整个内存区中的所有空闲块,并从中找出一个“合适”的空闲哭分配之。对于第二种策略,需要建立一张记录所有空闲区的“可利用空间表”,此表可以是“目录表”,也可以是链表。
    

    这里写图片描述

    二、 可利用空间表及分配方法

    可利用空间表也称为存储池。
    
    1. 可利用空间表的三种不同结构形式
    (1)系统运行期间所有用户请求分配的存储量大小相同。对此类系统,在系统开始运行时将它使用的内存区按所需大小分割成若干大小相同的块,然后用指针链接成一个可利用空间表。因为表中节点的大小相同,则分配时无需查找,只要将表中的第一个节点分配给用户即可;同样,当用户释放内存时,系统只要将用户释放的空闲块插入表头即可。
    (2)第二种情况,系统运行期间用户请求分配的存储量有若干种大小的规格。对此类系统,一般情况下建立若干个可利用空间表,同一链表中的节点大小相同。此时的分配和回收在很大程度上和第一种情况类似,只是当节点大小和请求分配的内存大小相同的链表为空时,需要查询节点较大的链表,并从中取出一个节点,将其中一部分内存分配给用户,而将剩余部分插入到相应大小的链表中。回收和第一种情况相同。然而,这种情况的系统还有一个特殊的问题要处理:即当节点与请求相符的链表和节点更大的链表均为空时,分配不能进行,而实际上内存空间并不一定不存在所需大小的连续空间,只是由于在系统运行过程中,频繁出现小块的分配和回收,导致大街店链表中的空闲块被分隔成小块后插入在小节点的链表中,此时若要系统继续运行,就必须重新组织内存,即执行“存储紧缩”的操作。
    (3)第三种情况,系统在运行期间分配给用户的内存块的大小不固定,可以随请求而变。因此,可利用空间表中的节点即空闲块的大小也是随意的。
    

    这里写图片描述

    这种情况下节点的结构与之前的有点不一样,需要有一个size域来记录该空闲块的大小。
    由于可利用空间块中节点大小不同,则在分配时就有一个如何分配的问题。假设某用户需大小为n的内存,而可利用空间表中仅有一块大小为m》n的空闲块,则直接将这个空闲块分配给申请的用户,同时将剩余大小为m-n的部分作为一个节点落在链表中即可。若可利用空间表中有若干个不小于n的空闲块时,那该如何分配呢?下面给出三种不同的分配策略。
    
    a) 首次拟合法
    从表头指针开始查找可利用空间表,将找到的第一个大小不小于n的空闲块的一部分分配给用户。
    
    b) 最佳拟合法
    将可利用空间表中不小于n且最接近n的空闲块的一部分分配给用户。在用最佳拟合法进行分配时,为了避免每次分配都要扫视整个链表,通常预先设定可利用空间表的结构按空间块的大小由小至大有序。因此分配时,只需找到第一块大于n的空闲块即可进行分配;但在回收时,必须将释放的空闲块插入到合适的位置上去。
    
    c) 最差拟合法
    将可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户。同样,为了节约时间,此时的可利用空间表的结构应按空闲块的大小自大至小有序。这样每次分配的时候无需查找,只需判断链表的第一个节点大小是否大于所需要的要求,如果满足则直接分配。当然,回收时也要将空闲块插入可利用空间表中合理的位置。
    
    三种分配策略各有所长。一般来说,最佳拟合法适用于请求分配的内存大小范围较广的系统。最差你和法适用于请求分配的内存范围较窄的系统。而首次拟合法的分配时随机的。
    但是从分配和回收来上看,首次拟合法在分配时需要查找可利用空间表,而回收时只需直接将节点插入表头即可;而最佳拟合法无论是分配和回收均需查找链表,最费时间;而最差拟合法,分配时不需要查找,但回收时需要。
    
    另外存在的一个问题时,相邻空闲块的节点合并问题。所以在回收空闲块时,首先应检查地址与它相邻的内存是否是空闲块。
    

    三、边界标识法(C语言实现)

    1.思想
    将系统中所有空闲块链接在一个双重循环链表结构的可利用空间表中,然后根据上面提到的三种分配策略中的一种进行分配内存(这里是实现首次拟合法)。系统的特点在于,在每个内存区的头部和底部两个边界上设有标识,以标识该区域为占用块或空闲块,使得在回收用户释放的空闲块时易于判别在物理位置上与其紧邻内存区域是否为空闲块,以便将所有地址连续的空闲块组合成一个尽可能大的空闲块。
    
    2.可利用空间表的结构
    可利用空间表节点结构:
    

    这里写图片描述

    每个节点有两个边界,一个是head,一个是foot;其中head中有四个成员变量,分别是llink、tag、size和rlink;llink的含义是指向前驱节点;tag是用于标识该内存块的状态,其中tag为1表示该内存块已被占用,tag为0表示该内存块为空闲;size用于指示当前内存块的大小(size这个大小包括了head和foot所占的空间);rlink的含义是指向后继节点。
    foot中有两个成员,一个是uplink,用于指向当前内存块的起始地址,这个成员在内存回收时起了很大的作用,tag用于表示内存块的状态,和head中的tag一样。
    
    在这里要特别说明的一点,其实foot的本质应该如下图:
    

    这里写图片描述

    只不过是size和rlink域没有使用而已。之所以说明这一点,就是为了下面说明我们结构体的定义中将uplink和llink放在一个共用体中的原因。
    
    typedef struct Word
    {
        union
        {
            struct Word *llink;     //前驱
            struct Word *uplink;    //指向头部地址    
        };
        int tag;        //tag为0表示空闲,tag为1表示占用   
        int size;       //内存块大小
        struct Word *rlink; //后继
    
    }Word, Head, Foot, *Space;
    在说明将uplink和llink放在一个共用体中之前,我们要明确的一点是,foot和head是两个不同的字,当使用每个内存区的head时,我们要使用的是llink域;而要使用foot时,我们要使用的是uplink域;即同一个结构中,根据不同情况使用不同的成员,正好符合共用体的使用。
    
    3.代码实现(C语言)
    在实现代码之前,先进行几点说明:
    (1)这里实现的是首次拟合法;
    (2)采用的是不带头结点的双向循环链表,所以当链表中无节点时,表头指针为空;
    
    在Boundary.h中实现结构体定义,以及内存操作函数的声明:
    
    /*
    内存分配策略:
               插入      回收    特点
    首次拟合法:O(n)      O(1)   链表无序,
    最佳拟合法:O(n)      O(n)   链表有序,导致空闲内存两极化
    最差拟合法:O(1)      O(1)   链表有序,导致内存平均化
    */
    
    #ifndef BOUNDARY_H_
    #define BOUNDARY_H_
    
    #define FootLoc(p) (p + p->size - 1)    //计算块尾部
    #define MEM_SIZE  1024          //字的个数  
    #define EPISION   10            //整块分配的临界阈值
    
    typedef struct Word //双向循环链表
    {
        union
        {
            struct Word *llink;    //前驱
            struct Word *uplink;   //指向当前内存块的首地址
        };
    
        int tag;    //0表示空闲,1表示占用
        int size;   //空闲内存块大小,包含头和尾
        struct Word *rlink; //后继
    }Word, Head, Foot, *Space;
    
    //先创建内存池,用于模拟内存的分配和回收
    Space CreateMem();
    Space AllocBoundTag(Space *pav, int n);
    
    void ShowUsed(Space *pav, int len);
    void ShowSpace(Space pav);
    void Destroy(Space s);
    void Free(Space *pav, Space p);
    #endif
    在Boundary.c中实现以上操作:
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include "Boundary.h"
    
    typedef struct Word
    {
        union
        {
            struct Word *llink;     //前驱
            struct Word *uplink;    //指向头部地址    
        };
        int tag;        //tag为0表示空闲,tag为1表示占用   
        int size;       //内存块大小
        struct Word *rlink; //后继
    
    }Word, Head, Foot, *Space;
    
    #define FootLoc(p) (p + p->size - 1)    //计算块尾部
    #define MEM_SIZE  1024          //字的个数  
    #define EPISION   10            //整块分配的临界阈值
    
    //申请内存池
    Space CreateMem()
    {
        Word *p = (Word*)malloc(MEM_SIZE * sizeof(Word));
        assert(NULL != p);
    
        p->llink = p;  //双向循环链表初始化
        p->rlink = p;
        p->size = MEM_SIZE;
        p->tag = 0;
    
        FootLoc(p)->uplink = p;
        FootLoc(p)->tag = 0;
    
        return p;
    }
    
    //内存分配
    Space MemAlloc(Space *pav, int n)
    {
        if (NULL == *pav)
        {
            return NULL;
        }
        //分配前先在空闲链表中找合适的空闲块
        Word *pTemp = *pav; 
        do
        {
            if (pTemp->size >= n)
            {
                break;
            }
            pTemp = pTemp->rlink;
        } while (pTemp != *pav);
        if (pTemp->size < n)    //没有找到合适的空闲块
        {
            return NULL;
        }
        else                //找到合适的空闲块
        {
            if (pTemp->size - n <= EPISION) //整块分配
            {
                if (pTemp->rlink == *pav)   //说明此时只有一个空闲块节点,此时整块分配以后链表为空
                {
                    *pav = NULL;
                }
                else
                {   //如果将此节点分配以后链表中还有其他空闲节点,则删除此已分配的空闲节点
                    pTemp->llink->rlink = pTemp->rlink;
                    pTemp->rlink->llink = pTemp->llink;
                }
                pTemp->tag = 1;
                FootLoc(pTemp)->tag = 1;
                return pTemp;   //将分配出去的内存首地址返回
            }
            else    //只分出高地址的部分内存
            {
                pTemp->size -= n;
                FootLoc(pTemp)->tag = 0;
                FootLoc(pTemp)->uplink = pTemp;
                Word *pTail = FootLoc(pTemp) + 1;
                pTail->tag = 1;
                pTail->size = n;
                FootLoc(pTail)->tag = 1;
                FootLoc(pTail)->uplink = pTail;
                return pTail;
            }
        }
        return NULL;
    }
    
    //打印占用块信息
    void ShowUsed(Space *UsedMem, int iLen)
    {
        printf("占用块信息:\n");
        for (int i = 0; i < iLen; ++i)
        {
            if (UsedMem[i] != NULL)
            {
                printf("起始地址:%d, 内存块大小:%d, 结束地址:%d\n",
                    UsedMem[i], UsedMem[i]->size, FootLoc(UsedMem[i]) + 1);
            }
        }
    }
    
    //打印空闲块信息
    void ShowSpace(Space pav)
    {
        if (NULL == pav)
        {
            return;
        }
        Space pTemp = pav;
        printf("空闲块信息:\n");
        do
        {
            printf("起始地址:%d, 内存块大小:%d, 结束地址:%d\n",
                pTemp, pTemp->size, FootLoc(pTemp));
            pTemp = pTemp->rlink;
        } while (pTemp != pav);
    }
    
    //释放某个占用块
    void Free(Space *pav, Space p)
    {
        if (NULL == *pav)   //如果链表为空,即此时没有空闲块
        {
            p->tag = 0;
            p->llink = p;
            p->rlink = p;
            FootLoc(p)->tag = 0;
            FootLoc(p)->uplink = p;
    
            *pav = p;
            return;
        }
    
        Space left;
        Space right;
        //在这里才可以体会到在内存块尾部设立uplink和tag的作用,不然没办法找到物理上的前面内存块的状态,无法进行合并
        if ((p - 1)->tag != 0 && (FootLoc(p) + 1)->tag != 0) 
        { //左右均不为空, 直接将p所指的内存插在pav之前
            left = (*pav)->llink;
            p->tag = 0;
            FootLoc(p)->tag = 0;
            p->llink = left;
            p->rlink = (*pav);
            FootLoc(p)->uplink = p;
            left->rlink = p;
            (*pav)->llink = p;
        }
        else if ((p - 1)->tag == 0 && (FootLoc(p) + 1)->tag != 0)
        {   //左空右不空,直接将p接在左边内存块的后面
            left = (p-1)->uplink;
            left->size += p->size;
            FootLoc(p)->uplink = left;
            FootLoc(p)->tag = 0;
        }
        else if ((p - 1)->tag != 0 && (FootLoc(p) + 1)->tag == 0)
        {   //右空左不空
            left = (*pav)->llink;
            right = FootLoc(p) + 1;
            //将节点p查到pav的前面
            p->tag = 0;
            left->rlink = p;
            p->llink = left;
            p->rlink = (*pav);
            (*pav)->llink = p;
            //然后删除右边的可合并节点
            right->llink->rlink = right->rlink;
            right->rlink->llink = right->llink;
            //合并节点
            p->size += right->size;
    
            FootLoc(p)->tag = 0;
            FootLoc(p)->uplink = p;
            *pav = p;
        }
        else if ((p - 1)->tag == 0 && (FootLoc(p) + 1)->tag == 0)
        {   //左右均空
            left = (p - 1)->uplink; //物理左
            right = FootLoc(p) + 1; //物理右
            //先删除物理右
            right->llink->rlink = right->rlink;
            right->rlink->llink = right->llink;
            left->size += p->size + right->size;
            FootLoc(right)->uplink = left;
            *pav = left;
        }
    }
    int main(void)
    {
        Word *pav = CreateMem();
        Word *UsedMem[10] = { NULL };        //用于存已分配的节点的首地址
        UsedMem[0] = MemAlloc(&pav, 200);
        UsedMem[1] = MemAlloc(&pav, 300);
        UsedMem[2] = MemAlloc(&pav, 400);
        UsedMem[3] = MemAlloc(&pav, 100);
        UsedMem[4] = MemAlloc(&pav, 20);    //此时还剩下24个字,而整块分配的临界值为10,所以应该将24个字全部分配
        //////  1   /////////
        ShowSpace(pav);
        ShowUsed(UsedMem, sizeof(UsedMem) / sizeof(*UsedMem));
        printf("==============================================\n"); //测试右空左不空
        Free(&pav, UsedMem[0]);
        UsedMem[0] = NULL;
        ShowSpace(pav);
        ShowUsed(UsedMem, sizeof(UsedMem) / sizeof(*UsedMem));
        printf("==============================================\n"); //测试左右均不为空
        Free(&pav, UsedMem[1]);
        UsedMem[1] = NULL;
        ShowSpace(pav);
        ShowUsed(UsedMem, sizeof(UsedMem) / sizeof(*UsedMem));
        printf("==============================================\n"); //测试左空右不空
        Free(&pav, UsedMem[3]);
        UsedMem[3] = NULL;
        ShowSpace(pav);
        ShowUsed(UsedMem, sizeof(UsedMem) / sizeof(*UsedMem));
        printf("==============================================\n"); //测试左空右不空
        Free(&pav, UsedMem[2]);
        UsedMem[2] = NULL;
        ShowSpace(pav);
        ShowUsed(UsedMem, sizeof(UsedMem) / sizeof(*UsedMem));
        printf("==============================================\n"); //测试左空右不空
        Free(&pav, UsedMem[4]);
        UsedMem[4] = NULL;
        ShowSpace(pav);
        ShowUsed(UsedMem, sizeof(UsedMem) / sizeof(*UsedMem));
        return 0;
    }
    运行结果如下:
    

    这里写图片描述

    最后再对main函数中的内存分配情况用图加以说明,当执行到main函数中标签1处为止,内存的分布如下图:
    

    这里写图片描述

    每次分配时,总是先从高地址进行分配,举个简单的例子进行说明,假设现在有两个空闲块节点,一个节点大小为100,一个节点大小为400,这两个节点在链表中的关系如下图:
    

    这里写图片描述

    现要求分配内存大小为200,则此时需要从节点大小为400的内存块中进行分配。现在分别从节点大小为400的低地址开始分配200和从高地址为尾部分配200两种情况进行说明:
    a)从节点大小为400的低地址开始分配200
    

    这里写图片描述

    b)从节点大小为400的高地址分配200
    

    这里写图片描述

    从上面两图可以看出,如果从低地址开始分配,则需要修改内存块的head,而如果从高地址开始分配,则只需修改内存块的foot即可,相比而言更加方便和简单。
    
    展开全文
  • 1、数据结构进阶一动态存储管理概念  在之前的笔记中,我们学习了数据结构的一些重要概念以及简单实现。很多代码都是摘自网络的,不过都亲测可用的并附以解释了。  这篇开始还是学习数据结构,不过类似数据结构...
  • 数据结构随笔—动态存储管理

    千次阅读 2015-04-10 16:12:33
    动态存储管理的基本问题是如何应用户请求分配内存,如何回收那些用户不在使用而释放的内存。 经过一段时间的运行,有些用户运行结束,它所占用的内存区变成空闲块,只就使整个内存区呈现出占用快和空闲块交错的状态...
  • 结构中的每个数据元素都占有一定的内存位置。 在程序执行的过程当中数据元素的存取是通过对应的存储单元来进行的。 有了高级语言之后,程序员不需要直接和内存地址打交道了。 程序中使用的存储单元都由逻辑变量...
  • 链表定义 ...单链表:n个结点链接成一个链表,即为线性表(a1,a2,a3……an)的链式存储结构,因为此链表的每个结点只包含一个指针域,所以叫做单链表。 头结点与头指针 头结点: 是指链表中的第一...
  • 链表——动态存储分配的数据结构

    千次阅读 2017-05-31 23:46:03
    链表——链式存储结构 ① 静态链表:把线性表的元素存放在数组中,这些元素之间通过逻辑关系来连接。数组单元存放链表结点,结点的莲域指向下一个元素的位置,即下一个元素所在的数组单元的下标。但是涉及长度定义的...
  • 动态存储管理的基本问题是系统如何应用户提出的'请求'分配内存?又如何回收用户不再使用而'释放'的内存,以备新的'请求'产生时重新进行分配。 提出请求的用户可能是进入系统的一个作业,也可能是程序执行过程中的...
  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。 顺序表一般可以分为: 1.静态顺序表:使用定长数组存储。 2.动态顺序表:使用动态开辟的数组存储。 以下是顺序表实现的...
  • 数据结构的概述 定义:我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序)而执行...
  • 线性表:零个或多个数据元素的有限序列 线性表是一个序列,即元素...线性表的顺序存储结构,指的是用一段地址连续的存储单元依此存储线性表的数据元素。 代码实现动态线性表的顺序存储 环境:VS2013 语言:c ...
  • 1.运算符new要为一个整数动态分配存储空间,可以用下面的语句说明一个整型指针变量int *x;当需要使用该整型时,可用下面的语句为它分配存储空间:y=new int; 为了在刚分配的空间中存储一个整数值10,*y=10;int *y y=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,525
精华内容 4,210
关键字:

数据结构动态存储

数据结构 订阅