本资料由网友IOU_520JRForever整理提供，仅供参考，如有好的建议或意见请与编者联系，谢谢！第一章绪论视频为数据结构1&2。

同步教学视频下载：

数据结构1：http://v.youku.com/v_show/id_XMzc1MTYxNzY=.html?f=2175086 数据结构2：http://v.youku.com/v_show/id_XMzc1MTYzNTI=.html?f=2175086

第一章 绪论.................................................................................................................. 1

1.1数据结构讨论的范畴....................................................................................... 1

1.2基本概念........................................................................................................... 2

1.3算法及其量度................................................................................................... 3

本章小结................................................................................................................. 3

第一章 绪论

1.1数据结构讨论的范畴

数据结构讨论什么？ 简单的回答是数据结构是一门和程序设计密切相关的课程。有言：“算法+数据结构=程序设计”。——美国计算机教授Wirth教授.

程序设计：为计算机处理问题编制一组指令集——对某类信息进行处理 算法：处理问题的策略——如何进行处理，即处理的策略

数据结构：问题的数据模型——处理问题的信息如何表示

任何程序设计问题都包含算法和数据结构两方面的问题，例如数值计算和非数值计算的程序设计问题

数值计算的程序设计问题

例，如根据地球上不同地方的重力值变化，要得到一个虽纬度高低不同重力值变化的线性方程。其数据模型就是该方程，计算机求解的问题即数学所要研究的问题。 非数值计算的程序设计问题——现今计算机主要处理的问题

1/3

本资料由网友IOU_520JRForever整理提供，仅供参考，如有好的建议或意见请与编者联系，谢谢！

例：编写一与计算机下棋的程序 算法：下棋的规则和计算对棋手针对的策略 模型：棋盘棋子如何表示

概括的说，数据结构讨论的是非数值性计算的程序设计问题现实世界实体的数学模型（非数值计算）及其上的操作在计算机中表示和实现。

1.2基本概念

数据与数据结构

数据：所有能被输入到计算机中，且被计算机处理的符号的集合，计算机操作的对象的总称；是计算机处理的信息的某种特定的符号表示形式。

数据元素：数据中的一个“个体”，是数据结构中的讨论的基本单位。不是最小单位。课时简单的字符，或者是多个数据项。数据元素师数据项的集合

数据项：数据结构中讨论的最小单位。——数据属性。若数据项中还有数据则该数据项被称为组合项。

例：运动员（数据元素），姓名、出生日期(年月日)（组合项）、籍贯等（数据项）。

数据结构：带结构的数据元素的集合。结构，数据元素之间存在的关系。次序关系等。

数据元素之间的关系——数据的逻辑关系，主要有四类：

线性结构

树形结构

图形结构

集合结构

以后将讨论的数体结构为以上两种。

数据结构的形式定义是一个二元组（D，S），D是元素的有限集，S是关系的有限集。只说明里数据结构的一方面，强调的是数据结构中逻辑关系。另一重要的方面是数据的存储结构。也就是怎样在计算机中表示数据的逻辑结构。存储结构就是逻辑结构在计算机中的表示。

数据元素的表示：二进制位的位串表示。

2/3

本资料由网友IOU_520JRForever整理提供，仅供参考，如有好的建议或意见请与编者联系，谢谢！

关系的表示：有序对关系集合表示。

有序对在计算机中的表示方法：

顺序印象：一个接一个，位置固定，有顺序。

链式印象：位置随意，则需要一信息表示其联系——指针。指向其所联系的元素的位置，使之联系在一起。

数据类型：一个值的集合和定义在此集合上的一组操作的总称。

抽象数据类型（ADT）：一个数据模型以及定义在此数据模型上的一组操作。特征：数据抽象和数据封装。描述方法：用一三元组（D，S，P），D元素集，S关系集，P基本操作集。（基本操作的参数，一、赋值参数，只为操作提供输入值；二、引用参数，即可提供输入值，还将返回操作的结果）表现和实现：用固有的数据类型来实现。数体结构和其操作实质上是一整体。

1.3算法及其量度

算法：简单地说就是对问题求解的描述，定义为算法是为了解决某类问题而规定的一个有限长的操作序列。特征：有穷性 确定性 可行性 有输入 有输出。要求（目标）：正确性 可读性 健壮性 高效率与低存储量需求

算法衡量的方法和准则：事后统计法和事前分析估计法

时间复杂度：随着程序的运行，算法执行时间的增长率和某规模函数f(n)的增长率相同，T(n)=O(f(n))，T(n)即为算法的时间复杂度。

如何估算时间复杂度：默认为与原重复操作的执行次数之和成正比。一般情况看算法的循环部分的内容。

空间复杂度：随着程序的运行程序所要存储的数据空间变化与某规模函数g(n)变化相同。S(n)=O(g(n))，S(n)即为算法的空间复杂度。

本章小结

1、熟悉各名词、术语的含义，掌握基本概念。

2、理解算法的五个要素的确切含义。

3、掌握计算语句频度和估算算法时间复杂度的方法。

3/3

本资料由网友IOU_520JRForever整理提供，仅供参考，如有好的建议或意见请与编者联系，谢谢！