本次课内容:动态存储分配、链表 教学目的:掌握相关概念、函数和链表的基本操作。 重点:动态存储分配方法,链表的基本操作(建、插、 删) 难点:链表的基本操作(建、插、删)。 预习: 结构体类型定义,变量定义和成员引用; 指向结构体类型变量的指针; 结构体类型的嵌套定义
本次课内容：动态存储分配、链表 教学目的：掌握相关概念、函数和链表的基本操作。 重点：动态存储分配方法，链表的基本操作（建、插、 删）。 难点：链表的基本操作（建、插、删）。 预习： 结构体类型定义，变量定义和成员引用； 指向结构体类型变量的指针； 结构体类型的嵌套定义
简单单向链表举例 结点构成 结点 mum学号 数据域 score 成绩 next下一学生数据地址 指针域 head 3010 3010 89101 结点 89.5 3028 头指针 3028 89102 结点结构定义: 90.5 struct stud score 4016 4016 89105 long num; float score, 4048 4048 struct stud score *next 89018 94.5 NULL
简单单向链表举例： num score *next 学号 成绩 下一学生数据地址 3010 head 3010 3028 4016 4048 89101 89102 89105 89018 89.5 90.5 91 94.5 3028 4016 4048 NULL 结点 头指针 数据域 指针域 结点 结点构成 结点结构定义： struct stud_score { long num; float score; struct stud_score *next; };
、动态存储分配和链表概念 1、动态存储分配 根据需要临时分配存储单元用于存放数据,当数据 不用时,又可随时释放存储单元。 2、链表 若干数据按一定的原则连接起来 原则:前一个结点指向下一个结点,通过前一个结 点找到下一个结点。 结点构成:数据域和指针域。 结点:一组数据或一个记录。 头指针:用head(一般情况下)表示的首结点地 址 NULL(尾结点指针域值):符号常量,值为0 般表示不指向任何一个数据。 基本操作 (1)建立链表 (2)插入结点 (3)删除结点
一、动态存储分配和链表概念 1、动态存储分配 根据需要临时分配存储单元用于存放数据，当数据 不用时，又可随时释放存储单元。 2、链表 若干数据按一定的原则连接起来。 原则：前一个结点指向下一个结点，通过前一个结 点找到下一个结点。 结点构成：数据域和指针域。 结点：一组数据或一个记录。 头指针：用head（一般情况下）表示的首结点地 址。 NULL（尾结点指针域值）：符号常量，值为0 一般表示不指向任何一个数据。 基本操作: (1)建立链表 (2)插入结点 (3)删除结点
插入结点: 3028 4016 89102 89105 90.5 340+原4016 4048 1340 89103 92.5 4016 删除结点: 3028 4016 89102 89105 90.5 4016 1340 4048 原1340 89103 92.5 点虽仍指向下一结点, 4016 此结点已无法访问
插入结点： 删除结点： 1340 89103 92.5 4016 3028 89102 90.5 1340 4016 89105 91 4048 3028 89102 90.5 4016 1340 89103 92.5 4016 4016 89105 91 4048 原4016 原1340 结点虽仍指向下一结点， 但此结点已无法访问。 89103 92.5 4016
结点构成: 数据域:若干不同类型变量 指针域:一个或多个指针类型变量 结点定义方法:定义包含指针项的结构体变量,结构 体成员中至少有一个指向该结构体类型的指针成员。 如: struct stud score long num; float score: struct stud score *next. }; 其中:*next是指向该类型的指针成员。用于存放该结 构体类型数据的首地址。 struct stud score *next;是嵌套定义
结点构成： 数据域：若干不同类型变量 指针域：一个或多个指针类型变量 结点定义方法：定义包含指针项的结构体变量，结构 体成员中至少有一个指向该结构体类型的指针成员。 如： struct stud_score { long num; float score; struct stud_score *next; }; 其中：*next是指向该类型的指针成员。用于存放该结 构体类型数据的首地址。 struct stud_score *next; 是嵌套定义
例:简单的单向链表 struct stud score long num; float score 定义结点结构 struct stud score *next struct stud score stud1 stud2 stud3. head stud1 num=8910l: stud 1 score=89.5 stud2 num=89102: stud2 score=90.5 各结点赋有用值 stud3 num=89103: stud3 score=94.5 head=&stud 1 stud1next=&stud2 形成“链” stud2. next=&stud3 stud3, nextNULLs head &stud &stud2 &stud 3 &stud 89101 89102 89103 89.5 90.5 94.5 &stud2 1 &stud3 [NULL人
例：简单的单向链表 struct stud_score { long num; float score; struct stud_score *next; }; struct stud_score stud1,stud2,stud3,*head; stud1.num=89101;stud1.score=89.5; stud2.num=89102;stud2.score=90.5; stud3.num=89103;stud3.score=94.5; head=&stud1; stud1.next=&stud2; stud2.next=&stud3; stud3.next=NULL; 定义结点结构 各结点赋有用值 形成“链” &stud1 head 89101 89102 89103 89.5 90.5 94.5 &stud1 &stud2 &stud2 &stud3 &stud3 NULL
动态存储分配函数 分配一个动态存储空间 Void *malloc(unsigned int size) 功能:函数分配了一个指定大小的存储空间,返回值为 起始地址,指针是不指向任何具体的类型 如: long p; p=(long*)malloc(4); EX:p=(long*)malloc(sizeof(long) 注(1)函数值为指针(地址); (2)若指向某一类型时,需强制类型转换; (3)内容若无足够的空间,返回值为0 2、分配多个动态存储空间 Void *calloc(unsigned int num, unsigned int size) 空间个数 空间大小 如:calc(1,20) 分配了10个,每个大小为20个字节的空间。 引用地址时,类型要强制转换
三、动态存储分配函数 1、分配一个动态存储空间 Void *malloc(unsigned int size) 功能：函数分配了一个指定大小的存储空间，返回值为 起始地址，指针是不指向任何具体的类型。 如：long p; p=(long*)malloc( 4 ); 或：p=(long*)malloc(sizeof(long)) 注 (1)函数值为指针（地址）； (2)若指向某一类型时，需强制类型转换； (3)内容若无足够的空间，返回值为0。 2、分配多个动态存储空间 Void *calloc(unsigned int num,unsigned int size) 空间个数 空间大小 如：calloc(10,20); 分配了10个，每个大小为20个字节的空间。 引用地址时，类型要强制转换
如: struct stud i char name 10; int age, char sex struct stud * next; new, new=(struct stud *)calloc(1, 15); 3、释放存储空间 void free(void * ptr 功能:将指针变量ptr指向的存储空间释放。 注:ptr值不能是任意的地址,而只能是由在程序中执行 过的malc或caoc函数所返回的地址。 如:p=(ong*malc(4); free(p); E: p=(long*)calloc(1, 4) free(p); 注:函数无返回值,函数会自动将指针变量类型转换为 void类型
如：struct stud { char name[10]; int age; char sex; struct stud *next; }new; new=(struct stud*)calloc(1,15); 3、释放存储空间 void free(void *ptr) 功能：将指针变量ptr指向的存储空间释放。 注：ptr值不能是任意的地址，而只能是由在程序中执行 过的malloc或calloc函数所返回的地址。 如：p=(long*)malloc(4); : free(p); 或：p=(long*)calloc(1,4); free(p); 注：函数无返回值，函数会自动将指针变量类型转换为 void类型
四、举例P260例713 switch( ch # include“ stdio.h” case e include“ stdlib. h” struct stud case 'E: new record o; case i char name 201; case 'L: listall(; break; long num; default: flag=0 Int age; 3/end switch*/ char sex; 3 end while*/ float score, struct stud * next: struct stud *head. *this, new: main (0 i char ch; int flag=1 head=NULL: while(flag) f ch=getchar(; getchar(;
四、举例P260_例7.13 #include “stdio.h” #include “stdlib.h” struct stud { char name[20]; long num; int age; char sex; float score; struct stud *next; }; struct stud *head,*this,*new; main() { char ch; int flag=1; head=NULL; while (flag) { ch=getchar( );getchar( ); switch( ch ) { case ‘e’: case ‘E’:new_record( ); case ‘l’: case ‘L’:listall( );break; default:flag=0; } /*end switch*/ } /*end while*/ }
Void new record(void) i char numstr(20]: new=(struct stud *)malloc(sizeof(struct stud)); if (head-==NULL) head=new. ese i this=head; while(this->next !=NULL) this=this->next: this->next= new: gets(this->name); gets(numstr); this->num=atol(numstr); gets(numstr); this->age=atoi(numstr); this->sex=getchar(; getchar( gets(numstr); this->score=atof(numstr); this->next=NULL:
Void new_record(void) { char numstr[20]; new=(struct stud *)malloc(sizeof(struct stud)); if (head==NULL) head=new; else { this=head; while(this->next !=NULL) this=this->next; this->next = new; } gets(this->name); gets(numstr);this->num=atol(numstr); gets(numstr);this->age=atoi(numstr); this->sex=getchar( );getchar( ); gets(numstr);this->score=atof(numstr); this->next=NULL; }