动态内存分配链表.ppt

第10章 链表;批量数据的存储;主要内容;1 动态内存分配; ;1、栈区（stack）：编译器自动分配释放，存放函数参数、局部变量等。 2、堆区（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由操作系统回收。 3、全局区（静态区）（static）：存放全局变量和静态变量，其中初始化的全局与静态变量在一块区域，未初始化的全局与静态变量在相邻的另一块区域。程序结束后由系统释放。 4、文字常量区：存放常量字符串，程序结束后由系统释放。 5、程序代码区：存放函数体的二进制代码。;1-2 内存分配方式;1-2 内存分配方式;1-2 内存分配方式;1-2 内存分配方式;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 C的动态内存分配函数;1-3 动态内存分配函数;主要内容;2 链表概述;2-1 结点的结构;2 -1结点结构; 以链表中第一个数据元素的存储地址作为链表的地址，称作链表的头指针;头结点;2 -2单链表结构;2-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-2链表结点的插入;一、开辟新结点;二、修改指针域;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-3链表结点的删除;5;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-1逆序建链表;4-1逆序建链表;4-1逆序建链表;4-1逆序建链表;struct node * creat1(int n) { struct node * head,* p; int i; head=(struct node *)malloc(sizeof(struct node)); head-next=NULL; for(i=1;i=n;i++) { p=(struct node *)malloc(sizeof(struct node)); scanf(%d,p-data); p-next=head-next; head-next=p; } return(head); };顺序建链表也是一个结点逐个插入的过程，只不过逆序建链表每次都是在头结点之后插入，而顺