(数据结构)清华大学出版社ppt

《(数据结构)清华大学出版社ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、王钢主编清华大学出版社数据结构主要内容数据结构概论线性表栈队列串数组、特殊矩阵和广义表树和二叉树图查找排序实验内容第一章数据结构概论数据结构的基本概念和术语数据的逻辑结构和物理结构数据类型和抽象数据类型算法的时间复杂度和空间复杂度分析是相互之间存在一种或多种特定关系的数据元素的集合。从1.1.1节中的三个例子可以看到，在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(structure)。1.1数据结构的概念其他相关概念数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入计算机并能被计算机处理的

2、符号的总称。数据元素(dataelement)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象(dataobject)：是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质(数据元素的值不一定相等)，属于同一数据对象。数据结构的四类基本结构集合：集合结构中的所有元素都“属于同一集合”，即只要满足同属于一个集合就是集合结构，这是一种极为松散的结构。线性结构：该结构的数据元素之间存在着一对一的关系。树形结构：该结构的数据元素之间存在着一对多的关系。图形结构：该结构的数据元素之间存在着多对多的关系，图形结构也称为网状结构。四类

3、基本结构关系图(a)集合结构(b)线性结构(c)树形结构(d)图形结构数据的逻辑结构和数据的物理结构数据的逻辑结构：以上四种数据结构是从实际问题中抽象出来的数学模型，结构中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。数据的物理结构：数据结构在计算机中的表示(又称映像)称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据元素的表示和相互之间关系的表示。数据结构课程的内容第一，抽象。从实际问题中抽象出逻辑结构，即分析解决该问题需要用到什么样的数据，数据元素之间的关系如何，以及基于这种逻辑结构上的基本运算。第二，实现。

4、将逻辑结构用适当的物理结构在计算机内表示出来，同时编写算法实现各种基本运算。第三，评价。对不同的数据结构进行比较和算法分析。数据结构课程的任务数据结构课程的任务就是将实际问题抽象成数据的逻辑结构，再将逻辑结构用适当的存储结构在计算机中表示出来，并实现基本运算，为编写程序及实现用计算机处理实际问题打下坚实的基础。这同时也体现了数据结构这门课程的重要性。数据类型数据类型是一个值的集合和定义在这个值的集合上的一组操作的总称。例如C语言中的整型变量，其值集为某个区间上的整数(区间大小依赖于不同的机器)，定义在其上的操作有：加、减、乘、除和取模等算术运算。原子类型。原子类型的值

5、是不可分解的。如C语言中的整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标示。结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。例如数组的值是由若干元素组成，每个元素可以是整数，也可以是数组等。抽象数据类型抽象数据类型(abstractdatatype，简称ADT)是指一个数学模型以及定义在该数学模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不便，都不影响其外部

6、的使用。和数据结构的形式定义相对应，抽象数据类型可以用以下三元组表示：ADT=(D，S，P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。参数传递传值调用：调用函数在引用被调用函数时，只把实参的值传给形参，实参和形参使用不同的内存地址。因此在被调用函数的执行过程中，形参值的改变不会改变实参变量的值。在不需要改变实参值的场合通常使用这种调用方式。传址调用(或称引用调用)：调用函数在引用被调用函数时，只是把实参的地址传给了形参，使调用与被调用函数的参数占用相同的内存地址，因此被调用函数在执行过程中若参数值改变，则相应的调用函数的实参值也会改变。在需要改变实参

7、值的场合需要使用这种调用方式。例1.4voidswap1(intx,inty){inttemp;temp=x;x=y;y=temp;}voidswap2(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}main(){inta,b;a=3;b=50;swap1(a,b);printf("swapedis:%d,%d",a,b);swap2(&a,&b);printf("swapedis:%d,%d",a,b);}程序执行的输出结果为：swapedis:3,50swapedis:50,3算法特性有穷性一个算