open-graph-logo

323 次

一、实验目的

(1)了解抽象数据类型(ADT)的基本概念和及描述方法
(2)熟悉C/C++语言语法及程序设计,为以后章节的学习打下基础。
(3)熟悉使用软酷网

二、实验相关知识

(1)C/C++语言程序设计基础
(2)抽象数据类型定义

三、实验题目

(1)编写算法,输入整数n(1<=n<=1000),x(1<=x<=1000)和ai(i=0,1,2,3,…n)的值,求一元多项式的值,并计算法的时间复杂度。(假设多项式每一项的值以及和均不超过int型的范围)

测试用例:

输入2 1 2 3 43 2 -1 -2 0 5 4 2 2 1 0 0 0
输出9354

【实现要求】算法中不能使用求幂函数。

(2)实现以下复数抽象数据类型,并编写程序实现计算两复数的和、差、积。

ADT complex{
数据对象:D={c1,c2|c1,c2∈float}
基本操作:创建一个复数 creat(a);
输出一个复数 output(a);
求两个复数的和 add(a,b);
求两个复数的差 sub(a,b);
求两个复数的积 mul(a,b);
}ADT complex;

输入a,b,c,d,输出两复数a+bi 和c+ di的和差积。

测试用例:

输入 1 2 3 4-1 2 1 1
输出4+6i
-2-2i
-5+10i
0+3i
-2+1i
-3+1i

【实现要求】必须以实现复数ADT中的各个操作的函数来完成程序设计。

(3)一线性表中元素为正数或负数,设计一个算法,将负数排在正数之前,不要求整个排序,要求时间复杂度为O(N),空间复杂度为O(1)。

四、程序代码及运行结果

(1)【程序代码】

#include <iostream>
using namespace std;

int main()
{
	int n, x, j, p;
	int i[1005];
	cin >> n;
	cin >> x;
	for(j=0; j<=n; j++)
	{
		cin >> i[j];
	}
	p = 0;
	n=n+1;
	while(--n >= 0)
	{
		p = p * x + i[n];
	}
	cout << p << endl;
	return 0;
}

【运行结果】

【算法时间复杂度分析】

时间复杂度为O(N),空间复杂度为O(1)。

(2)【程序代码】

//complex.h
typedef struct
{
	double x;
	double y;
} complex;


//complex.cpp
#include "complex.h"
#include<iostream>
#include<stdlib.h> 
using namespace std;

void creat(complex &a);
void outputc(complex a);
complex add(complex a,complex b);
complex sub(complex a,complex b);
complex mul(complex a,complex b);

int main()
{   

	complex c1,c2,a,s,c;
	creat(c1);
	creat(c2);
	a=add(c1,c2);
	outputc(a);
	a=sub(c1,c2);
	outputc(a);
	a=mul(c1,c2);
	outputc(a);
	return 0;
}
void creat(complex &a)
{

	cin>>a.x;
	cin>>a.y;
}
void outputc(complex a)
{
	if(a.y<0)
	{
		cout<<a.x<<a.y<<"i"<<endl;
	}
	else
	{
		cout<<a.x<<"+"<<a.y<<"i"<<endl;
	}
} 

complex add(complex a,complex b)
{
	complex c;
	c.x=a.x+b.x;
	c.y=a.y+b.y;
	return c;
}

complex sub(complex a,complex b)
{
	complex c;
	c.x=a.x-b.x;
	c.y=a.y-b.y;
	return c;
}

complex mul(complex a,complex b)
{
	complex c;
	c.x=a.x*b.x-a.y*b.y;
	c.y=a.y*b.x+a.x*b.y;
	return c;
}

   【运行结果】

【算法时间复杂度分析】

时间复杂度为O(1),空间复杂度为O(1)。

(3)【程序代码】

#include <iostream>
using namespace std;

void swap(int &a, int &b)
{
	if (a*b < 0)
	{
		int temp = a;
		a = b;
		b = temp;
	}
}

void sort(int *p, int nNum)
{
	int *p1 = p;
	int *p2 = p;
	int *pEnd = p + nNum - 1;
	while (p1 < pEnd && p2 < pEnd)
	{
		while (p1 < pEnd && *p1 < 0)
		{
			p1++;
		}
		while (p2 < pEnd && *p2>0)
		{
			p2++;
		}
		if (p1 < p2)
		{
			while ((p2 - p1) > 1)
			{
				swap(*p2, *(p2 - 1));
				p2--;
			}
			swap(*p1, *p2);
			p1++;
		}
		p2++;
	}
}

int main()
{
	int n[1005];
	int i, t;
	cin >> t;
	for (i = 0; i < t; i++)
	{
		cin >> n[i];
	}
	sort(n, t);

	for (i = 0; i < t; ++i)
	{
		cout << n[i] << " ";
	}
	cout << endl;
	return 0;
}

   【运行结果】

、实验心得体会

巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。培养独立思考,深入研究,分析问题、解决问题的能力。

赞赏

微信赞赏支付宝赞赏

评论

电子邮件地址不会被公开。 必填项已用*标注

CAPTCHAis initialing...

%d 博主赞过: