搜索
数据结构C语言版第0章指导思想和目标一、指导思想基础性；系统性；先进性；实践性二、教学目标通过本课程学习，要求掌握数据结构和算法的基本概念和技术，从而能够对于给定问题选择合适的数据结构，并设计相应的操作算法。掌握数组、线性表、栈和队列、串、广义表、树和二叉树、图等典型数据结构及相关算法，以及内排序、查找等重要技术。参考书1、数据结构题集严蔚敏吴伟民清华大学出版社2、数据结构习题与解析李春葆清华大学出版社3、数据结构与离散数学分册（计算机专业研究生入学考试全真题解）前沿考试研究室人民邮电出版社4、数据结构-用C语言描述唐策善等高等教育出版社5、C语言程序设计谭浩强清华大学出版社6、C＋＋程序设计第1章绪论1.1《数据结构》课程研究的内容1.2《数据结构》课程的发展历史及课程的重要性1.3基本概念和术语1.4抽象数据类型的表示与实现1.5算法和算法分析1.1《数据结构》课程研究的内容数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科。它主要研究：①数据的逻辑结构--数据关系之间的逻辑关系②数据的存储结构--数据的逻辑结构在计算机中的表示③操作算法--插入、删除、修改、查询、排序等1.2《数据结构》课程的发展历史及课程的重要性·1968年在美国开设。它随着大型程序的出现而出现。·我国80年代初开设。它是计算机专业的核心课程，考研必考。·学习《数据结构》的目的：①提高复杂程序设计的能力②培养算法设计能力③为后继课程（如操作系统、编译原理等）打基础。1.3基本概念和术语1、数据2、数据元素3、数据项4、数据对象5、数据结构6、存储结构7、数据类型8、抽象数据类型数据:是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项:是数据的不可分割的最小单位。数据对象:是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性，通常有下列四类基本结构：①集合②线性结构③树形结构④图状结构或网状结构它可形式定义为：数据结构是一个二元组Data_Structure=(D,S)其中：D是数据元素的有限集、S是D上关系的有限集。存储结构：是数据结构在计算机中的表示（又称映象）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。有两种不同的存储结构：顺序存储结构----其特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构----其特点是借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。数据类型：是和数据结构密切相关的一个概念。它是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型可以用以下三元组表示(D,S,P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型的定义格式如下：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名1.4抽象数据类型的表示与实现抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。例子如P121.5算法和算法分析1、算法的特性算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法有五个特性：⑴有穷性⑵确定性⑶可行性⑷输入⑸输出1.5算法和算法分析2、评价算法好坏的标准⑴正确性：⑵可读性：⑶健壮性：⑷时间复杂性：⑸空间复杂性：1.5算法和算法分析3、算法效率的度量度量一个程序的执行时间通常有两种方法：①事后统计的方法②事前分析估算的方法1.5算法和算法分析4、时间复杂性算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度（AsymptoticTimeComplexity），简称时间复杂度。1.5算法和算法分析5、空间复杂性空间复杂性(SpaceComplexity)作为算法所需存储空间的量度，记作S(n)=O(f(n))其中n为问题的规模（或大小）。一个程序上机执行所需空间包括：①程序指令存储的空间②数据存储的空间③变量分配的空间小结•本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。•需要达到识记层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。•需要达到领会层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。对基本概念的理解•数据•数据元素•数据结构例如一个表（数据库）逻辑结构：线性结构和非线性结构存储方法：顺序存储方法，链接存储方法，索引存储方法，散列存储方法难点问题：算法的描述和分析，主要是算法复杂度的分析习题一1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。1.3常用的存储表示方法有哪几种?1.4设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大?1.5按增长率由小至大的顺序排列下列各函数：2^100,(2/3)^n，(3/2)^n，n^n,,n!，2^n，lgn,n^lgn,n^(3/2)