当前位置: 首页 > >

C语言程序的设计电子课件源代码参考的答案14单元5 构造类型程序的设计链表

发布时间:

软件技术专业国家教学资源库建设项目 5.7 链表 主讲人 张静 常州信息职业技术学院 C语言程序设计 知识/能力目标 1、了解动态存储分配和链表的基本概念 2、掌握链表的建立、插入和删除算法 3、能利用链表编写应用程序 4、能够独立思考编写代码,并基本熟练 在VC6.0环境下进行程序的调试和测试 常州信息职业技术学院 C语言程序设计 一、动态存储分配及链表的概念 (一)动态存储分配 我们把由程序员控制存储分配方法,根据需要临时分配 存储单元用以存放有用的数据,当数据不用时又可以随 时释放存储单元的过程称为动态存储分配。 常州信息职业技术学院 C语言程序设计 一、动态存储分配及链表的概念 (二)链表 数组的特点 常州信息职业技术学院 1.系统为数组分配一片连续的存储 空间 ;对数组元素的访问非常方便 ,只要指定其下标就可以; 2.向数组中插入或删除一个元素时 ,该元素后的所有元素都要向后或向 前移动,增加了对内存的访问量;且 当数据无用时,不能及时释放存储空 间为其他变量所用; 3.用数组存放数据时,必须事先定 义固定的长度,在某些情况下可能 会出现比较严重的内存浪费现象。 C语言程序设计 链 能够弥补数组存在的上 表 述缺陷。 head 0012FF20H 头指针,存放开始 结点的地址 开始结点 (头结点) 0012FF20H 03101 李晗 …… 0012FF32H 指针区,指 向下一结点 typedef struct node { char num[10]; char name[20]; … struct student *next; }NODE; 结点 数据区,存放 本结点的数据 0012FF32H 03102 王丽丽 …… 0012FF5CH 0012FF5CH 03108 吴婷 …… NULL 尾结点,指 针域为空 常州信息职业技术学院 图5-16 一个简单的单向链表 二、用于动态存储分配的函数 C语言程序设计 (一)分配内存空间malloc()函数 调用形式 作用 示例 (类型说明符*) malloc (size) 在内存的动态存储区开辟一块长度为size个字节 的连续区域。若成功分配,则函数的返回值为该 区域的首地址,否则返回空指针。 long *p; p=(long *)malloc(8); 把开辟的8个字节的存储空 间转换为long型,并把该空 间的起始地址赋给指针变 量p,使p指向该空间。 常州信息职业技术学院 二、用于动态存储分配的函数 (二)realloc()函数 C语言程序设计 调用形式 作用 说明 (类型说明符*) realloc (指针变量ptr, size) 将指针变量ptr指向的存储空间(用malloc()分配 的)的大小改为size个字节。 当用函数malloc()分配的存储空间的大小需要改 变时,使用该函数。 常州信息职业技术学院 二、用于动态存储分配的函数 C语言程序设计 (三)calloc()函数 调用形式 作用 示例 (类型说明符*) calloc (n, size) 在内存的动态存储区开辟n个大小为size个字节的 连续区域。若成功分配,则函数的返回值为该区 域的首地址,否则返回空指针。 struct student *stu[30]; stu[0]=(struct student *)calloc(30,sizeof(struct student)); 把申请的30*sizeof(struct student)个字节的存储空 间转换为struct student结构体类型并赋给结构体指 针数组元素stu[0],使stu[0]指向开辟的存储空间 的首地址。 常州信息职业技术学院 二、用于动态存储分配的函数 C语言程序设计 (四)free()函数 调用形式 作用 示例 free (指针变量ptr) 释放指针变量ptr指向的存储空间。 struct student *p; p=(struct student *)malloc(sizeof(struct student)); ……… free(p); ANSI C标准要求在使用动态存储分配函数时,要在程序 的前面使用编译预处理命令#include stdlib.h,还有许 多编译系统是使用命令#include alloc.h。 常州信息职业技术学院 C语言程序设计 三、链表的建立、插入和删除 (一)链表的建立 1.头插法建不带头结点的单链表 (1)将头指针置为NULL (2) 生成一个新结点S (3)将结点的值写入数据域 heahdead s ^ s c ab a^ (4)将head的值写入结点的指针域 (5)将新结点的地址s赋给head (6)重复(2)-(5),建立多个结点 常州信息职业技术学院 说明:头插法建立的单链表 结点的次序与数据输入的次 序相反,即最先输入的是链 表的尾结点,最后输入的是 链表的开始结点。 C语言程序设计 LinkList CreatListF(void) {//返回单链表的头指针 DataType ch; LinkList head; //头指针 ListNode *s; //工作指针 head=NULL; //链表开始为空 printf(请输入链表各结点的数据(字符型):\n); while((ch=getchar())!='\n') 算 { 法 实 现 if((s=(ListNode *)malloc(sizeof(ListNode ))==NULL) { printf(不能分配内存空间!); exit(0); } s->data=ch; s->next=head; head=s; } return head; } 常州信息职业技术学院 C语言程序设计 2.尾插法建带头结点的单链表 (1



友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网