浙江万里学院计算机系

数据结构课件第1章绪论第1讲2004年9月1浙江万里学院计算机系数据结构课程学分：5共计16周周学时：4（讲）+2（实验）教师：电话：88222400短624289邮箱：yxj@地点:7207答疑:星期一下午2浙江万里学院计算机系课程基本要求

记笔记（到课堂听课）成绩构成：考勤10%完成书面作业10%完成上机实验作业10%期末卷面考试70%考试资格：缺课或作业1/3取消资格3浙江万里学院计算机系本讲主要内容1.1数据结构的基本概念与术语

1.2抽象数据类型（ADT）和面向对象技术（OOP）

1.3C++语言回顾4浙江万里学院计算机系1.1数据结构的基本概念与术语1.1.1引言图书档案类问题、棋类对奕问题、

交通或通信网问题、

非数值计算5浙江万里学院计算机系图书档案类问题

线性表6浙江万里学院计算机系棋类对奕问题

树结构7浙江万里学院计算机系交通或通信网问题

图结构8浙江万里学院计算机系1.1数据结构的基本概念与术语1.1.2概念与术语1.数据(data):

是描述客观事物的数字、字符以及所有能够输入到计算机中并被计算机处理的信息的总称。

9浙江万里学院计算机系1.1.2概念与术语2.数据元素(DataElement)

是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据元素除了可以是一个数字或一个字符串以外，它也可以由一个或多个数据项组成。数据项(DataItem)是有独立含义的数据的最小单位，数据项有时也称为字段(field)。

10浙江万里学院计算机系图书档案类问题

线性表11浙江万里学院计算机系1.1.2概念与术语3.数据对象(DataObject)

是具有相同性质的数据元素的集合，是数据的一个子集。整数数据对象是集合Ｎ＝{０，±１，±２，…}，字母字符数据对象是集合Ｃ＝{′Ａ′，′Ｂ′，…，′Ｚ′}。图1.1中的学籍表也可看成一个数据对象。12浙江万里学院计算机系1.1.2概念与术语4.数据的逻辑结构(DataStructure)

是带有结构的数据元素的集合，它是指数据元素之间的相互关系，即数据的组织形式。把数据元素间的逻辑上的联系，称之为数据的逻辑结构，如:线性结构、树结构、图结构。特点：

抽象关系，独立于计算机。13浙江万里学院计算机系1.1.2概念与术语5.数据的存储结构(物理结构)

数据的逻辑结构在计算机存储设备中的映象被称为数据的存储结构，也可以说数据的存储结构是逻辑结构在计算机存储器里的实现，又称物理结构。数据的存储结构依赖于计算机常见存储结构有：顺序存储结构（顺序映象）、链式存储结构（非顺序映象）。14浙江万里学院计算机系1.1.2概念与术语6.“数据结构”课程研究内容包括数据的逻辑结构、数据在计算机内的存储结构以及定义在它们之上的一组运算。考虑存储空间的开销和运行时间的效率。数据结构课程不仅讲授数据信息在计算机中的组织和表示方法，同时也训练高效地解决复杂问题程序设计的能力。数据结构是专业基础课、核心课15浙江万里学院计算机系1.2抽象数据类型（ADT）和

面向对象技术（OOP）1.2.1高级语言的数据类型(DateType)intkey;charch,*st;

只需了解整数的加、减、乘法或取模运算的抽象特性，不必了解“位运算”细节，就可运用高级语言进行程序设计。还有用户自己定义的：数组、结构体、类

16浙江万里学院计算机系1.2.2

抽象数据类型（ADT）

（Abstract

DateType）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关。抽象数据类型（ADT）和数据类型（DataType）实质上是一个概念。整数类型就是一个ADT实例。所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件复用程度就越高。

17浙江万里学院计算机系例1.1复数的抽象数据类型ADT。

ADTcomplex

[复数ADT的描述]

{数据对象：D={c1,c2c1,c2∈FloatSet}

数据关系：R={<c1,c2>c1是实部，c2是虚部}

基本操作：创建一个复数

creat(a);

输出一个复数

outputc(a);

求两个复数相加之和

add(a,b);

求两个复数相减之差

sub(a,b);

求两个复数相乘之积

chengji(a,b);

等等;}ADTcomplex;

18浙江万里学院计算机系1.复数ADT实现的面向过程源程序-1#include<iostream.h>#include<conio.h>structcomp//存储表示，结构体类型的定义{floatx;//实部子域

floaty;//虚部的实系数子域};voidcreat(comp&c);//子函数的原型声明voidoutputc(compa);compadd(compk,comph);compsub(compk,comph);compa,b,a1,b1;intz;//全局变量的说明19浙江万里学院计算机系复数ADT实现的面向过程源程序-2intmain()//主函数{creat(a);outputc(a);

creat(b);outputc(b);a1=add(a,b);outputc(a1);_getch();return0;}voidcreat(comp&c){floatx1,y1;

cout<<“输入实部realx=?”);cin>>x1;

cout<<“输入实部xvpuy=?”);cin>>y1;c.x=x1;c.y=y1;}20浙江万里学院计算机系复数ADT实现的面向过程源程序-3voidoutputc(compa)//

输出一个复数{cout<<“复数：”<<a.x<<“+i*”<<a.y<<endl;}compadd(compk,comph)//求两个复数相加之和{compl;l.x=k.x+h.x;l.y=k.y+h.y;returnl;}compsub(compk,comph)//求两个复数相减之差{compl;l.x=k.x-h.x;l.y=k.y-h.y;returnl;}21浙江万里学院计算机系2.复数ADT实现的面向对象源程序-1#include<iostream.h>#include<conio.h>classComplex

//定义复数类Complex{private:floatx;//实部

floaty;//虚部

public:

Complex(){}

Complex(floatx0,floaty0){x=x0;y=y0;}~Complex(){}

22浙江万里学院计算机系复数ADT实现的面向对象源程序-2voidoutputc(){cout<<“复数：”<<x<<“+i*”<<y<<endl;}Complexoperator+(Complexk){returnComplex(x+k.x,y+k.y);}Complexoperator-(Complexk){returnComplex(x-k.x,y-k.y);}Complexoperator*(Complexk);};

//类定义结束

23浙江万里学院计算机系复数ADT实现的面向对象源程序-3ComplexComplex::operator*(Complexk){Complexg;g.x=k.x*x-k.y*y;g.y=k.y*x+y*k.x;returng;}intmain(){Complexa1(1,2),a2(4,6),a3,a4,a5;a3=a1+a2;a3.outputc();a4=a1-a2;a4.outputc();a5=a1*a2;a5.outputc();_getch();return0;}24浙江万里学院计算机系1.3C++语言简介1.3.1基本输入/输出1.3.2函数与参数传递