第10章动态数组与链表

第十章

动态数组与链表内存分配方式有三种：（1）从静态存储区域分配。（2）在栈上创建。

（3）从堆上分配，亦称动态内存分配。

内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。

在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。效率很高，但是分配的内存容量有限。

用malloc等函数申请任意多少的内存，程序员自己负责在何时用free函数释放内存。动态内存的生存期从malloc等函数执行开始，到free函数被调用结束，若没有free函数，则到整个程序运行结束为止。使用非常灵活，但问题也最多。引入问题1.求某班级（30人）中所有学生的成绩平均分。floata[30]2.求任意一个班级（人数不定）中所有学生的成绩平均分。方法：求最大班级人数（假设100），floata[100]解决办法：能不能根据我输入的班级人数，来自动的确定数组长度。缺点：浪费内存空间静态分配动态分配动态存储分配函数malloc函数(memoryallocation)

void*malloc(intn);calloc函数(countallocation)void*calloc(intcount,intn);free函数

voidfree(void*ptr);realloc函数(reallocation)

void*realloc(void*p,intn);使用时包含malloc.h或stdlib.hint*p,n;Scanf(“%d”,&n);p=malloc(n);

(int*)inta[10];

40int*p,count,n;Scanf(“%d%d”,&count,&n);p=calloc(count,n);(int*)104int*p,n;Scanf(“%d”,&n);p=malloc(n);p=realloc(p,40);(int*)10(int*)free(p)#include<stdio.h>#include<malloc.h>voidmain(){float*p,s=0;intnum,i;scanf("%d",&num);p=(float*)malloc(num);for(i=0;i<num;i++)scanf("%f",p+i);

for(i=0;i<num;i++)printf("%6.2f",*(p+i));

for(i=0;i<num;i++)s=s+(*(p+i));printf("\n%f",s/num);}2.求任意一个班级（人数不定）中所有学生的成绩平均分。free函数voidfree(void*ptr);#include<stdlib.h>#include<string.h>#include<stdio.h>voidmain(){char*str;str=(char*)malloc(10*sizeof(char));strcpy(str,"china");printf("Stringis%s\n",str);free(str);printf("Stringis%s\n",str);}#include<stdlib.h>#include<string.h>#include<stdio.h>voidmain(){

char*str;char*m(); str=m();printf("Stringis%s\n",str);}char*m(){char*str;str=(char*)malloc(10*sizeof(char));strcpy(str,"china");printf("Stringis%s\n",str);//free(str);//考察str所指向的空间什么时候被回收？printf("Stringis%s\n",str);returnstr}动态内存分配函数是在整个程序运行完毕时，才回收内存；但是函数的局部变量是在本函数执行完毕时就回收。使用了free函数，就可以在执行到该语句时，就能够回收该内存空间。realloc函数void*realloc(void*p,intn);#include<stdio.h>#include<string.h>#include<malloc.h>main(){char*p;p=(char*)malloc(100);if(p)printf("MemoryAllocatedat:%x",p);elseprintf("NotEnoughMemory!\n");strcpy(p,"helloworld");p=(char*)realloc(p,600);if(p)printf("MemoryReallocatedat:%x",p);elseprintf("NotEnoughMemory!\n");free(p);}#include<stdio.h>#include<string.h>#include<malloc.h>main(){ structstu {intnum; char*name; charsex; floatscore[10]; structstu*q; }*p; p=(structstu*)malloc(sizeof(structstu)); scanf(“%s”,p->name);%出现错误！！！Name所指向的存储空间不可用printf("%s",(*p).name);} p->name=“zhangsan”;“zhangsan”在常量存储区由编译器自动开辟空间例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。动态链表依上图有7个结点x1y1每个节点既有数据(xi和yi)又有指针（下个结点的地址），用什么样的数据类型表示每个节点x2y2x7y7x6y6structnode{intx;inty;};构造节点的数据类型structnode*next链表的几个基本概念x1,y11249x2,y21356x4,y41021x3,y314751356147510210NULL12491、链表中的元素称为“结点”，每个结点包括数据域和指针域；2、单向链表通常由一个头指针（head)，用于指向链表第一个结点；3、单向链表有一个尾结点，该结点的指针部分为NULL。尾结点头指针第一个结点

链表的基本操作（1）创建链表:

从无到有地建立起一个链表，即往空链表中依次插入若干结点（2）检索链表:

按给定的检索条件，查找某个结点。（3）插入操作:

在结点ki-1与ki之间插入一个新的结点k’，使链表的节点数增1，（4）删除操作:删除结点ki，使链表的节点数减1，(5)打印输出1)创建链表1)定义三个指针变量：头指针（head）、指向尾结点的指针（p2）、指向新开辟结点的指针（p1）2)结束输入结点的两个方式：1）创建的结点数已知2）创建的节点数事先未知，但通过输入一个不存在的数作为结束状态。3)模块函数要返回指向结点的指针

structnode*createlist();x1,y11249x2,y21356x4,y41021x3,y314751356147510210NULL12492)打印输出链表模块函数中的形参是指向结点的指针，无需返回值voidoutputlist（structnode*);voidoutputlist(structnode*p){while(p!=NULL){printf("(%d,%d)\n",p->x,p->y);p=p->next;}}3)检索链表模块函数中的形参是指向结点的指针。voidretrieve（structnode*,intx,inty);voidretrieve(structnode*p,intx,inty){while(p){if(p->x==x&&p->y==y){printf("FOUND");return;}p=p->next;}printf("NOFOUND");}4)对链表的插入操作插入结点：通常是在插入一个新的结点后，仍然保持原有顺序。实现关键：寻找插入位置插入位置共分四种情况（假设原链表从小到大为例）：1、要插入的链表是个空链表2、要插入的结点最小3、要插入的结点最大4、要插入的结在中间5head61015null12500084000如图所示的链表；现在要插入一个结点，该结点中的数为10演示520006300010002000300040005000100080004000待插入结点p0实际上是第一个结点。这时必然有head==null。只要让头指针指向p0就可以了。6nullheadp0实现语句：head=p0;p0->next=null;1、要插入的链表是个空链表链表已建成，待插入结点p0的数据要比头结点的数据还要小， (p0->num)<(head->num)2、要插入的结点最小6head8512nullheadp0语句为p0->next=head;head=p0;链表已建成，待插入结点p0的数据要比尾结点的数据还要大，3、要插入的结点最大6head81812nullp0p1->next=p0;P0->next=NULL;语句为nullp1链表已建成，待插入结点p0的数据大小位于已有链表中的中间，假设p0的数据比p2指向的数据大，比p1指向的数据小，即p0插入在p2和p1之间。

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

问题是：如何找到p1和p2?---通过循环实现4、要插入的结在中间6head81213nullp015p1p2p1=p1->next;P2=p2->next;6head81213nullp015p1p2p1=p1->next;P2=p2->next;6head81213p015nullp1p2p2->next=p0;p0->next=p1;操作分析需要几个临时指针：P0:指向待插的结点;初始化：p0=(structnode*)malloc(sizeof(structnode));P1:在P1指向的结点之前插入新结点；初始化:p1=head;P2:在P2指向的结点之后插入新结点；在表尾插入在头结点之前插入在中间插入空表p0->num<=p1->num5)对链表的删除操作删除结点原则：只是从链表中分离开要删除的结点，撤消原来的链接关系，并释放该结点的空间。5)对链表的删除操作A1249B1356D1021C14751356147510210NULL1249p1p2p2->next=p1->nextA1249B1356D1021C14751475147510210NULL1249p1p2free(p1)考虑两种情况：1、要删的结点是头指针所指的结点（第一个结点）；2、删除的不是第一个结点