数据结构实验一 预备实验

实验一预备实验

一、实验目的

(1)了解抽象数据类型(ADT)的基本概念和及描述方法

(2)熟悉C/C++语言语法及程序设计，为以后章节的学习打下基础。

(3)熟悉使用软酷网

二、实验相关知识

(1)C/C++语言程序设计基础

(2)抽象数据类型定义

三、实验题目

(1)编写算法，输入整数n(l<=n<=1000),x(l<=x<=1000)和ai(i=0』,2,3,…n)的值,

求一元多项式七(X)=。0+alxl+a2x2+。3炉+…+与产的值4(a)，并计算法的时间复

杂度。(假设多项式每一项的值以及和均不超过int型的范围)

测试用例:

输入2123432-1-205422100

0

输出9354

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

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

复数ADT：

ADTcomplex{

数据对象：D={cl,c2|cl,c2efloat)

基本操作：创建一个复数creat(a);

输出一个复数output(a);

求两个复数的和add(a,b);

求两个复数的差sub(a,b);

求两个复数的积mul(a,b);

}ADTcomplex;

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

测试用例：

输入1234-1211

输出4+6i0+3i

-2-2i-2+li

-5+10i-3+li

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

(3)一线性表中元素为正数或负数，设计一个算法，将负数排在正数之前，不要求整个

排序，要求时间复杂度为0(N),空间复杂度为0(1)。

四、程序代码及运行结果

(1)【程序代码】

#include<iostream>

usingnamespacestd;

intmain()

{

intn,x,j,p;

inti[1005];

cin>>n;

cin>>x;

for(j=0;j<=n;j++)

{

cin»i[j]；

}

P=0；

n=n+l;

while(--n>=0)

(

p=p*x+i[n];

)

cout<<p<<endl;

return0;

)

【运行结果】

SSC:\windows\system32\cmd.exe

322312

28

请按任意键继续.・・

ranC:\windows\system32\cmd.exe

23231

20

请按任意键继续・..

【算法时间复杂度分析】

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

(2)【程序代码】

//complex.h

typedefstruct

(

doublex;

doubley;

}complex;

//complex.cpp

#include"complex.hH

#include<iostream>

#include<stdlib.h>

usingnamespacestd;

voidcreat(complex&a);

voidoutputc(complexa);

complexadd(complexcomplexb);

complexsub(complexa,complexb);

complexmul(complexa,complexb);

intmain()

(

complexcl,c2,a,s,c;

creat(cl);

creat(c2);

a=add(cl,c2);

outputc(a);

a=sub(cl,c2);

outputc(a);

a=mul(cl,c2);

outputc(a);

return0;

)

voidcreat(complex&a)

cin>>a.x;

cin>>a.y;

)

voidoutputc(complexa)

(

if(a.y<0)

{

cout<<a.x<<a.y<<"i"<<endl;

)

else

{

cout<<a.x<<"+"<<a.y<<,,i,,<<endl;

}

)

complexadd(complexa,complexb)

(

complexc;

c.x=a.x+b.x;

c.y=a.y+b.y;

returnc;

)

complexsub(complexcomplexb)

(

complexc;

c.x=a.x-b.x;

c.y=a.y-b.y;

returnc;

)

complexmul(complexa,complexb)

{

complexc;

c.x=a.x*b.x-a.y*b.y;

c.y=a.y*b.x+a.x*b.y;

returnc;

)

【运行结果】

SBC:\windows\system32\cmd.exe

2132

5+3i

-1-1i

4+7i

请按任意键继续・.・

SJC:\windows\system32\cmd.exe

4221

6+3i

2+li

6+8i

请按任意键继续・.•

【算法时间复杂度分析】

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

(3)【程序代码】

#include<iostream>

usingnamespacestd;

voidswap(int&a,int&b)

{

if(a*b<0)

{

inttemp=a;

a=b;

b=temp;

}

)

voidsort(int*p,intnNum)

(

int*pl=p;

int*p2=p;

int*pEnd=p+nNum-1;

while(pl<pEnd&&p2<pEnd)

{

while(pl<pEnd&&*pl<0)

{

P1++；

}

while(p2<pEnd&&*p2>0)

(

P2++；

}

if(pl<p2)

{

while((p2-pl)>1)

(

swap(*p2,*(p2-1));

)

swap(*plj*p2);

P1++；

}

P2++；

}

)

intmain()

(

intn[1005];

inti,t;

cin>>t;

for(i=0;i<t;i++)

cin>>n[i];

)

sort(