13 二叉树的建立 循环链表 文件操作.ppt

第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函数的与或图

insert(proot, p) 可用下列与或结点图来描述：先判断根结点是否为空，为空则把 p 作为根；不为空则比较 p 结点数据与根结点数据的大小，分别递归插入左子树或右子树。

第6页：proot形参的含义

注意在上图中 proot 是被调用函数的形参。从前面对它的定义看，proot 是指针的指针，实际上是指向二叉树根结点的指针的指针，或者说是指向二叉树根结点的指针的地址，如下图。

因此，在主程序调用 insert 函数时，实参为 &root，形参为 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;};

第8页：insert函数的递归实现

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