第10章动态数组与链表

1、第十章 动态数组与链表内存分配方式有三种：（1）从静态存储区域分配。）从静态存储区域分配。（2）在栈上创建。）在栈上创建。 （3） 从堆上分配，亦称动态内存分配。从堆上分配，亦称动态内存分配。 内存在程序编译的时候就已经分配内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间好，这块内存在程序的整个运行期间都存在。例如全局变量，都存在。例如全局变量，static变量。变量。 在执行函数时，函数内局部变在执行函数时，函数内局部变量的存储单元都可以在栈上创建，量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动函数执行结束时这些存储单元自动被释放。被释放。 效率很高，但是分配的内

2、存容效率很高，但是分配的内存容量有限。量有限。 用用malloc等函数申请任意多少的内存，等函数申请任意多少的内存，程序员自己负责在何时用程序员自己负责在何时用free函数释放函数释放内存。内存。 动态内存的生存期从动态内存的生存期从malloc等函数等函数执行开始，到执行开始，到free函数被调用结束，若函数被调用结束，若没有没有free函数，则到整个程序运行结束函数，则到整个程序运行结束为止。使用非常灵活，但问题也最多。为止。使用非常灵活，但问题也最多。引入问题引入问题1. 求某班级（求某班级（30人人）中所有学生的成绩平均分。）中所有学生的成绩平均分。 float a302. 求任意一个

3、班级（求任意一个班级（人数不定人数不定）中所有学生的成绩）中所有学生的成绩平均分。平均分。方法：求最大班级人数（假设方法：求最大班级人数（假设100），），float a100 解决办法：能不能根据我输入的班级人数，来自动的确解决办法：能不能根据我输入的班级人数，来自动的确定数组长度。定数组长度。 缺点：浪费内存空间缺点：浪费内存空间静态分配静态分配动态分配动态分配动态存储分配函数动态存储分配函数 malloc函数(memory allocation) void *malloc(int n);calloc函数(count allocation) void *calloc(int count,i

4、nt n);free函数 void free(void *ptr);realloc函数(reallocation) void *realloc(void *p,int n);使用时包含使用时包含malloc.h或或stdlib.hint *p,n;Scanf(“%d”,&n);p= malloc(n); (int*)int a10; 40int *p,count,n;Scanf(“%d%d”,&count,&n);p= calloc(count,n);(int*)10 4int *p,n;Scanf(“%d”,&n);p= malloc(n);p= reallo

5、c(p,40);(int*)10(int*)free(p)#include #include void main() float *p,s=0;int num,i; scanf(%d,&num); p=(float*)malloc(num); for (i=0;inum;i+) scanf(%f,p+i); for (i=0;inum;i+) printf(%6.2f,*(p+i); for (i=0;inum;i+) s=s+(*(p+i); printf(n%f,s/num);2. 求任意一个班级（求任意一个班级（人数不定人数不定）中所有学生的成绩平均分。中所有学生的成绩平均分。f

6、ree函数 void free(void *ptr);#include#include#includevoid main() char *str; str=(char *)malloc(10*sizeof(char); strcpy(str,china); printf(String is %sn,str); free(str); printf(String is %sn,str); #include#include#includevoid main() char *str; char* m();str=m();printf(String is %sn,str);char* m()char *

7、 str;str=(char *)malloc(10*sizeof(char); strcpy(str,china); printf(String is %sn,str); / free(str); /考察考察str所指向的空间什么时候被回收？所指向的空间什么时候被回收？ printf(String is %sn,str);return str 动态内存分配函数是在整个程序运行完毕动态内存分配函数是在整个程序运行完毕时，才回收内存；但是函数的局部变量是时，才回收内存；但是函数的局部变量是在本函数执行完毕时就回收。使用了在本函数执行完毕时就回收。使用了free函数，就可以在执行到该语句时，就能够

8、函数，就可以在执行到该语句时，就能够回收该内存空间。回收该内存空间。reallocrealloc函数函数void *realloc(void *p,int n); #include #include #include main() char *p; p=(char *)malloc(100); if(p) printf(Memory Allocated at: %x,p); else printf(Not Enough Memory!n); strcpy(p,hello world); p=(char *)realloc(p,600); if(p) printf(Memory Realloca

9、ted at: %x,p); else printf(Not Enough Memory!n); free(p); #include #include #include main() struct stu int num; char *name; char sex; float score10; struct stu *q; *p; p=(struct stu *)malloc(sizeof(struct stu); scanf(“%s”,p-name);%出现错误！出现错误！Name所指向的存储空间不可用所指向的存储空间不可用 printf(%s,(*p).name); p-name=“zh

10、angsan”;“zhangsan”在常量存储区由编译在常量存储区由编译器自动开辟空间器自动开辟空间例：跳马。依下图将每一步跳马之后的位置例：跳马。依下图将每一步跳马之后的位置(x,y)(x,y)放放到一个到一个“结点结点”里，再用里，再用“链子穿起来链子穿起来”，形成，形成一条链，相邻两结点间用一个指针将两者连到一一条链，相邻两结点间用一个指针将两者连到一起。起。动态链表动态链表 0 1 2 3 4 5 6 7 8 4 3 2 1 结点结点 1 2 3 4 5 6 7 依上图有依上图有7个结点个结点x1x1y1y1每个节点既有数据每个节点既有数据(xi(xi和和yi)yi) 又有指针（下个结

11、点的地址），又有指针（下个结点的地址），用什么样的数据类型表示每个节点用什么样的数据类型表示每个节点x2x2y2y2x7x7y7y7x6x6y6y6 struct nodeint x;int y;构造节点的数据类型构造节点的数据类型struct node *next链表的几个基本概念链表的几个基本概念x1,y1x1,y11249x2,y2x2,y21356x4,y4x4,y41021x3,y3x3,y314751356147510210NULL12491、链表中的元素称为、链表中的元素称为“结点结点”，每个结点包括，每个结点包括数据域数据域和和指针域指针域；2、单向链表通常由一个、单向链表通常

12、由一个头指针头指针（head)，用于指向链表，用于指向链表第一个第一个结点结点；3、单向链表有一个、单向链表有一个尾结点尾结点，该结点的指针部分为，该结点的指针部分为NULL 。尾结点尾结点头指针头指针第一个结点第一个结点链表的基本操作链表的基本操作（1 1）创建链表创建链表: : 从无到有地建立起一个链表，即往空链表中依次插入若干结点从无到有地建立起一个链表，即往空链表中依次插入若干结点（2 2）检索链表检索链表: : 按给定的检索条件，查找某个结点。按给定的检索条件，查找某个结点。（3 3）插入操作插入操作: : 在结点在结点ki-1ki-1与与kiki之间插入一个新的结点之间插入一个新的

13、结点kk，使链表的节点数增，使链表的节点数增1 1，（4 4）删除操作删除操作: : 删除结点删除结点kiki，使链表的节点数减，使链表的节点数减1 1， (5)(5)打印输出打印输出1) 1) 创建链表创建链表1)1)定义定义三个三个指针变量：头指针（指针变量：头指针（headhead）、指向尾结）、指向尾结点的指针（点的指针（p2p2）、指向新开辟结点的指针（）、指向新开辟结点的指针（p1p1）2)2)结束输入结点的结束输入结点的两个两个方式：方式： 1 1）创建的结点数已知）创建的结点数已知 2 2）创建的节点数事先未知，但通过）创建的节点数事先未知，但通过 输入一个不存在的数作为结束状

14、态。输入一个不存在的数作为结束状态。3)3)模块函数要返回指向结点的指针模块函数要返回指向结点的指针 struct nodestruct node* * createlist(); createlist();x1,y1x1,y11249x2,y2x2,y21356x4,y4x4,y41021x3,y3x3,y314751356147510210NULL12492)2)打印输出链表打印输出链表模块函数中的形参是指向结点的指针，无需返回值模块函数中的形参是指向结点的指针，无需返回值void void outputlist outputlist（struct nodestruct node* * )

15、; );void outputlist(struct node *p)while(p!=NULL)printf(%d,%d)n,p-x,p-y);p=p-next;3)3)检索链表检索链表模块函数中的形参是指向结点的指针。模块函数中的形参是指向结点的指针。void retrievevoid retrieve（struct nodestruct node* *,int x,int y );,int x,int y );void retrieve (struct node *p,int x,int y) while(p) if(p-x=x&p-y=y) printf(FOUND); ret

16、urn; p=p-next; printf(NO FOUND);4) 4) 对链表的插入操作对链表的插入操作插入结点：插入结点：通常是在插入一个新的结点后，仍然保持原通常是在插入一个新的结点后，仍然保持原有顺序。有顺序。实现关键：实现关键： 寻找插入位置寻找插入位置插入位置共分四种情况插入位置共分四种情况（假设原链表从小到大为例）：（假设原链表从小到大为例）：1 1、要插入的链表是个空链表、要插入的链表是个空链表2 2、要插入的结点最小、要插入的结点最小3 3、要插入的结点最大、要插入的结点最大4 4、要插入的结在中间、要插入的结在中间5 5head6 610101515nullnull121

17、2500050008 840004000 如图所示的链表；现在要插入一个结点，该结点中如图所示的链表；现在要插入一个结点，该结点中 的数为的数为1010演示演示5 5200020006 63000300010002000300040005000100080004000 待插入结点待插入结点p0p0实际上是第一个结点。这时必然有实际上是第一个结点。这时必然有head=nullhead=null。只要让头指针指向。只要让头指针指向 p0p0 就可以了。就可以了。6nullheadp0实现语句：实现语句：head = p0;p0-next = null;1 1、要插入的链表是个空链表、要插入的链表是

18、个空链表 链表已建成，待插入结点链表已建成，待插入结点 p0 p0 的数据要比头结的数据要比头结点的数据还要小，点的数据还要小，(p0-num )num)(p0-num )num)2 2、要插入的结点最小、要插入的结点最小6head8512nullheadp0语句为语句为p0-next=head;p0-next=head;head=p0;head=p0; 链表已建成，待插入结点链表已建成，待插入结点 p0 p0 的数据要比尾结的数据要比尾结点的数据还要大，点的数据还要大，3 3、要插入的结点最大、要插入的结点最大6head81812nullp0p1-next=p0;P0-next=NULL;语

19、句为语句为nullp1 链表已建成，待插入结点链表已建成，待插入结点 p0 p0 的数据大小位于的数据大小位于已有链表中的中间，已有链表中的中间， 假设假设p0 p0 的数据比的数据比p2p2指向的数据大，比指向的数据大，比p1p1指向指向的数据小，即的数据小，即p0p0插入在插入在p2p2和和p1p1之间。之间。 问题是：如何找到问题是：如何找到p1p1和和p2?p2?4 4、要插入的结在中间、要插入的结在中间6head81213p015nullp1p2p2-next = p0;p0-next = p1; 链表已建成，待插入结点链表已建成，待插入结点 p0 p0 的数据大小位于的数据大小位于

20、已有链表中的中间，已有链表中的中间， 假设假设p0 p0 的数据比的数据比p2p2指向的数据大，比指向的数据大，比p1p1指向指向的数据小，即的数据小，即p0p0插入在插入在p2p2和和p1p1之间。之间。 问题是：如何找到问题是：如何找到p1p1和和p2?p2? - -通过循环实现通过循环实现4 4、要插入的结在中间、要插入的结在中间6head81213nullp015p1p2p1=p1-next ;P2=p2-next;6head81213nullp015p1p2p1=p1-next ;P2=p2-next;6head81213p015nullp1p2p2-next = p0;p0-nex

21、t = p1; 操操 作作 分分 析析需要几个临时指针：需要几个临时指针：P0: P0: 指向待插的结点指向待插的结点; ;初始化：初始化： p0=(struct nodep0=(struct node* * )malloc(sizeof(struct node); )malloc(sizeof(struct node);P1: P1: 在在P1P1指向的结点之前插入新结点；初始化指向的结点之前插入新结点；初始化: : p1=head;p1=head;P2: P2: 在在P2P2指向的结点之后插入新结点；指向的结点之后插入新结点；在表尾插入在表尾插入在头结点在头结点之前插入之前插入在中间插入在

22、中间插入空表空表p0-numnum5) 5) 对链表的删除操作对链表的删除操作删除结点原则：删除结点原则： 只是从链表中只是从链表中分离分离开要删除的结点，撤消原来的链接开要删除的结点，撤消原来的链接关系，并释放该结点的空间。关系，并释放该结点的空间。5) 5) 对链表的删除操作对链表的删除操作 A A1249 B B1356 D D1021 C C14751356147510210 NULL1249p1p2p2-next = p1-next A A1249 B B1356 D D1021 C C14751475147510210 NULL1249p1p2free(p1)考虑两种情况：考虑两种情况：