第12章 结构设计之美.ppt
《第12章 结构设计之美.ppt》由会员分享,可在线阅读,更多相关《第12章 结构设计之美.ppt(70页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第11章章 算法和数据结构基础算法和数据结构基础结构设计之美结构设计之美哈尔滨工业大学哈尔滨工业大学12.1 从定长数组到动态数组从定长数组到动态数组n本节主要讨论如下问题:本节主要讨论如下问题:(1)什么是动态内存分配?如何进行动态内存分配?)什么是动态内存分配?如何进行动态内存分配?(2)常见的内存错误有哪些?如何避免这些内存错误?)常见的内存错误有哪些?如何避免这些内存错误?12.1.1 动态内存分配动态内存分配nC程序中变量的内存分配方式有以下程序中变量的内存分配方式有以下3种:种:(1)从静态存储区分配)从静态存储区分配(2)在栈上分配)在栈上分配(3)从堆上分配)从堆上分配1.函
2、数函数malloc()函数函数malloc()的原型为:的原型为:void *malloc(unsigned int size);2.函数函数calloc()函数函数calloc()的函数原型为:的函数原型为:void *calloc(unsigned int num,unsigned int size);3.函数函数free()函数函数free()的函数原型为:的函数原型为:void free(void*p);4.函数函数realloc()函数函数realloc()的函数原型为:的函数原型为:void *realloc(void*p,unsigned int size);12.1.1 动态内
3、存分配动态内存分配void*型指针型指针不指定其指向变量的类型,可指向任意类型的变量不指定其指向变量的类型,可指向任意类型的变量是一种是一种generic(通用)或(通用)或typeless(无类型)的指针(无类型)的指针 使用时,需强转使用时,需强转(Type*)为其他类型为其他类型12.1.1 动态内存分配动态内存分配void*malloc(unsigned int size);向系统申请向系统申请size字节的连续内存块,系统找到一块未占用的内存,将其标记为已占用,把首地址返回字节的连续内存块,系统找到一块未占用的内存,将其标记为已占用,把首地址返回p=(float*)malloc(n*
4、sizeof(float);free(p);/释放释放p指向的内存指向的内存l频繁申请频繁申请/释放,速度慢,易造成内存碎片释放,速度慢,易造成内存碎片l程序员不释放程序员不释放内存泄漏内存泄漏l释放仍继续使用释放仍继续使用野指针野指针n空指针空指针的用途的用途 l定义指针时进行初始化定义指针时进行初始化l在程序中常用作状态比较在程序中常用作状态比较n指针不能与非指针类型变量进行比较指针不能与非指针类型变量进行比较l但可与但可与NULL(即(即0值)进行相等或不等的关系运算值)进行相等或不等的关系运算 p=(int*)malloc(n*sizeof(int);if(p=NULL)/判断内存申请
5、是否成功判断内存申请是否成功 printf(No enough memory!n);exit(0);int*p;Heap(堆区)(堆区)若申请不成功则返回若申请不成功则返回NULLNULL12.1.1 动态内存分配动态内存分配【例例12.1】请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从学生名单中随机抽取学生名单中随机抽取1个学生,直到按个学生,直到按ESC键或者学生名单中的学生全部抽完为止,键或者学生名单中的学生全部抽完为止,要求每个学生最多只能被抽中一次,即不能被重复点到名字。要求每个学生最多只能被抽中一次,即不
6、能被重复点到名字。#include#include#include#include#define NO 120#define SIZE 30typedef struct char nameSIZE;short flag;/标记是否被点过名标记是否被点过名ROLL;int ReadFromFile(char fileName,ROLL msg);void MakeRollCall(ROLL msg,int total);int main(void)ROLL msgNO;/定长数组定长数组 char*fileName=student.txt;int total=ReadFromFile(fileN
7、ame,msg);printf(总计总计%d名学生名学生n现在开始随机点名现在开始随机点名n,total);MakeRollCall(msg,total);/随机点名随机点名 return 0;12.1.2 动态数组实例动态数组实例随机点名随机点名使用定长的结构体数组来实现点名神器【例例12.1】请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从学生名单中随机抽取学生名单中随机抽取1个学生,直到按个学生,直到按ESC键或者学生名单中的学生全部抽完为止,键或者学生名单中的学生全部抽完为止,要求每个学生最多只能被抽中一次,即
8、不能被重复点到名字。要求每个学生最多只能被抽中一次,即不能被重复点到名字。12.1.2 动态数组实例动态数组实例随机点名随机点名/函数功能:从文件函数功能:从文件filename中读取名单存入数组中读取名单存入数组msgint ReadFromFile(char fileName,ROLL msg)FILE*fp=fopen(fileName,r);if(fp=NULL)printf(can not open file%sn,fileName);return 1;int i=0;while(fgets(msgi.name,sizeof(msgi.name),fp)i+;fclose(fp);r
9、eturn i;【例例12.1】请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从学生名单中随机抽取学生名单中随机抽取1个学生,直到按个学生,直到按ESC键或者学生名单中的学生全部抽完为止,键或者学生名单中的学生全部抽完为止,要求每个学生最多只能被抽中一次,即不能被重复点到名字。要求每个学生最多只能被抽中一次,即不能被重复点到名字。12.1.2 动态数组实例动态数组实例随机点名随机点名/函数功能:随机点名,总计名单中有函数功能:随机点名,总计名单中有total个学生个学生void MakeRollCall(ROLL ms
10、g,int total)srand(time(NULL);for(int i=0;itotal;i+)msgi.flag=0;/标记都没有被点过标记都没有被点过 char ch=;int i=0;do int k=rand()%total;/随机确定被点名学生的下标随机确定被点名学生的下标 if(kbhit()&msgk.flag=0)/当有按键,并且第当有按键,并且第k个人也没有被点过个人也没有被点过 ch=getch();/等待用户按任意键,以回车符结束输入等待用户按任意键,以回车符结束输入 if(ch!=27)i+;printf(请第请第%d位同学回答问题:位同学回答问题:%sn,i,m
11、sgk.name);msgk.flag=1;/标记其已经被点过标记其已经被点过 while(ch!=27&i total);if(ch=27)printf(点名结束点名结束n);else printf(所有同学均已点名完毕所有同学均已点名完毕n);【例例12.1】请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从学生名单中随机抽取学生名单中随机抽取1个学生,直到按个学生,直到按ESC键或者学生名单中的学生全部抽完为止,键或者学生名单中的学生全部抽完为止,要求每个学生最多只能被抽中一次,即不能被重复点到名字。要求每个学生最
12、多只能被抽中一次,即不能被重复点到名字。int main(void)int n;printf(How many students?);scanf(%d,&n);/输入学生人数输入学生人数 ROLL*msg=(ROLL*)malloc(n*sizeof(ROLL);/向系统申请内存向系统申请内存 if(msg=NULL)/确保指针使用前是非空指针,为空指针时结束程序运行确保指针使用前是非空指针,为空指针时结束程序运行 printf(No enough memory!n);exit(1);char*fileName=student.txt;int total=ReadFromFile(fileNa
13、me,msg,n);printf(总计总计%d名学生名学生n现在开始随机点名现在开始随机点名n,total);MakeRollCall(msg,total);/随机点名随机点名 free(msg);/释放向系统申请的内存释放向系统申请的内存 return 0;12.1.2 动态数组实例动态数组实例随机点名随机点名使用一维动态数组来实现点名神器【例例12.1】请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从学生名单中随机抽取学生名单中随机抽取1个学生,直到按个学生,直到按ESC键或者学生名单中的学生全部抽完为止,键或者学
14、生名单中的学生全部抽完为止,要求每个学生最多只能被抽中一次,即不能被重复点到名字。要求每个学生最多只能被抽中一次,即不能被重复点到名字。/函数功能:从文件函数功能:从文件filename中读取名单存入数组中读取名单存入数组msg,返回名单中的实际人数,返回名单中的实际人数int ReadFromFile(char fileName,ROLL*msg,int n)FILE*fp=fopen(fileName,r);if(fp=NULL)printf(can not open file%sn,fileName);return 1;int i;for(i=0;in;i+)/读取你条记录,若已经读到文
15、件尾,则结束循环读取你条记录,若已经读到文件尾,则结束循环 if(!fgets(msgi.name,sizeof(msgi.name),fp)break;fclose(fp);return i;/返回名单中的实际人数返回名单中的实际人数12.1.2 动态数组实例动态数组实例随机点名随机点名【例例12.1】请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从请编写一个点名神器,从文件中读取学生名单,每按一次回车键,就从学生名单中随机抽取学生名单中随机抽取1个学生,直到按个学生,直到按ESC键或者学生名单中的学生全部抽完为止,键或者学生名单中的学生全部抽完为止,要求每个学生最多只能被抽中
16、一次,即不能被重复点到名字。要求每个学生最多只能被抽中一次,即不能被重复点到名字。/函数功能:随机点名,总计名单中有函数功能:随机点名,总计名单中有total个学生个学生void MakeRollCall(ROLL*msg,int total)srand(time(NULL);for(int i=0;itotal;i+)msgi.flag=0;/标记都没有被点过标记都没有被点过 char ch=;int i=0;do int k=rand()%total;/随机确定被点名学生的下标随机确定被点名学生的下标 if(kbhit()&msgk.flag=0)/当有按键,并且第当有按键,并且第k个人也
17、没有被点过个人也没有被点过 ch=getch();/等待用户按任意键,以回车符结束输入等待用户按任意键,以回车符结束输入 if(ch!=27)i+;printf(请第请第%d位同学回答问题:位同学回答问题:%sn,i,msgk.name);msgk.flag=1;/标记其已经被点过标记其已经被点过 while(ch!=27&i next!=NULL)/若未到表尾若未到表尾p=p-next;/pr指向下指向下一一节点节点 p-next=newP;/末节点指针指向新建节点末节点指针指向新建节点 newP=(struct link*)malloc(sizeof(struct link);newP-d
18、ata=nodeData;newP-next=NULL;12.2.2 单向链表的基本操作单向链表的基本操作n删除节点删除节点n分两种情况:空表、非空表(待删节点为头节点、非头节点)分两种情况:空表、非空表(待删节点为头节点、非头节点)datanextheaddatanext pr/找待删除节点while(p-data!=nodeData&p-next!=NULL)/未找到且未到表尾未找到且未到表尾pr=p;/在在pr中保存当前节点的指针中保存当前节点的指针 p=p-next;/p指向当前节点的下一节点指向当前节点的下一节点 p p待删除节点待删除节点待删除节点待删除节点12.2.2 单向链表的
19、基本操作单向链表的基本操作n分两种情况:空表、非空表(待删节点为头节点、非头节点)分两种情况:空表、非空表(待删节点为头节点、非头节点)若原链表为空表,则退出程序若原链表为空表,则退出程序 若待删节点若待删节点p是头节点,则将是头节点,则将head指向当前节点的后继节点即可指向当前节点的后继节点即可datanexthead待删除节点待删除节点待删除节点待删除节点datanext p头节点头节点头节点头节点if(p-data=nodeData)/找到待删节点找到待删节点if(p=head)/若待删节点若待删节点p为头节点为头节点 head=p-next;/head指向待删除节点指向待删除节点p的
20、后继节点的后继节点 else /若待删节点不是头节点若待删节点不是头节点 pr-next=p-next;/前驱节点指向待删节点的后继前驱节点指向待删节点的后继 free(p);/释放为已删除节点分配的内存释放为已删除节点分配的内存12.2.2 单向链表的基本操作单向链表的基本操作若待删节点不是头节点,则若待删节点不是头节点,则前驱前驱节点指向节点指向后继后继节点节点datanextdatanext待删除节点待删除节点待删除节点待删除节点datanext p中间节点中间节点中间节点中间节点datanext若已搜到表尾若已搜到表尾(p-next=NULL)仍未找到待删仍未找到待删除节点,则显示除节
21、点,则显示“未找到未找到”prif(p-data=nodeData)/找到待删节点找到待删节点if(p=head)/若待删节点若待删节点p为头节点为头节点 head=p-next;/head指向待删除节点指向待删除节点p的后继节点的后继节点 else /若待删节点不是头节点若待删节点不是头节点 pr-next=p-next;/前驱节点指向待删节点的后继前驱节点指向待删节点的后继 free(p);/释放为已删除节点分配的内存释放为已删除节点分配的内存else /找到表尾仍未找到找到表尾仍未找到 printf(Not found!n);12.2.2 单向链表的基本操作单向链表的基本操作n在升序的链
22、表中插入节点在升序的链表中插入节点n分两种情况:空表、非空有序表分两种情况:空表、非空有序表非空表分三种情况:在头节点前、中间节点、表尾节点后插入新节点非空表分三种情况:在头节点前、中间节点、表尾节点后插入新节点n若原链表为空表,则将新节点若原链表为空表,则将新节点p作为头节点,让作为头节点,让head指向新节点指向新节点p head待插入节点待插入节点待插入节点待插入节点data p if(head=NULL)/若原链表为空表若原链表为空表 head=p;/待插入节点作为头节点待插入节点作为头节点else/若原链表为非空若原链表为非空 /找待插入位置找待插入位置 while(nodeData
23、 pr-data&pr-next!=NULL)temp=pr;/在在temp中保存当前节点的指针中保存当前节点的指针pr=pr-next;/pr指向当前节点的后继节点指向当前节点的后继节点 p=(struct link*)malloc(sizeof(struct link);p-data=nodeData;p-next=NULL;head12.2.2 单向链表的基本操作单向链表的基本操作待插入节点待插入节点待插入节点待插入节点nodeData next pdatanextdata prprtemp待插入位置待插入位置待插入位置待插入位置p=(struct link*)malloc(sizeof
24、(struct link);p-data=nodeData;p-next=NULL;pr=head;if(head=NULL)/若原链表为空表若原链表为空表 head=p;/待插入节点作为头节点待插入节点作为头节点else/若原链表为非空若原链表为非空 /找待插入位置 while(nodeData pr-data&pr-next!=NULL)temp=pr;/在在temp中保存当前节点的指针中保存当前节点的指针pr=pr-next;/pr指向当前节点的后继节点指向当前节点的后继节点 n若原链表非空,则若原链表非空,则按节点值大小(假按节点值大小(假设升序)确定插入设升序)确定插入新节点的位置新
25、节点的位置12.2.2 单向链表的基本操作单向链表的基本操作head待插入节点待插入节点待插入节点待插入节点datanext pdatanextdatanextdata if(nodeData data)/不在表尾插入不在表尾插入if(pr=head)/若在头节点前插入新节点若在头节点前插入新节点 p-next=head;/将新节点指向链头将新节点指向链头 head=p;/head指向新节点指向新节点else /若在链表中间插入新节点若在链表中间插入新节点 pr=temp;p-next=pr-next;/新节点指向后继节点新节点指向后继节点 pr-next=p;/前驱节点指向新节点前驱节点指向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第12章 结构设计之美 12 结构设计
限制150内