数据结构实验报告——查找与排序

哈尔滨工业大学(深圳)

数据结构实验报告

查找与排序

学 院: 计算机科学与技术

姓 名: 学 号: 专 业: 日 期:

数据结构实验报告

一、问题分析

此题是一道排序问题，排序的方法有很多种，此题我用的是堆排序，这是一种不稳定排序，但时间复杂度较低，比较快。计算机首先需要把文件中的数据读入内存中，用动态数组存储数据，然后建立数据结构，然后建立堆，比较子节点和父节点大小，降序排列，之后互换头结点与尾节点，再递归重复即可。查找的话，依次查找对比即可。

二、详细设计

2.1 设计思想

将股票的代码，交易日期，及开盘价等信息分别用不同的动态数组存储起来。因为要根据交易量的降序进行排序所以应将交易量的信息另外用一个float型的数组保存起来便于比较。

排序：使用一个下标数组用来模拟交易量的堆排序，将下标数组进行降序排序。再根据下标数组里的值将股票信息保存在新的文件中。

查看：因为录入文件时是先把股票的代码相同的信息存入数组的。所以查找时比较股票的代码，找到该代码后比较交易日期。最后输出交易量。

2.2 存储结构及操作

(1) 存储结构（一般为自定义的数据类型，比如单链表，栈等。） vector a;//股票代码 vector b;//股票交易日期

vector c;//股票开盘价_最高价_最低价_收盘价

1

数据结构实验报告

vector d;//将交易量转换为float用于比较 不过有的会被舍去 vector e;//交易量的原始数据 用于输出到排序的文件中 (2) 涉及的操作（一般为自定义函数，可不写过程，但要注明该函数的含义。） read_file() 将文件信息分别保存在上述存储结构中

HeapAdjust(vector& x,long s,long n) 小顶堆的调整函数 HeapSort() 用堆排序进行交易量的降序排序并存储在指定文件中 serach() 查找某交易日期某股票的交易量

2.3 程序整体流程

A 开始 读入文件，存入数组 B 排序 C 查找 D 结束

E

2

数据结构实验报告

2. 堆排序示意图（由于堆排序描述时需要具体数据，所以只弄到示意图）

三、用户手册

1>将股票文件先存入指定文件夹中，根据提示输入文件名字按回车即可 2>先在指定文件夹新建你要保存的文件后将文件的名字输入 3>根据提示输入股票代码及交易日期，以空格隔开。

四、总结

需要说明一下的是，这次实验我写的是c++代码。为什么用c++代码呢，主要是因为是最后一次实验了，需要有些纪念意义，更重要的是，c++代码比c代码简洁有效许多，我的电脑并不是很好，所以就选择了更快更简洁的c++代码。其实真正的原因是时间不够了，c++代码写的比较快，而且大一时写过类似的东西刚好用得上。最后一次了，希望助教大人高抬贵手，通融一二，在下不胜感激。

3

数据结构实验报告

五、结果

程序正确运行的结果截图。

注：abc.txt即原文件 a. txt为新建文件

源代码：#include #include #include #include #include #include #include using namespace std;

4

数据结构实验报告

vectora; //股票代码 vectorb; //股票交易日期 vectorc;

//股票开盘价_最高价_最低价_收盘价 vectord;

//将交易量转换为float用于比较不过有的会被舍去 vectore;

//交易量的原始数据用于输出到排序的文件中 void HeapAdjust(vector&x,long s,long n){ long x1=x[s]; float x2=d[x[s]];

for(long j=2*s;j<=n;j*=2){

if(jx[s]=x[j];//将子节点上调为父节点 s=j;//进入下一深度节点的判断 }

x[s]=x1;

5

数据结构实验报告

}

bool HeapSort(){

fstream file;//文件变量

vector x;//存储下标

string name;

cout<<\"输入要存的文件名\"<cin>>name;

file.open(name.c_str());

if(!file){

cout<<\"不能打开指定文件\"<return false; } else{

time_t start=clock(); //开始计时

long n=d.size();

x.push_back(1);//x[0]不能用来建堆

for(long i=0;i0;--i){

HeapAdjust(x,i,n);//建堆

}

for(long i=n;i>1;--i){

6

数据结构实验报告

swap(x[1],x[i]); //把最小的放在最后面

HeapAdjust(x,1,i-1); //调整头结点 }

for(long i=1;ifile<time_t end=clock(); cout<<\"

堆

排

序

时

间

为

\"<return true; } }

bool serach(){ string data,code;

cout<<\"输入要查看的股票代码及交易日期\"<>code>>data; time_t start=clock(); long number=a.size(); for(long i=0;ifor(long j=i;jtime_t end=clock();

7

数据结构实验报告

cout<<\"你选择的股票当前日期交易量为\"<}

return true; }

}

return false; }

bool read_file(){

int flag=0; //读到第几个数据的标记 string filename; char dean[100]; fstream file; string x;

cout<<\"输入文件名\"<>filename;

file.open(filename.c_str()); if(!file){

cout<<\"不能打开指定文件\"<return false;

8

数据结构实验报告

} else{

time_t start=clock();

while(1){

file.getline(dean,100,'_'); string shuju(dean);

flag++;

switch(flag){ case 1:

a.push_back(shuju);

break; //股票代码

case 2:

b.push_back(shuju);

break; //股票交易日期

case 3:

x.clear();

shuju+='_';

x+=shuju;

break;

case 4:

shuju+='_';

9

数据结构实验报告

x+=shuju; break;

case 5:

shuju+='_';

x+=shuju; break;

case 6:

shuju+='_';

x+=shuju; c.push_back(x);

break;//股票其他信息

case 7:

d.push_back(atof(shuju.c_str()));//把交易量转为float

e.push_back(shuju);

file.getline(dean,100);//将交易量后面的数据扔掉

if(file.peek()==EOF){//判断是否到达文件末尾

time_t end=clock(); cout<<\"

读

文

件

用

了

\"<return true; }

10

数据结构实验报告

flag=0; break;//为读下一行做准备 } }

}

}

int main(){

read_file(); HeapSort(); serach(); }

11