动态内存分配链表.ppt

第10章 链表,开 始,批量数据的存储,批量数据的存储方式:数组存储的缺陷：必须预先指定数组的大小 链表：不需要事先指定空间大小，动态分配与释放,数组,链表,太小？,太大？,主要内容,动态内存分配单链表概述单链表结点的基本操作单链表的建立单链表的应用循环链表与约瑟夫环问题,1 动态内存分配,C程序的内存划分内存分配方式动态内存分配函数,栈区stack,静态区static,堆区heap,代码区code,数据区,代码区,memory,存放程序的代码,存放程序的全局数据和静态数据,存放程序动态申请的数据,存放程序的局部数据和参数,1-1 C程序的内存划分,1、栈区（stack）：编译器自动分配释放，存放函数参数、局部变量等。2、堆区（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由操作系统回收。3、全局区（静态区）（static）：存放全局变量和静态变量，其中初始化的全局与静态变量在一块区域，未初始化的全局与静态变量在相邻的另一块区域。程序结束后由系统释放。4、文字常量区：存放常量字符串，程序结束后由系统释放。5、程序代码区：存放函数体的二进制代码。,1-1 C程序的内存划分,1-2 内存分配方式,根据内存分配的时机，可分为：静态内存分配；动态内存分配；根据内存分配区域的不同，又可以分为：静态存储区分配；栈区分配；堆区分配；,1-2 内存分配方式,1、从静态存储区域分配。编译阶段完成分配，在程序结束后内存空间才会被释放。例如全局变量，static变量。2、在栈区创建。在执行函数时，函数局部变量可在栈区创建，函数执行结束时自动释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。,1-2 内存分配方式,3、从堆区分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意内存，程序员负责用free或delete释放内存。生存期由程序员决定，使用非常灵活。如何使用一个大数组：栈区分配?静态区分配&堆区分配?,1-2 内存分配方式,静态内存分配把内存的控制权交给了编译器，而动态内存分配则把内存的控制权交给了程序员动态内存管理水平严重依赖于程序员的水平，如果处理不当容易造成内存泄漏动态内存的分配与释放需要占用额外的CPU资源要避免频繁的使用动态内存分配,静态分配与动态分配的注意事项,1-3 C的动态内存分配函数,动态内存分配函数是C的标准函数，函数的原型声明在头文件中给出C提供下列与动态内存分配相关的函数void*malloc(unsigned int size);void*calloc(unsigned int n,unsigned int size);void*realloc(void*p_block,unsigned int size);void free(void*p_block);,1-3 C的动态内存分配函数,malloc函数：void*malloc(unsigned int size);向系统申请分配指定字节数的存储空间：分配成功：返回新分配存储空间的首地址，新分配存储空间未被初始化；分配失败：返回NULL例如：,int i,*p=(int*)malloc(6*sizeof(int);if(p)for(i=0;i 6;i+)pi=i;else printf(dynamic alloc failed!);,1-3 C的动态内存分配函数,#include#includeint main()int i,j;int*array=NULL;scanf(%d,1-3 C的动态内存分配函数,free函数：void free(void*p_block);释放指针p_block指向的动态分配的存储空间，如：free(p);一旦释放，就不能再用该指针引用存储区中的数据如果指针为NULL，free函数无释放操作注意：动态分配的存储空间一定要用free函数释放，而静态分配的存储空间当程序运行完成的时候自动释放,1-3 C的动态内存分配函数,#include#includeint main()int i,j;int*array=NULL;scanf(%d,1-3 C的动态内存分配函数,calloc函数：void*calloc(unsigned int n,unsigned int size);向系统申请分配n项大小相同的存储空间分配成功：返回新分配存储空间的首地址，新分配存储空间均被初始化为0；分配失败：返回NULL例如：int*q=(int*)calloc(6,sizeof(int);可以代替：int*q=(int*)malloc(6*sizeof(int);,1-3 C的动态内存分配函数,realloc函数：void*realloc(void*p_block,unsigned int size);对指针所指向的已动态分配的存储空间重新进行动态存储分配如果缩小空间则返回的地址是原地址;如果是扩大空间，则有三种可能：,1-3 C的动态内存分配函数,如果是扩大空间，则有三种可能：原空间位置有足够的空间可以扩充，返回的地址与扩充前的地址相同；如果原位置无足够的空间而其它位置有足够的空间，按照size指定的大小重新分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来指针所指内存区域，同时返回新分配的内存区域的首地址；否则说明内存无足够的空间可以分配，分配失败，返回值为NULL。,1-3 C的动态内存分配函数,#include#includeint main()int i;int*pn=(int*)malloc(5*sizeof(int);printf(%pn,pn);for(i=0;i5;i+)scanf(%d,1-3 动态内存分配函数,动态数组实现的一般过程：(1)定义数组元素类型(t)的指针(p)(2)指定数组要存放的元素个数(n)(3)动态申请(n*sizeof(t)大小的存储空间，并让p指向该存储空间首地址(4)通过p对数组进行赋值和操作(5)使用结束后释放数组空间,int*p;p=(int*)malloc(100*sizeof(int);for(i=0;i100;i+)scanf(“%d”,主要内容,动态内存分配单链表概述单链表结点的基本操作单链表的建立单链表的应用循环链表与约瑟夫环问题,2 链表概述,链表是一种常用的动态数据结构，链表中的每一个元素称为结点每个结点是类型相同的一个结构变量与数组不同，每个结点的存储空间不一定相邻本质上看，链表就是一个结点的序列。,2-1 结点的结构,结点由两部分组成：数据域：存放被处理的任何类型数据指针域：存放下一结点的地址（指针），指针的类型为结点的类型，即为指向自身的结构指针,2-1结点结构,假设一个链表结点的数据域只存放一个整数值，该结点结构可以如下定义：struct node int data;struct node*next;/指针域，指向下一结点,以链表中第一个数据元素的存储地址作为链表的地址，称作链表的头指针,头指针,空指针,head,p,p=head;,p=p-next;,p,p,一个指向结点的指针变量，依次指向链表的每一个结点，从而实现对每个结点的逐个访问，这样的指针变量被称为游动指针。,2-2单链表结构,头指针与游动指针的变量定义：struct node*head,*p;,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,链表为空表时，头结点的指针域为空,p,p=head-next;,p=p-next;,2-2单链表结构,例如：简单的链表结点定义：struct stud_node int num;char name10;struct stud_node*next;/*指针域，指向下一学生记录*/n1=1,Zhang,NULL,n2=2,Wang,NULL;n2.next=,/*数据域，存放一个学生记录*/,2-2单链表结构,执行n2.next=之前,n1,n2,NULL,执行n2.next=之后,n1,n2,NULL,Zhang,1,Wang,2,3单链表结点的基本操作,查找结点插入结点删除结点,3-1结点的查找,数组由于是用地址连续的空间存放元素，利用数组名+下标的方式可以实现对元素的随机查找；单链表是用地址离散的空间存放元素的，不能直接知道每一个结点的存放地址，只能从头指针所指结点开始逐个往后才能找到要访问的结点，因此也称单链表是一种“顺序存取”的结构。,3-1结点的查找,单链表的查找过程：设置头指针与游动指针；其中头指针提供了在链表中查找的起始位置；游动指针从该起始位置开始逐个往后“游走”，直到找到要找的结点或者到了链表结束停止查找。,struct node int data;struct node*next;struct node*search(struct node*head,int key)/head为单链表的头指针；struct node*p;/p为游动指针；p=head-next;/游动指针指向第一个实际结点；while(p!=NULL)/p为空表示链表已经访问结束；if(p-data=key)return(p);/找到，返回该结点的地址；else p=p-next;/未找到，指向下一个结点继续查找；return NULL;/循环正常结束，说明不存在该结点；,3-1结点的查找,3-2链表结点的插入,单链表与数组的不同之处还体现在单链表是一个动态存储的结构，可以在需要时再分配空间，用完后马上释放空间。而且，与数组做元素插入删除需要移动元素不同，单链表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。要在链表插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只有两点：一：把为要插入的元素分配空间，生成一个新结点；二：是通过指针域的修改，把新结点插入到链表中。,一、开辟新结点,5,8,6,22,head,10,p,p-next,q,struct node*q;q=(struct node*)malloc(sizeof(struct node);q-data=10;q-next=NULL;,二、修改指针域,5,8,6,22,head,10,p,p-next,q,q-next=p-next;p-next=q;,void insert(struct node*p,int key)struct node*q;q=(struct node*)malloc(sizeof(sturuct node);if(!q)printf(不能分配内存空间!);exit(0);q-data=key;q-next=NULL;q-next=p-next;p-next=q;,3-2链表结点的插入,链表中结点的插入并不需要元素的移动，只需要作指针域的修改即可。首先修改新结点的指针域，指向下一个元素；再修改前一个元素的指针域，指向新元素。这两者的顺序是否可以颠倒？为什么？,3-2链表结点的插入,3-3链表结点的删除,与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即可。作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所占的内存空间释放。要删除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的修改操作。,5,8,6,22,head,p,q,q=p-next;p-next=q-next;free(q);,3-3链表结点的删除,删除该结点是通过修改其前驱结点的指针域来实现的，因此，在删除之前首先应找到被删结点的前驱结点。,int del(struct node*head,int key)struct node*p,*q;int flag=0;p=head;while(p-next!=NULL)if(p-next-data=key)flag=1;break;else p=p-next;/如果链表存在值为key的结点，找到其前驱结点p，flag变量置1；if(flag=1)q=p-next;p-next=q-next;free(q);return 1;else return 0;,4单链表的建立,单链表的实质是一个结点的序列，建立单链表实质上就是逐个生成每一个结点，并把结点插入链表的过程。单链表的建立是一个结点插入的过程，只不过需要插入的不是一个结点，而是多个结点而已。多个结点的插入方式是相同的，因此可以借助循环过程来实现。,顺序建链表。逆序建链表。,4单链表的建立,4-1逆序建链表,(1)首先建立一个只包含头结点的空链表。需要执行的操作是：head=(struct node*)malloc(sizeof(struct node);head-next=NULL;,head,4-1逆序建链表,(2)在空链表头结点之后插入第一个结点。需要执行的操作是：p=(struct node*)malloc(sizeof(struct node);scanf(“%d”,head,p,a1,4-1逆序建链表,(3)在上面链表的头结点之后插入第二个结点。需要执行的操作是：p=(struct node*)malloc(sizeof(struct node);scanf(“%d”,head,p,a1,p,a2,4-1逆序建链表,(4)按照同样的方法依次插入第三个、第四个第n个结点。需要执行的操作是：p=(struct node*)malloc(sizeof(struct node);scanf(“%d”,head,an,an-1,a1,struct node*creat1(int n)struct node*head,*p;int i;head=(struct node*)malloc(sizeof(struct node);head-next=NULL;for(i=1;idata);p-next=head-next;head-next=p;return(head);,4-1逆序建链表,顺序建链表也是一个结点逐个插入的过程，只不过逆序建链表每次都是在头结点之后插入，而顺序建链表是在最后一个结点之后插入罢了。链表中的最后一个结点常被称为尾结点，为了更好地标记插入位置，设置一个专门的指针变量来保存尾结点地址，该指针变量被称为尾指针。,4-2顺序建链表,a2,a1,an,head,tail,4-2顺序建链表,a1,an,head,tail,当链表顺序插入结点后尾指针的值要随之修改，以指向新的尾结点。,an+1,(1)首先建立一个只包含头结点的空链表，此时头指针、尾指针均指向头结点。需要执行的操作是：head=(struct node*)malloc(sizeof(struct node);head-next=NULL;tail=head；,4-2顺序建链表,head,tail,(2)在空链表头结点之后插入第一个结点。需要执行的操作是：p=(struct node*)malloc(sizeof(struct node);scanf(“%d”,4-2顺序建链表,head,tail,p,a1,(3)按照同样的操作，可以在上面的链表的尾结点之后插入第二个结点。p=(struct node*)malloc(sizeof(struct node);scanf(“%d”,按照这样的方式还可以继续插入后面每一个结点，而且每个结点的插入要执行的操作是完全一样的。,4-2顺序建链表,head,tail,p,a1,p,a2,按照上述步骤，得到顺序建链表的函数如下：,struct node*creat2(int n)struct node*head,*tail,*p;int i;head=(struct node*)malloc(sizeof(struct node);head-next=NULL;tail=head;for(i=1;idata);p-next=NULL;tail-next=p;tail=p;return(head);,5 单链表的应用,同单链表的建立过程相似，单链表应用也要借助结点的查找、插入、删除等基本操作。逆置单链表单链表归并单链表拆分,5-1逆置单链表,a2,a1,an,an-1,an,a1,head,head,head,有什么想法？与数组逆置相似的过程来做？下一步呢？怎么办呢？,a2,a1,an,5-1逆置单链表,a3,an,an-1,p,q,交换p-data与q-data,a1,p,q,怎么实现？,容易实现：p=p-next;,逆置可以看成重新建链表。新链表的结点来源不需要申请新的空间与输入新的数据，而是利用原来链表的结点。建链表的方式应采用逆序建的方法。,5-1逆置单链表,head,a2,a1,5-1逆置单链表,a3,an,an-1,p,第一步：将原链表分成两个部分：1、只包含头结点的空链表；2、由原链表的所有非头结点构成的链表,p=head-next;head-next=NULL;q=p-next;,q,head,a2,a1,5-1逆置单链表,a3,an,an-1,p,第二步：重复如下操作：1、将p指针所指结点插入头结点之后；2、p指针与q指针指向各自的下一个结点；,p-next=head-next;head-next=p;p=q;q=q-next;,q,head,a2,a1,5-1逆置单链表,a3,an,an-1,p,第二步：重复如下操作：1、将p指针所指结点插入头结点之后；2、p指针与q指针指向各自的下一个结点；,p-next=head-next;head-next=p;p=q;q=q-next;,q,head,a2,a1,5-1逆置单链表,a3,an,an-1,p,第二步：重复如下操作：1、将p指针所指结点插入头结点之后；2、p指针与q指针指向各自的下一个结点；,p-next=head-next;head-next=p;p=q;q=q-next;,q,void reverse(struct node*head)struct node*p,*q;p=head-next;head-next=NULL;q=p-next;while(p!=NULL)p-next=head-next;head-next=p;p=q;if(q!=NULL)q=q-next;,5-1逆置单链表,5-2链表的归并,对于已经存在的多个单链表，有时需要将它们合并成一个大的单链表，这类问题称为单链表的归并。有序单链表的归并，即将多个结点有序排列的单链表合并成一个大的单链表，合并成生成的新的单链表结点仍然按照结点有序排列。,5-2链表的归并,逆置链表的思路归并的目的仍是生成一个新链表，与逆置相同的是：新链表的结点来源不是新分配的空间与新输入的数据，而是来源于旧的链表。与逆置不同之处在于逆置的结点来源是一个旧的链表，而归并的结点来源是两个旧的链表而已。按照什么顺序选取结点呢？,5-2链表的归并,需要设置的指针变量：在两个旧链表中要分别设置两个指针，用以指向旧链表的当前结点（同逆置中的p指针）。新链表的结点插入位置都是尾结点的后端，因此建链表的方法得用顺序建链表的方式。需要设置好新链表的尾指针，能够始终标记新链表的尾结点的位置。,head2,20,5,25,80,75,p2,两个待归并的有序链表：,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,head2,20,5,25,80,75,借用原来链表头结点生成一个空的新链表;两个旧链表指针指向要比较的结点的位置，用p1与p2指针指向两个链表的当前结点。,5-2链表的归并,head1,15,10,30,90,70,50,45,head2,20,5,25,80,75,p2,p1=head1-next;p2=head2-next;head1-next=NULL;tail=head1;free(head2);,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,20,5,25,80,75,p2,1、比较：两个单链表的当前结点的数据域的值；,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,20,5,25,80,75,p2,2、删除/插入：把数值较小的结点从原链表删除并插入到新链表尾结点之后；新链表的尾指针、旧链表游动指针后移。tail-next=p2;tail=p2;p2=p2-next;tail-next=NULL;,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,20,5,25,80,75,p2,2、删除/插入：把数值较小的结点从原链表删除并插入到新链表尾结点之后；新链表的尾指针、旧链表游动指针后移。tail-next=p1;tail=p1;p1=p1-next;tail-next=NULL;,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,20,5,25,80,75,p2,2、删除/插入：把数值较小的结点从原链表删除并插入到新链表尾结点之后；新链表的尾指针、旧链表游动指针后移。tail-next=p1;tail=p1;p1=p1-next;tail-next=NULL;,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,20,5,25,80,75,p2,if(p1-data data)tail-next=p1;tail=p1;p1=p1-next;tail-next=NULL;,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,elsetail-next=p2;tail=p2;p2=p2-next;tail-next=NULL;,20,5,25,80,75,p2,if（p1）tail-next=p1;elsetail-next=p2;,5-2链表的归并,head1,15,10,30,90,70,p1,50,45,tail,struct node*merge(struct node*head1,struct node*head2)struct node*p1,*p2,*tail;p1=head1-next;p2=head2-next;tail=head1;free(head2);,while(p1,if(p1)tail-next=p1;elsetail-next=p2;return(head1);,单链表的拆分,单链表的归并是将几个链表合并成一个链表，单链表的拆分与归并相反，是将一个单链表拆分成几个小的链表。这是一个建多个子链表的过程，建子链表的过程可以根据题目的要求选择顺序或逆序的方式，结点来源于原始的大链表。为此，可以为各个子链表分别建立各自只包含头结点的空链表，然后依次访问原始链表取得每一个结点，根据结点的特征确定在那哪个子链表进行插入。,单链表的拆分,例：一个带头结点的单链表存放了一批整数值，其中有负整数也有非负整数，要求将其拆分成两个子链表，一个存放原链表中所有负数，另外一个存放原链表中所有非负数。,-5,10,9,-7,12,head,-8,单链表的拆分,-5,10,9,-7,12,head1,-8,head2=(struct node*)malloc(sizeof(struct node);head2-next=NULL;p=head1-next;head1-next=NULL;q=p-next;,head2,p,q,单链表的拆分,-5,10,9,-7,12,head1,-8,if(p-data=0)p-next=head1-next;head1-next=p;elsep-next=head2-next;head2-next=p;,head2,p,q,单链表的拆分,-5,10,9,-7,12,head1,-8,if(p-data=0)p-next=head1-next;head1-next=p;elsep-next=head2-next;head2-next=p;,head2,p,q,单链表的拆分,-5,10,9,-7,12,head1,-8,if(p-data=0)p-next=head1-next;head1-next=p;elsep-next=head2-next;head2-next=p;,head2,p,q,struct node*split(struct node*head1)struct node*head2,*p,*q;head2=(struct node*)malloc(sizeof(struct node);head2-next=NULL;p=head1-next;head1-next=NULL;q=p-next;,while(p!=NULL)if(p-data=0)p-next=head1-next;head1-next=p;else p-next=head2-next;head2-next=p;p=q;if(q!=NULL)q=q-next;return(head2);,单链表的拆分,To be continued,