数据结构实训指导-修改3

1、数据结构实训指导教学目的：数据结构实训课是该课程实践能力提高的课程， 希望通过该实训课程的教学实践，使学牛能进一步提高算法 设计（程序设计）以及相关数据结构及其操作的应用能力。 教学实施：本课程由教师确定实习题供学生选择，并由教师 对各实习题进行必要的分析、设计思路讲解，在此基础上， 以学生上机完成程序。学生需要补习c语言的文件操作相关知识。考核方式：该课程为考查课，其学生的成绩评定以其各个实 习题的成绩综合评定。实习选题：实训题一：设计一个程序，完成以下功能：1）建立学生信息管理的数据文件stud.dat;文件中至少包含 15个学生的信息；每个学生至少包括：学号、姓名、年龄等 5项内容（另2

2、项自泄），当再次运行程序时从该文件中读取 数据；2）可以添加（插入、追加）学生信息；3）可以修改某个学生的某项信息。要求：请同学们参考c语言程序设计教材中关于文件操作的 内容和示例，掌握c语言程序对文件的操作。考虑到学生关于文件操作不太熟悉，本实习题的完成时间分 配10-12课时。实习题二：设计一个程序，完成如下功能：从一个c语言源程序文件中，统计出该c程序中使用的关键 字及其频率。统计结果表格保存到文件中。提示：可以预先建立一个c语言的保留字表，利用该表对c 语言源程序进行字符串匹配。实习题三：(1)设线性表a=(al,a2,am),b=(bl,b2,.bn),试写一个按如下规则合并a,b为

3、线性表c 的算法，使得c=(al,b2,am,bm,bm+l,bn)当m<=n 时或 c=(al,bl,an,bn,an+l,am)当m>n时线性表均为单链表作存储结构，且c表利用a表和b 表中的结点空间构成、数据存储到文件lnklist.txt中。实习题三(2)编写程序，求出指定结点在给定二叉排序树中所在的层数。实习题三(3)编写程序判别给定二叉树是否为二叉排序树。设此二叉树以 二叉链表作存储结构，且树中结点的关键字均不同。要求(2)(3)的二叉树的数据以某种方式存储到文件 中，以便程序运行时读取数据创建二叉树。请选做其一。实习题四(1)为(实习题一)学生信息管理的数据文件中的数

4、据，建立一 个索引：每个学生信息记录在索引中有一个索引项，其包含 该学生的学号、记录的位置（即记录在文件中的序号）；索 引文件采用平衡二叉（avl）树。程序应能根据输入的学号 通过索引进行查找；并且，你所建立的索引需要保存到文件 屮，以便重复使用。实习题四（2）校园导游程序。用无向网表示你所在学校的校园景点平面 图，图中顶点表示主要景点，存放景点的编号、名称、简介 等信息，图中的边表示景点间的通路，存放路径长度等信息。 要求实现以下功能：（1）查询各景点的相关信息；（2）查询图屮任意两个景点间的最短路径；（3）查询图中任意两个景点间的所有路径。实习题四（3）创建有向网的存储结构，并对某有向网（

5、不少于15个顶点） 进行拓扑排序，将拓扑结果排序存储到文件中。请选做其一。下列题目供有能力的同学选做实习题五（1）偶交换排序如下所述：第一趟对所有奇数i,将ai和 ai+l进行比较；第二趟对所有偶数i,将ai和ai+l进行比 较，若ai和i+l,则将两者交换；第一趟对所有奇数i, 第二趟对所有偶数i,以此类推直至整个序列有序为止。请 编写算法实现之。（2）实现链式基数排序算法。并根据同一批数据（不少于500个、存储在文件种）的排序, 通过程序排序所需时间来简单分析比较上述2种算法的性能 差异。提示：链式基数排序要求所有关键码的长度相同。附录：关于文件操作c语言的文件操作主要有三个步骤：（-）打

6、开文件打开文件使用函数fopen（“文件名”，”方式”）；其中，”文件名”可以是字符串变量表示，它告诉系统要打开 的文件的文件名，一般应为文件全名。“方式”为打开该文件欲进行什么操作，如“读” /r,或者“写” /w等。该函数执行后返回所打开文件缓冲区指针。所以，一般需要: 先定义一个文件类型的指针，如：file *fp;然后，fp=fopen（“d:mydata.dat”,"w”）；若打开不成功，则指针值为null。（二）文件读写读/写文件主要有如下几组函数：（1 ） fprintf（fp,格式描述串”,v输出列表）;-写数据到文件fscanf(fpj格式描述串二v变量列表-从文件

7、读数据(2 )fwrite("数据缓冲区地址，丁，记录字节数，丫'记录数”,fp);-写记录数据到文件(二进制)fread("数据缓冲区地址罗记录字节数罗记录数”,fp);-从 二进制文件中读数据(3 )fputc();和 fgetc();读/写数据为字符类型。当把文件中的数据读到内存后，可以对其中的数据进行所需 要的操作(如通过赋值语句等对先观数据进行修改等)。这 阶段看作是对文件数据进行实质性操作的阶段。(三)关闭文件关闭文件用函数：close(fp);其中，fp为你所要关闭的文件指针，当一个程序中对多个文 件进行操作时，特别注意不要关闭不希望关闭的文件。此外，

8、数据存储到文件中时，数据的存储格式也有不同，即 通常所说的“文本文件"和“二进制文件”。下面给出一些示例：例一. 将0-14这15个整数存入文件stud2.dat#include <stdio.h> #define max 15/*以文本方式存储15个整数勺void save_dat()file *fp;inti;if(fp=fopen(nd:stud3.dat，v，wn)=null) printf(hcannot open filenn);/*打开d盘根目录下的文件stud2.dat,注意：因为是(2的转 义字符，所以需要再加一个。我在实验时，只有一个斜杠 window

9、s2000能正确但在windows xp下就发现不能正确了 */ return;for(i=0;i<max;i+)fprintf(fp,n%dn,i);printf(ndata have been saved to a filenn);fclose(fp);main()save_dat();当用记事本打开数据文件stud2.dat,可以看到0-14这15个 数以字符(文本)格式存储在文件中，并且，这15个数据 是紧挨着存储的-当再用fscanf(“ct,&i)从该文件中读取这 些数据时、将不能正确读取、故需要注意数据存储格式。- 可以修改fprintf()为：for(i=0;i&

10、lt;max;i+)fprintf(fp,n%6dn,i);这样，每个整数占6位宽度，存储时各数据之间就留有空格, 再用fscanf(“)读取时，每个空格将成为数据的分界 符；但是，如果将fscanf(“d，',&i)修改为fscanf(“d,",&i) /* 多一个逗号 */那么，在读取数据时，将按格式描述串中约定的逗号作各个 数据之间的分隔符，此时，需要将存储文件是的fprintf()对 应地修改为：for(i=0;i<max;i+)fprintf(fp/%d/,i);用该语句存储数据的结果(从记事本打开看)，可以看到每 个数据之间也存储了逗号(最后

11、一个数据之后也有逗号)。 当然，这15个整数也可以以二进制格式存储到文件中，如 下程序即是：#include <stdio.h>#define max 15/*用二进制方式存储0-14*/void save_dat()file *fp;inti;if(fp=fopen(nd:stud4.dath,nwbn)=null) printf(hcannot open filenn);return;for(i=0;i<max;i+)fwrite (&i,sizeof(int),l ,fp);printf(ndata have been saved to a file nn);f

12、close(fp);main()save_dat();运行该程序并用记事本打开文件stud3.dat,所看到的数据就 不再是ascii码格式，而是以整数的内码(二进制补码)存 储的了。因此，也只能采用对应的语句(fread )读取数据。 例二.存储记录(结构体)数据以下程序是定义了学生信息结构体，然后输入4个学生信息、 存入文件d:studl.dat#include <stdio.h>#define size 4/*建立学生信息-结构体-数据文件*/struct stud_type char name10;int num,age;char addr15;studsize;void

13、save_dat()file *fp;inti; if(fp=fopencd:studldar,”wb”)=null) printf(ncannot open filenn);return;for(i=0;i<size;i+)if(fwrite(&studi,sizeof(struct stud_type),l ,fp)!=l) printf(nfile write error!nn);printf(hdata have been saved to a file nn); fclose(fp);main()int i;printf(nplease enter the studen

14、t information:nh);for(i=0;i<size;i+)scanf(n%s%d%d%sn,,&studi.nu m，& studi.age,st udi.addr);save_dat();用记事本打开数据文件studl.dat,看到学生信息中的姓名、 地址这两个字符串数据是按sacii码存储的，但学号和年龄(数值)却是按内码存储的。对应的读取该数据文件中数据 的程序如下：#include <stdio.h>#define size 4/*从记录数据文件中读取学生信息数据*/struct stud_type char name

15、10;int num,age;char addr15;studsize;main()inti;file *fp;fp=fopen(nd:studl.dat，7，rbn);if(fp=null) printf(nfile open error!nh);retum; for(i=0;i<size;i+) fread(&studi ,sizeof(struct stud_type)丄fp);printf(n%-10s%4d%4d%-15snn,,studi.num,studfi.age,studi.addr);fclose(fp);可以验证，存入的数据被正确地读取、

16、显示。当然，也可以将结构体(记录)采用文本格式存储到文件中，看入下程序:#include <stdio.h>#define size 4/*建立学生信息-结构体-数据文件，用文本格式存储*/struct stud_type char name10;int num,age;char addr15;studsizej;void save_dat()file *fp;inti;if(fp=fopen(nd:stud2.dat,nwn)=null) printf(ncannot open filenn);return;for(i=0;i<size;i+)fprintf(fp,h%-1

17、0s%5d%3d%-15sn,stud|,studi.num,stud i. age,studi .addr);printf(ndata have been saved to a file nn);fclose(fp);main()int i;printf(nplease enter the student information:nn);for(i=0;i<size;i+)scanf(n%s%d%d%sn,,&studi.nu m,&studi.age,st udi.addr);save_dat();用记事本打开文件stud3.dat,可

18、以看到，记录(结构体)中 的数值数据也以sacii码存储的(注意比较数据文件 studl.dat和stud3.dat在记事本中的显示区别)。更多的知识和示例，可以参考c程序设计教程。3.其他相关知识1）用户程序的文件读写，实际上是在文件缓冲区中进行, 系统自动为文件的读写设置一个文件指针，每从文件中读、 写一个数据单位（如文本文件则以字节为单位、如果是记录 文件则以结构体大小为单位）,指针自动移动一个数据单位。 所以，c还提供了函数rewind。、fseek（）和ftell（）,主要用来 定位指针。当用户程序对文件进行写操作时，数据并非立即写入磁盘 文件，而是暂存于缓冲区中，当缓冲区满或执行关闭文件操 作时，系统才将缓冲区中的数据写入文件。这就说明程序在 文件操作结束使用关闭文件语句关闭的重要性。2）对于非流式文件（如文本文件、缓冲文件系统），如果 要修改文件中某些数据（并写入文件），通常采用复制的方 法（复制完成后再将原文件删除并将复制的文件改名），因 为，这类文件是顺序文件。3）部分目录操作函数参考cddir（char *