数据结构实验一 预备实验

一、实验目的

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

二、实验相关知识

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

三、实验题目

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

测试用例：

输入	2 1 2 3 4	3 2 -1 -2 0 5	4 2 2 1 0 0 0
输出	9	35	4

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

（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;
}

   【运行结果】

五、实验心得体会

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