第十三讲 指向结构体的指针与链表(C语言).doc

第十三讲 指向结构体的指针与链表 本讲首先介绍了C语言中指向结构体变量和结构体数组的指针变量的使用，接着介绍了结构体数据作为函数参数的使用，最后介绍了链表的概念和基本操作。要求大家掌握指向结构体变量的指针变量和指向结构体数组及数组元素的指针变量的定义和引用，理解指向结构体变量的指针变量、结构体变量及其成员作为函数参数的使用方法，掌握链表中结点的描述方式，了解链表的建立、输出、插入和删除操作。 知识要点 指向结构体变量的指针变量1. 指向结构体变量的指针变量的定义2. 利用指向结构体变量的指针变量对结构体变量成员的引用 指向结构体数组的指针变量1. 指向结构体数组的指针变量的使用 结构体数据作函数参数1. 结构体变量的成员作函数参数2. 结构体变量作函数参数3. 指向结构体的指针作函数参数 链表的概念1. 链表的组成2. 结点用结构体类型描述3. 动态申请和释放内存单元的函数 链表的操作1. 建立链表2. 在链表中插入结点3. 删除链表中的结点 13.1 指向结构体变量的指针变量 指向结构体变量的指针变量的定义形式与一般指针变量的定义形式相同，只是将其指向类型定义为结构体类型即可。例如： struct person char name20; char sex; int age; float height; ; struct person *p;则指针变量p，它可以指向struct person类型的结构体变量。 将一个指针变量指向一个结构体变量后，可以利用指向该结构体的的指针变量引用成员，如： （* 指针变量名）成员名以上形式也常写成： 指针变量名成员名其中，为指向运算符，它是由符号“”和“”两部分构成的。指向运算符的优先级和成员运算符相同，也是最高一级。13.2 指向结构体数组的指针变量 指针变量可以指向整型、字符型、浮点型等基本类型数组。同样，指针变量也可以指向结构体类型的数组。 程序L13_2.C功能：使用指向结构体数组的指针变量。 #include void main() struct person char name20;char sex;int age;float height;per3= Li Ping, M ,20,175,Wang Ling, F ,19,162.5,Zhao Hui, M ,20,178;struct person *p;for (p=per;pname, psex, page, pheight); 13.3 结构体数据作函数参数 不仅结构体变量的成员可以作函数参数，结构体变量以及指向结构体变量的指针都可以作函数参数。 一、结构体变量的成员作函数参数 结构体变量的成员作实参与简单变量、数组元素等作实参是一样的。 二、结构体变量作函数参数 C允许将整个结构体变量作为函数参数传递。传递的是结构体变量全部成员的值，将实参中成员的值赋给对应的形参成员。 用结构体变量作实参时，由于要为形参结构体变量分配存储空间，还要一一对应传递各成员的值，这样会增加处理的时间同时也浪费了内存空间，从而影响程序的运行效率。 三、指向结构体的指针作函数参数 使用指向结构体的指针作函数实参，形参也必须是一个指向相同结构体类型的指针变量，其它使用方法不变。13.4 链表的概念 链表是动态数据结构中最基本的形式，它的规模大小可以根据需要进行动态变化，达到合理地使用存储空间。 链表有一个“头指针”变量，用来指向链表的第一个元素。链表中的每个元素都称为“结点”，结点包含两部分内容：一是实际的数据信息；二是下一结点的指针，。链表的最后一个元素置为“NULL”（空地址），标志链表结束。 一个结点可以用一个结构体类型来描述。结构体中包含若干成员，用来表示结点的数据信息。此外必须有一个成员是与结点类型一致的指针，用来指向后续结点。例如，一个链表的结点可以定义为以下的结构体类型： struct node int data1; float data2; struct node *next; ;其中，成员next是指向结点的指针变量，它指向next所在的struct node结构体类型数据。C系统的库函数中提供了动态申请和释放内存存储单元的函数。 （1）malloc函数 malloc函数的原型为： void *malloc(unsigned int size) 函数的功能是：在动态存储区域中分配一个size字节的连续空间。函数的返回值为指针，它的值是所分配的存储区域的起始地址。如没有足够的存储空间分配，则返回0（记为NULL）值。 （2）calloc函数 calloc函数的原型为： void *calloc(unsigned int n, unsigned int size) 函数的功能是：在动态存储区域中分配n个为size字节的连续空间，并将该存储空间自动置初值0。函数的返回值为指针，它的值是所分配的存储区域的起始地址。如分配不成功，则返回0值。 （3）free函数 free函数的原型为： void free(void *ptr) 函数的功能是：释放由ptr所指向的存储空间。ptr的值必须是malloc或calloc函数返回的地址。此函数无返回值。13.5 链表的操作 一、建立链表 建立链表就是从无到有逐渐增加链表结点的过程，即输入结点数据，并建立前后链接的关系。 下面是建立链表的函数creat() ： struct node *create( ) struct node *head, *tail, *p;int x;head=tail=NULL;printf(n请输入一个整数：);scanf(%d,&x);while(x!=0) p=(struct node *)malloc(sizeof(struct node);pdata=x;pnext=NULL;if (head= = NULL)head=tail=p;else tailnext=p;tail=p;printf(请输入一个整数：);scanf(%d,&x);return (head);二、在链表中插入结点 插入结点的操作有以下几种情况： （1）链表是空链表，插入的结点作为链表的第一个结点。（2）链表非空，结点插入到链表的第一个结点前，使插入的结点成为链表第一个结点。（3）链表非空，结点插入到链表的末尾，使插入的结点成为链表最后一个结点。（4）链表非空，结点插入到链表中间某个结点之后。 下面函数insert (struct node *head, int value)的作用是在已知头结点head链表中按照从小到大的顺序插入数据value。 struct node *insert(struct node *head, int value )struct node *new, *p, *q;new=(struct node *)malloc(sizeof(struct node);newdata=value;p=head;if(head= =NULL) /*链表是空链表*/ head=new;newnext=NULL;else while(pnext !=NULL) &(pdatanext; if(pdata=value) if(head= =p) /*链表非空，插入到第一个结点前*/ newnext=head;head=new;else /*链表非空，插入到链表中间*/ qnext=new;newnext=p;else /*链表非空，插入到链表末尾*/ pnext=new;newnext=NULL;return(head); 三、删除链表中的结点 从链表中删除结点，是指把该结点从链表中分离出来，即改变链表的链接关系。从链表中删除的结点有两种处理情况：一是调用函数free（）来释放该结点所占的存储空间，将它从内存中删除；二是将该结点插入到其它链表中等待处理。 下面函数delete(struct node *head, int value)的作用是在已知头结点head链表中查找一个数据value，并从链表中删除。 struct node *delete(struct node *head, int value ) struct node *p, *q;p=head;if(head= =NULL) /*链表是空链表*/ printf(这是一个空链表!n); return(head); while(pnext !=NULL) &(pdata!=value) /*寻找删除结点位置*/ q=p; p=pnext; if(value= = pdata) if(head= =p) head=pnext; /*删除链表第一个结点*/else qnext=pnext; /*删除链表结点*/free(p);elseprintf(此链表没有数据%d!n,value); /*链表中无此结点*/return(head); 学以致用 1. 在例13.5的基础上，增加一个求链表中所有结点数据之和的函数add()，在主函数中输出结果。 2. 修改例13.5，使得建立的链表是一个由浮点数据组成的无序链表，然后将链表中所有结点数据按照从小到大的顺序生成一个新的链表，最后输出显示。 3. 已知一个链表中存储了若干名学生的信息，每名学生的信息包括：学号、英语成绩、数学成绩、计算机成绩。现编写一个函数search()，要求根据输入的学生学号，输出他的各科成绩。 4. 使用链表存储同学的通讯录，内容包含姓名、地址、邮政编码和电话，然后利用函数delete()，根据输入的同学姓名，删除该同学