实验六 动态组织数据.doc

实验六 动态组织数据一、目的和要求1. 掌握动态组织数据的概念；2. 掌握动态申请存储空间的相关函数的使用；3. 掌握动态数组的建立方法；4. 掌握动态链表的基本操作；5. 进一步掌握文件的操作。二、重点与难点重点：动态申请存储空间，动态数组的建立，建立有序的动态链表，文件的操作。难点：建立有序的动态链表。三、实验内容1. 编写一个程序，将二制文件“student.dat”中的数据，按成绩从高到低排序并输出。其中，文件中的数据包含了众多学生的信息，包括：学号、姓名、成绩。其结构如下：struct studentchar id11;char name21;int score;在做实验时需要事先生成包含学生成绩的二进制文件，可以单独编写相应的程序，要求输出排序后的数据有如下形式：id name score2013011001Wangxiaotang952013011030FangMin702013011101Zuzhong85本实验要点：（1）问题分析：本实验涉及两个关键问题：一是二制数据的读入；二是数据排序。从文件中读入结构化的二进制数据，可以使用fread()函数。对数据排序，可以将所有数据存储在数组中，并采用熟悉的算法排序。但这里的关键的问题是：之前不知道文件中的数据个数，因此无法确定数组的大小。此处采用动态分配空间的方式使用动态数组。但还是需要计算文件中数据的个数。这里可采用两种方法来统计个数：方法一是先将所有数据读出，以统计出个数；方法二是利用函数fseek()和ftell()计算出个数。（2）实现要点二进制文件数据的读写与处理先以二进制文件读方式 “rb”打开文件。由于需要知道记录的个数并申请动态数组空间， 可以采用以下两中方法：方法一：循环中用fread()读出每一条记录统计人数，再根据人数精确地分配存储数据的存储空间，然后使用rewind()函数将文件指针移到文件首，再次读出数据放入动态分配的存储空间内。最后对这些读出的数据进行处理。方法二：先使用fseek()控制文件指针到文件尾，再利用ftell()获得相对于文件开关的字节数，然后通过计算获得文件内存储的人数，然后使用rewind()函数将文件指针移到文件首，再次读出数据放入动态分配的存储空间内。最后对这些读出的数据进行处理。排序函数的定义、参数传递、调用。可定义函数 void sort(struct student *p , int n),实现以p为首地址的连续n条记录（结构体变量），按结构分量score排序。在主函数中，调用sort(p,n),将存储空间首地址实参p和人数n传给对应的形参。基本算法描述开始定义变量，函数声明以”rb” 方式打开文件student.dat统计人数送变量n用malloc()分配n个长度为sizeof(struct student)的连续存储空间，首地址送入指针变量p将文件指针移到文件首读出n位学生数据到以p为首地址的存储空间关闭文件调用sort()函数对 p所指的存储空间内的数据进行排序循环输出p0-至pn-1中的数据结束（3）实验参考程序#include #include #include typedef struct studentchar id11;char name12;int score;STU;void main() STU st,*p;FILE *fp;int i,n=0;void sort(STU *p , int n);void input();input();if(fp = fopen(student.dat,rb)=NULL)printf(Cant open file!n);exit(0);/读出数据统计人数while(!feof(fp) fread(&st,sizeof(STU),1,fp);n+;n-; /c程序自动将最后一个学生的数据重复读出一次p= (STU *)malloc(n*sizeof(STU); /根据读到的人数动态分配存储单元rewind(fp);fread(p,sizeof(STU),n,fp); / 将n个学生数据存储在以p为首地址的存储单元fclose(fp);sort(p,n);printf(%6s%13s%15sn,id,name,socre);for(i=0;in;i+)printf(% -12s% -20s%dn,pi.id,,pi.score);void sort(STU *p , int n)int i,j;STU stu;for(i=1;in;i+)for(j=0; jpj+1.score )stu = pj;pj = pj+1;pj+1 = stu;方法二的程序片断为（将方法一中黄色底纹替换为以下程序段）fseek(fp,0l,2);n=ftell(fp)/sizeof(stu);2. 要求从文件读出的数据采用链表存储数据，并将sort()函数改为链表插入函数insert(),且从文件中只读出一遍数据，编写相应的程序。（1）实现要点 数据类型的定义 要分别定义两个类型：学生数据类型和链表结点类型。 二进制文件数据的读写与处理先以二进制文件读方式 “rb”打开文件。由于采用链表，所以不需要确定学生数据的个数。排序函数的定义、参数传递、调用。可定义函数 NODE *insert(NODE *head, NODE *p),实现将结点p插入到头指为head所指的链表中，成为有序的链表。基本算法描述N开始定义变量，函数声明以”rb” 方式打开文件student.dat将stu的值赋给p的data成员，p-next=NULL用malloc()分配长度为sizeof(NODE)的空间，首地址送入指针变量p读出一个学生数据到stu中关闭文件调用insert()将 p结点插入到链表中，插入结点后链表仍有序循环输出链表中的数据结束数据文件结束?参考程序：#include #include #include /定义文件中每个学生的数据类型typedef struct studentchar id11;char name12;int score;STU;/定义链表结点类型typedef struct nodeSTU data;node *next;NODE;void main() STU stu;NODE *p,*head=NULL;FILE *fp;NODE *insert(NODE *head , NODE *p);if(fp = fopen(student.dat,rb)=NULL)printf(Cant open file!n);exit(0);while(!feof(fp) p= (NODE *)malloc(sizeof(NODE); fread(&stu,sizeof(STU),1,fp); /从文件中读入一个学生数据p-data =stu; / 将学生数据作为结点的data成员p-next = NULL;head = insert(head,p); /将结点p插入到以head为头指针的链表中fclose(fp);printf(%6s%13s%15sn,id,name,socre);for(p=head; p!=NULL;p=p-next)printf(% -12s% -20s%dn,p-data.id,,p-data.score);NODE* insert(NODE *head, NODE *p)NODE *q1=head,*q2;if(head = NULL)/如果是空链表head=p;return head;/查找结点p的插入位置while(p-data.score q1-data.score & q1-next !=NULL)q2=q1;q1=q1-nex