动态内存分配链表.ppt

1、第10章 链表,开 始,批量数据的存储,批量数据的存储方式: 数组存储的缺陷： 必须预先指定数组的大小 链表： 不需要事先指定空间大小，动态分配与释放,数组,链表,太小？,太大？,主要内容,动态内存分配 单链表概述 单链表结点的基本操作 单链表的建立 单链表的应用 循环链表与约瑟夫环问题,1 动态内存分配,C程序的内存划分 内存分配方式 动态内存分配函数,栈区stack,静态区static,堆区heap,代码区code,数据区,代码区,memory,存放程序的代码,存放程序的全局数据和静态数据,存放程序动态申请的数据,存放程序的局部数据和参数,1-1 C程序的内存划分,1、栈区（stack）：

2、编译器自动分配释放，存放函数参数、局部变量等。 2、堆区（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由操作系统回收。 3、全局区（静态区）（static）：存放全局变量和静态变量，其中初始化的全局与静态变量在一块区域，未初始化的全局与静态变量在相邻的另一块区域。程序结束后由系统释放。 4、文字常量区：存放常量字符串，程序结束后由系统释放。 5、程序代码区：存放函数体的二进制代码。,1-1 C程序的内存划分,1-2 内存分配方式,根据内存分配的时机，可分为： 静态内存分配； 动态内存分配； 根据内存分配区域的不同，又可以分为： 静态存储区分配； 栈区分配； 堆区分配；,1-

3、2 内存分配方式,1、从静态存储区域分配。编译阶段完成分配，在程序结束后内存空间才会被释放。例如全局变量，static变量。 2、在栈区创建。在执行函数时，函数局部变量可在栈区创建，函数执行结束时自动释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。,1-2 内存分配方式,3、从堆区分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意内存，程序员负责用free或delete释放内存。生存期由程序员决定，使用非常灵活。 如何使用一个大数组： 栈区分配? 静态区分配 void * calloc(unsigned int n, unsigned int

4、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(d

5、ynamic alloc failed!);,1-3 C的动态内存分配函数,#include #include int 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的动态内存分配函数,#

6、include #include int 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的

7、动态内存分配函数,realloc函数： void * realloc(void * p_block, unsigned int size); 对指针所指向的已动态分配的存储空间重新进行动态存储分配 如果缩小空间则返回的地址是原地址; 如果是扩大空间，则有三种可能：,1-3 C的动态内存分配函数,如果是扩大空间，则有三种可能： 原空间位置有足够的空间可以扩充，返回的地址与扩充前的地址相同； 如果原位置无足够的空间而其它位置有足够的空间，按照size指定的大小重新分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来指针所指内存区域，同时返回新分配的内存区域的首地址； 否则说明内存无足够

8、的空间可以分配，分配失败，返回值为NULL。,1-3 C的动态内存分配函数,#include #include int 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)使用结束后释放数组空间,in

9、t *p; p=(int *) malloc(100*sizeof(int); for(i=0;i100;i+) scanf(“%d”,主要内容,动态内存分配 单链表概述 单链表结点的基本操作 单链表的建立 单链表的应用 循环链表与约瑟夫环问题,2 链表概述,链表是一种常用的动态数据结构，链表中的每一个元素称为结点 每个结点是类型相同的一个结构变量 与数组不同，每个结点的存储空间不一定相邻 本质上看，链表就是一个结点的序列。,2-1 结点的结构,结点由两部分组成： 数据域：存放被处理的任何类型数据 指针域：存放下一结点的地址（指针），指针的类型为结点的类型，即为指向自身的结构指针,2 -1结点

10、结构,假设一个链表结点的数据域只存放一个整数值，该结点结构可以如下定义： struct node int data; struct node *next; /指针域，指向下一结点 ,以链表中第一个数据元素的存储地址作为链表的地址，称作链表的头指针,头指针,空指针,head,p,p=head;,p=p-next;,p,p,一个指向结点的指针变量，依次指向链表的每一个结点，从而实现对每个结点的逐个访问，这样的指针变量被称为游动指针。,2 -2单链表结构,头指针与游动指针的变量定义： struct node *head,*p;,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结

11、点”，以指向头结点的指针为链表的头指针。,空指针,链表为空表时， 头结点的指针域为空,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,NUL

12、L,Zhang,1,Wang,2,3单链表结点的基本操作,查找结点 插入结点 删除结点,3-1结点的查找,数组由于是用地址连续的空间存放元素，利用数组名+下标的方式可以实现对元素的随机查找； 单链表是用地址离散的空间存放元素的，不能直接知道每一个结点的存放地址，只能从头指针所指结点开始逐个往后才能找到要访问的结点，因此也称单链表是一种“顺序存取”的结构。,3-1结点的查找,单链表的查找过程： 设置头指针与游动指针； 其中头指针提供了在链表中查找的起始位置； 游动指针从该起始位置开始逐个往后“游走”，直到找到要找的结点或者到了链表结束停止查找。,struct node int data; str

13、uct 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链表结点的插入,单链表与数组的不同之

14、处还体现在单链表是一个动态存储的结构，可以在需要时再分配空间，用完后马上释放空间。而且，与数组做元素插入删除需要移动元素不同，单链表无论是插入还是删除元素，都不需要做元素的移动，实现过程非常简洁。 要在链表插入一个元素时，如果已经确定了该元素的插入位置，需要做的事情只有两点： 一：把为要插入的元素分配空间，生成一个新结点；二：是通过指针域的修改，把新结点插入到链表中。,一、开辟新结点,5,8,6,22,head,10,p,p-next,q,struct node * q; q=(struct node *) malloc (sizeof(struct node); q-data=10; q-n

15、ext=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链表结点的插入,链表中结点的插入并不需要元素的移动，只需要作指针域的修改即可。

16、首先修改新结点的指针域，指向下一个元素；再修改前一个元素的指针域，指向新元素。 这两者的顺序是否可以颠倒？为什么？,3-2链表结点的插入,3-3链表结点的删除,与结点的插入相类似，结点的删除也不需要作元素的移动，而只需要作指针的修改即可。 作为动态分配的存储结构，当链表的结点不再需要时，可以在删除结点时将其所占的内存空间释放。 要删除结点，首先要找到被删结点的前一个结点，然后再对这前一个结点实施指针的修改操作。,5,8,6,22,head,p,q,q=p-next; p-next=q-next; free(q);,3-3链表结点的删除,删除该结点是通过修改其前驱结点的指针域来实现的，因此，在删

17、除之前首先应找到被删结点的前驱结点。,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单链表的建立,单链表的实质是一个结点的序列，建立单链表实质上

18、就是逐个生成每一个结点，并把结点插入链表的过程。 单链表的建立是一个结点插入的过程，只不过需要插入的不是一个结点，而是多个结点而已。 多个结点的插入方式是相同的，因此可以借助循环过程来实现。,顺序建链表。 逆序建链表。,4单链表的建立,4-1逆序建链表,(1)首先建立一个只包含头结点的空链表。 需要执行的操作是： head=(struct node *) malloc ( sizeof ( struct node ) ); head-next=NULL;,head,4-1逆序建链表,(2)在空链表头结点之后插入第一个结点。 需要执行的操作是： p=(struct node *) malloc

19、( 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,s

20、truct 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逆序建链表,顺序建链表也是一个结点逐个插入的过程，只不过逆序建链表每次都是在头结点之后插入，而顺序建链表是在最后一个结点之后插入罢了。 链表中的最后一个结点常被称为尾结点， 为了更好地标记插入位置，设置一个专门的指针变量来保存

21、尾结点地址，该指针变量被称为尾指针。,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 no

22、de *) 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) st

23、ruct 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,有什么想法？ 与数组逆置相

24、似的过程来做？ 下一步呢？ 怎么办呢？,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,he

25、ad,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,第二步

26、：重复如下操作： 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链表的归并,对于已经存在的多个单链表，有时需要

27、将它们合并成一个大的单链表，这类问题称为单链表的归并。 有序单链表的归并，即将多个结点有序排列的单链表合并成一个大的单链表，合并成生成的新的单链表结点仍然按照结点有序排列。,5-2链表的归并,逆置链表的思路 归并的目的仍是生成一个新链表，与逆置相同的是：新链表的结点来源不是新分配的空间与新输入的数据，而是来源于旧的链表。 与逆置不同之处在于逆置的结点来源是一个旧的链表，而归并的结点来源是两个旧的链表而已。 按照什么顺序选取结点呢？,5-2链表的归并,需要设置的指针变量： 在两个旧链表中要分别设置两个指针，用以指向旧链表的当前结点（同逆置中的p指针）。 新链表的结点插入位置都是尾结点的后端，因此

28、建链表的方法得用顺序建链表的方式。需要设置好新链表的尾指针，能够始终标记新链表的尾结点的位置。,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-nex

29、t=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

30、,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

31、; 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,else tail-next=p2; tail=p2; p2=p2-next; tail-next=NULL; ,20,5,25,80,75,p2,if（p1） tail-next=p1; else tail-

32、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; else tail-next=p2; return(head1); ,单链表的拆分,单链表的归并是将几个链表合并成一个链表，单链表的拆分与归并相反，是将一个单链表拆分成几个小的链表。 这是一个建多个子链表的过程，建子链表的过程可以根据题