数据结构专科电子教案一课件

1、数 据 结 构数 据 结 构 第一章 绪论 第一章 绪论数据结构讨论的范畴 :非数值计算程序设计问题算法数据结构讨论的范畴 :非数值计算程序设计问题算法 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。数据结构课程介绍和研究数据在计算机中的存储和处理的方法。 数据结构是一门讨论“描述现实世界实体的数学模型(非1.1 常用术语数据(Data): 人们利用文字符号,数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述. 是能够被计算机输入，存储，处理和输出的信息。1.1 常用术语数据(Data): 人们利用文字符号, 简称元素,

2、它是一个数据整体中相对独立的单位. 即:数据（集合）中的一个“个体”是数据结构中讨论的基本单位数据元素（Data Element): 简称元素,它是一个数据整体中相对独立的单位.数据元素（D 数据纪录(Data Record) 简称记录,它是数据处理领域组织数据的基本单位。 数据项(Item) 关键项(Key Item) 关键字(Key Word , Key) 数据纪录(Data Record) 数据结构 ( Data Structure) ： 是指数据及其相互之间的联系或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构 ( Data Structure) ： 数据之间的相

3、互联系，被称为数据的逻辑结构，一种数据结构在存储器中的存储方式称为数据的物理结构（顺序结构、链接结构、索引结构、散列结构）。数据的逻辑结构和物理结构： 数据之间的相互联系，被称为数据的逻辑结构，一种数顺序存储 : 用一组地址连续的存储单元依次存储数据元素 x1 x2 x3 顺序存储 : 用一组地址连续的存储单元 x1 x2 链式存储: 以附加信息(指针)表示后继关系需要用一个和 x 在一起的附加信息指示 y 的存储位置。a1a2a3链式存储: 以附加信息(指针)表示后继关系需要用一个和 数据结构的描述： 二元组表示: 数据结构 B= ( K , R ) R = | ku , kvK 对于R中的

4、任一序偶,x叫做序偶第一 元素(前驱),y叫做序偶的第二元素(后继)。 图表示 : 数据结构的描述：例 画出二元组 (K，R)的图形表示 其中K=01,02,03,04,05,06,07,08,09,10R=,01040602050703080910例 画出二元组 (K，R)的图形表示 010406020典型的数据结构可归结为以下四类:线性结构( 1:1联系）树形结构( 1:N联系）图状结构 ( M:N联系） 集合结构(关系R= ）典型的数据结构可归结为以下四类:线性结构树形结构图状结构 ( 数据类型( Data Type) 是对数据的取值范围、每一数据的结构以及允许施加操作的一种描述。可分为

5、简单类型和结构类型两种.简单类型：整数、实数、字符、指针、枚举量等。结构类型：数组、记录、字符串、文件等。 数据类型( Data Type)简单类型：整数、实数、一维和二维数组的元素地址计算： 一维数组 an:元素 ai的存储位置为： Address (ai)=a+i*L （0in-1） 二维数组 bmn : 行元素 bi的存储位置为： Address(bi)=b+i*n*L (0im-1)元素 bij的存储位置为： Address (bij)=b+i*n*L+j*L (0im-1,0jn-1) 其中L表示数组中元素类型的大小一维和二维数组的元素地址计算：抽象数据类型( Abstract Da

6、ta Type 简称 ADT ) 由一组数据结构和在该组数据结构上的一组操作所组成。也可以被定义为由一组数据和在该数据上的一组操作所组成。抽象数据类型 由一组数据结构和在该组数据结构上的一组操 本课程中，为了便于叙述和分析数据结构与算法，在实现所定义的抽象数据类型时，把数据部分用 struct 结构类型来描述，把操作部分中的每个操作用外部函数（即普通函数）来描述。注： 本课程中，为了便于叙述和分析数据结构与算 在本课程中，定义一种抽象数据类型采用如下书写格式： ADT is Data: Operations: end 在本课程中，定义一种抽象数据类ADT RECtangle is Data:

7、float length , width ； Operations: void InitRectangle (Rectangle& r , float len , float wid ); float Circumference (Rectangle& r ); float Area (Rectangle& r );end RECtangle例：对于矩形定义一种抽象数据类型，其数据部分包括矩形的长度和宽度，操作部分包括初始化矩形的尺寸，求矩形的周长和求矩形的面积。 struct Rectangle float length , width ; ;ADT RECtangle is例：对于矩形定义

8、一种抽void Initrectangle (Rectangle& r, float len, float wid) r.length=len; r.width=wid; /初始化矩形数据函数float Circumference (Rectangle& r) returm 2 * (r.length+r.Width); /求矩形周长函数float Area (Rectangle& r) return r.length * r.width; /求矩形面积函数void Initrectangle (Rectangle 数据对象（Data Object)：简称对象，它属于一种数据类型中的特定实例。

9、 算法（Algorithm) ：是对解决某类问题的方法的一种描述。 一个算法必须具备以下五个特性：（1）有穷性 （2）确定性 （3）可行性（4）有输入（5）有输出 数据对象（Data Object)：简称对象，它1.2 算法描述1.2.1 包含文件语句1. # include 标准输入设备（键盘）流对象 cin ;标准输出设备（屏幕）流对象 cout ;标准错误输出设备（屏幕）流对象 cerr ;用于输入的提取操作符 ;用于输出的插入操作符 和 (istream& istr, struct_type& x) istr x.成员1 x.成员2 x.成员n ; return istr;ostrea

10、m& operater (ostream& istr, struct_type& x) ostr x.成员1 “ ” x.成员2 “ ” x.成员n x1cout 和2. # include void exit(int) ； int rand(void) ； void srand(unsigned) ；3. # include 输入文件流类 ifstream； 输出文件流类 ofstream； 输入输出文件流类 fstream。 例如： ifstream input 1(“a1.dat” , ios: in | ios: nocreate)；2. # include vo4. # includ

11、e int strlen(const char* s); /求串长度 char* strcpy(char* dest,const char* src); /串拷贝 char* strcat(char* dest,const char* src); /串连接 int strcmp(const char* s1,const char* s2); /串比较 char* strchr(const char* s , int c); /串定位 char* strchr(const char* s , int c); /串右定位 char* strstr(const char* s1,const char

12、* s2);/查找子串ofstream input 2(“a2.dat” , ios: out )；ofstream input 3(“a3.dat” , ios: app )；fstream input 4(“a4.dat” , ios: in | ios: out )；4. # include i1.2.2 函 数例：不同返回类型的三个重载函数引用参数与值参数： 值参数：具有自己的存储空间，内容的改变不会影响到对应的实在参数。 引用参数：和实在变量参数具有同一存储位置，对引用参数的读写操作实际上就是对相应实参变量的读写操作，对引用参数的改变将反映给对应的实参变量。1.2.2 函 数例：不同

13、返回类型的三个重载函数引用参数与例：void swap1(int a,int b) int t; t = a; a = b; b = t;void swap2 (int& a,int& b) int t ; t = a; a = b; b = t; 设x,y是两个整数变量，那么调用函数swap1(x,y)将不改变x,y的值，而调用函数swap2(x,y)将交换x,y的数值。例：void swap1(int a,int b)void1.23 运算符重载 对于自定义的结构类型，需要对关系运算符进行重载，使得记录同记录之间、记录同其中一个域类型的数据之间也能够进行比较。 如下例所示：1.23 运算符

14、重载 对于自定义的结构类型，需struct pupil char pnum 8; int grade;bool operator = =(pupil& r1 ,pupil& r2) if (strcmp(r1.pnum ,r2.pnum)= =0) return true; else return false;bool operator = =(pupil& r ,char* key) if (strcmp(r.pnum ,r2.key)= =0) return true; else return false;bool operator (pupil& r1 ,pupil& r2) retur

15、n r1.grade r2.grade;bool operator (pupil& r,int key) return r.grade key;struct pupil char 1.3 算法评价1.正确性 ( Correctness )2. 健壮性 ( Robustness )3. 可读性 ( Readability )4. 时间复杂度 ( Time Complexity ) 又称计算复杂度( Computational Complexity )5.空间复杂度 ( Space Complexity )1.3 算法评价1.正确性 ( Correctness ) 随着问题规模 n 的增长，算法执

16、行时间 f(n) 的增长率和 g(n)的增长率相同。 即：存在n0，当n n0时，存在两个正的常数A和B,使得 Af(n)/g(n) B均成立。f (n) = O(g(n) 时间复杂度的数量级形式表示 : 随着问题规模 n 的增长，算法执行时间 f(n例：算法1:（累加求和）int Sum ( int b ,int n ) int s=0; for ( int i=0 ; in ; i+) s+=bi ; 算法 1的时间复杂度为O(n)算法2:(矩阵相加）void MatrixAdd ( int aMSMS ,int bMSMS , int cMSMS ,int n ) int i, j; f

17、or ( int i=0 ; in ; i+) for (j=0 ; jn ; j+) cij = aij+bij ; 算法 2 的时间复杂度为O(n2)算法3:（简单选择排序）Void SelectSort ( int b , int n ) int i , j , k , x ; for ( int i=0 ; in -1 ; i+) k=i ; for (j=i+1 ; j n ; j+) if ( bi bk ) k = j ; x=bi ; bi = bk ; bk = x ; 算法 3的时间复杂度的数量级为O(n2)例：算法1:（累加求和）算法2:(矩阵相加）算法3:（简单选如：某程序的时间复杂度为：10log2n+ nlog2n+100则数量级表示为 O(nlog2n) O(log2n) O(n) O(n*log2n) O(n2) O(n3) O(2n) O(n!) 时间复杂度的各种不同数量级对应的值存在如下关系：如：某程序的时间复杂度为：O(log2n) O(n) int SequenceSearch( int a , int