数据结构实验报告4877

数据结构课内实验报告班级：学号：姓名：实验地点：实验验收日期：实验背景：利用数据结构的知识分析鼠标操作者的鼠标行为，评价鼠标的操作效率，比如最大移动速度、平均移动速度等。实验一文件读取和数据处理（一）实验目的：综合运用数据结构所学知识，掌握抽象数据类型的定义方法以及文件操作。（二）基本要求：读取文本文件数据，自定义合适的抽象数据类型按照要求存储数据，并实现下述要求。（三）内容提要：1、数据采集采集内容：包括鼠标的移动、鼠标单击和鼠标双击。2、数据处理采集到的数据会以文本的形式保存，一个文本文件称为一个样本。每位同学需要m个样本完成实验。读取文本文件并对数据进行如下操作：1）自定义合适的数据结构类型保存读取到的数据，以方便后续的数据处理（原始数据格式见下述提示）；2）对一个样本中的数据按照鼠标操作的事件类型（单击和双击）进行切分，一16段（鼠标事件类型的定义见下述提示）；3）对于每段数据，如保留第一个点，删掉后面的重复个样本中的数据可以切分为果出现时间戳重复的点，点；4）删除掉时间戳重复的间、（2）移动速度序列、（3）移动自定义一个合适的数据结构类型保存上述4种数据，体，那么结构体中包含4项分别对应上述计算的4种类点之后，对于每段数据进行如下计算：（1）移动持续时加速度序列、（4）平均速度（计算方法见下述提示），以方便后续的数据处理。比如定义一个结构型的数据。（四）要点分析：1.构造合适的数据类型。1)结点数据类类型应包括每个点的操作类型、x坐标、y坐标、时间戳。2)段的数据类型应包括每段的所有结点、结点数目、速度序列、加速度列、移动类型：一个样本包含十六个段。序时间、平均速度。3)样本数据2.存储。1)结点之间是线性关系，而结点数目又不确定，故宜采用且为便于计算每个点的速度，应采用双向链表。2)从文件中读入数据，每读一个，指针回溯查找时间戳重复的点，并删除之。链式结构存储，3.分段并计算每段的数据。1)识别每段的分界点。当出现操作类型为514的点且其后紧跟着的是类型为512的点，则标志着前一段的结束和下一段的开始。2)每一段结点链表的头指针头指向每段第一个类型为512的点，即514的下一个点。3)分段同时可计算移动时间和每段的结点数。从每段第一个结点即第一个512的点到出现第一个513类型的点之间的时间即移动时间。在遇到每段开始的标志时每读入一个结点，相应该段结点数目加一。4)计算每段的速度序列和加速度序列，根据速度序列计算平均速度。（五）解题步骤：1.认真分析题目，看清要求。2.构造合适的数据类型。3.从样本文件中读入数据并存储在构造好的数据结构中。4.实现分段、各段数据的计算。实验二数据排序和查找（一）实验目的：综合运用数据结构所学知识，掌握抽象数据类型的定义方法，熟悉并熟练运用查找、排序算法以及文件操作。（二）基本要求：自定义合适的抽象数据类型存储数据，并实现下述要求的查找和排序功能。（三）内容提要：1、数据处理1）数据处理的~4）数据处理之后，对于每个样本，数据实体存储本段的段ID和4）中计算得到的4个变量：（1）移动持续时间、（2）移动速度序列、（3）移动加速度序列、（4）平均速度。2）对于每段移动，计算平均速度在m个样本上的速度平均值，16段移动可以得给出最大和最小速度对应的过程在第一次实验数据处理的基础上继续进行；经过实验一中1）被分为16段，每段数据有一个数据结构到16个速度平均值，对这16个速度平均值进行排序，段ID和平均速度。3）对于每段移动，计算移动持续时间在m个样本上的移动持续时间平均值，16段移动可以得到16个移动持续时间平均值，对这16个移动持续时间平均值进行排序，给出最长和最短移动持续时间对应的段ID和移动持续时间。（四）要点分析1.构造每段在m个样本上的平均速度和平均移动时间的数据类型。应包括该段的平均速度或平均移动时间和段的ID。宜采用数组来存储。验一的基础上计算每段的平均速度和移动时间在m个样本上的平均3.利用选择法对16个平均速度和移动时间进行排序。2.在实值。4.排好序直接给出平均速度和移动时间的最值及所在段。程序的算法描述：（包括实验一和实验二）#include"stdafx.h"#include"stdio.h"#include"stdlib.h"#include"string.h"typedefstructnode{intoprtype;intx;inty;intmoment;structnode*next,*prior;}node,*nodelist;//结点的数据类型typedefstruct{nodelistclick;intnodenum;floatmovingtime;float*v;float*a;floataverv;}s,*section;//段的数据类型typedefsection*sample;//样本的数据类型typedefstruct{floatspaverv;intsctnum;}spav;typedefstruct{floatspavert;intsctnum;}spat;intmain(intargc,char*argv[]){sampleyangben;nodelistp;node*q=NULL,*r=NULL;FILE*fp;intm,i,j,t;charfilename[20];floatvx,vy,sumv=0,sumt=0;spavavv[16],kv;spatavt[16],kt;printf("请输入样本文件数:\n");scanf("%d",&m);yangben=(sample)malloc(m*sizeof(section));printf("请依次输入样本文件名:\n");for(i=0;i<m;i++){yangben[i]=(section)malloc(16*sizeof(s));printf("%d.",i+1);scanf("%s",filename);if((fp=fopen(filename,"r"))==NULL){printf("cannotopenthefile\n");exit(0);}for(j=0;j<16;j++)yangben[i][j].nodenum=0;yangben[i][0].click=(nodelist)malloc(sizeof(node));p=yangben[i][0].click;p->prior=NULL;while(!feof(fp)){fscanf(fp,"%d%d%d%ld",&(p->oprtype),&(p->x),&(p->y),&(p->moment));p->next=(node*)malloc(sizeof(node));p->next->prior=p;for(r=p->prior;r;r=r->prior)if(p->moment==r->moment){q=r;//删掉时间戳重复的点if(r->prior){r->prior->next=r->next;r->next->prior=r->prior;}else{r->next->prior=NULL;yangben[i][0].click=r->next;}r=r->next;free(q);}p=p->next;}p->prior->next=NULL;p=yangben[i][0].click;j=0;while(p)//分段并计算移动时间{yangben[i][j].nodenum++;if(p->prior&&p->oprtype==513&&p->prior->oprtype==512)//计算移动时间yangben[i][j].movingtime=p->prior->moment-yangben[i][j].click->moment;if(p->prior&&p->oprtype==512&&p->prior->oprtype==514)//如果遇到单击或双击则开始下一段{j++;yangben[i][j].click=p;yangben[i][j].nodenum++;yangben[i][j-1].nodenum--;}p=p->next;}for(j=0;j<16;j++)//计算每段的速度序列{yangben[i][j].v=(float*)malloc(yangben[i][j].nodenum*sizeof(float));yangben[i][j].v[0]=0;p=yangben[i][j].click->next;for(t=1;t<yangben[i][j].nodenum;t++){vx=(p->x-p->prior->x)/(double)(p->moment-p->prior->moment);vy=(p->y-p->prior->y)/(double)(p->moment-p->prior->moment);vx=(vx>0)?vx:-vx;vy=(vy>0)?vy:-vy;yangben[i][j].v[t]=(vx>vy)?vx:vy;p=p->next;}}for(j=0;j<16;j++)//计算每段的加速度序列{yangben[i][j].a=(float*)malloc(yangben[i][j].nodenum*sizeof(float));yangben[i][j].a[0]=0;p=yangben[i][j].click->next;for(t=1;t<yangben[i][j].nodenum;t++){yangben[i][j].a[t]=(yangben[i][j].v[t]-yangben[i][j].v[t-1])/(double)(p->moment-p->prior->moment);p=p->next;}}for(j=0;j<16;j++){sumv=0;//计算每段的平均速度for(t=0;t<yangben[i][j].nodenum;t++)sumv+=yangben[i][j].v[t];yangben[i][j].averv=sumv/yangben[i][j].nodenum;}}for(i=0;i<m;i++){printf("第%d个样本的数据：\n",i+1);for(j=0;j<16;j++){printf("第%d段：\n",j+1);p=yangben[i][j].click;for(t=0;t<yangben[i][j].nodenum;t++){printf("%d%d%d%ld%lf%lf\n",p->oprtype,p->x,p->y,p->moment,yangben[i][j].v[t],yangben[i][j].a[t]);p=p->next;}printf("该段移动时间：%f\n该段平均速度：%f\n",yangben[i][j].movingtime,yangben[i][j].averv);}}for(j=0;j<16;j++)//计算出每段平均速度和移动时间在m个样本上的平均值{avv[j].sctnum=j+1;avt[j].sctnum=j+1;sumv=0;sumt=0;for(i=0;i<m;i++){sumv+=yangben[i][j].averv;sumt+=yangben[i][j].movingtime;}avv[j].spaverv=sumv/m;avt[j].spavert=sumt/m;}for(j=0;j<15;j++)//选择法按递增排序每段平均速度和移动时间for(t=j+1;t<16;t++){if(avv[j].spaverv>avv[t].spaverv){kv=avv[t];avv[t]=avv[j];avv[j]=kv;}if(avt[j].spavert>avt[t].spavert){kt=avt[t];avt[t]=avt[j];avt[j]=kt;}}printf("按递增排好序的平均速度列：\n");for(j=0;j<16;j++)printf("第%d段：%f\n",avv[j].sctnum,avv[j].spaverv);printf("最大速度：%f所在段：%d\n最小速度：%f所在段：%d\n",avv[15].spaverv,avv[15].sctnum,avv[0].spaverv,avv[0].sctnum);printf("按递增排好序的移动时间列：\n");for(j=0;j<16;j++)printf("第%d段：