堆和链表 ,堆和链表

我们经常在题目中有要求,输入一个整数,然后以这个整数作为数组的元素个数,下面的程序代码是错误的。
    int n,array[n];
    scanf(\"%d\",&n);
Turbo C中,不允许出现动态数组。那么如果必须需要这样时,就只能使用链表了。

一、堆
    堆是一种动态存储结构,实际上就是数据段中的自由存储区,它是C语言中使用的一种名称,常常用于动态数据的存储分配。堆中存入一数据,总是以2字节的整数倍进行分配,地址向增加方向变动。堆可以不断进行分配直到没有堆空间为止,也可以随时进行释放、再分配,不存在次序问题。
    所谓动态数组是指在程序运行期间确定其大小的,如常用到的动态数组,它们是在程序执行过程中动态进行变化的,即在程序开始部分没有说明大小,只有在程序运行期间用堆的分配函数为其分配存储空间,分配的大小可根据需要而定,这些数据使用过后,可释放它们占用的堆空间,并可进行再分配。
    堆和栈在使用时相向生长,栈向上生长,即向小地址方向生长,而堆向下增长,即向大地址方向,其间剩余部分是自由空间。使用过程中要防止增长过度而导致覆盖。
    一般的程序我们都是使用小内存模式,它的内存分配如下:
               ________________
              |     代码段     |   
              |————————|
              |     数据段     |
              |————————|
              |     BSS段     |
              |————————|
              |       堆       |
              |----------------| 自由空间
              |----------------|      
              |       栈       |
              |————————|
              |      远堆      |
              |----------------|
              |________________| 自由空间

    在堆和栈之间、以及远堆地址的后面都是自由空间,总共是64K
    堆管理函数:
        1.得到堆和栈之间的自由空间大小的函数
            小数据内存模式:unsigned coreleft(void);
            大数据内存模式:unsigned long coreleft(void);
            对于远堆,可以用farcoreleft()函数。
        2.分配一个堆空间函数
              void malloc (unsigned size);
          该函数将分配一个大小为size字节的堆空间,并返回一个指向这个空间的指针。由于这个指针是void型的,因此当将它赋给其他类型的指针时,必须对该指针进行强制类型转换。例如info是一个结构类型指针,即:
              struct addr *info;
          将由malloc()函数返回的指针赋给info时,必须进行类型转换:
              info=(struct addr *)malloc (sizeof(record));
              malloc()函数所分配的堆空间将不进行初始化。在调用malloc()函数时,若当时没有可用的内存空间,该函数便返回一个NULL指针。
        3.分配一个堆空间,其大小为能容纳几个元素,没有元素长度为size的函数
              void calloc(unsigned n,unsigned size);
          该函数将分配一个容量为n*size大小的堆空间,并用0初始化分配的空间。该函数将返回一个指向分配空间的指针,没有空间可用时,则返回一个NULL指针。
4.重新分配堆空间函数
              void *realloc(void *ptr,unsigned newsize);
          该函数将对由ptr指向的堆空间重新分配,大小变为newsize
        5.释放堆空间函数
              void free(void *ptr);

    下面举一个关于堆和栈的综合例子:

        void push(int);
        int pop();
        int *pi,*tos;

        main()
        {
            int v;
            pi=(int *)malloc(50*sizeof(int));
            if(!pi)
            {
                printf(\"allocation failure\\n\");
                exit(0);
            }
            tos=pi;
            do
            {
                printf(\"please input value,push it;enter 0 then pop;(enter -1 then stop)\\n\");
                scanf(\"%d\",&v);
                if(v!=0) push(v);
                else printf(\"pop this is it %d\\n\",pop());
            }
            while(v!=-1);
        }

        void push(int i)
        {
            pi++;
            if(pi==(tos+50))
            {
                printf(\"stack overflow\\n\");
                exit(0);
            }
            *pi=i;
        }

        int pop()
        {
            if(pi==tos)
            {
                printf(\"stack underflow\\n\");
                exit(0);
            }
            pi--;
            return *(pi+1);
        }

        程序分配100字节的堆空间,转换成int型赋给pi,当piNULL时,表示没有可用的空间了,则显示allocation failure。输入一个整数,压入栈中,当超过50时,则显示stack overflow.当输入0时,则把栈中的数据弹出。这个程序也演示了栈的后进先出的特点。

二、链表
    堆是用来存储动态数据的。动态数据最典型的例子就是链表。
    形象的说:将若干个数据项按一定的原则前后链接起来,没有数据项都有一个指向下一个数据的指针,则这些数据项靠指针链成一个表,最后的一个数据没有指针(指针为NULL),这就是链表。可以看出链表放在存储器中,并不一定象数组一样,连续存放,也可以分开存放。由于链的各节点均带有指向下一个节点的地址,因而要找到某个节点,必须要找到上一个节点,如此类推,则可由第一个节点出发找到目的点。链表在数据库建立和管理中用得比较普遍。
链表中的每个节点都具有相同的结构类型,它们是由两部分组成,即数据部分(它们包含一些有用的信息),另一部分就是链的指针。下面就定义一个通信链节点的数据结构:
        struct address
        {
            char name[30];
            char street[40];
            char city[20];
            char state[10];
            char zip[6];
            struct address *next;  /*pointer to next entry*/
        }list_entry;
    该结构中前五个成员是该节点的信息部分,最后一个成员是指向同一个结构类型的指针。即next又指向一个同样结构类型的节点。

    1.建立链表               
        建立链表时,首先要将第一个节点的内容存入堆中,为此要将堆中能存入该节点内容的内存区域首地址赋给一个指针。我们可以用malloc()函数来分配内存区域。如info是一个指针:
            info=(struct address *)malloc(sizeof(list_entry));
        当第一个节点存入有info指出的内存区后,再执行该函数,便得到狭义个节点的存储地址info,此时将该info赋给上一个节点的next,并将该节点内容存入info指出的内存区,这样两个节点就链接起来了。此过程反复多次,就可不断的将节点加入链表的尾端。

            #include \"stdlib.h\"
            #include \"alloc.h\"
            #include \"stdio.h\"
            #include \"string.h\"

            struct address
            {
                char name[30];
                char street[40];
                char city[20];
                char state[10];
                char zip[6];
                struct address *next;
            }list_entry;

            void inputs(char *,char *,int);
            void dls_store(struct address*);

            main()
            {
                struct address *info;
                int i;
                for(i=0;i<5;i++)
                {
                    info=(struct address *)malloc(sizeof(list_entry));
                    inputs(\"enter name:\",info->name,30);
                    inputs(\"enter street:\",info->street,40);
                    inputs(\"enter city:\",info->city,20);
                    inputs(\"enter state:\",info->state,10);
                    inputs(\"enter zip:\",info->zip,6);
dls_store(info);
                }
            }

            void inputs(char *prompt,char *s,int count)
            {
                char p[255];
                do
                {
                    printf(prompt);
                    gets(p);
                    if(strlen(p)>count) printf(\"\\n too long \\n\");
                }
                while(strlen(p)>count);
                strcpy(s,p);
            }

            void dls_store(struct address *in)
            {
                static struct address *last=NULL;
                if(!last) last=in;
                else last->next=in;
                in->next=NULL;
                last=in;
            }

            inputs()函数比较简单,就不说明了。
            dls_store()函数是将输入的节点地址写到上一个节点的next指针项。其中定义的结构指针last是一个静态变量,初始值为NULL,这意味着在编译时将为该变量分配一个固定的存储空间以存放其值。因初始值为NULL,这样在第一次调用该函数时,由于它代表一个空指针,因而把由malloc()分配的第一个节点地址赋给它,使last指向该节点,第二次调用时,静态变量last已指向第一个节点地址。如此反复调用,便建立起了n次调用产生的n个节点的链了(本题n=5)

        2.链数据的插入和删除
            对于一个已排序好的链表(假设是生序),现在想插入一个数据进去,可能有三种情况:
            (1).比首项数据还小,即插入的数据作为首项出现:
                这种情况我们的处理方法是:把该数据作为第一项,指针指向原先的首项即可。设原先首项为top,待插入的数据为in,则:
                    in->next=top;
                即可让该数据作为链表的头。
            (2).比最后一项大,即插入的数据作为最后一项出现:
                这也很好办,设原先最后一项为old,则:
                    old->next=in;
                    in->next=NULL;
            (3).作为中间某一项出现:前面是old,后面是top,则:
                    old->next=in;
                    in->next=top;
                如果想删除一个数据,也可能是出现在开头,中间和结尾。
例如想删除in这个数据,它原先的前面是old,后面是top,即原先的链表是这样:
                    old->next=in;
                    in->next=top;
                现在删除in,只需把old指向top即可:
                    old->next=top->next;

            /*删除节点函数*/
                void delete(struct address *info,struct address *old)
                {
                    if(info)
                    {
                        if(info==start) start=info->next;  /*删除的是第一个节点*/
                        else
                        {
                            old->next=info->next;          /*被删除节点前的指针指向下一个节点*/
                            last=old;                      /*若节点是链表尾,则该节点前的节点指针指向NULL*/
                        }
                        free(info);   /*释放删除节点占用空间*/
                    }
                }

           /*查找链表中是否有该数据*/
                struct address *search(struct address *top,char *n)
                {
                    while(top)
                    {
                        if(!strcmp(n,top->name)) return top;    /*找到要删除的节点指针*/
                        top=top->next;                          /*继续找*/
                    }
                    return NULL;       /*没有找到*/
                }

            /*链表的输出*/
                void display(struct address *top)
                {
                    while(top)
{
                        printf(top->name);
                        top=top->next;
                    }
                }

    链表问题比较复杂,但又是很重要的概念。上面说的输入,查找,删除,插入等功能一定要理解,可以参考别的一些资料看看。               
    上面说的单链表,但是单链表有一个缺点,就是无法反向操作,当某一个链因破坏而断裂,则整个链就被破坏而无法恢复。双链表可以弥补这个缺点,所谓双链表是指每个节点有两个指针项,一个指针指向其前面的节点,而另一个指针指向后面的节点。关于双链表的使用相对要复杂一些,这里就不介绍了,可以找其他一些资料看看。


评论