数据结构(C语言版)第1章--绪论.pptVIP

gfhgfhgf数据结构(DataStructures)

(C语言版)主讲教师：吴让仲Instructor:WU,RANGZHONGE-mail:wurangzhong@163.com课程目的能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构正确、清晰、易读；初步掌握算法的时间分析和空间分析技术。第一章绪论计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和处理又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。计算机解决问题的步骤当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：分析具体问题抽象数据模型设计算法编程、调试得出结果例1.1考生录取信息系统考生录取信息系统计算机处理的对象是表元素间的关系是线性关系施加于对象上的操作有查询、插入、删除等例1.2人－机博弈国际象棋DeepBlue:2亿结点/秒，60万种棋局，评价函数有8000个参数；计算机预见10~15步，心理学家认为，人类选手只能预测3~5步；棋局中期计算机往后看75步。人－机博弈计算机处理的对象是树型结构元素间的关系是层次关系施加于对象上的操作有查询、插入、删除等例1.3哥尼斯堡七桥问题哥尼斯堡七桥问题计算机处理的对象是图元素间的关系是复杂的图形或网状关系施加于对象上的操作有查询、插入、删除等数据结构研究的内容由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。1.2基本概念和术语(1)数据(Data)：客观事物在计算机中的符号表示，是能被计算机识别和处理的符号总称。数据元素(DataElement)：数据的基本单位，用于完整地描述一个对象;(也称为：记录，元素，结点，顶点等）数据项(DataItem)：组成数据元素的有特定意义的最小的不可分割的单位。基本概念和术语（2）数据的三个层次数据数据元素数据项数据对象(DataObject)：具有相同特性的数据元素的集合，是数据的一个子集;基本概念和术语（3）数据结构：相互之间存在一种或多种特定关系的数据元素的集合。形式定义：数据结构是一个二元组Data_Structure＝（D，R）,其中，D是数据元素的有限集，R是D上关系的有限集。数据结构的三要素：逻辑结构，存储结构，运算。逻辑结构的分类数据的逻辑结构是本质，可以分为：线性结构和非线性结构也可以分为集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构结构中的数据元素之间存在一对一的关系。树型结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。存储结构存储结构(物理结构)指数据结构在计算机中的表示。顺序存储结构：借助元素在存储器中的相对位置表示数据元素之间的关系。链式存储结构：借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。物理（存储）结构的分类物理（存储）结构的分类顺序存储结构：链式存储结构：索引存储结构：散列存储结构1.3抽象数据类型的表示和实现(1)

抽象数据类型:（AbstractDataType）ADT:一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型（3）抽象数据类型的定义：ADT抽象数据类型名{ 数据对象：{数据对象定义} 数据关系：{数据关系定义} 基本操作：{基本操作定义}}ADT抽象数据类型名数据结构发展简史作为独立课程国外1968年开始设立。1968年美国KNUTH教授开创了数据结构的最初体系。计算机专业的专业基础课。非计算机专业的主要选修课。数据结构课程的内容数据结构是介于数学、计算机硬件和计算机软件之间的一门计算