11.5 链表（课件）-《 C语言程序设计》同步教学（电子工业出版社）

第11章结构体、共同体和枚举类型 内容概述 结构体类型定义　 结构体变量定义引用 结构体数组与指针 结构体与函数 结构体数组应用 结构体与链表应用 教学目标 认识引入结构体类型的必要性,描述结构体类型变量的定义方法,正确地引用结构体变量,正确的对结构体变量初始化。 牢记结构体数组的定义，并能正确地使用。 牢记指向结构体类型数据的定义,并能正确地使用。 使用结构体指针处理链表的各种操作。 使用typedef定义新类型名来代替已有类型名。 11.5 链表 静态数据结构：前面讨论的各种基本类型和组合类型的数据都属静态数据结构，它们所占存储空间的大小在程序的说明部分就已经确定，如变量、数组、结构等，它们不能在程序运行过程中加以改变。 动态数据结构：它是在程序运行过程中动态的建立起来的，这种数据结构的规模大小在程序执行期间可动态的变化。 动态数据结构中最基本的形式是链表和二叉树，它们在应用软件和系统软件的设计中非常有用。 head: 称为表头，仅存放一个地址，无数据。 head 数据D Null 数据C 数据B 数据A 数据 指针 : 为数据块，又称为链表的结点(node)，由两部分 组成，数据和指针。 数据：该结点的具体数据 指针：下一个结点的地址 11.5.1 链表概述 链表结点的数据结构可描述为 struct 结构名 { 数据成员列表; struct 结构名 *指针名; }; 例如: struct node { int num; struct node *next; }; num next 11.5.2 链表的基本操作 1．创建链表 创建链表是指从无到有地建立起一个链表 。 NULL … （a）表头插入法 head p NULL head p … （b）表尾插入法 last 【例11.5】写一函数建立一个有若干名学生数据的单向链表，当输入的成绩为1时结束输入。 结点的数据结构可定义为： struct node { int num; int score; struct node *next; }; 用宏定义结点的长度： #define LEN sizeof(struct node) 单链表的创建过程（表头插入法）： （1）创建一个空表。 head=NULL; （2）利用malloc()函数向系统申请分配一个结点。 p=(struct node*)malloc(sizeof(struct node)); （3）表头插入操作。 p->next=head; head=p; （4）若有后续结点要接入链表，转（2），否则结束。 struct node *create( ) /*创建一个链表并返回一个指向链表头结点的指针*/ { struct node *head,*p; head=NULL; p=(struct node*)malloc(LEN); /*创建第一个结点*/ scanf("%d%d",&p->num,&p->score); while(p->score!=-1) /*若输入成绩不为-1，插入*/ { p->next=head; head=p; p=(struct node*)malloc(LEN); /*开辟下一个结点*/ scanf("%d%d",&p->num,&p->score); }; free(p); /*释放成绩为-1的结点所占的内存*/ return(head); /*链表创建完毕，返回头指针*/ } 2．插入结点 可以在表头、表中或表尾插入结点。下面给出了在键表中插入结点的示意图。 … … head p0 p NULL p1 【例11.6】以例11.5建立的链表为例。假设链表中的结点已按学号从小到大排序，编写函数，在单链表中插入结点p，使链表仍然有序。 在链表中插入结点时应考虑插入位置在头结点之前还是在表的中间，另外还要考虑空表的情况。具体算法描述如下： （1）若链表空，则插入结点即为头结点。 head=p; p->next=NULL; （2）若插入位置在头结点之前，则执行下列语句。 p->next=head; head=p; （3）否则，从链表头开始逐一查找要插入位置的前一个结点，并保存为p0，然后将结点p插入到p0之后。 p->next=p1; p0->next=p; struct node *insert(struct node *head,struct node *p) /*向以head为头结点的有序链表中插入结点p，插入后链表仍有序*/ { struct node *p0,*p1; if(head==NULL) /* 若链表空，则插入结点即为头结点 */ { head=p; p->next=NULL; return(head); } if(p->num<head->num) /* 欲插入的结点p的学号最小，将p插入到头结点之前 */ { p->next=head; head=p; return(head); } p1=head; while((p->num>p1->num)&&(p1->next!=NULL)) /*查找合适的位置*/ { p0=p1; p1=p1->next; } if(p->num<p1->num) /* 在链表的中间找到合适位置，插入结点 */ { p->next=p1; p0->next=p; } else /*欲插入的结点p的学号最大，将p插入到尾结之后*/ { p1->next=p; p->next=NULL; } return(head); } 实际上，可以通过调用insert()函数实现一个有序链表的创建。 struct node *create( ) /*创建一个链表并返回一个指向链表头结点的指针*/ { struct node *head,*p; head=NULL; p=(struct node*)malloc(LEN); /*创建第一个结点*/ scanf("%d%d",&p->num,&p->score); while(p->score!=-1) /*若输入成绩不为1，则进入循环执行插入操作*/ { head=insert(head,p); p=(struct node*)malloc(LEN); /*开辟下一个结点*/ scanf("%d%d",&p->num,&p->score); }; free(p); /*释放学号为0的结点所占的内存*/ return(head); /*链表创建完毕，返回头指针*/ } 3．删除结点 从一个链表中删去一个结点，只要改变链接关系即可，即修改结点指针成员的值。 … head p NULL （a）删除表头结点 … head p NULL pre （b）删除表中间结点 【例11.7】以例11.5建立的学生链表为例，编写函数删除单链表中的学号为num的结点p。 删除结点时应判断结点在链表中的位置，具体算法描述如下： （1）若p为头结点，第二个结点成为新的头结点并转（4），否则执行（2）。 head=head->next; （2）寻找要删除结点p，注意保存要删结点的前一个结点pre。 pre=head; while((pre->next!=p)&&(pre->next!=NULL)) pre=pre->next; （3）找到要删除结点则修改链接关系。 条件（2）中，若while循环中条件pre->next==NULL成立说明链表中不存在结点p；若条件pre->next==p成立，则找到结点p，执行语句“pre->next=pre->next->next;”，将它删除。 （4）释放删除结点的内存，函数结束。 free(p); struct node *delete(struct node *head,int num) /* 删除单链表中的学号为num的结点p，函数返回删除结点p后的单链表头结点*/ { struct node *pre,*p; if(head==NULL) /*链表为空*/ { printf(" list is empty! "); return NULL; } if(head->num==num) /*要删除结点为头结点*/ { p=head; head=head->next; } else { pre=head; p=pre->next; /*从头结点开始查找*/ while(p!=NULL && p->num!=num) { pre=p; p=p->next; } if(p->num==num) /* 找到了需删除的结点 */ pre->next=p->next; /* 后继结点的地址赋予前一结点 */ } free(p); /* 释放结点所占的内存 */ return(head); } 4．输出链表的值 【例11.8】以例11.5建立的学生链表为例，编写输出链表的函数。 void print(struct node *head) /* 遍历链表，从表头开始，依次输出每个结点的值 */ { struct node *p; printf("These records are: "); p=head; if(head!=NULL) do { printf("%d%5d ",p->num,p->score); /*输出结点的值*/ p=p->next; /* 指针p后移，指向下一个结点 */ }while(p!=NULL); } 11.5.3 链表综合应用举例 【例11.9】用链表管理学生成绩信息。main函数依次调用creat函数，创建按学号排序的有序单链表；调用insert函数将一个学生的信息（学号、成绩）插入到链表中，使链表仍然有序；调用delete函数将指定学号的结点从链表中删除；要求每次调用完上述函数之后，都要调用print函数输出链表当前结点的内容。 程序阅读:设head是node类型的全程量，以head为头指针的链表各节点的值如下图所示。 head→ 3 ()→4 ()→5 ()→6 ()→7 NULL 调用fun（head）返回值是 。 #include<stdio.h> #define LEN sizeof(struct node) struct node { int num； struct node *next； }; 练 习 int fun（struct node*h） { int k=0；struct node*p=h； while（p！=NULL） { if（p->next！=NULL）k+=p->num； p=p->next； } return k； } void main() { struct node*head ,*p1,*p2; int i; head=(struct node *) malloc(LEN);p1=head; for(i=3;i<=7;i++) { p2=(struct node*)malloc(LEN);p1->next=p2; p2->num=i;p2->next=NULL; p1=p2;printf(“%d ”,fun(head->next)); } } 0 3 7 12 18 练 习 程序填空:已建立学生"英语"课程的成绩链表（成绩存于score域中，学号存于num 域中），下列函数用于查询某个学生的成绩并输出。 void require (head,no) struct student *head; int no; { struct student * p; if( ) {p = head; while(p->next!=NULL && no!=(*p).num) __________; if( )printf ("%6.1f ",p->num); else printf ("%ld not been found! ",no);} } head!=NULL p=p->next no==p.num 练 习 程序填空:下列函数用于在节点类型为ltab的非空链表中插入一个节点（由形参指针变量p0指向），链表按照节点数据成员no的升序排列，填空将程序补充完整。 ltab *insert(ltab *head, ltab *stud) { ltab *p0, *p1, *p2； p1=head; p0=stud; while((p0->no>p1->no)&&(（1）)) { p2=p1; p1=p1->next; } if(p0->no<=p1->no) if(head==p1) { p0->next=head; head=p0;} else { p2->next=p0; （2）} else { p1->next=p0; （3）} return (head); } (1)  p1 -> next != NULL (2)  p0 -> next = p1; (3)  p0 -> next = NULL; 练 习 程序阅读 # include<stdio.h> void main() { struct info {int data; struct info *pn;}; struct info base, p; base=NULL; for(int i=0; i<10; i++) { p=(struct info*)malloc(sizeof(struct info)); p->data=i+1; p->pn=base; base=p; } p=base; while(p!=NULL) { printf("%2d", p->data); p=p->pn; } printf(" "); } 10 9 8 7 6 5 4 3 2 1 练 习 1 -5 7 练 习 程序阅读 #include<stdlib.h> void main( ) { struct node {int x; struct node *next;} *p1,*p2=NULL; int a[5]={7,6,-5,28,1},i,j,s; for(i=0;i<5;i++) { s=0; for(j=1;j<=a[i]/2;j++) if(a[i]%j==0)s+=j; if(a[i]!=s) { p1=(struct node*)malloc(sizeof(struct node)); p1->x=a[i];p1->next=p2;p2=p1; } } while(p1!=NULL) {printf(“%d ”,p1->x);p1=p1->next ;} } 11.6 共用体 11.6.1 共用体的概念 所谓共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。其定义方式与结构体类型完全相同。把结构体类型中的关键字struct换成union即可。 例如: union data { char ch; int i; float f; }un1,un2; 与结构体类似之处：由不同的数据项组成一个整体。 与结构体不同之处：占用的内存单元不同。 结构体 struct data { char ch; int i; float f; }; ch i f 1 4 4 9 共用体 struct data { char ch; int i; float f; }; ch i f 4字节 字节 一个共用体中可能有若干个不同类型的成员，但在任何时刻，只有一个成员的值被存储。这就是最后赋给它的值。 #include<stdio.h> union data { char ch; int i; float f; }; void main( ) { union data un; un.ch='d'; un.i=40; un.f=12.6; printf("%5c%5d%5.1f ",un.ch,un.i,un.f); } 运行结果： ? 1095342490 12.6 输出结果中，除了un.f的值外，un.ch和un.i的值是我们无法预料的 共用体类型可以出现在结构体类型定义中，反之亦然。例如： union ub { char s[40]; int x; }; struct st { int a; char c; union ub x1; }; union un { int i; struct st s1; }; 11.6.2 共用体类型的应用 【例11.10】设有一个教师与学生通用的表格，见表11.4。学生的数据中包括编号、姓名、年龄、职业及班级/职务，教师的数据包括编号、姓名、年龄、职业及职务。编程输入人员数据，再输出它。 编 号 姓 名 年 龄 职 业 班级/职务 2 zhang 20 s 1102 6 wang 43 t prof #include "stdio.h" main() { int i; struct { int num; char name[10]; int age; char job; union { int class; char position[10]; }category; }person[2]; printf("input num,name,age job and class/position "); for(i=0;i<2;i++) { scanf("%d %s %d %c", &person[i].num,person[i].name,&person[i].age,&person[i].job); if(person[i].job=='s') scanf("%d",&person[i]. category.class); else scanf("%s",person[i].category.position); } printf("num name age job class/position "); for(i=0;i<2;i++) { printf("%3d%8s%4d%4c", person[i].num,person[i].name,person[i].age,person[i].job); if(person[i].job=='s') printf("%10d ",person[i].category.class); else printf("%10s ",person[i].category.position); } } 11.7 枚举 一种自定义的用标识符表示的集合，这个集合自动具有序号。 定义形式： enum 枚举标识符 { 枚举元素表 }; 例如： enum weekday {sun,mon,tue,wed,thu,fri,sat}; 有了枚举类型，即可声明枚举类型的变量。例如： enum weekday today,nextday; 也可以在定义类型的同时定义变量： enum weekday {sun,mon,tue,wed,thu,fri,sat}today,nextday; enum {sun,mon,tue,wed,thu,fri,sat} today,nextday; 针对枚举类型有几点说明： （1）enum是关键字，标识枚举类型，定义枚举类型必须以enum开头。 （2）枚举元素是程序设计者自己指定的，命名规则与标识符相同。这些名字并无固定的含义，只是一个符号，程序设计者仅仅是为了提高程序的可读性才使用这些名字。 （3）枚举元素不是变量，不能改变其值。例如下面这些赋值是不对的： sun=5;mon=2;sun=mon; × 枚举元素本身由系统定义了一个表示序号的数值，从0 开始顺序定义为0，1，2，…。所以枚举元素可以进行比较。例如，mon>sun结果为真，语句“printf("%d",sun);”输出的值是0。 （4）枚举元素的值也可以在定义时由程序指定，即为一个或多个枚举元素指定希望的值。此时，每使用一个初始值后，其后面没指定初始值的元素依次比它前面的元素大1。 例如， enum weekdays {sun=7,mon＝1,tue,wed,thu,fri,sat}; 此时，sun的值为7，mon的值为1，tue的值为2，……，sat的值为6。 （5）一个枚举变量的值只能是这几个枚举常量之一，可以将枚举常量赋给一个枚举变量。但不能将一个整数赋给它。例如， today=mon; nextday=tue; /*right*/ today=1; nextday=2; /*error*/ 11.7.2 枚举类型的应用 【例11.11】枚举类型应用举例。 #include <stdio.h> enum color {yellow,blue,green,black,white,red}; main() { enum color select; for(select=yellow;select<=red;select++) switch(select) { case yellow: printf("你选择了黄色. ");break; case blue: printf("你选择了蓝色. ");break; case green: printf("你选择了绿色. ");break; case black: printf("你选择了黑色. ");break; case white: printf("你选择了白色. ");break; case red: printf("你选择了红色. ");break; } } 11.8 类型定义 C语言为了适应用户的习惯和便于程序移植，允许用户通过类型定义typedef将已有的各种类型名定义成新的类型标识符。 typedef定义的一般形式为： typedef 原类型名 新类型名 例如： （1） typedef int INTEGER; /* 简单的名字替换 */ （2） typedef struct student { long num; char name[20]; float score; }STUDENT; /* 定义一个类型名STUDENT代表一个结构体类型 */ （3） typedef char* STRING; /* 定义指针类型 */ 为类型起了别名之后，可用别名来定义相应的变量。例如： INTEGER x,y; STUDENT stul,stu2; STRING p1,p2; 它们等价于： int x,y; struct student studentl,student2; char *p1,*p2; $$