数据结构（C语言版）课件 第1章绪论.pptxVIP

;;课程学习指导;平时成绩:40%

课堂表现

作业

单元测验

实验;;;N.沃思（NiklausWirth)教授提出：;用计算机求解问题;书目自动检索系统;人机对奕问题;;多叉路口交通灯管理问题;六度空间理论;描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。

设计出合适的数据结构及相应的算法。

即：首先要考虑对相关的各种信息如何表示、组织和存储？;形成阶段：

60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。;

数据结构创始人--高德纳(DonaldErvinKnuth)

;1968年，第一卷《基本算法》

1969年，第二卷《半数字化算法》

1973年，第三卷《排序与有哪些信誉好的足球投注网站》

2011年，第四卷A《组合算法》

……

计划七卷;;

数据结构创始人--高德纳(DonaldErvinKnuth)

;练内功不要只花功夫学习各种流行的编程语言和工具，以及一些公司招聘广告上要求的科目。

学好基础课程离散数学、数据结构、计算机组成原理、操作系统、计算机网络、编译原理、数据库等。

试试Knuth的TheArtofComputerProgramming的题目。

多实战

通过编程的实战，积累经验、内化知识。

建议大家争取在大学四年中积累编写十万行代码的经验。;;数据结构在计算机学科中的地位;;;所有能输入到计算机中去的描述客观事物的符号。

数值性数据：整数、实数等；

非数值性数据：字符、文本、声音、图像、视频等；

数据是计算机程序加工的原料，是信息的编码表示。;;;;数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。;数据元素之间的关系?结构

现实世界的结构是纷繁复杂的;数据结构的两个层次;逻辑结构与存储结构的关系;划分方法一;;存储结构;元素n;1536;逻辑结构和存储结构都相同，但运算不同，则数据结构不同。

例如，栈与队列。;数据类型决定了变量或常量的取值范围及可以对其进行的操作。;C语言;抽象数据类型(ADT:AbstractDataType);抽象数据类型的定义格式;;小结;小结;以下说法正确的是（）

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构;;抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。;抽象数据类型（概念层）;;(2)数据元素被约定为ElemType类型，用户需要根据具体情况

，自行定义该数据类型。;（4）内存的动态分配与释放

使用new和delete动态分配和释放内存空间：

分配空间指针变量=new数据类型;

释放空间delete指针变量;;（9）输入输出语句形式有：

输入语句cin(scanf);

输出语句cout(printf);

（10）扩展函数有：

求最大值max

求最小值min;;;;;;算法和算法分析;;算法的描述---流程图;;算法的描述---程序设计语言;算法的特性：;正确性;正确性;一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。

可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。

;算法应具有容错处理的功能，当输入的数据不合法或运行环境改变时，算法都能恰当地做出反应或进行处理，而不是产生莫名其妙的输出结果。

处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。;;;;;;;;;;算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n)=O(f(n))。

;;;;;;;算法的特性：;基本语句重复执行的次数;例4：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。

for(i=0;in;i++)

if(a[i]==e)returni+1;

return0;;时间复杂度（最好、最坏、平均）;;空间复杂度：算法所需存储空间的度量，记作:S(n)=O(f(n))

其中n为问题的规模(或大小)。;【算法