7.3 结构体指针的定义和引用
7.3.1 指向结构体类型变量的使用
7.3.2 指向结构体类型数组的指针的使用
7.4 链表的建立、插入和删除
7.4.1 单链表
7.4.2 单链表的插入与删除
7.3 结构体指针的定义和引用
指针变量非常灵活方便，可以指向任一类型的变量，若定义指针变量指向结构体类型变量，则可以通过指针来引用结构体类型变量。
7.3.1 指向结构体类型变量的使用
首先让我们定义结构体：
struct stu
{
char name[20];
long number;
float score[4];
} ;
再定义指向结构体类型变量的指针变量：
struct stu *p1, *p2 ;
定义指针变量p 1、p 2，分别指向结构体类型变量。引用形式为：指针变量→成员；
[例7-2] 对指向结构体类型变量的正确使用。输入一个结构体类型变量的成员，并输出。
#include /*使用malloc( ) 需要*/
struct data /*定义结构体*/
{
int day,month,year;
};
struct stu /*定义结构体*/
{
char name[20];
long num;
struct data birthday; /* 嵌套的结构体类型成员*/
} ;
main() /*定义main( ) 函数*/
{
struct stu *student; /* 定义结构体类型指针*/
student=malloc(sizeof(struct stu)); /* 为指针变量分配安全的地址* /
printf("Input name,number,year,month,day:\n");
scanf("%s",student->name); /* 输入学生姓名、学号、出生年月日*/
scanf("%ld", &student->num);
scanf("%d %d %d", &student->birthday.year,&student->birthday.month,&student->birthday.day);
printf("\nOutput name,number,year,month,day\n" );
/*打印输出各成员项的值*/
printf("%20s%10ld%10d//%d//%d\n",student->name,student->num,student->birthday.year,student->birthday.month,student->birthday.day);
}
程序中使用结构体类型指针引用结构体变量的成员，需要通过C提供的函数malloc( )来为指针分配安全的地址。函数sizeof( )返回值是计算给定数据类型所占内存的字节数。指针所指各成员形式为：
student->name
student->num
student->birthday.year
student->birthday.month
student->birthday.day
运行程序：
Input name,number,year,month,day:
Wangjian 34 1987 5 23
Wangjian 34 1987//5//23
7.3.2 指向结构体类型数组的指针的使用
定义一个结构体类型数组，其数组名是数组的首地址，这一点前面的课程介绍得很清楚。定义结构体类型的指针，既可以指向数组的元素，也可以指向数组，在使用时要加以区分。
[例7-3] 在例7 - 2中定义了结构体类型，根据此类型再定义结构体数组及指向结构体类型的指针。
struct data
{
int day,month,year;
} ;
struct stu /*定义结构体*/
{
char name[20];
long num;
struct data birthday; /* 嵌套的结构体类型成员* /
} ;
struct stu student[4],*p; /* 定义结构体数组及指向结构体类型的指针*/
作p = student，此时指针p就指向了结构体数组student。
p是指向一维结构体数组的指针，对数组元素的引用可采用三种方法。
1) 地址法
student+i和p+i均表示数组第i个元素的地址，数组元素各成员的引用形式为：
(student+i)-> name、(student+i)->num和(p+i)->name、(p+i)->num等。student+i和p+i与&student[i]意义相同。
2) 指针法
若p指向数组的某一个元素，则p++就指向其后续元素。
3) 指针的数组表示法
若p=student，我们说指针p指向数组student，p[i]表示数组的第i个元素，其效果与student[i]等同。对数组成员的引用描述为: p[i].name、p[i].num等。
[例7-4] 指向结构体数组的指针变量的使用。
struct data /*定义结构体类型*/
{
int day,month,year;
} ;
struct stu /*定义结构体类型*/
{
char name[20];
long num;
struct data birthday;
} ;
main( )
{
int i;
struct stu *p,student[4]={{"liying",1,1978,5,23},{"wangping",2,1979,3,14},
{ "libo",3,1980,5,6},{"xuyan",4,1980,4,21}};
/ *定义结构体数组并初始化* /
p=student; /*将数组的首地址赋值给指针p , p 指向了一维数组student*/
printf("\n1----Output name,number,year,month,day\n");
for(i=0;i<4;i++) /*采用指针法输出数组元素的各成员*/
printf("%20s %10ld %10d// %d// %d\n",(p+i)->name,(p+i)->num,(p+i)->birthday.year,(p+i)->birthday.month,(p+i)->birthday.day);
printf("\n2----Output name,number,year,month,day\n" );
for(i=0;i<4;i++,p++)/*采用指针法输出数组元素的各成员*/
printf("%20s %10ld %10d// %d// %d\n",p->name,p->num,p->birthday.year,p->birthday.month,p->birthday.day);
printf("\n3-----Output name,number,year,month,day\n" );
for(i=0;i<4;i++)/*采用地址法输出数组元素的各成员*/
printf("%20s %10ld %10d// %d// %d\n",(student+i)->name,(student+i)->num,(student+i)->birthday.year,(student+i)->birthday.month,(student+i)->birthday.day);
p=student;
printf("\n4-----Output name,number,year,month,day\n" );
for(i=0;i<4;i++) /* 采用指针的数组描述法输出数组元素的各成员*/
printf("%20s %10ld %10d// %d// %d\n",p[i].name,p[i].num,p[i].birthday.year,p[i].birthday.month,p[i].birthday.day);
}
运行程序：
1----Output name,number,year,month,day
liying 1 1978//5//23
wangping 2 1979//3//14
libo 3 1980//5//6
xuyan 4 1980//4//21
2----Output name,number,year,month,day
liying 1 1978//5//23
wangping 2 1979//3//14
libo 3 1980//5//6
xuyan 4 1980//4//21
3----Output name,number,year,month,day
liying 1 1978//5//23
wangping 2 1979//3//14
libo 3 1980//5//6
xuyan 4 1980//4//21
4----Output name,number,year,month,day
liying 1 1978//5//23
wangping 2 1979//3//14
libo 3 1980//5//6
xuyan 4 1980//4//21
对二维或多维数组的指针，有兴趣的同学可课后讨论，总结出来。
7.4 链表的建立、插入和删除
数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。
我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。
链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。
7.4.1 单链表
单链表有一个头节点head，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为NULL。
图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。
看一下链表节点的数据结构定义：
struct node
{
int num;
struct node *p;
} ;
在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。
• 单链表的创建过程有以下几步：
1 ) 定义链表的数据结构。
2 ) 创建一个空表。
3 ) 利用malloc( )函数向系统申请分配一个节点。
![]()
4) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新
节点接到表尾。
5) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束。
• 单链表的输出过程有以下几步
1) 找到表头。
2) 若是非空表，输出节点的值成员，是空表则退出。
3) 跟踪链表的增长，即找到下一个节点的地址。
4) 转到2 )。
[例7-5] 创建一个存放正整数（输入- 9 9 9做结束标志）的单链表，并打印输出。
#include /* 包含malloc( ) 的头文件*/
#include
struct node /*链表节点的结构* /
{
int num;
struct node *next;
} ;
main( )
{
struct node *creat(); / *函数声明* /
void print();
struct node *head; / * 定义头指针* /
head=NULL; /* 建一个空表*/
head=creat(head); /* 创建单链表*/
print(head);/*打印单链表*/
}
/******************************************************/
struct node *creat(struct node *head) /* 函数返回的是与节点相同类型的指针*/
{
struct node *p1,*p2;
p1=p2=(struct node*) malloc(sizeof(struct node)); /* 申请新节点*/
scanf("%d", &p1->num); /* 输入节点的值*/
p1-> next = NULL; /* 将新节点的指针置为空*/
while(p1->num>0) /* 输入节点的数值大于0 */
{
if (head==NULL) head=p1; /* 空表，接入表头*/
else p2->next=p1; /* 非空表，接到表尾*/
p2 = p1;
p1=(struct node *)malloc(sizeof(struct node)); /* 申请下一个新节点*/
scanf("%d", &p1->num); /*输入节点的值*/
}
return head; /*返回链表的头指针*/
}
/****************************************************/
void print(struct node *head) /* 输出以head 为头的链表各节点的值*/
{
struct node *temp;
temp=head; /*取得链表的头指针*/
while (temp!=NULL) / *只要是非空表* /
{
printf("%6d", temp->num); /*输出链表节点的值*/
temp=temp->next; /*跟踪链表增长*/
}
}
在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。
运行程序：
1 2 3 4 5 6 7 -999 ¿
1 2 3 4 5 6 7
链表的创建过程用图示如下：
![]()
7.4.2 单链表的插入与删除
在链表这种特殊的数据结构中，链表的长短需要根据具体情况来设定，当需要保存数据时向系统申请存储空间，并将数据接入链表中。对链表而言，表中的数据可以依此接到表尾或连结到表头，也可以视情况插入表中；对不再需要的数据，将其从表中删除并释放其所占空间，但不能破坏链表的结构。这就是下面将介绍的链表的插入与删除。
1. 链表的删除
在链表中删除一个节点，用图7 - 4描述如下：
![]()
[例7-6] 创建一个学生学号及姓名的单链表，即节点包括学生学号、姓名及指向下一个
节点的指针，链表按学生的学号排列。再从键盘输入某一学生姓名，将其从链表中删除。
首先定义链表的结构：
struct
{
int num;/* 学生学号*/
char str[20]; /* 姓名*/
struct node *next;
} ;
从图7 - 4中看到，从链表中删除一个节点有三种情况，即删除链表头节点、删除链表的中间节点、删除链表的尾节点。题目给出的是学生姓名，则应在链表中从头到尾依此查找各节点，并与各节点的学生姓名比较，若相同，则查找成功，否则，找不到节点。由于删除的节点可能在链表的头，会对链表的头指针造成丢失，所以定义删除节点的函数的返回值定义为返回结构体类型的指针。
struct node *delet(head,pstr)/* 以head 为头指针，删除pstr 所在节点*/
struct node *head;
char *pstr;
{
struct node *temp,*p;
temp=head; /* 链表的头指针*/
if (head==NULL) /*链表为空*/
printf("\nList is null!\n");
else /*非空表* /
{
temp=head;
while (strcmp(temp->str,pstr)!=0&&temp->next!=NULL)
/* 若节点的字符串与输入字符串不同，并且未到链表尾*/
{
p=temp;
temp=temp->next; /* 跟踪链表的增长，即指针后移*/
if(strcmp(temp->str,pstr)==0 ) /*找到字符串*/
{
if(temp==head)
{ / * 表头节点* /
printf("delete string :%s\n",temp->str);
head=head->next;
free(temp); /*释放被删节点*/
}
else
{
p->next=temp->next; /* 表中节点*/
printf("delete string :%s\n",temp->str);
free(temp);
}
}
else printf("\nno find string!\n");/* 没找到要删除的字符串*/
}
return(head); /*返回表头指针*/
}
2. 链表的插入
首先定义链表的结构：
struct
{
int num; /*学生学号*/
char str[20]; /*姓名*/
struct node *next;
} ;
在建立的单链表中，插入节点有三种情况，如图7 - 5所示。
![]()
插入的节点可以在表头、表中或表尾。假定我们按照以学号为顺序建立链表，则插入的
节点依次与表中节点相比较，找到插入位置。由于插入的节点可能在链表的头，会对链表的
头指针造成修改，所以定义插入节点的函数的返回值定义为返回结构体类型的指针。节点的
插入函数如下：
struct node *insert(head,pstr,n) /*插入学号为n、姓名为pstr的节点*/
struct node *head; /*链表的头指针*/
char *pstr;
int n;
{
struct node *p1,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));/* 分配一个新节点* /
strcpy(p1->str,pstr); /* 写入节点的姓名字串*/
p1->num=n; /* 学号*/
p2=head;
if(head==NULL) /* 空表*/
{
head=p1; p1->next=NULL;/*新节点插入表头*/
}
else
{ /*非空表* /
while(n>p2->num&&p2->next!=NULL)
/ *输入的学号小于节点的学号，并且未到表尾* /
{
p3=p2;
p2=p2->next; /* 跟踪链表增长*/
}
if(n<=p2->num) /*找到插入位置*/
if (head==p2) / * 插入位置在表头* /
{
head=p1;
p1->next=p2;
}
else
{ /*插入位置在表中*/
p3->next=p1;
p1->next=p2;
}
else
{ /*插入位置在表尾*/
p2->next=p1;
p1->next=NULL;
}
}
return(head);/* 返回链表的头指针*/
}
3. 实例[例7 - 7 ]
创建包含学号、姓名节点的单链表。其节点数任意个，表以学号为序，低学号的在前，高学号的在后，以输入姓名为空作结束。在此链表中，要求删除一个给定姓名的节点，并插入一个给定学号和姓名的节点。
#include "stdlib.h"
#include "malloc. h"
struct node /*节点的数据结构*/
{
int num;
char str[20];
struct node *next;
};
/*******************************************************/
main( )
{
/*函数声明*/
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head=NULL; /*做空表*/
head=creat (head); /*调用函数创建以head 为头的链表*/
print(head);/*调用函数输出节点*/
printf("\n input inserted num,name:\n");
gets(str); /*输入学号*/
n=atoi (str);
gets(str); /*输入姓名* /
head=insert (head, str, n); /* 将节点插入链表*/
print (head)； / *调用函数输出节点*/
printf("\n input deleted name:\n");
gets(str); /*输入被删姓名*/
head=delet(head,str); /* 调用函数删除节点*/
print (head); /*调用函数输出节点*/
return;
}
/****************创建链表******************/
struct node *creat(struct node *head)
{
char temp[30];
struct node *pl,*p2;
pl=p2=(struct node*) malloc(sizeof(struct node));
printf ("input num, name: \n") ;
printf("exit:double times Enter!\n");
g e t s ( t e m p ) ;
gets (p1->str);
pl->num=atoi (temp);
pl->next=NULL;
while (strlen (pl->str)>0
{
if(head==NULL) head=pl;
else p2->next=p1;
P2=pl;
pl=(struct node *)malloc(sizeof(struct node));
printf ("input num, name: \n");
printf("exit:double times Enter!\n");
gets(temp);
gets(pl ->str);
p1->num=atoi (temp);
P1->next=NULL;
}
return head;
}
/********** 插入节点**********/
struct node *insert (head, pstr,n);
struct node *head;
char *pstr;
int n;
{
struct node *pl,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));
strcpy (p1->str, pstr);
p1->num=n;
p2=head;
if(head==NULL)
{
head=pl;pl->next=NULL;
}
else
{
while (n>p2->num&&p2->next!=NULL)
{
p3=P2
p2=p2->next;
}
if (n<=p2->num)
if (head==p2)
{
head=pl;
pl->next=p2;
}
else
{
p3->next=pl;
pl->next=p2;
}
else
{
p2->next=pl;
pl->next=NULL;
}
}
return(head);
}
/***** 删除节点*************/
struct node *delet (head, pstr)
struct node *head;
char *pstr;
{
struct node *temp,*p;
temp=head;
if (head==NULL)
printf("\nList is null!\n");
else
{
temp=head;
while (strcmp(temp->str,pstr)!=O&&temp->next!=NULL)
{
p=temp;
temp=temp->next,
}
if(strcmp(temp->str,pstr)==0)
{
if(temp== head)
{
head=head->next;
free(temp);
}
else
{
p->next =temp->next;
printf("delete string :%s\n",temp->str);
free(temp);
}
}
else printf("\nno find string!\n");
}
return(head);
}
/**********链表各节点的输出**********/
void print (struct node *head)
{
struct node *temp;
t e m p = h e a d ;
printf("\n output strings:\n");
while (temp!=NULL)
{
printf("\n%d----%s\n",temp->num,temp->str);
temp=temp->next;
}
return;
}
运行程序：
input num,name:
exit:double times Enter!
1
Huangping
input num,name:
exit:double times Enter!
3
Lixiaobo
input num,name:
exit:double times Enter!
4
Yangjinhua
input num,name:
exit:double times Enter!
7
xuehong
input num,name:
exit:double times Enter!
output strings:
1------- Huangping
3--------Lixiaobo
4--------Yangjinhua
7--------xuehong
input inserted num,name:
5
Liling
output strings:
1------- Huangping
3--------Lixiaobo
4--------Yangjinhua
5--------Liling
7--------xuehong
input deleted name:
Lixiaobo
delete string : Lixiaobo
1------- Huangping
4--------Yangjinhua
5--------Liling
7--------xuehong
| | |
