数据结构与算法课内实验实验报告.doc

数据结构与算法课内实验实验报告 实验报告 一、实验任务 实验题目：数据结构与算法课内实验二、实验内容实验背景：利用数据结构的知识分析鼠标操作者的鼠标行为，评价鼠标的操作效率，比如最大移动速度、平均移动速度等。实验一 文件读取和数据处理（一）实验目的：综合运用数据结构所学知识，掌握抽象数据类型的定义方法以及文件操作。（二）基本要求：读取文本文件数据，自定义合适的抽象数据类型按照要求存储数据，并实现下述要求。（三）内容提要：1、数据采集本次实验，每位同学对自己采集到的数据进行处理。数据采集的要求如下：1）采集时间：（1）11.1511.16（数据结构专题实验第4次实验）； （2）11.24（第11周周末）； （3）第5次数据结构专题实验时间； （4）课内实验验收时间待定2）采集地点：西一楼307；3）采集时长：每位同学510分钟；4）采集内容：每位同学认真完成指定的鼠标操作，包括鼠标的移动、鼠标单击和鼠标双击（见下述提示1）。2、数据处理采集到的数据会以文本的形式保存，一个文本文件称为一个样本。每位同学需要m个样本完成实验。读取文本文件并对数据进行如下操作：1） 自定义合适的数据结构类型保存读取到的数据，以方便后续的数据处理（原始数据格式见下述提示）；2） 对一个样本中的数据按照鼠标操作的事件类型（单击和双击）进行切分，一个样本中的数据可以切分为16段（鼠标事件类型的定义见下述提示）；3） 对于每段数据，如果出现时间戳重复的点，保留第一个点，删掉后面的重复点；4） 删除掉时间戳重复的点之后，对于每段数据进行如下计算：（1）移动持续时间、（2）移动速度序列、（3）移动加速度序列、（4）平均速度（计算方法见下述提示），自定义一个合适的数据结构类型保存上述4种数据，以方便后续的数据处理。比如定义一个结构体，那么结构体中包含4项分别对应上述计算的4种类型的数据。实验二 数据排序和查找（一）实验目的：综合运用数据结构所学知识，掌握抽象数据类型的定义方法，熟悉并熟练运用查找、排序算法以及文件操作。（二）基本要求：自定义合适的抽象数据类型存储数据，并实现下述要求的查找和排序功能。（三）内容提要：1、数据处理1） 数据处理的过程在第一次实验数据处理的基础上继续进行；经过实验一中1）4）数据处理之后，对于每个样本，数据被分为16段，每段数据有一个数据结构实体存储本段的段ID和4）中计算得到的4个变量：（1）移动持续时间、（2）移动速度序列、（3）移动加速度序列、（4）平均速度。2） 对于每段移动，计算平均速度在m个样本上的速度平均值，16段移动可以得到16个速度平均值，对这16个速度平均值进行排序，给出最大和最小速度对应的段ID和平均速度。3） 对于每段移动，计算移动持续时间在m个样本上的移动持续时间平均值，16段移动可以得到16个移动持续时间平均值，对这16个移动持续时间平均值进行排序，给出最长和最短移动持续时间对应的段ID和移动持续时间。实验提示1. 鼠标操作示意图16段移动，其中，前8段移动以鼠标单击为分割点，后8段移动以鼠标双击为分割点。fig1鼠标操作示意图2. 原始鼠标数据格式文本文件中的数据分多行保存，每一行的数据有4个维度，数据格式为（鼠标操作类型、x坐标、y坐标、时间戳）table1 鼠标操作类型鼠标操作类型数值（十进制）初始状态512移动或静止512左键按下513左键放开514eg：鼠标操作类型 x坐标 y坐标 时间戳512, 570,372,5724860 移动起始点. . . . 移动持续中512, 575,372,5724884 移动终止点513, 576,372,5724796 分割点512, 576,372,5724818 点击时间间隔514, 576,372,5724884 分割点3. 第i点速度计算：如果x轴速度大于y轴速度，那么第i点的速度等于x轴速度；如果y轴速度大于x轴速度，那么第i点的速度等于y轴速度。对于每段第一个点，当i=1的时候，i-1等于0，所以第一点的速度记为0。4. 第i点加速度计算：对于每段第一个点当i=1的时候，i-1等于0，所以第一个点的加速度记为0。5. 移动持续时间： 对于每段移动，移动结束点的时间戳减去移动起始点的时间戳。6. 平均速度每一段的平均速度等于该段每一点的速度值之和与该段总点数的比值。三、要点分析题目中涉及的主要知识点：1、 抽象数据结构类型的定义及使用。分别定义了四个数据结构类型struct Record（每条记录的存储结构）、struct Sample （每个样本（文件）的存储结构）struct Data（读取原始数据时的中间存储结构）struct Result （统计结果的存储结构）。2、 文件的基本操作。文件的打开及读取数据，写入数据等。3、 排序算法。对得到的结果进行排序，得到最大最小值。4、 建立哈希函数进行查找操作。四、程序的算法描述1、所用存储结构：typedef struct Record /每条记录的存储结构int ID; /记录的ID号int interval; /每段记录的移动时间float v100; /每段记录的速度序列float a100; /每段记录的加速度序列float average; /每段的平均速度Record;typedef struct Sample /每个样本（文件）的存储结构char filename40; /文件名Record record16; /文件中的十六段记录Sample;typedef struct Data /读取原始数据时的中间存储结构int x; /x坐标int y; /y坐标int time; /时间戳int type; /操作类型Data;typedef struct Result /统计结果的存储结构int ID; /每段的IDfloat average_v; /每段在m个文件上的平均速度int average_interval;/每段在m个文件上的平均移动时间Result;2、 程序中各函数的简要说明：（1）void statistic(Sample *sample,int m)统计函数，将m个文件的原始数据读入并进行初步处理。借助于data0、data1俩个数据交替读入文件内容，根据数据的操作类型执行不同的操作。若是512，则进行速度、加速度的计算及移动时间的累加；若是513、514，则进行数据的切分。在对数据进行统计的同时，将统计结果写入文件“log1.txt”中。(2)void analyse(Result result16,Sample *sample,int m)分析函数。求出各项数据在m个文件上的平均值，并利用冒泡法进行排序，将排序结果结最大最小值写入文件“log2.txt”中。(3)int main()主函数：调用statistic(sample,m);analyse(result,sample,m);统计数据并实现查询功能。由输入要查找的ID号，用哈希函数计算的相应的存储地址，得到查询结果。3、源代码完整程序及相应说明如下：#include stdio.h#include stdlib.h#include malloc.h#include math.h#include string.htypedef struct Record /每条记录的存储结构int ID; /记录的ID号int interval; /每段记录的移动时间float v100; /每段记录的速度序列float a100; /每段记录的加速度序列float average; /每段的平均速度Record;typedef struct Sample /每个样本（文件）的存储结构char filename40; /文件名Record record16; /文件中的十六段记录Sample;typedef struct Data /读取原始数据时的中间存储结构int x; /x坐标int y; /y坐标int time; /时间戳int type; /操作类型Data;typedef struct Result /统计结果的存储结构int ID; /每段的IDfloat average_v; /每段在m个文件上的平均速度int average_interval;/每段在m个文件上的平均移动时间Result;void statistic(Sample *sample,int m)/统计函数，将m个文件的原始数据读入并进行初步处理FILE *fp;FILE *fpp;if(fpp=fopen(log1.txt,w)=NULL)printf(无法打开文件);return;int i,j,k=0;Data data2;/俩个原始数据单元，交替读入数据for(i=0;im;i+)while(fp=fopen(samplei.filename,r)=NULL)/打开文件，若文件无法打开，重新输入printf(无法打开第%d个文件,请重新输入n,i+1);scanf(%s,samplei.filename);fprintf(fpp,第%d个文件的文件名：%sn,i+1,samplei.filename);fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);for(j=0;j16;j+)float sum=0;int count=0;for(k=0;kabs(float(data0.y-data1.y)/float(data0.time-data1.time)samplei.recordj.vk=float(data0.x-data1.x)/float(data0.time-data1.time);samplei.recordj.ak=samplei.recordj.vk/(data1.time-data0.time);sum=sum+samplei.recordj.vk;k+;count+;elsesamplei.recordj.vk=(float(data0.y-data1.y)/float(data0.time-data1.time);samplei.recordj.ak=samplei.recordj.vk/(data1.time-data0.time);sum=sum+samplei.recordj.vk;k+;count+;data0=data1;erval=erval;samplei.recordj.average=sum/float(count);fprintf(fpp,第%d个样本的第%d个记录的ID：%dn,i+1,j+1,samplei.recordj.ID);/将处理结果写入文件中fprintf(fpp,第%d个样本的第%d个记录的移动持续时间：%dn,i+1,j+1,erval);fprintf(fpp,第%d个样本的第%d个记录的平均速度：%fn,i+1,j+1,samplei.recordj.average);fprintf(fpp,第%d个样本的第%d个记录的速度及加速度序列：ntvttan,i+1,j+1);for(k=0;k100;k+)if(samplei.recordj.vk=300000000)break;fprintf(fpp,%9.6ft%9.6fn,samplei.recordj.vk,samplei.recordj.ak);if(data1.type=513)/对文件进行切分fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);while(data0.type=512)fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);if(data0.type=513)fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);while(data0.type=512)fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);fscanf(fp,%d %d %d %d,&data0.type,&data0.x,&data0.y,&data0.time);continue;fclose(fp);fclose(fpp);printf(原始数据读入成功,已存入log1.txtn);void analyse(Result result16,Sample *sample,int m)/分析函数。求出各项数据在m个文件上的平均值，并排序int i,j,k;int sum_time;float sum_v;Result temp;FILE *fpp;if(fpp=fopen(log2.txt,w)=NULL)printf(无法打开文件);return;for(j=0;j16;j+)/对16段上的数据在m个文件上求平均值sum_time=0;sum_v=0.0;for(i=0;im;i+)sum_time+=erval;sum_v+=samplei.recordj.average;resultj.ID=j+1;resultj.average_interval=sum_time/m;resultj.average_v=sum_v/float(m);fprintf(fpp,按移动时间由小到大排序：nID、移动时间、平均速度：n);for(i=0;i16;i+)/对16个数据用冒泡法按时间进行排序for(j=0;j15-i;j+)if(resultj.average_interval=resultj+1.average_interval)temp=resultj;resultj=resultj+1;resultj+1=temp;fprintf(fpp,%2dt%4dtt%9.6fn,result15-i.ID,result15-i.average_interval,result15-i.average_v);fprintf(fpp,最大移动时间段的信息：n%dt%dtt%9.6fn,result0.ID,result0.average_interval,result0.average_v);fprintf(fpp,最小移动时间段的信息：n%dt%dtt%9.6fnn,result15.ID,result15.average_interval,result15.average_v);fprintf(fpp,按平均速度由小到大排序：nID、移动时间、平均速度：n);for(i=0;i16;i+)/对16个数据用冒泡法按时间进行排序for(j=0;j15-i;j+)if(abs(resultj.average_v)=abs(resultj+1.average_v)temp=resultj;resultj=resultj+1;resultj+1=temp;fprintf(fpp,%2dt%4dtt%9.6fn,result15-i.ID,result15-i.average_interval,result15-i.average_v);fprintf(fpp,最大平均速度段的信息：n%dt%dtt%9.6fn,result0.ID,result0.average_interval,result0.average_v);fprintf(fpp,最小平均速度段的信息：n%dt%dtt%9.6fnn,result15.ID,result15.average_interval,result15.average_v);fclose(fpp);printf(数据分析完成,排序结果已存入log2.txtn);int main()/主函数：调用statistic(sample,m);analyse(result,sample,m);统计数据并实现查询功能int i,m,id,flag;char string4;Result result16;printf(请输入要分析的文件个数：);scanf(%d,&m);Sample *sample;sample=(Sample*)malloc(m*sizeof(Sample);/创建m个文件的存储空间for(i=0;im;i+)printf(请输入第%d个文件的文件名：,i+1);scanf(%s,samplei.filename);statistic(sample,m);analyse(result,sample,m);printf(是否要进行查找操作？YES or NO：);/实现查找功能scanf(%s,string);whil