【数据结构】实验二：顺序表

实验二  顺序表

一、实验目的与要求

1）熟悉顺序表的类型定义；

2）熟悉顺序表的基本操作；

3）灵活应用顺序表解决具体应用问题。

二、实验内容

1）在一个整数序列a1,a2,…,an中，若存在一个数，大于它的整数数量和小于它的整数数量相等，则该数被称为“中间数”。请编写程序实现整数序列的“中间数”测试。具体样例：

/*样例输入  5    //包含5个整数的序列

3 4 6 6 7          //随机产生一个整数序列

则输出

-1               //输出-1表示整数序列“3 4 6 6 7”中不存在中间数

说明：

①在一个整数序列中，可能存在多个中间数。

②整数序列在程序中由随机数生成，程序输出“中间数”的值，若中间数不存在，则输出-1。

2）股票收益：假设你知道接下来n天的某只股票的价格序列a1,a2,…,an，请编写程序实现确定最优的买入时间和卖出时间以获得最大收益。股票价格数组在程序中由随机数组成，程序输出最终可以获得的最大收益和买入卖出时间，若无收益则输出0。

三、实验结果

1）简述算法步骤：

2）分析算法时间复杂度：

实验内容1：

 0）代码内容：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <time.h>
using namespace std;int main(){//初始化array int n;cout<<"请输入序列所包含的个数："; cin>>n;int arr[n];int i=0;
//	for(i=0;i<n;i++){
//		arr[i]=rand()%100;//假设随机生成为100以内的数字 
//	}
//	//check array
//	cout<<endl<<"随机生成的整数数组如下："<<endl; 
//	for(i=0;i<n;i++){
//		cout<<arr[i]<<endl;
//	}//srand优于rand随机生成？ int *p;srand(time(0));for(p=arr;p<(arr+n);p++){*p=rand()%100;//假设随机生成为100以内的数字 }//check arraycout<<endl<<"随机生成的整数数组如下："<<endl; for(p=arr;p<(arr+n);p++){cout<<*p<<" ";}//遍历寻找中间数int big,small,j;//big->比当前数大的个数，small->比当前数小的个数 int temp[n],cnt=0;//暂存中间数的数组 for(i=0;i<n;i++){big=0;//初始化big small=0;//初始化small for(j=0;j<n;j++){if(arr[i]>arr[j]){big++;}else if(arr[i]<arr[j]){small++;}}if(small==big){//符合中间数的要求->判断是否为重复元素 if(cnt==0){temp[cnt]=arr[i];//首个元素 cnt++;}else{int t=0,flag=1;for(t=0;t<cnt;t++){if(arr[i]==temp[t]){flag=0;//重复元素，不计入temp数组 break;}}if(flag==1){temp[cnt]=arr[i];//非重复元素，计入temp数组 cnt++;}}}} //	//check cnt
//	cout<<endl<<cnt<<endl;//输出中间数cout<<endl;if(cnt==0){cout<<-1<<endl;//中间数不存在 }else{cout<<"中间数如下："<<endl; for(i=0;i<cnt;i++){cout<<temp[i]<<endl;} }return 0;
}

1）简述算法步骤：

-->程序开始

-->利用srand函数随机生成数组元素

-->通过内外层循环遍历寻找中间数（以当前数为基准，遍历比较其他数字）

-->若序列有中间数，判断中间数是否重复（建立临时数组存放并比较）

-->输出序列中间数的情况（不存在中间数 / 所有的中间数）

-->程序结束

2）分析算法时间复杂度：

首先，我们在遍历寻找中间数的时候使用了内外层循环，即先通过外层循环假设arr数组中每一个元素均可以作为中间数进行遍历，再通过内层循环比较当前元素与其他剩余元素的大小，确定比当前元素大的个数及比当前元素小的个数，进而确定当前元素作为数组序列的中间数是否可行。所以，这段算法的时间复杂度为平方阶O(n²)。

其次，我们在判断所有中间数是否有重复情况时，建立了临时数组存放既往已经判断过的可行且不重复元素。那么，我们在下一次遇到可行的中间数元素的时候，在temp数组里面遍历与已经存入的中间数元素进行比较，确定当前元素的重复性。所以，这段算法的时间复杂度为线性阶O(n)。

3）程序运行结果示例：

 

 实验内容2：

0）代码内容：

 #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <time.h>
using namespace std;int main(){cout<<"请输入某只股票的价格序列的模拟天数：";int n,i,j;cin>>n; //随机生成价格 int price[n-1];//n天的价格 天数为i+1 int *p;srand(time(0));for(p=price;p<(price+n);p++){*p=rand()%100;//假设随机生成为100以内的数字 }//check price[]cout<<endl<<"随机生成的价格数组如下："<<endl; for(p=price;p<(price+n);p++){cout<<*p<<" ";}cout<<endl;int cnt=0,myday[n-1],money[n-1],maxday=0;for(i=0;i<n-1;i++){maxday=i+1;//从当前开始计算利润 for(j=i+1;j<=n-1;j++){if(price[j]-price[i]>price[maxday]-price[i]){maxday=j;}}myday[cnt]=maxday;money[cnt]=price[maxday]-price[i];cnt++;}//	//check myday and money
//	for(i=0;i<cnt;i++){
//		cout<<myday[i]+1<<","<<money[i]<<endl;
//	}//最优买入时间int best=0; for(i=1;i<cnt;i++){if(money[i]>money[best]){best=i;}} //cout<<best<<endl;//输出最大收益、买入卖出时间if(money[best]<0){cout<<0<<endl;//no benefit} else{cout<<"最大收益为："<<money[best]<<endl;cout<<"买入时间为：第"<<best+1<<"天"<<endl;cout<<"卖出时间为：第"<<myday[best]+1<<"天"<<endl;}return 0; 
}

1）简述算法步骤：

-->程序开始

-->利用srand函数随机生成数组元素，作为接下来几天该只股票的价格

-->通过内外层循环遍历寻找当前天数时买入后可获得的最优价格及卖出天数（以当前天数的价格为基准，遍历后续几天的价格并作差比较）

-->通过循环遍历并比较每个天数买入后的最优价格，获取最优买入时间

-->输出序列的最大收益、买入时间、卖出时间等情况

-->程序结束

2）分析算法时间复杂度：

首先，我们在遍历寻找当前天数时买入后可获得的最优价格及卖出天数的时候，使用了内外层循环。先通过外层循环确立当前天数并初始化下一次的天数的股票价格为最优卖出天数，再通过内层循环比较后面每一天与当前天数的股票价格差值，确定当前天数的最优价格和卖出天数，并分别存入money数组与myday数组之中。所以，这段算法的时间复杂度为平方阶O(n²)。

其次，我们在通过循环遍历并比较每个天数买入后的最优价格，获取最优买入时间的时候，是寻找一阶线性数组的最值的过程，即通过遍历money数组寻找最优解，并锁定myday数组里面的对应值。所以，这段算法的时间复杂度为线性阶O(n)。

3）程序运行结果示例：

 

 

 

---

其他参考代码：

#include <iostream>
#include <cmath>
using namespace std;
int n,i;
class Sqlist{public:Sqlist()//初始化顺序表{data= new int[n];length=0;}~Sqlist()//删除顺序表{delete [] data;}void getSqlist(int m)//创建顺序表{int max=10;int min=0;for(int i=0;i<m;i++){data[i]=rand()%(max-min+1);}}void seekmiddle()//寻找中间数并输出“中间数”的值，若中间数不存在，则输出-1。{int j=0;for(;j<n;j++)//外层循环，锁定一个被比较的数data[j]{int g=0,l=0;//定义较大数（greater）的个数、较小数（less）的个数；for(i=0;i<n;i++)//内层循环，依次比较除data[j]本身的其他的数。{if(i!=j){if(data[i]>data[j]) g++;if(data[i]<data[j]) l++;}}if(g==l)//如果较大数=较小数，输出中间数{cout<<data[j];break;}}if(j==n) cout<<-1;}void printlist()//打印顺序表{for(i=0;i<n;i++)cout<<data[i]<<' ';cout<<endl;}int getlength()//返回顺序表长度{return length;}bool isEmpty()//判断顺序表是否为空；若为空，返回0{if(length==0) return false;}private:int *data;//顺序表的元素int length;//顺序表的长度
};
int main()
{Sqlist list1;cin>>n;list1.getSqlist(n);//获得随机数列list1.printlist();//打印顺序表list1.seekmiddle();//寻找并输出中间数return 0;}

#include <iostream>
#include <cmath>
using namespace std;
int n,i;
class Sqlist{public:Sqlist(){data= new int[n];length=0;}~Sqlist(){delete [] data;}void getSqlist(int m){int max=50;int min=0;for(int i=0;i<m;i++){data[i]=rand()%(max-min+1);}}void seekmax(){int max=0;int index1,index2;//记录下标，对应最佳买入、卖出的天数for(int j=0;j<n-1;j++)//外层循环，锁定第j+1天，以便比较和后面天数的差值{for(int k=j+1;k<n;k++)//内层循环，计算第j+1天和之后（第k+1天）的股票的差值{if(data[k]-data[j]>max)//依次寻找最大的差值{max=data[k]-data[j];index1=j;//记录对应下标index2=k;}}}if(max!=0){cout<<"在第"<<index1+1<<"天买入,第"<<index2+1<<"天卖出最合适。"<<endl;cout<<"最大利益为"<<max;}else cout<<0;//最大利益为0，则输出0}void printlist()//打印顺序表{for(i=0;i<n;i++)cout<<data[i]<<' ';cout<<endl;}int getlength()//返回顺序表长度{return length;}bool isEmpty()//判断顺序表是否为空；若为空，返回0{if(length==0) return false;}private:int *data;//顺序表的元素int length;//顺序表的长度
};
int main()
{Sqlist list1;cin>>n;//输入预测的天数nlist1.getSqlist(n);//获取股票list1.printlist();//打印股票list1.seekmax();//寻找最大利益return 0;
}