数据结构与算法基础——第01周-抽象数据类型的表示与实现(1.3)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 计算机如何处理数据

二 概念小节

三 抽象数据类型的表示与实现

3.1 抽象数据类型的表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ADT Circle{
数据对象：D={r,x,y|r,x,y均为实数}
数据关系：R={<r,x,y>|r是半径，<x,y>是圆形坐标}
基本操作：
  Circle(&C,r,x,y)
  	操作结果：构造一个圆。
  double Area(C)
  	初始条件：圆已存在
  	操作结果：计算面积
  double Circumference(C)
  	初始条件：圆已存在
  	操作结果：计算周长
  	....
}ADT Circle
  • 一个问题抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的
  • 要实现这个目标，就要把抽象的变成具体的，即抽象数据类型在计算机上实现，变成一个能用的具体的数据类型

3.2 抽象数据类型的实现

3.3 抽象数据类型如何实现

  • 抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现
  • 即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作

四 抽象数据类型实现的示例

4.1 抽象数据类型“复数”的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct{
	float realpart; /*实部 */
	float imagpart; /*虚部 */
}Complex            /*定义复数抽象类型 */

void assign(Complex *A,float real,float imag); /* 赋值*/
void add(Complex *c,Complex A,Complex B); /* A+B*/
void minus(Complex *c,Complex A,Complex B); /* A-B*/
void multiply(Complex *c,Complex A,Complex B); /* A*B*/
void divide(Complex *c,Complex A,Complex B); /* A/B*/

void assign(Complex *A,float real,float imag)
{
	A->realpart=real;
	A->imagpart=imag;
}
void add(Complex *c,Complex A,Complex B)
{
	c->realpart=A.realpart+B.realpart;
	c->imagpart=A.imagpart+B.imagpart;
}

说明：

  • Complex使我们定义的一个结构体类型
  • 带*：指针变量，它是指向Complex类型的指针
  • 不带*：Complex类型的普通变量

4.2 复数计算函数

1
z=(8+6i)(4+3i)/(8+6i)+(4+3i)

4.3 编程实现(伪代码)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<studio.h>
void main()
{
	Complex z1,z2,z3,z4,z;
	float RealPart,ImagPart;
	assign(z1,8.0,6.0);//构造复数z1
	assign(z2,4.0,3.0);//构造复数z2
	add(z1,z2,z3);//两个复数相加
	multiply(z1,z2,z4);//两个复数相乘
	if(divide(z4,z3,z)){ //两数相除
		GetReal(z,Realpart);
		GetReal(z,ImagPart);
	}
}