1
第九讲 结构
2
例：跳马。依下图将每一步跳马之后的位置 (x,y)放到
一个, 结点, 里，再用, 链子穿起来,,形成一条
链，相邻两结点间用一个指针将两者连到一起。
结构的概念与应用
0 1 2 3 4 5 6 7 8
4
3
2
1
结点 1
2
3
4
5
6
7
3
依上图有 7个结点
(x1,y1) (x2,y2) (x6,y6) (x7,y7)
为了表示这种既有数据又有指针的情况，引入结构
这种数据类型。
4
结构 ——是一种构造类型的数据类型。结构是数
目固定、类型不同的若干变量的有序集合。结
构与数组的区别在于结构内允许有不同类型的
数据。
结构的定义,格式如下,
struct <结构名 >
{
<成员说明 >
}
5
例如跳马棋局可如下定义
struct TM
{
int x,y; // 结构 TM的成员,x,y为整数型
struct TM *next // 结构 TM的成员，属 TM型
}
下面的表是马的跳步方案，从左下角跳到右上角
结点 n1 n2 n3 n4 n5 n6 n7
x
y
0
0
1
2
2
4
4
3
6
4
7
2
8
4
6
8
4
NULL
NULL为空地址
下面是形成链表的一个参考程序 （分三页）
2
4
&n4
1
2
&n3
0
0
&n2
&n1
head
7
// 结构 1.c
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
struct TM // 定义结构 TM
{
int x,y; // 整型变量 x,y
struct TM *next; // 指向 TM结构的指针
};
void main() // 主函数
{ // 主函数开始
int i; // 声明整型变量
// 声明 TM结构 n1~n7,结构指针 head,p
struct TM n1,n2,n3,n4,n5,n6,n7,*head,*p;
8
// 分别对 TM结构 n1~n7中的 x,y赋值
n1.x=0;n1.y=0;
n2.x=1;n2.y=2;
n3.x=2;n3.y=4;
n4.x=4;n4.y=4;
n5.x=6;n5.y=4;
n6.x=7;n6.y=2;
n7.x=8;n7.y=4;
// head赋值为 n1，即 head指向 n1
head=&n1;
// n1~n7构成链表
n1.next=&n2;
n2.next=&n3;
n3.next=&n4;
n4.next=&n5;
n5.next=&n6;
n6.next=&n7;
// n7的 next指针赋值为空指针
n7.next=null;
9
p=head; // p赋值为 head，即 p指向 head所指的内容
i=1; // i赋值为 1
do // 直到型循环
{ // 循环体开始
// 输出结点信息
printf("结点 %d,x=%d,y=%d\n",i,p->x,p->y);
p=p->next; // p指向下一个结点
i=i+1; // 计数加 1
} while(p!=null); // 未到达链表尾部，则继续循环
} // 主函数结束
10
用结构数组，利用键盘输入结点中的数据。
重点看
scanf(“%d”,&a);
n[i].x=a;
结构数组，数组中的元素为结构类型的数据，如 n[8]
// 结构 2.c
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
struct TM // 定义 TM结构
{
int x,y; // 整型变量 x,y
struct TM *next; // 指向 TM结构的指针
};
11
void main() // 主函数
{ // 主函数开始
int i,a,b; // 声明整型变量 i,a,b
// 声明 TM型结构数组 n[8],TM结构指针 head,p
struct TM n[8],*head,*p;
for(i=1;i<=7;i=i+1) // 循环
{ // 循环体开始
printf("输入 n[%d]的 x\n",i); // 提示输入第 i个结构的 x值
scanf("%d",&a); // 输入 a
n[i].x=a; // 将 a的值赋给结构 n[i]的元素 x
printf("输入 n[%d]的 y\n",i); // 提示输入第 i个结构的 y值
scanf("%d",&b); // 输入 b
n[i].y=b; // 将 b的值赋给结构 n[i]的元素 y
} // 循环体结束
12
head=&n[1]; // 链表头部指向 n[1]
for(i=1;i<=6;i=i+1) // 将结构数组 n形成链表
{
n[i].next=&n[i+1]; // n[i]的 next指针指向下一个结构 n[i+1]
}
n[7].next=null; // 链表尾部指向空
p=head; // p指向链表头部 head
i=1; // i赋值为 1
do // 直到型循环, 用于输出链表内容
{ // 循环体开始
// 输出结点内容
printf("结点 %d,x=%d,y=%d\n",i,p->x,p->y);
p=p->next; // p指向相邻的下一个结点
i=i+1; // 计数 i加 1
} while(p!=null); // 未到链表尾部，则继续循环
} // 主函数结束
13
下面的程序与上面的程序区别仅在
scanf(“%d”,&(n[i].x));
去替换
scanf(“%d”,&a);
n[i].x=a;
// 结构 3.c
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
struct TM // 定义 TM结构
{
int x,y; // 整型变量 x,y
struct TM *next; // 指向 TM结构的指针
};
14
void main() // 主函数
{ // 主函数开始
int i,a,b; // 声明整型变量 i,a,b
// 声明 TM型结构数组 n[8],TM结构指针 head,p
struct TM n[8],*head,*p;
for(i=1;i<=7;i=i+1) // 循环
{ // 循环体开始
printf("输入 n[%d]的 x\n",i); // 提示输入第 i个结构的 x值
scanf("%d",&(n[i].x)); // 输入 n[i].x
printf("输入 n[%d]的 y\n",i); // 提示输入第 i个结构的 y值
scanf("%d",&(n[i].y)); // 输入 n[i].y
} // 循环体结束
15
head=&n[1]; // 链表头部指向 n[1]
for(i=1;i<=6;i=i+1) // 循环
{ // 循环体开始
n[i].next=&n[i+1]; // n[i].next指向 n[i+1]
} // 循环体结束
n[7].next=null; // 链表尾部赋值为空指针
p=head; // p指向链表头部 head
i=1; // i赋值为 1
do // 直到型循环
{ // 循环体开始
// 提示输入结点信息
printf("结点 %d,x=%d,y=%d\n",i,(*p).x,(*p).y);
p=(*p).next; // p指向相邻的下一个结点
i=i+1; // i加 1
} while(p!=null); // 未到达链表尾部，则继续循环
} // 主函数结束
16
任务,
我们要作一张登记表，登记排队求职信息，包括：姓名、年
龄、性别、电话四个参数。希望便于管理，即可以插入和删
除，这时可用队列，采用结构类型变量。
struct ST
{
char name[20]; // 字符串，姓名
int age; // 整数，年龄
char sex; // 字符，性别
long num; // 电话号码
struct ST *next; // ST结构的指针
}; // 注意，这里必须有分号
声明结构指针变量用下列形式
struct ST *head,*p,*q;
上面的 head,p,q 为结构指针。
17
结构的成员可以是指针，意味着这种结构指针可以指
向结构变量。
结构变量和指向结构变量的指针可以作为函数的参数
与返回值。用结构变量作函数返回值的函数称之为
结构函数。 struct ST *create(void)就是结构函数，
为了了解结构变量成员的地址情况，我们给出了程
序“结构 5.c”，在这个程序中我们重点看
1,#include <malloc.h>
这是预编译命令，为了分配结构变量的内存地址用
的。
2,#define null 0
这是定义空指针变量常量,null 代表 0。
3,#define LEN sizeof(struct ST)
定义常量 LEN，表示结构 ST中的变量的全部单元
的长度，分配内存空间时需要知道这个长度信息。
18
4、结构 ST的定义
5、函数 create的定义
6、给结构指针 p分配内存空间。
p=(struct ST *) malloc (LEN);
7、查看指针 p所在的地址
printf(“指针 p所在的地址 &p=%X\n”,&p);
8、查看指针 p所指向的地址
printf(“指针 p所指向的地址 p=%X\n\n”,p);
9、输入姓名，查看姓名所在的地址
scanf(“%s”,&((*p).name));
10、输入年龄，查看年龄数据所在的地址
scanf(“%d”,&((*p).age));
printf(“年龄数据所在地址 %X\n\n”,&((*p).age));
19
// 结构 5.c（分四页）
#include <stdio.h> // 预编译命令
#include <malloc.h> // 预编译命令，内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct ST) // 定义常量 LEN,
// 表示结构 ST的长度
struct ST // 结构 ST定义
{
char name[20]; // 字符串，表示名字
int age; // 整数类型，表示年龄
char sex; // 字符类型，表示性别
long num; // 长整型，表示电话号码
struct ST *next; // ST结构指针
};
struct ST *head,*p,*q; // 声明，结构指针变量 head,p,q
20
void create(void)// 定义一个名为 create的函数，无形参和返回值
{ // 函数体开始
int n=0; // 整型变量 n，赋初值为 0
head=null; // ST结构指针 head，赋初值为 null
p=(struct ST *) malloc(LEN); // 给结构指针 p分配内存空间
// 输出指针 p所在地址
printf("指针 p所在地址 &p=%X\n",&p);
// 输出指针 p所指向的地址
printf("指针 p所指向的地址 p=%X\n\n",p);
q=p; // q赋值为 p，即 q指向 p所指的内容
// 输出指针 p所在地址
printf("指针 q所在地址 &q=%X\n",&q);
// 输出指针 p所指向的地址
printf("指针 q所指向的地址 q=%X\n\n",q);
21
// 提示输入第 n+1个结点的数据
printf("输入第 %d个结点的数据 \n",n+1);
printf("依次为 name,age,sex,num\n");
// 提示输入姓名数据，并输出其所在地址
printf("输入姓名数据 %d\n",n+1);
scanf("%s",&((*p).name));
printf("姓名数据所在地址 %X\n\n",&((*p).name));
// 提示输入年龄数据，并输出其所在地址
printf("输入年龄数据 %d\n",n+1);
scanf("%d",&((*p).age));
printf("年龄数据所在地址 %X\n\n",&((*p).age));
// 提示输入性别数据，并输出其所在地址
printf("输入性别数据 %d\n",n+1);
scanf("%s",&((*p).sex));
printf("性别数据所在地址 %X\n\n",&((*p).sex));
22
printf("输入电话号码数据 %d\n",n+1);// 输出提示信息
// 从键盘输入电话号码
scanf("%ld",&((*p).num));
// 输出电话号码所在地址
printf("电话号码所在地址 %X\n\n",&((*p).num));
printf("输出姓名 %s\n",p->name); // 输出姓名
printf("输出年龄 %d\n",p->age); // 输出年龄
printf("输出性别 %c\n",p->sex); // 输出性别
printf("输出电话号码 %ld\n",p->num);// 输出电话号码
}
void main() // 主函数
{ // 主函数开始
create(); // 调用函数 create()，建立链表
} // 主函数结束
23
定义 p,q 为 ST 结构指针，定义一个 t m p S t r 字符串
作临时变量，让 h e a d,p,q 三个指针初始化为空。
让 n = 0 （初始化计数器 n ）
n = n + 1 ; 计数器加 1
输入姓名赋给临时变量 t m p S t r
s t r c m p ( t m p S t r,”,, ) = = 0
T F
输入了,,,,结束输入，退出
循环
分配空间给 p 指针,p = ( s t r u c t S T * ) m a l l o c ( L EN );
给出出错信息，退出循环
s t r c p y ( ( * p ), n a m e,t m p S t r ) ;
将临时变量 t m p S t r 中存放的姓名存入结构中
p = = n u l l,分配不成功？
T F
输入，并存入年龄,
输入，并存入性别,
输入，并存入电话号码
h e a d = p ; 让头指针指向第 1
个结点
n = = 1,是第一个结点吗？
T F
( * q ), n e x t = p ; 将该
结点加到表尾
q = p ; 让 q 指向新加入的结点 p,这是表尾
w h i l e ( 1 ) ; 用 1 表示死循环
do
struct ST * create(void)
24
( * q ), n e x t = n u l l ; 让表尾的 n e x t 指向空
q! = n u l l,链表尾不空 T F
do
w h i l e ( 1 ) ; 用 1 表示死循环
25
// 结构 6.c（分四页）
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct ST) // 定义常量，表示结构长度
struct ST // 结构声明
{
char name[20]; // 名字，字符串
int age; // 年龄，整型数组
char sex; // 性别，字符型变量
long num; // 电话号码，长整型变量
struct ST *next; // ST结构指针
};
struct ST *head; // 声明全局变量 head为 ST结构指针
void create(void) // 被调用函数，用于建立链表
{ // 函数体开始
struct ST *p,*q; // 声明 ST结构指针 p,q
int n=0; // 整型变量，用于记录输入的人数
char tmpStr[20]; // 字符串，作为临时变量
head=null; // 链表头部指针，初始化为空
p = null; // 链表当前结构指针，初始化为空
q = null; // 链表尾部指针，初始化为空
26
do // 直到型循环，用于循环输入人员信息
{
n=n+1; // 人数加 1
printf("输入第 %d个结点的数据 \n",n);// 提示信息
printf("输入姓名数据 %d\n",n); // 提示输入姓名
scanf("%s",tmpStr); // 输入姓名信息，并存入临时变量
// 判断输入是否结束，如果为 "."，则结束
if (strcmp(tmpStr,".")==0) break;
p=(struct ST *) malloc(LEN); // 为 p分配空间
if (p == null) // 判断分配是否成功
{
// 如果分配出错，则输出出错信息
printf("Insufficient memory available\n" );
break; // 退出循环
}
27
strcpy((*p).name,tmpStr);// 将名字存入 p结构中的 name单元
printf("输入年龄数据 %d\n",n); // 提示输入年龄
scanf("%d",&((*p).age)); // 输入年龄
printf("输入性别数据 %d\n",n); // 提示输入年龄
scanf("%s",&((*p).sex)); // 输入性别
printf("输入电话号码数据 %d\n",n); // 提示输入电话号码
scanf("%ld",&((*p).num)); // 输入电话号码
if(n==1) head=p; // 如果是第一个结构，则将 head指向此结构
else (*q).next=p; // 如果不是第一个结构,
// 则将此结构加到链表尾部
q=p; // q指针指向此结构，表示新的链表尾部
}while(1); // 循环体结束,1表示死循环
if (q!=null) // 链表尾部是否为空
q->next = null; // 如果不为空，则链表尾部的 next指向空指针
}
28
void print() // 被调用函数，形参为 ST结构指针
{
int k=0; // 整型变量，用于计数
struct ST * r; // 声明 r为 ST结构指针
r=head; // r赋值为 head，即指向 head所指向的内容
while(r != null) // 当型循环，链表指针不为空
{ // 循环体开始
k=k+1; // 计数加 1
printf("输出排队求职者信息 %d:%s,%d,%c,%ld\n"
,k,r->name,r->age,r->sex,r->num); // 输出人员信息
r=r->next;
} // 循环体结束
} // 被调用函数结束
void main() // 主函数开始
{ // 函数体开始
create(); // 调用 create函数建立链表
print(); // 调用 print函数，输出链表内容
} // 主函数结束
29
字符串处理函数简介
1,strcmp(s1,s2)
例
printf(“###### %d\n”,strcmp(“b”,”b”));
输出 ###### 0
printf(“######%d\n”,strcmp(“b”,”f”));
输出 ###### -1
结论,
?当 s1>s2时 strcmp(s1,s2)的值为 1
?当 s1＝ s2时 strcmp(s1,s2)的值为 0
?当 s1<s2时 strcmp(s1,s2)的值为 -1
30
字符串处理函数简介
2,strncmp(s1,s2,n)
类似于 strcmp(s1,s2,n)，但只比较两个字符串的前 n
个字符。
3,strlen(s)
返回 s字符串的长度（不包括结束符 ’\0’）
例,printf(“###### %d\n”,strlen(“abcdefgh”));
输出 ###### 8
4,strcpy(s1,s2)
将 s2的内容复制到 s1中，返回 s1指针。其中 s1和 s2
为指向 char的指针。
31
链表插入结点
原则,
?1、插入操作不应破坏原链接关系
?2、插入的结点应该在它该在的位置。应该
有一个插入位置的查找子过程。
32
5
head
6
10
15
null
12 8
先看下面一个简单的例子,已有一个如图所示的链表。
它是按结点中的整数域从小到大排序的。现在要插
入一个结点，该节点中的数为 10。
待插入结点 此结点已插入链表
33
分析,
考虑将结点 p插入链表 head中，分如下三种情况,
?1、第一种情况，链表还未建成（空链表），待插入结
点 p实际上是第一个结点。这时必然有 head==null。只
要让头指针指向 p就可以了。语句为
6
null
head
p head = p; p->next = null;
?2、第二种情况，链表已建成，待插入结点 p的数据
要比头结点的数据还要小，这时有
p->num <head->num
当然 p结点要插在 head结点前。
34
6 head 8
5
12
null
head
p
p->next=head;
head=p;
语句为
null
35
?3、第三种情况，链表已建成，待插入结点 p的数
据比头结点的数据大，需要找到正确的插入位置。
这时，可以借助两个结构指针 r和 q，利用循环比
较来找到正确位置。然后将结点 p插入到链表中正
确的位置。
参见下面的图示
36
6 head 8 12
13
null
p
15
q r
说明,这种情况下,p结点已经与链表的第一个结点
比较过了，所以从链表的下一个结点开始比较。
13>8，继续比较。
37
6 head 8 12
13
null
p
15
q r
说明,13>12，继续比较。
38
6 head 8 12
13 p
15
q r
null
说明,13<15，找到了正确的插入位置，则插入结点 p。
语句为,
r->next = p;
p->next = q;
39
// 结构 7.c
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct numST) // 定义常量，表示结构长度
struct numST // 结构声明
{
int num; // 整型数
struct numST *next; // numST结构指针
};
参考程序
40
// 被调用函数 insert()，两个形参分别表示链表和待插入的结点
void insert (struct numST **phead,struct numST *p)
{ // 函数体开始
struct numST *q,*r; // 定义结构指针 q,r
if ((*phead)==null) // 第一种情况,链表为空
{
*phead = p; // 链表头指向 p
return; // 完成插入操作，返回
}
else // 链表不为空
{
// 第二种 情况, p结点 num值小于链表头结点的 num值
if ( (*phead)->num > p->num)
{ // 将 p结点插到链表头部
p->next = *phead;// 将 p的 next指针指向链表头 (*phead)
*phead = p; // 将链表头赋值为 p
return; // 返回
}
41
// 第三种 情况,循环查找正确位置
r = *phead; // r赋值为链表头
q = (*phead)->next; // q赋值为链表的下一个结点
while (q!=null) // 利用循环查找正确位置
{
// 判断当前结点 num是否小于 p结点的 num
if (q->num < p->num)
{
r = q; // r赋值为 q，即指向 q所指的结点
q = q->next;// q指向链表中相邻的下一个结点
}
else // 找到了正确的位置
break; // 退出循环
}
// 将 p结点插入正确的位置
r->next = p;
p->next = q;
}
}
42
// 被调用函数，形参为 ST结构指针, 用于输出链表内容
void print(struct numST *head)
{
int k=0; // 整型变量，用于计数
struct numST * r; // 声明 r为 ST结构指针
r=head; // r赋值为 head，即指向 链表头
while(r != null) // 当型循环，链表指针不为空 则 继续
{ // 循环体开始
k=k+1; // 计数加 1
printf("%d %d\n",k,r->num);
r=r->next; // 取链表中相邻的下一个结点
} // 循环体结束
}
43
void main() // 主函数开始
{ // 函数体开始
struct numST *head,*p; // ST型结构指针
head = null;
// 分配两个 ST结构的内存空间，用于构造链表
head = (struct numST *) malloc(LEN);
head->next = (struct numST *) malloc(LEN);
// 为链表中的两个结点中的 num赋值为 5和 10
head->num = 5;
head->next->num = 10;
head->next->next = null; // 链表尾赋值为空
// 构造一个结点 p，用于插入链表
p = (struct numST *) malloc(LEN);
p->num = 8;
p->next = null;
insert(&head,p); // 调用 create函数建立链表,
print(head); // 调用 print函数，输出链表内容
} // 主函数结束
44
说明,函数 insert()的第一个形参为 struct numST**
类型，即“指针的指针”。调用时送入的实参是
链表头指针的地址，即程序中的 &head。这样对
head的修改才会在函数返回后仍有效。如果形参
为 struct numST*，则传入的为指针，当函数返回
后,head无法改变。
45
结 束
第九讲 结构
2
例：跳马。依下图将每一步跳马之后的位置 (x,y)放到
一个, 结点, 里，再用, 链子穿起来,,形成一条
链，相邻两结点间用一个指针将两者连到一起。
结构的概念与应用
0 1 2 3 4 5 6 7 8
4
3
2
1
结点 1
2
3
4
5
6
7
3
依上图有 7个结点
(x1,y1) (x2,y2) (x6,y6) (x7,y7)
为了表示这种既有数据又有指针的情况，引入结构
这种数据类型。
4
结构 ——是一种构造类型的数据类型。结构是数
目固定、类型不同的若干变量的有序集合。结
构与数组的区别在于结构内允许有不同类型的
数据。
结构的定义,格式如下,
struct <结构名 >
{
<成员说明 >
}
5
例如跳马棋局可如下定义
struct TM
{
int x,y; // 结构 TM的成员,x,y为整数型
struct TM *next // 结构 TM的成员，属 TM型
}
下面的表是马的跳步方案，从左下角跳到右上角
结点 n1 n2 n3 n4 n5 n6 n7
x
y
0
0
1
2
2
4
4
3
6
4
7
2
8
4
6
8
4
NULL
NULL为空地址
下面是形成链表的一个参考程序 （分三页）
2
4
&n4
1
2
&n3
0
0
&n2
&n1
head
7
// 结构 1.c
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
struct TM // 定义结构 TM
{
int x,y; // 整型变量 x,y
struct TM *next; // 指向 TM结构的指针
};
void main() // 主函数
{ // 主函数开始
int i; // 声明整型变量
// 声明 TM结构 n1~n7,结构指针 head,p
struct TM n1,n2,n3,n4,n5,n6,n7,*head,*p;
8
// 分别对 TM结构 n1~n7中的 x,y赋值
n1.x=0;n1.y=0;
n2.x=1;n2.y=2;
n3.x=2;n3.y=4;
n4.x=4;n4.y=4;
n5.x=6;n5.y=4;
n6.x=7;n6.y=2;
n7.x=8;n7.y=4;
// head赋值为 n1，即 head指向 n1
head=&n1;
// n1~n7构成链表
n1.next=&n2;
n2.next=&n3;
n3.next=&n4;
n4.next=&n5;
n5.next=&n6;
n6.next=&n7;
// n7的 next指针赋值为空指针
n7.next=null;
9
p=head; // p赋值为 head，即 p指向 head所指的内容
i=1; // i赋值为 1
do // 直到型循环
{ // 循环体开始
// 输出结点信息
printf("结点 %d,x=%d,y=%d\n",i,p->x,p->y);
p=p->next; // p指向下一个结点
i=i+1; // 计数加 1
} while(p!=null); // 未到达链表尾部，则继续循环
} // 主函数结束
10
用结构数组，利用键盘输入结点中的数据。
重点看
scanf(“%d”,&a);
n[i].x=a;
结构数组，数组中的元素为结构类型的数据，如 n[8]
// 结构 2.c
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
struct TM // 定义 TM结构
{
int x,y; // 整型变量 x,y
struct TM *next; // 指向 TM结构的指针
};
11
void main() // 主函数
{ // 主函数开始
int i,a,b; // 声明整型变量 i,a,b
// 声明 TM型结构数组 n[8],TM结构指针 head,p
struct TM n[8],*head,*p;
for(i=1;i<=7;i=i+1) // 循环
{ // 循环体开始
printf("输入 n[%d]的 x\n",i); // 提示输入第 i个结构的 x值
scanf("%d",&a); // 输入 a
n[i].x=a; // 将 a的值赋给结构 n[i]的元素 x
printf("输入 n[%d]的 y\n",i); // 提示输入第 i个结构的 y值
scanf("%d",&b); // 输入 b
n[i].y=b; // 将 b的值赋给结构 n[i]的元素 y
} // 循环体结束
12
head=&n[1]; // 链表头部指向 n[1]
for(i=1;i<=6;i=i+1) // 将结构数组 n形成链表
{
n[i].next=&n[i+1]; // n[i]的 next指针指向下一个结构 n[i+1]
}
n[7].next=null; // 链表尾部指向空
p=head; // p指向链表头部 head
i=1; // i赋值为 1
do // 直到型循环, 用于输出链表内容
{ // 循环体开始
// 输出结点内容
printf("结点 %d,x=%d,y=%d\n",i,p->x,p->y);
p=p->next; // p指向相邻的下一个结点
i=i+1; // 计数 i加 1
} while(p!=null); // 未到链表尾部，则继续循环
} // 主函数结束
13
下面的程序与上面的程序区别仅在
scanf(“%d”,&(n[i].x));
去替换
scanf(“%d”,&a);
n[i].x=a;
// 结构 3.c
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
struct TM // 定义 TM结构
{
int x,y; // 整型变量 x,y
struct TM *next; // 指向 TM结构的指针
};
14
void main() // 主函数
{ // 主函数开始
int i,a,b; // 声明整型变量 i,a,b
// 声明 TM型结构数组 n[8],TM结构指针 head,p
struct TM n[8],*head,*p;
for(i=1;i<=7;i=i+1) // 循环
{ // 循环体开始
printf("输入 n[%d]的 x\n",i); // 提示输入第 i个结构的 x值
scanf("%d",&(n[i].x)); // 输入 n[i].x
printf("输入 n[%d]的 y\n",i); // 提示输入第 i个结构的 y值
scanf("%d",&(n[i].y)); // 输入 n[i].y
} // 循环体结束
15
head=&n[1]; // 链表头部指向 n[1]
for(i=1;i<=6;i=i+1) // 循环
{ // 循环体开始
n[i].next=&n[i+1]; // n[i].next指向 n[i+1]
} // 循环体结束
n[7].next=null; // 链表尾部赋值为空指针
p=head; // p指向链表头部 head
i=1; // i赋值为 1
do // 直到型循环
{ // 循环体开始
// 提示输入结点信息
printf("结点 %d,x=%d,y=%d\n",i,(*p).x,(*p).y);
p=(*p).next; // p指向相邻的下一个结点
i=i+1; // i加 1
} while(p!=null); // 未到达链表尾部，则继续循环
} // 主函数结束
16
任务,
我们要作一张登记表，登记排队求职信息，包括：姓名、年
龄、性别、电话四个参数。希望便于管理，即可以插入和删
除，这时可用队列，采用结构类型变量。
struct ST
{
char name[20]; // 字符串，姓名
int age; // 整数，年龄
char sex; // 字符，性别
long num; // 电话号码
struct ST *next; // ST结构的指针
}; // 注意，这里必须有分号
声明结构指针变量用下列形式
struct ST *head,*p,*q;
上面的 head,p,q 为结构指针。
17
结构的成员可以是指针，意味着这种结构指针可以指
向结构变量。
结构变量和指向结构变量的指针可以作为函数的参数
与返回值。用结构变量作函数返回值的函数称之为
结构函数。 struct ST *create(void)就是结构函数，
为了了解结构变量成员的地址情况，我们给出了程
序“结构 5.c”，在这个程序中我们重点看
1,#include <malloc.h>
这是预编译命令，为了分配结构变量的内存地址用
的。
2,#define null 0
这是定义空指针变量常量,null 代表 0。
3,#define LEN sizeof(struct ST)
定义常量 LEN，表示结构 ST中的变量的全部单元
的长度，分配内存空间时需要知道这个长度信息。
18
4、结构 ST的定义
5、函数 create的定义
6、给结构指针 p分配内存空间。
p=(struct ST *) malloc (LEN);
7、查看指针 p所在的地址
printf(“指针 p所在的地址 &p=%X\n”,&p);
8、查看指针 p所指向的地址
printf(“指针 p所指向的地址 p=%X\n\n”,p);
9、输入姓名，查看姓名所在的地址
scanf(“%s”,&((*p).name));
10、输入年龄，查看年龄数据所在的地址
scanf(“%d”,&((*p).age));
printf(“年龄数据所在地址 %X\n\n”,&((*p).age));
19
// 结构 5.c（分四页）
#include <stdio.h> // 预编译命令
#include <malloc.h> // 预编译命令，内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct ST) // 定义常量 LEN,
// 表示结构 ST的长度
struct ST // 结构 ST定义
{
char name[20]; // 字符串，表示名字
int age; // 整数类型，表示年龄
char sex; // 字符类型，表示性别
long num; // 长整型，表示电话号码
struct ST *next; // ST结构指针
};
struct ST *head,*p,*q; // 声明，结构指针变量 head,p,q
20
void create(void)// 定义一个名为 create的函数，无形参和返回值
{ // 函数体开始
int n=0; // 整型变量 n，赋初值为 0
head=null; // ST结构指针 head，赋初值为 null
p=(struct ST *) malloc(LEN); // 给结构指针 p分配内存空间
// 输出指针 p所在地址
printf("指针 p所在地址 &p=%X\n",&p);
// 输出指针 p所指向的地址
printf("指针 p所指向的地址 p=%X\n\n",p);
q=p; // q赋值为 p，即 q指向 p所指的内容
// 输出指针 p所在地址
printf("指针 q所在地址 &q=%X\n",&q);
// 输出指针 p所指向的地址
printf("指针 q所指向的地址 q=%X\n\n",q);
21
// 提示输入第 n+1个结点的数据
printf("输入第 %d个结点的数据 \n",n+1);
printf("依次为 name,age,sex,num\n");
// 提示输入姓名数据，并输出其所在地址
printf("输入姓名数据 %d\n",n+1);
scanf("%s",&((*p).name));
printf("姓名数据所在地址 %X\n\n",&((*p).name));
// 提示输入年龄数据，并输出其所在地址
printf("输入年龄数据 %d\n",n+1);
scanf("%d",&((*p).age));
printf("年龄数据所在地址 %X\n\n",&((*p).age));
// 提示输入性别数据，并输出其所在地址
printf("输入性别数据 %d\n",n+1);
scanf("%s",&((*p).sex));
printf("性别数据所在地址 %X\n\n",&((*p).sex));
22
printf("输入电话号码数据 %d\n",n+1);// 输出提示信息
// 从键盘输入电话号码
scanf("%ld",&((*p).num));
// 输出电话号码所在地址
printf("电话号码所在地址 %X\n\n",&((*p).num));
printf("输出姓名 %s\n",p->name); // 输出姓名
printf("输出年龄 %d\n",p->age); // 输出年龄
printf("输出性别 %c\n",p->sex); // 输出性别
printf("输出电话号码 %ld\n",p->num);// 输出电话号码
}
void main() // 主函数
{ // 主函数开始
create(); // 调用函数 create()，建立链表
} // 主函数结束
23
定义 p,q 为 ST 结构指针，定义一个 t m p S t r 字符串
作临时变量，让 h e a d,p,q 三个指针初始化为空。
让 n = 0 （初始化计数器 n ）
n = n + 1 ; 计数器加 1
输入姓名赋给临时变量 t m p S t r
s t r c m p ( t m p S t r,”,, ) = = 0
T F
输入了,,,,结束输入，退出
循环
分配空间给 p 指针,p = ( s t r u c t S T * ) m a l l o c ( L EN );
给出出错信息，退出循环
s t r c p y ( ( * p ), n a m e,t m p S t r ) ;
将临时变量 t m p S t r 中存放的姓名存入结构中
p = = n u l l,分配不成功？
T F
输入，并存入年龄,
输入，并存入性别,
输入，并存入电话号码
h e a d = p ; 让头指针指向第 1
个结点
n = = 1,是第一个结点吗？
T F
( * q ), n e x t = p ; 将该
结点加到表尾
q = p ; 让 q 指向新加入的结点 p,这是表尾
w h i l e ( 1 ) ; 用 1 表示死循环
do
struct ST * create(void)
24
( * q ), n e x t = n u l l ; 让表尾的 n e x t 指向空
q! = n u l l,链表尾不空 T F
do
w h i l e ( 1 ) ; 用 1 表示死循环
25
// 结构 6.c（分四页）
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct ST) // 定义常量，表示结构长度
struct ST // 结构声明
{
char name[20]; // 名字，字符串
int age; // 年龄，整型数组
char sex; // 性别，字符型变量
long num; // 电话号码，长整型变量
struct ST *next; // ST结构指针
};
struct ST *head; // 声明全局变量 head为 ST结构指针
void create(void) // 被调用函数，用于建立链表
{ // 函数体开始
struct ST *p,*q; // 声明 ST结构指针 p,q
int n=0; // 整型变量，用于记录输入的人数
char tmpStr[20]; // 字符串，作为临时变量
head=null; // 链表头部指针，初始化为空
p = null; // 链表当前结构指针，初始化为空
q = null; // 链表尾部指针，初始化为空
26
do // 直到型循环，用于循环输入人员信息
{
n=n+1; // 人数加 1
printf("输入第 %d个结点的数据 \n",n);// 提示信息
printf("输入姓名数据 %d\n",n); // 提示输入姓名
scanf("%s",tmpStr); // 输入姓名信息，并存入临时变量
// 判断输入是否结束，如果为 "."，则结束
if (strcmp(tmpStr,".")==0) break;
p=(struct ST *) malloc(LEN); // 为 p分配空间
if (p == null) // 判断分配是否成功
{
// 如果分配出错，则输出出错信息
printf("Insufficient memory available\n" );
break; // 退出循环
}
27
strcpy((*p).name,tmpStr);// 将名字存入 p结构中的 name单元
printf("输入年龄数据 %d\n",n); // 提示输入年龄
scanf("%d",&((*p).age)); // 输入年龄
printf("输入性别数据 %d\n",n); // 提示输入年龄
scanf("%s",&((*p).sex)); // 输入性别
printf("输入电话号码数据 %d\n",n); // 提示输入电话号码
scanf("%ld",&((*p).num)); // 输入电话号码
if(n==1) head=p; // 如果是第一个结构，则将 head指向此结构
else (*q).next=p; // 如果不是第一个结构,
// 则将此结构加到链表尾部
q=p; // q指针指向此结构，表示新的链表尾部
}while(1); // 循环体结束,1表示死循环
if (q!=null) // 链表尾部是否为空
q->next = null; // 如果不为空，则链表尾部的 next指向空指针
}
28
void print() // 被调用函数，形参为 ST结构指针
{
int k=0; // 整型变量，用于计数
struct ST * r; // 声明 r为 ST结构指针
r=head; // r赋值为 head，即指向 head所指向的内容
while(r != null) // 当型循环，链表指针不为空
{ // 循环体开始
k=k+1; // 计数加 1
printf("输出排队求职者信息 %d:%s,%d,%c,%ld\n"
,k,r->name,r->age,r->sex,r->num); // 输出人员信息
r=r->next;
} // 循环体结束
} // 被调用函数结束
void main() // 主函数开始
{ // 函数体开始
create(); // 调用 create函数建立链表
print(); // 调用 print函数，输出链表内容
} // 主函数结束
29
字符串处理函数简介
1,strcmp(s1,s2)
例
printf(“###### %d\n”,strcmp(“b”,”b”));
输出 ###### 0
printf(“######%d\n”,strcmp(“b”,”f”));
输出 ###### -1
结论,
?当 s1>s2时 strcmp(s1,s2)的值为 1
?当 s1＝ s2时 strcmp(s1,s2)的值为 0
?当 s1<s2时 strcmp(s1,s2)的值为 -1
30
字符串处理函数简介
2,strncmp(s1,s2,n)
类似于 strcmp(s1,s2,n)，但只比较两个字符串的前 n
个字符。
3,strlen(s)
返回 s字符串的长度（不包括结束符 ’\0’）
例,printf(“###### %d\n”,strlen(“abcdefgh”));
输出 ###### 8
4,strcpy(s1,s2)
将 s2的内容复制到 s1中，返回 s1指针。其中 s1和 s2
为指向 char的指针。
31
链表插入结点
原则,
?1、插入操作不应破坏原链接关系
?2、插入的结点应该在它该在的位置。应该
有一个插入位置的查找子过程。
32
5
head
6
10
15
null
12 8
先看下面一个简单的例子,已有一个如图所示的链表。
它是按结点中的整数域从小到大排序的。现在要插
入一个结点，该节点中的数为 10。
待插入结点 此结点已插入链表
33
分析,
考虑将结点 p插入链表 head中，分如下三种情况,
?1、第一种情况，链表还未建成（空链表），待插入结
点 p实际上是第一个结点。这时必然有 head==null。只
要让头指针指向 p就可以了。语句为
6
null
head
p head = p; p->next = null;
?2、第二种情况，链表已建成，待插入结点 p的数据
要比头结点的数据还要小，这时有
p->num <head->num
当然 p结点要插在 head结点前。
34
6 head 8
5
12
null
head
p
p->next=head;
head=p;
语句为
null
35
?3、第三种情况，链表已建成，待插入结点 p的数
据比头结点的数据大，需要找到正确的插入位置。
这时，可以借助两个结构指针 r和 q，利用循环比
较来找到正确位置。然后将结点 p插入到链表中正
确的位置。
参见下面的图示
36
6 head 8 12
13
null
p
15
q r
说明,这种情况下,p结点已经与链表的第一个结点
比较过了，所以从链表的下一个结点开始比较。
13>8，继续比较。
37
6 head 8 12
13
null
p
15
q r
说明,13>12，继续比较。
38
6 head 8 12
13 p
15
q r
null
说明,13<15，找到了正确的插入位置，则插入结点 p。
语句为,
r->next = p;
p->next = q;
39
// 结构 7.c
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct numST) // 定义常量，表示结构长度
struct numST // 结构声明
{
int num; // 整型数
struct numST *next; // numST结构指针
};
参考程序
40
// 被调用函数 insert()，两个形参分别表示链表和待插入的结点
void insert (struct numST **phead,struct numST *p)
{ // 函数体开始
struct numST *q,*r; // 定义结构指针 q,r
if ((*phead)==null) // 第一种情况,链表为空
{
*phead = p; // 链表头指向 p
return; // 完成插入操作，返回
}
else // 链表不为空
{
// 第二种 情况, p结点 num值小于链表头结点的 num值
if ( (*phead)->num > p->num)
{ // 将 p结点插到链表头部
p->next = *phead;// 将 p的 next指针指向链表头 (*phead)
*phead = p; // 将链表头赋值为 p
return; // 返回
}
41
// 第三种 情况,循环查找正确位置
r = *phead; // r赋值为链表头
q = (*phead)->next; // q赋值为链表的下一个结点
while (q!=null) // 利用循环查找正确位置
{
// 判断当前结点 num是否小于 p结点的 num
if (q->num < p->num)
{
r = q; // r赋值为 q，即指向 q所指的结点
q = q->next;// q指向链表中相邻的下一个结点
}
else // 找到了正确的位置
break; // 退出循环
}
// 将 p结点插入正确的位置
r->next = p;
p->next = q;
}
}
42
// 被调用函数，形参为 ST结构指针, 用于输出链表内容
void print(struct numST *head)
{
int k=0; // 整型变量，用于计数
struct numST * r; // 声明 r为 ST结构指针
r=head; // r赋值为 head，即指向 链表头
while(r != null) // 当型循环，链表指针不为空 则 继续
{ // 循环体开始
k=k+1; // 计数加 1
printf("%d %d\n",k,r->num);
r=r->next; // 取链表中相邻的下一个结点
} // 循环体结束
}
43
void main() // 主函数开始
{ // 函数体开始
struct numST *head,*p; // ST型结构指针
head = null;
// 分配两个 ST结构的内存空间，用于构造链表
head = (struct numST *) malloc(LEN);
head->next = (struct numST *) malloc(LEN);
// 为链表中的两个结点中的 num赋值为 5和 10
head->num = 5;
head->next->num = 10;
head->next->next = null; // 链表尾赋值为空
// 构造一个结点 p，用于插入链表
p = (struct numST *) malloc(LEN);
p->num = 8;
p->next = null;
insert(&head,p); // 调用 create函数建立链表,
print(head); // 调用 print函数，输出链表内容
} // 主函数结束
44
说明,函数 insert()的第一个形参为 struct numST**
类型，即“指针的指针”。调用时送入的实参是
链表头指针的地址，即程序中的 &head。这样对
head的修改才会在函数返回后仍有效。如果形参
为 struct numST*，则传入的为指针，当函数返回
后,head无法改变。
45
结 束
