1
第十二讲
?二叉树的建立
?循 环 链 表
2
二叉树的建立
3
二叉树的建立
建立二叉树的过程是一个“插入”过程，下面我们用
一个例子来讲解这一过程。
我们想建立这样一棵二叉树，树中的每一个结点有一
个整数数据名为 data，有两个指针：左指针 L，右指
针 R，分别指向这个结点的左子树和右子树，显然
可以用如下名为 TREE的结构来描述这种结点,
struct TREE
{
int data;
struct TREE *L,*R;
}
4
对二叉树最重要的是根，它起定位的作用，因此，首先
建立的是根结点。也就是说，如果从键盘输入数据来
建立二叉树，第一个数据就是这棵树的根的数据，之
后再输入的数据，每一个都要与根中的数据作比较，
以便确定该数据所在结点的插入位置。假定我们这里
依然用图 1的中序遍历的方式。即如果待插入结点的
数据比根结点的数据小，则将其插至左子树，否则插
入右子树。
定义一个递归函数
void insert(struct TREE **proot,struct TREE *p)
其中，指针 p指向含有待插入数据的结点。
proot为树的根指针的地址。
insert函数棵理解为将 p结点插入到 *proot所指向
的树中。
5
insert(proot,p)可用下列与或结点图来描述
inse rt (proot,p)
将结点p插入根结点
*proot=p; return;
返回
C
根结点不空，
树已存在
根结点为空
*proot==null
p->data<=( *proot) ->dat a
inse rt (& (( *proot) ->R),p) ;
将p结点插入右子树
图3
p->data> ( *proot) ->dat a
inse rt (& (( *proot) ->L),p) ;
将p结点插入左子树
6
注意在上图中 proot是被调用函数的形参。从前面对它
的定义看,proot是指针的指针，实际上是指向二叉
树根结点的指针的指针，或者说是指向二叉树根结点
的指针的地址。如下图。因此，在主程序调用 insert
函数时,
根结点
proot
实参
&root
实参为 &root,p
形参为 proot,p
下面是建立二叉树的参考程序。
7
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct TREE) // 定义常量，表示结构长度
struct TREE // 结构声明
{
int data; // 整型数
struct TREE *L,*R; // TREE结构指针
};
8
// 被调用函数 insert，将结点插入二叉树
void insert (struct TREE **proot,struct TREE* p)
{ // 函数体开始
if (*proot==null) // 如果根结点为空
{
*proot = p; // 将结点 p插入根结点
return; // 返回
}
else // 根结点不为空
{
// 如果 p结点数据小于等于根结点数据
if (p->data <= (*proot)->data)
insert( &((*proot)->L),p); // 插入左子树
else // 如果 p结点数据大于等于根结点数据
insert( &((*proot)->R),p); // 插入右子树
}
} // 函数体结束
9
// 被调用函数，形参为 TREE结构指针，输出二叉树内容
void print(struct TREE *root)
{ // 函数体开始
if (root == null) // 根或子树根结点为空
return; // 返回
print(root->L); // 输出左子树内容
printf("%d",root->data);// 输出根结点内容
print(root->R); // 输出右子树内容
} // 被调用函数结束
void main() // 主函数开始
{ // 函数体开始
struct TREE *root,*p; // TREE型结构指针
int temp; // 临时变量，用于用户输入数据
root = null; // 初始化二叉树根结点为空
p = null; // 初始化待插入结点的指针为空
printf("请输入待插入结点的数据 \n"); // 提示信息
printf("如果输入 -1表示插入过程结束 \n");// 提示信息
scanf("%d",&temp); // 输入待插入结点数据
10
while(temp != -1) // 当型循环,-1为结束标志
{ // 循环体开始
// 为待插入结点分配内存单元
p = (struct TREE *) malloc(LEN);
p->data = temp; // 将 temp赋值给 p结点的数据域
p->L = p->R = null; // 将 p结点的左右指针域置为空
insert( &root,p ); // 将 p结点插入到根为 root的树中，
// &root表示二叉树根结点的地址
printf("请输入待插入结点的数据 \n"); // 提示信息
printf("如果输入 -1表示插入过程结束 \n");// 提示信息
scanf("%d",&temp); // 输入待插入结点数据
} // 循环体结束
if (root==null) // 如果根结点为空
printf("这是一棵空树。 \n");// 输出空树信息
else // 根结点不为空
print(root); // 调用 print函数，输出二叉树内容
} // 主函数结束
11
循 环 链 表
12
循环链表
例：猴子选大王。
n只猴子围成一圈，顺时针方向从 1到 n编号。
之后从 1号开始沿顺时针方向让猴子从 1，
2,…, m依次报数，凡报到 m的猴子，都让
其出圈，取消候选资格。然后不停地按顺时
针方向逐一让报出 m者出圈，最后剩下一个
就是猴王。
13
起始位置
猴 王
1
2
3
4
5
6
7
8
3 6 1 5 2 8 4 猴子被淘汰的顺序
演示,n=8,m=3
14
说明,
如图 1所示有 8只猴子围成一圈,m=3。从 1#
猴的位置开始，顺时针 1至 3报数，第一个出
圈的是 3#；第二个出圈的是 6#，第 3个出圈
的是 1#；第 4个出圈的是 5#；第 5个是 2#，第
6个是 8#；第 7个是 4#。最后剩下一个是 7#，
它就是猴王。
我们用 循环链表 来模拟这个选择过程。
15
1、定义一个名为 mon的结构
struct mon
{
int num; // 整数，表示猴子的编号
struct mon *next; // 指针，指向相邻的下一只猴子
}
2、将链表的头指针 head定义为全局变量。
struct mon*head;
3、主函数
用键盘输入猴子数 n，输入数 m，调用函数 create建立一个
循环链表，模拟众猴围成一圈的情况。该函数的实参为 n。
调用函数 select，模拟 1至 m报数，让 n-1只猴子逐一出列的
过程。即在具有 n个结点的循环链表按报数 m删除结点的
过程。该函数的实参为 m，最后输出猴王的编号。
16
4、建立循环链表的函数 create(int nn)
其中 nn为形式参数。要从编号 1到编号 nn。 思路是
（ 1）先做第 1个结点，让其中的数据域 p->num赋值为 1，让
指针域赋值为 null。之后让链头指针 head指向第 1个结点。
利用指针 q记住这个结点，以便让指针 p去生成下面的结
点。
（ 2）利用一个计数循环结构，做出第 2个结点到第 nn个结点。
并将相邻结点一个接一个链接到一起。
（ 3）最后一个结点要和头结点用下一语句链接到一起
tail = q; tail->next = head;
head tail
q
17
5、删结点的函数 select(int mm)
mm为形式参数，从 1至 m报数，凡报到 mm者删除其
所在的结点。
设计两个指针 p和 q。一开始让 q指向链表的尾部 q=tail。
让 p指向 q的下一个结点。开始时让 p指向 1#猴所在的结点。
用一个累加器 x，初始时 x=0，从 1#猴所在结点开始让
x=x+1=1，如果 mm是 1的话,1#猴所在的 p结点就要被删
除。有三条语句
printf(“被删掉的猴子号为 %d号 \n”,p->num);
q->next = p->next;
free(p);
1 head 2 8 tail
q p
演示
18
这里 free(p)是释放 p结点所占用的内存空间的语句。
如果 mm不是 1而是 3，程序会在 do-while循环中，
让 x加两次 1,q和 p一起移动两次,p指向 3#所在结
点,q指向 2#所在结点，之后仍然用上述三条语句
删去 3#所在的结点。
1 head 2 8
q p
3 4
q p p q
演示
19
这个 do-while循环的退出条件是 q==q->next。即当只
剩下一个结点时才退出循环。当然猴王非其莫属了。
这时，让头指针 head指向 q,head是全局变量，在
主程序最后输出猴王时要用 head->num。
参考程序如下,
7 head
q
20
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
// 定义常量，表示结构长度
#define LEN sizeof(struct mon)
struct mon // 结构声明
{
int num; // 整型数，用于记录猴子号
struct mon *next; // mon结构指针
};
struct mon *head,*tail; // mon结构指针，全局变量
21
void create(int nn) // 被调用函数
{ // 函数体开始
int i; // 整型变量 i，用于计数
struct mon *p,*q; // 声明 mon结构指针 p,q
// 为 p分配内存空间
p=(struct mon *) malloc(LEN);
p->num=1; // 初始化 p结点 num域为 1
p->next=null; // 初始化 p结点 next域为空
head=p; // 链表头指针 head赋值为 p
q=p; // q赋值为 p
22
for(i=2;i<=nn;i=i+1) // 利用循环结构构造链表
{ // 循环体开始
p=(struct mon *)malloc(LEN);// 为 p分配内存空间
p->num=i; // 初始化 p结点 num域为 i，表示猴子号
q->next=p; // 将 p结点加到链表尾部
q=p; // 让 q指向链表尾部结点
p->next=null; // 链表尾部指向空
} // 循环体结束
tail = q; // 链表尾
tail->next=head; // 链表尾部指向链表头,
// 形成循环链表
} // 函数体结束
23
// 被调用函数 select,mm表示结点删除间隔
void select(int mm)
{ // 函数体开始
int x=0; // 声明整型值 x，并初始化为 0
struct mon *p,*q; // 声明结构指针 p,q
q=tail; // q赋值为 tail，指向循环链表尾部
do // 直到型循环，用于循环删除指定间隔的结点
{ // 循环体开始
p=q->next; // p赋值为 q相邻的下一个结点
x=x+1; // x加 1
if(x % mm==0) // x是否整除 mm,
{ // 表示是否跳过指定间隔
// 输出被删掉的猴子号
printf("被删掉的猴子号为 %d号 \n",p->num);
q->next=p->next; // 删除此结点
free(p); // 释放空间
}
else q=p; // q指向相邻的下一个结点 p
}while(q!=q->next); // 剩余结点数不为 1，则继续循环
head = q; // head指向结点 q,q为链表中剩余一个结点
} // 函数体结束
24
void main() // 主函数开始
{ // 函数体开始
int n,m; // 声明整型变量 n,m
head = null; // 初始化 head为空
printf("请输入猴子数 \n"); // 提示信息
scanf("%d",&n); // 输入待插入结点数据
printf("请输入间隔 m\n"); // 提示信息
scanf("%d",&m); // 输入间隔
create(n); // 调用函数 create建立循环链表
select(m); // 调用函数 select，找出剩下的猴子
printf("猴王是 %d号 \n",head->num); // 输出猴王
} // 函数体结束
25
第十三讲 文件
26
有关文件的概念和名词
文件 ——是信息的集合，是信息存放在外存中的一
种形式。可以长期保存。
EOF——文件的结束符。
C语言中的文件视为信息流，文件的读写是按顺序
进行的。可以以字符为单位读写，也可以以“行”
为单位读写。一行是以,\n”为结束的一串字符。
文件指针 ——是指向含有文件信息结构的指针。文
件指针又称内部文件名。
对文件进行操作，先要将文件打开。所谓“打开文
件”，就是在内存中为文件建立一个缓冲区，文件
指针就要指向缓冲区的首地址。
27
标准文件
C语言中规定的标准文件有三个,
?1、标准输入文件（键盘），文件指针为 stdin;
?2、标准输出文件（显示屏幕），文件指针为 stdout;
?3、标准出错信息文件，文件指针为 stderr。
特点是这些文件在操作前或后，系统会自动将其打开
或关闭，程序不需管。
28
一般文件
特点,操作前需打开，操作后需关闭。开和闭均是通
过函数进行的。
打开文件 就是要在内存中建立缓冲区，如打开成功，
打开函数返回一个内存地址值，由一个文件指针接
收。以后的操作使用这个指针。如内存不可建立缓
冲区，则打开失败，打开函数返回 NULL。
关闭文件 很重要，是要将文件送回磁盘，并从内存中
清除。及时释放内存空间，并可保证文件安全。
29
标准文件的操作
1,getchar()，从标准输入文件 <stdio.h>中使
用该函数可以得到一个字符。返回值是该字
符的 ASCII码值。因此可见返回值是 int型的。
2,putchar()，将字符代码送至屏幕上，显示
成字符。
30
#include <stdio.h>
void main() // 主函数
{ // 主函数开始
int temp; // 定义整型变量
while((temp=getchar())!=EOF) // 标准输入未结束
if (temp>=?a? && temp<=?z?) // 小写字母
// 将对应的大写字母 输出到屏幕
putchar(temp-?a?+?A?);
else
putchar(temp); // 输出到屏幕
} // 主函数结束
例 文件 1.c
31
说明,
1、由于 getchar()返回的是整数（ ASCII码值）,因此，
temp定义为整数型。
2,EOF被定义为 -1，当 getchar()函数返回 -1时结束，这
里 EOF被定义为 -1，在 DOS系统中只有用 <Ctrl>+Z才
能结束键盘输入。从实验中可以看出 getchar()函数是
将键盘输入的字符的 ASCII码的形式存至缓冲区，敲
入字符之后，须回车才响应输出
a // 敲入的小写字符
temp = 97 // 回车之后，输入 ?a?的 ASCII码
A // 回应大写字符 ?A?,
temp = 65 // 输出回车键的 ASCII码值
32
3、在上述程序基础上，将 getchar改为 getch，
观察程序运行情况。这时不再显示敲入的小
写字母，屏幕上看到的都是大写字母了。但
显示的 ASCII码值仍是小写字母的码值。
退出方式用 <Ctrl>+<Break>
4、将 getch改为 getche再试，观察有何变化？
5、字符串的读写函数 gets()和 puts()。
33
#include <stdio.h> // 预编译命令
#define null 0 // 定义 null为空
void main() // 主函数
{ // 主函数开始
char s[256]; // 定义字符数组 s
int no; // 定义整型变量 no
no = 1; // 初始化 no为 1
while(gets(s)!=null) // s须为指针
{ // 循环体开始
printf(“%d:%s\n”,no,s);// 输出 no和 s
printf(“%X\n”,s); // s是指针
no=no+1; // no加 1
} // 循环体结束
} // 主函数结束
例 文件 2.c
34
说明,
gets(s)函数的形参为字符指针，指向一个由键盘输
入的字符串。正常时返回一个读取到的字符串的
首地址。出错时返回 NULL。输入的字符串以‘ \n?
结束，该函数在内存中将‘ \n?以‘ \0?存放，从而
使 s变为字符串。
看下例,
35
puts(s)是将 s所指向的字符串写到屏幕上，写时将‘ \n?
转换为‘ \0?。
6、使用 printf( ),scanf( ) 略
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
void main() // 主函数
{ // 主函数开始
char s[256]; // 定义字符串
while(gets(s)!=null) // 循环输入
puts(s); // 输出 s到屏幕
} // 循环体结束
36
一般文件的操作
1、打开和关闭文件函数
1.1 打开文件函数 fopen( )
格式为
fopen(,文件名”,打开方式 );
“r”：读方式
“w”：写方式
“a”：追加方式
,rb”：二进制读方式
,wb”：二进制写方式
,ab”：二进制追加方
式
,r+w”：读写方式
37
?用,r”只能读不能写，用,w”只能写不能读。
?用,a”打开的文件可向已有文件内容后边增加新的内
容。使原内容不被新内容所覆盖。
?在用文本文件输入时，将回车换行符转换为一个换行
符；在输出时，把换行符转换成回车符和换行符（两
个字符），在用二进制文件时，不作上述转换，内存
当中的数据形式与输出到外部文件中的数据形式完全
一样。
?fopen函数有一个返回值，正常时返回一个文件指针，
指向内存为该文件开辟的缓冲区首地址。失败时返回
NULL。比如该文件并不存在，你要打开它，当然要
返回 NULL。
?为了写或追加写时，如果要打开的文件不存在，这时
系统会自动帮你建立一个要打开的文件。
38
实际使用时要判断 fopen( )函数的返回值。
常用语句为
if ((fp=fopen(“f1.c”,“r+w”))==NULL)
{
printf(“Can?t open this file.\n”);
exit(1);
}
其中的 fp是已经定义好的文件指针。
1.2 关闭文件的函数为 fclose(文件指针 );
这个函数在正常情况下返回值为 0，关闭有错时返
回非 0值，可用 ferror()函数来检查。
39
2、文件的读和写
#include <stdio.h>
char s[]=“I am a student”;
void main()
{
char a[100]; // 定义 a字符串
FILE *fp; // 定义文件指针为 fp
int n=strlen(s); // 字符串 s的长度
// 打开 f1.txt文件，写方式,fp不为空
if ((fp=fopen(“f1.txt”,”w”))!=NULL)
{
// 将 s所指的字符串写到 fp所指的文件中
fputs(s,fp);
}
fclose(fp);
40
// 打开 f1.txt文件，读，文件指针为 fp
fp = fopen(“f1.txt”,”r”);
// 将 fp所指的文件中的内容读到 a中去
fgets(a,n+1,fp);
printf(“%s\n”,a); // 输出 a中的内容
fclose(fp); // 关闭 fp所指向的文件
} // 主函数结束
说明,
1、要进行文件读写操作先要定义文件指针。
使用 FILE *fp，（ fp可以是其它名称）
2、测出 s字符串长度，使用 int n=strlen(s);
41
3、打开,f1.txt”，,w”，要往 f1.txt中写入。如空则自
动建立一个文件，自然不会空了。
4,fputs(s,fp)是说将 s字符串写入由指针 fp所指向的
f1.txt文件中。
5,fclose(fp)，将 fp所指向的 f1.txt文件关闭。
6、打开 f1.txt 用读的方式
fp=fopen(“f1.txt”,“r”);
7、将读出的字符串放入 a串中，在使用 fgets()函数时用
fgets(a,n+1,fp);其中 a是已经定义好的字符串,n+1是
让 fp所向的文件内容，依次取 n个字符给 a，这 n个字
符恰为 s串的内容，之后还要在该串后自动加入一
个 ?\0?字符。因此要写 n+1。
42
结 束
第十二讲
?二叉树的建立
?循 环 链 表
2
二叉树的建立
3
二叉树的建立
建立二叉树的过程是一个“插入”过程，下面我们用
一个例子来讲解这一过程。
我们想建立这样一棵二叉树，树中的每一个结点有一
个整数数据名为 data，有两个指针：左指针 L，右指
针 R，分别指向这个结点的左子树和右子树，显然
可以用如下名为 TREE的结构来描述这种结点,
struct TREE
{
int data;
struct TREE *L,*R;
}
4
对二叉树最重要的是根，它起定位的作用，因此，首先
建立的是根结点。也就是说，如果从键盘输入数据来
建立二叉树，第一个数据就是这棵树的根的数据，之
后再输入的数据，每一个都要与根中的数据作比较，
以便确定该数据所在结点的插入位置。假定我们这里
依然用图 1的中序遍历的方式。即如果待插入结点的
数据比根结点的数据小，则将其插至左子树，否则插
入右子树。
定义一个递归函数
void insert(struct TREE **proot,struct TREE *p)
其中，指针 p指向含有待插入数据的结点。
proot为树的根指针的地址。
insert函数棵理解为将 p结点插入到 *proot所指向
的树中。
5
insert(proot,p)可用下列与或结点图来描述
inse rt (proot,p)
将结点p插入根结点
*proot=p; return;
返回
C
根结点不空，
树已存在
根结点为空
*proot==null
p->data<=( *proot) ->dat a
inse rt (& (( *proot) ->R),p) ;
将p结点插入右子树
图3
p->data> ( *proot) ->dat a
inse rt (& (( *proot) ->L),p) ;
将p结点插入左子树
6
注意在上图中 proot是被调用函数的形参。从前面对它
的定义看,proot是指针的指针，实际上是指向二叉
树根结点的指针的指针，或者说是指向二叉树根结点
的指针的地址。如下图。因此，在主程序调用 insert
函数时,
根结点
proot
实参
&root
实参为 &root,p
形参为 proot,p
下面是建立二叉树的参考程序。
7
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct TREE) // 定义常量，表示结构长度
struct TREE // 结构声明
{
int data; // 整型数
struct TREE *L,*R; // TREE结构指针
};
8
// 被调用函数 insert，将结点插入二叉树
void insert (struct TREE **proot,struct TREE* p)
{ // 函数体开始
if (*proot==null) // 如果根结点为空
{
*proot = p; // 将结点 p插入根结点
return; // 返回
}
else // 根结点不为空
{
// 如果 p结点数据小于等于根结点数据
if (p->data <= (*proot)->data)
insert( &((*proot)->L),p); // 插入左子树
else // 如果 p结点数据大于等于根结点数据
insert( &((*proot)->R),p); // 插入右子树
}
} // 函数体结束
9
// 被调用函数，形参为 TREE结构指针，输出二叉树内容
void print(struct TREE *root)
{ // 函数体开始
if (root == null) // 根或子树根结点为空
return; // 返回
print(root->L); // 输出左子树内容
printf("%d",root->data);// 输出根结点内容
print(root->R); // 输出右子树内容
} // 被调用函数结束
void main() // 主函数开始
{ // 函数体开始
struct TREE *root,*p; // TREE型结构指针
int temp; // 临时变量，用于用户输入数据
root = null; // 初始化二叉树根结点为空
p = null; // 初始化待插入结点的指针为空
printf("请输入待插入结点的数据 \n"); // 提示信息
printf("如果输入 -1表示插入过程结束 \n");// 提示信息
scanf("%d",&temp); // 输入待插入结点数据
10
while(temp != -1) // 当型循环,-1为结束标志
{ // 循环体开始
// 为待插入结点分配内存单元
p = (struct TREE *) malloc(LEN);
p->data = temp; // 将 temp赋值给 p结点的数据域
p->L = p->R = null; // 将 p结点的左右指针域置为空
insert( &root,p ); // 将 p结点插入到根为 root的树中，
// &root表示二叉树根结点的地址
printf("请输入待插入结点的数据 \n"); // 提示信息
printf("如果输入 -1表示插入过程结束 \n");// 提示信息
scanf("%d",&temp); // 输入待插入结点数据
} // 循环体结束
if (root==null) // 如果根结点为空
printf("这是一棵空树。 \n");// 输出空树信息
else // 根结点不为空
print(root); // 调用 print函数，输出二叉树内容
} // 主函数结束
11
循 环 链 表
12
循环链表
例：猴子选大王。
n只猴子围成一圈，顺时针方向从 1到 n编号。
之后从 1号开始沿顺时针方向让猴子从 1，
2,…, m依次报数，凡报到 m的猴子，都让
其出圈，取消候选资格。然后不停地按顺时
针方向逐一让报出 m者出圈，最后剩下一个
就是猴王。
13
起始位置
猴 王
1
2
3
4
5
6
7
8
3 6 1 5 2 8 4 猴子被淘汰的顺序
演示,n=8,m=3
14
说明,
如图 1所示有 8只猴子围成一圈,m=3。从 1#
猴的位置开始，顺时针 1至 3报数，第一个出
圈的是 3#；第二个出圈的是 6#，第 3个出圈
的是 1#；第 4个出圈的是 5#；第 5个是 2#，第
6个是 8#；第 7个是 4#。最后剩下一个是 7#，
它就是猴王。
我们用 循环链表 来模拟这个选择过程。
15
1、定义一个名为 mon的结构
struct mon
{
int num; // 整数，表示猴子的编号
struct mon *next; // 指针，指向相邻的下一只猴子
}
2、将链表的头指针 head定义为全局变量。
struct mon*head;
3、主函数
用键盘输入猴子数 n，输入数 m，调用函数 create建立一个
循环链表，模拟众猴围成一圈的情况。该函数的实参为 n。
调用函数 select，模拟 1至 m报数，让 n-1只猴子逐一出列的
过程。即在具有 n个结点的循环链表按报数 m删除结点的
过程。该函数的实参为 m，最后输出猴王的编号。
16
4、建立循环链表的函数 create(int nn)
其中 nn为形式参数。要从编号 1到编号 nn。 思路是
（ 1）先做第 1个结点，让其中的数据域 p->num赋值为 1，让
指针域赋值为 null。之后让链头指针 head指向第 1个结点。
利用指针 q记住这个结点，以便让指针 p去生成下面的结
点。
（ 2）利用一个计数循环结构，做出第 2个结点到第 nn个结点。
并将相邻结点一个接一个链接到一起。
（ 3）最后一个结点要和头结点用下一语句链接到一起
tail = q; tail->next = head;
head tail
q
17
5、删结点的函数 select(int mm)
mm为形式参数，从 1至 m报数，凡报到 mm者删除其
所在的结点。
设计两个指针 p和 q。一开始让 q指向链表的尾部 q=tail。
让 p指向 q的下一个结点。开始时让 p指向 1#猴所在的结点。
用一个累加器 x，初始时 x=0，从 1#猴所在结点开始让
x=x+1=1，如果 mm是 1的话,1#猴所在的 p结点就要被删
除。有三条语句
printf(“被删掉的猴子号为 %d号 \n”,p->num);
q->next = p->next;
free(p);
1 head 2 8 tail
q p
演示
18
这里 free(p)是释放 p结点所占用的内存空间的语句。
如果 mm不是 1而是 3，程序会在 do-while循环中，
让 x加两次 1,q和 p一起移动两次,p指向 3#所在结
点,q指向 2#所在结点，之后仍然用上述三条语句
删去 3#所在的结点。
1 head 2 8
q p
3 4
q p p q
演示
19
这个 do-while循环的退出条件是 q==q->next。即当只
剩下一个结点时才退出循环。当然猴王非其莫属了。
这时，让头指针 head指向 q,head是全局变量，在
主程序最后输出猴王时要用 head->num。
参考程序如下,
7 head
q
20
#include <stdio.h> // 预编译命令
#include <malloc.h> // 内存空间分配
#define null 0 // 定义空指针常量
// 定义常量，表示结构长度
#define LEN sizeof(struct mon)
struct mon // 结构声明
{
int num; // 整型数，用于记录猴子号
struct mon *next; // mon结构指针
};
struct mon *head,*tail; // mon结构指针，全局变量
21
void create(int nn) // 被调用函数
{ // 函数体开始
int i; // 整型变量 i，用于计数
struct mon *p,*q; // 声明 mon结构指针 p,q
// 为 p分配内存空间
p=(struct mon *) malloc(LEN);
p->num=1; // 初始化 p结点 num域为 1
p->next=null; // 初始化 p结点 next域为空
head=p; // 链表头指针 head赋值为 p
q=p; // q赋值为 p
22
for(i=2;i<=nn;i=i+1) // 利用循环结构构造链表
{ // 循环体开始
p=(struct mon *)malloc(LEN);// 为 p分配内存空间
p->num=i; // 初始化 p结点 num域为 i，表示猴子号
q->next=p; // 将 p结点加到链表尾部
q=p; // 让 q指向链表尾部结点
p->next=null; // 链表尾部指向空
} // 循环体结束
tail = q; // 链表尾
tail->next=head; // 链表尾部指向链表头,
// 形成循环链表
} // 函数体结束
23
// 被调用函数 select,mm表示结点删除间隔
void select(int mm)
{ // 函数体开始
int x=0; // 声明整型值 x，并初始化为 0
struct mon *p,*q; // 声明结构指针 p,q
q=tail; // q赋值为 tail，指向循环链表尾部
do // 直到型循环，用于循环删除指定间隔的结点
{ // 循环体开始
p=q->next; // p赋值为 q相邻的下一个结点
x=x+1; // x加 1
if(x % mm==0) // x是否整除 mm,
{ // 表示是否跳过指定间隔
// 输出被删掉的猴子号
printf("被删掉的猴子号为 %d号 \n",p->num);
q->next=p->next; // 删除此结点
free(p); // 释放空间
}
else q=p; // q指向相邻的下一个结点 p
}while(q!=q->next); // 剩余结点数不为 1，则继续循环
head = q; // head指向结点 q,q为链表中剩余一个结点
} // 函数体结束
24
void main() // 主函数开始
{ // 函数体开始
int n,m; // 声明整型变量 n,m
head = null; // 初始化 head为空
printf("请输入猴子数 \n"); // 提示信息
scanf("%d",&n); // 输入待插入结点数据
printf("请输入间隔 m\n"); // 提示信息
scanf("%d",&m); // 输入间隔
create(n); // 调用函数 create建立循环链表
select(m); // 调用函数 select，找出剩下的猴子
printf("猴王是 %d号 \n",head->num); // 输出猴王
} // 函数体结束
25
第十三讲 文件
26
有关文件的概念和名词
文件 ——是信息的集合，是信息存放在外存中的一
种形式。可以长期保存。
EOF——文件的结束符。
C语言中的文件视为信息流，文件的读写是按顺序
进行的。可以以字符为单位读写，也可以以“行”
为单位读写。一行是以,\n”为结束的一串字符。
文件指针 ——是指向含有文件信息结构的指针。文
件指针又称内部文件名。
对文件进行操作，先要将文件打开。所谓“打开文
件”，就是在内存中为文件建立一个缓冲区，文件
指针就要指向缓冲区的首地址。
27
标准文件
C语言中规定的标准文件有三个,
?1、标准输入文件（键盘），文件指针为 stdin;
?2、标准输出文件（显示屏幕），文件指针为 stdout;
?3、标准出错信息文件，文件指针为 stderr。
特点是这些文件在操作前或后，系统会自动将其打开
或关闭，程序不需管。
28
一般文件
特点,操作前需打开，操作后需关闭。开和闭均是通
过函数进行的。
打开文件 就是要在内存中建立缓冲区，如打开成功，
打开函数返回一个内存地址值，由一个文件指针接
收。以后的操作使用这个指针。如内存不可建立缓
冲区，则打开失败，打开函数返回 NULL。
关闭文件 很重要，是要将文件送回磁盘，并从内存中
清除。及时释放内存空间，并可保证文件安全。
29
标准文件的操作
1,getchar()，从标准输入文件 <stdio.h>中使
用该函数可以得到一个字符。返回值是该字
符的 ASCII码值。因此可见返回值是 int型的。
2,putchar()，将字符代码送至屏幕上，显示
成字符。
30
#include <stdio.h>
void main() // 主函数
{ // 主函数开始
int temp; // 定义整型变量
while((temp=getchar())!=EOF) // 标准输入未结束
if (temp>=?a? && temp<=?z?) // 小写字母
// 将对应的大写字母 输出到屏幕
putchar(temp-?a?+?A?);
else
putchar(temp); // 输出到屏幕
} // 主函数结束
例 文件 1.c
31
说明,
1、由于 getchar()返回的是整数（ ASCII码值）,因此，
temp定义为整数型。
2,EOF被定义为 -1，当 getchar()函数返回 -1时结束，这
里 EOF被定义为 -1，在 DOS系统中只有用 <Ctrl>+Z才
能结束键盘输入。从实验中可以看出 getchar()函数是
将键盘输入的字符的 ASCII码的形式存至缓冲区，敲
入字符之后，须回车才响应输出
a // 敲入的小写字符
temp = 97 // 回车之后，输入 ?a?的 ASCII码
A // 回应大写字符 ?A?,
temp = 65 // 输出回车键的 ASCII码值
32
3、在上述程序基础上，将 getchar改为 getch，
观察程序运行情况。这时不再显示敲入的小
写字母，屏幕上看到的都是大写字母了。但
显示的 ASCII码值仍是小写字母的码值。
退出方式用 <Ctrl>+<Break>
4、将 getch改为 getche再试，观察有何变化？
5、字符串的读写函数 gets()和 puts()。
33
#include <stdio.h> // 预编译命令
#define null 0 // 定义 null为空
void main() // 主函数
{ // 主函数开始
char s[256]; // 定义字符数组 s
int no; // 定义整型变量 no
no = 1; // 初始化 no为 1
while(gets(s)!=null) // s须为指针
{ // 循环体开始
printf(“%d:%s\n”,no,s);// 输出 no和 s
printf(“%X\n”,s); // s是指针
no=no+1; // no加 1
} // 循环体结束
} // 主函数结束
例 文件 2.c
34
说明,
gets(s)函数的形参为字符指针，指向一个由键盘输
入的字符串。正常时返回一个读取到的字符串的
首地址。出错时返回 NULL。输入的字符串以‘ \n?
结束，该函数在内存中将‘ \n?以‘ \0?存放，从而
使 s变为字符串。
看下例,
35
puts(s)是将 s所指向的字符串写到屏幕上，写时将‘ \n?
转换为‘ \0?。
6、使用 printf( ),scanf( ) 略
#include <stdio.h> // 预编译命令
#define null 0 // 定义空指针常量
void main() // 主函数
{ // 主函数开始
char s[256]; // 定义字符串
while(gets(s)!=null) // 循环输入
puts(s); // 输出 s到屏幕
} // 循环体结束
36
一般文件的操作
1、打开和关闭文件函数
1.1 打开文件函数 fopen( )
格式为
fopen(,文件名”,打开方式 );
“r”：读方式
“w”：写方式
“a”：追加方式
,rb”：二进制读方式
,wb”：二进制写方式
,ab”：二进制追加方
式
,r+w”：读写方式
37
?用,r”只能读不能写，用,w”只能写不能读。
?用,a”打开的文件可向已有文件内容后边增加新的内
容。使原内容不被新内容所覆盖。
?在用文本文件输入时，将回车换行符转换为一个换行
符；在输出时，把换行符转换成回车符和换行符（两
个字符），在用二进制文件时，不作上述转换，内存
当中的数据形式与输出到外部文件中的数据形式完全
一样。
?fopen函数有一个返回值，正常时返回一个文件指针，
指向内存为该文件开辟的缓冲区首地址。失败时返回
NULL。比如该文件并不存在，你要打开它，当然要
返回 NULL。
?为了写或追加写时，如果要打开的文件不存在，这时
系统会自动帮你建立一个要打开的文件。
38
实际使用时要判断 fopen( )函数的返回值。
常用语句为
if ((fp=fopen(“f1.c”,“r+w”))==NULL)
{
printf(“Can?t open this file.\n”);
exit(1);
}
其中的 fp是已经定义好的文件指针。
1.2 关闭文件的函数为 fclose(文件指针 );
这个函数在正常情况下返回值为 0，关闭有错时返
回非 0值，可用 ferror()函数来检查。
39
2、文件的读和写
#include <stdio.h>
char s[]=“I am a student”;
void main()
{
char a[100]; // 定义 a字符串
FILE *fp; // 定义文件指针为 fp
int n=strlen(s); // 字符串 s的长度
// 打开 f1.txt文件，写方式,fp不为空
if ((fp=fopen(“f1.txt”,”w”))!=NULL)
{
// 将 s所指的字符串写到 fp所指的文件中
fputs(s,fp);
}
fclose(fp);
40
// 打开 f1.txt文件，读，文件指针为 fp
fp = fopen(“f1.txt”,”r”);
// 将 fp所指的文件中的内容读到 a中去
fgets(a,n+1,fp);
printf(“%s\n”,a); // 输出 a中的内容
fclose(fp); // 关闭 fp所指向的文件
} // 主函数结束
说明,
1、要进行文件读写操作先要定义文件指针。
使用 FILE *fp，（ fp可以是其它名称）
2、测出 s字符串长度，使用 int n=strlen(s);
41
3、打开,f1.txt”，,w”，要往 f1.txt中写入。如空则自
动建立一个文件，自然不会空了。
4,fputs(s,fp)是说将 s字符串写入由指针 fp所指向的
f1.txt文件中。
5,fclose(fp)，将 fp所指向的 f1.txt文件关闭。
6、打开 f1.txt 用读的方式
fp=fopen(“f1.txt”,“r”);
7、将读出的字符串放入 a串中，在使用 fgets()函数时用
fgets(a,n+1,fp);其中 a是已经定义好的字符串,n+1是
让 fp所向的文件内容，依次取 n个字符给 a，这 n个字
符恰为 s串的内容，之后还要在该串后自动加入一
个 ?\0?字符。因此要写 n+1。
42
结 束
