《指针链表和共用体》由会员分享，可在线阅读，更多相关《指针链表和共用体（52页珍藏版）》请在金锄头文库上搜索。
1、第14讲 结构体与共用体（2） -指针链表和共用体,主讲教师： 张常有 Email: 电话:13811931759,C语言程序设计,主要内容,作业,C语言程序设计,1.用指针处理链表（1）,1.1 链表概述,链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。,说明,C语言程序设计,链表概述,1）链表有一个“头指针”变量，存放一个地址。该地址指向下一个元素。 2）链表中每一个元素称为“结点”，每个结点都应该包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址。 3）链表中各元素在内存中可以不连续存放。要找某一元素，必须先找到上一个元素，根据它提供的下一元素地址才能找到下一
2、元素。 4）链表的数据结构，必须利用指针变量才能实现。即：一个结点中应包含一个指针变量，用它存放下一结点的地址。,C语言程序设计,1.用指针处理链表（2）,建立一个简单链表，它由三个学生数据的结点组成。输出各结点中的数据。,#define NULL 0 struct student long num; float score; struct student * next; ; main() struct student a,b,c,*head,*p; a.num=99101; a.score=89.5; b.num=99103; b.score=90; c.num=99107; c.score
3、=85;,1.2 建立一个简单的链表（1）,例 14-1,C语言程序设计,例14-1 建立一个简单的链表（2）,head= ,C语言程序设计,1.用指针处理链表（3）, malloc函数,void *malloc(unsigned int size); 其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的值（即“返回值”）是一个指向分配域起始地址的指针。如果此函数未能成功地执行（如内存空间不足），则返回空指针。, calloc函数,void *calloc(unsigned n,unsigned size); 其作用是在内存的动态区存储中分配n个长度为size的连续空间。函数
4、返回一个指向分配域起始地址的指针；如分配不成功，返回NULL。,1.3处理动态链表所需的函数（1）,C语言程序设计,1.用指针处理链表（4）, free函数,void free(void *p); 其作用是释放由p指向的内存区，使这部分内存区能被其他变量使用。p是最近一次调用calloc或malloc函数时返回的值。free函数无返回值。,1.3处理动态链表所需的函数（2）,C语言程序设计,1.用指针处理链表（5）,1.4 建立动态链表,建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。,例 14-2,C语言程序设计,例14
5、-2写一函数建立一个有3名学生数据的单向动态链表,数据结构设计：,struct student long num; float score; struct student * next; ;,C语言程序设计,例14-2写一函数建立一个有3名学生数据的单向动态链表,算法：,C语言程序设计,例13-2写一函数建立一个有3名学生数据的单向动态链表,代码（1）：,#include #define NULL 0 #define LEN sizeof(struct student) struct student long num; float score; struct student *next; ;
6、int n; struct student *creat(void) struct student *head; struct student *p1,*p2; n=0;,C语言程序设计,例14-2写一函数建立一个有3名学生数据的单向动态链表,代码（2）：,p1=p2=(struct student*)malloc(LEN)； scanf(“%ld,%f”, ,C语言程序设计,1.用指针处理链表（6）,1.5 输出链表,首先，知道链表第一个结点的地址，也就是要知道head的值；然后，设一个指针变量p，先指向第一个结点，输出p所指向的结点；而后，使p后移 一个结点，再输出。直到链表的尾结点。,例
7、 14-3,C语言程序设计,例14-3 编写一个输出链表的函数print,void print(struct student *head) struct student *p; printf(“nNow,These %d records are:n”,n); p=head; while( p!=NULL ) printf(“%ld%5.1fn”,p-num,p-score); p=p-next; ,C语言程序设计,1.用指针处理链表（7）,1.6 对链表的删除操作,举例： 一队小孩（A、B、C、D、E）手拉手，如果某一小孩（C）想离队有事，而要求队形保持不变。只要将C的手从两边脱开，B改为与D
8、拉手即可。,A,B,C,D,E,例 14-4,C语言程序设计,例14-4 写一函数以删除动态链表中指定的结点（1）,以指定的学号作为删除结点的标志。 例如，输入99103表示要求删除学号为99103的结点。,解题思路： 从p指向的第一个结点开始，检查该结点中的num值是否等于输入的要求删除的那个学号。如果相等就将该结点删除，如不相等，就将p后移一个结点，再如此进行下去，直到遇到表尾为止。,C语言程序设计,例14-4 写一函数以删除动态链表中指定的结点（2）,解题步骤： 1）设两指针变量p1和p2，先使p1指向第一个结点。如果要删除的不是第一个结点，则使p1后指向下一个结点。如此一次一次地使p后
9、移，直到找到所要删除的结点或检查完全部链表都找不到要删除的结点为止。,思考：两种情况，如果删除的是第一个结点和不是第一个结点,C语言程序设计,例14-4 写一函数以删除动态链表中指定的结点（3）,要删除的是第一个节点。这时须将头指针指向原有链表的第二个元素。 如下图：,C语言程序设计,例14-4 写一函数以删除动态链表中指定的结点（4）,要删除的不是第一个结点 如下图：,C语言程序设计,例14-4 写一函数以删除动态链表中指定的结点（6）,代码,struct student *del(struct student *head,long num) struct student * p1,* p2
10、; if( head=NULL ) printf(“nlist null! n”); p1=head;,C语言程序设计,例14-4 写一函数以删除动态链表中指定的结点（6）,代码,while( num!=p1-num ,C语言程序设计,1.用指针处理链表（8）,1.7 对链表的插入操作,对链表的插入是指将一个结点插入到一个已有的链表中。,为了能做到正确插入，必须解决两个问题： 怎样找到插入的位置； 怎样实现插入。,例 14-5,C语言程序设计,例14-5 插入结点的函数（1）,应用题目： 如果有一群小学生，按身高顺序（由低到高）手拉手排好队。现在来了一名新同学，要求按身高顺序插入队中。,分析：
11、 首先，要确定插到什么位置。 其次，进行插入。 再次，确定插入的位置是否在第一个结点之前,或是链表之尾。,C语言程序设计,例14-5 插入结点的函数（2）,C语言程序设计,例14-5 插入结点的函数（3）,C语言程序设计,例14-5 插入结点的函数（4）,C语言程序设计,例14-5 插入结点的函数（6）,struct student *insert(struct student *head,struct student *stud) struct student *p0,*p1,*p2; p1=head; p0=stud; if( head=NULL) head=p0; p0-next=NUL
12、L; else,代码,C语言程序设计,例14-5 插入结点的函数（6）, while(p0-nump1-num) ,代码,C语言程序设计,1.用指针处理链表（9）,1.8 对链表的综合操作,将例13.213.5中的四个函数顺序排列，用main函数作主调函数。,main() struct student *head,stu; long del_num; printf(“input Record:n“); head=creat(); print(head); printf(“ninput the deleted number:“); scanf(“%ld“, ,返回主菜单,C语言程序设计,2.共用
13、体（1）,2.1 共用体的概念（1）,几种不同类型的变量存放到同一段内存单元中。变量在内存中占的字节数不同，但都从同一地址开始存放。也就是使用覆盖技术，几个变量互相覆盖。这种使几个不同的变量共占同一段内存的结构，称为“共用体”类型的结构。,整型 变量,1000地址,字符变 量ch,实 型变 量 f,C语言程序设计,2.共用体（2）,2.1 共用体的概念（2）,定义共用体类型变量的一般形式为：,结构体变量所占内存长度是各成员占的内存长度之和。每个成员分别占有其自己的内存单元。,C语言程序设计,2.共用体（3）,2.2 共用体的变量的引用方式（1）,只有定义了共用体变量才能引用它。不能引用共用体变
14、量，而只能引用共用体变量中的成员。例如：,C语言程序设计,2.共用体（4）,2.3 共用体类型的特点（1）,1）同一个内存段可以用来存放几种不同类型的成员，但在每一瞬时只能存放其中一种，而不是同时存放几种。也就是说，每一瞬时只有一个成员起作用，其他的成员不起作用，即不是同时都存在和起作用。,2）共用体变量中起作用的成员是最后一次存放的成员，在存入一个新的成员后原有的成员就失去作用。,3）共用体变量的地址和它的成员的地址是同一地址。,例如：&a,&a.i, &a.c,&a.f是同一 地址。,C语言程序设计,2.共用体（5）,2.3 共用体类型的特点（2）,4）不能对共用体变量名赋值，也不能企图引
15、用变量名来得到一个值，又不能在定义共用体变量时对它初始化。,5)不能用共用体变量作为函数参数，也不能使函数带回共用体变量，但可以使用指向共用体变量的指针。,6)共用体类型可以出现在结构体类型定义中，也可以定义共用体数组。反之，结构体也可以出现在共用体类型定义中，数组也可以作为共用体的成员。,下列是不对的： 1)union int i;char ch; float f; a=1,a,1.5; 2)a=1; 3) m=a;,C语言程序设计,例14-6 共用体举例（1）,设有若干个人员的数据，其中有学生数据和教师数据。学生的数据中包括：姓名、号码、性别、职业、班级。教师的数据包括：姓名、号码、性别、
16、职业、职务。,C语言程序设计,例14-6 共用体举例（2）,算法,是,否,job等于t?,真,假,job等于s?,真,假,C语言程序设计,例14-6 共用体举例（3）,代码,struct int num;char name10;char sex;char job; union int class;char position10;category;person2; main() int n,i; for(i=0;i2;i+) scanf(“%d%s%c%c”,返回主菜单,C语言程序设计,3.枚举类型,枚举是指将变量的值一一列举出来，变量的值只限于列举出来的值的范围内。,也可以直接定义枚举变量。 例如：enumsum,mon,tue,wed,thu,fri,satworkday,week
