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

这篇具有很好参考价值的文章主要介绍了【数据结构】实验二:顺序表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实验二  顺序表

一、实验目的与要求

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 array
	cout<<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)程序运行结果示例:

【数据结构】实验二:顺序表,数据结构,数据结构,算法

 【数据结构】实验二:顺序表,数据结构,数据结构,算法

 【数据结构】实验二:顺序表,数据结构,数据结构,算法

 


其他参考代码:文章来源地址https://www.toymoban.com/news/detail-613017.html

#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;//输入预测的天数n
   
    list1.getSqlist(n);//获取股票
    list1.printlist();//打印股票
    list1.seekmax();//寻找最大利益
    return 0;
}

到了这里,关于【数据结构】实验二:顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:两个顺序表合并算法

            将a,b两个有序顺序表进行合并,放在c顺序表当中,并且要保证顺序表c仍然有序。         因为a,b两个顺序表是有序的,所有可以从前往后一起查找a,b当中最小的一个数值,放入到c中。         如果遍历到最后,a遍历完了,b没有遍历完,就把b剩下的放入

    2024年02月08日
    浏览(38)
  • 【数据结构与算法】3.顺序表

    📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有限,欢迎各位大佬指点,相互学习进步! 定义:线性表是 n 个具有相同特性的数据元素的有序序列。线性表是一种在实际中

    2024年01月23日
    浏览(45)
  • 基于Python的数据结构实验——循环顺序队列与递归(附详细代码和注释)

    1、创建名为 prac04_01.py 的文件,在其中编写一个循环顺序队列的类,该类必须包含 循环顺序队列的定义及基本操作,并通过以下步骤测试各种基本操作的实现是否正确。 (1)初始化一个循环顺序队列 CircularSequenceQueue。 (2)判断队列是否为空。 (3)遍历队列内的所有元素。 (4)将元

    2024年02月05日
    浏览(55)
  • 数据结构算法--1 顺序查找二分查找

    顺序查找时间复杂度为O(n) 我们可以借助Python中的函数enumerate,通过enumerate遍历列表返回其索引和值 也可以通过列表长度依次遍历: 但是二分查找时间复杂度为O(logn):

    2024年02月12日
    浏览(54)
  • 顺序表(更新版)——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天小雅兰又来更新新专栏啦,其实之前我就已经写过了顺序表的内容,只是之前的内容不是最新版的顺序表,现在,我来更新一下最新版的顺序表,下面,就让我们进入更新版的顺序表的世界吧 顺序表和小雅兰之前写的三子棋、扫雷、通讯录一样,

    2023年04月23日
    浏览(33)
  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(35)
  • 数据结构与算法 --顺序表的创建

    1. 顺序表(Sequence List)是一种线性表的实现方式,通过连续的内存空间存储元素,按照顺序排列。 顺序表的特点包括: 元素在内存中的存储是连续的,通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(50)
  • 数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(62)
  • 【数据结构】:实现顺序表各种基本运算的算法

    领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。 编写一个程序sqlist.cpp,实现顺序表的各种基本运算和整体建表算法(假设顺序表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能: 初始化顺序表L 依次插入a,b,c,d,e元素 输出顺序表L 输出顺

    2024年02月07日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包