《数据结构》(C语言版)第一章_绪论.pptVIP

数据结构在计算机科学中的地位 数据结构是计算机软件和计算机应用专业的核心课程之一，由于在计算机系统软件和应用软件中都要用到各种数据结构，要想更有效地使用计算机，就必须学习数据结构的有关知识。 程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 数据结构在软件从业人员的知识与技能结构中的地位 任何受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会陌生，但是在实际的编程工作中，大部分的数据结构都不会用到，而且也永远都不会用到。虽然如此，深入地理解基本数据结构的概念和实现细节，仍然是每个程序员的任务。这不仅仅是因为，掌握这些知识将有利于更加正确和灵活地应用它们，而且也是因为，对于语言背后的实现细节的求知欲是一个优秀程序员的素质。 --摘自《最基础的数据结构》 第一章 绪论 §1.1 什么是数据结构 数据的逻辑结构：只抽象反映数据元素的逻辑关系。 时间复杂度随n变化情况的比较 ADT的表示和实现： 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数。 typedef struct { float realpart； float imagpart； }complex； // -----存储结构的定义 // -----基本操作的函数原型说明 void Assign( complex Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以 //参数 realval 和 imagval 的值 float GetReal( complex Z )； // 返回复数 Z 的实部值 float Getimag( complex Z )； // 返回复数 Z 的虚部值 void add( complex z1, complex z2, complex sum )； // 以 sum 返回两个复数 z1, z2 的和 // -----基本操作的实现 void add( complex z1, complex z2, complex sum ) { // 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; } { 其它省略 } 一、算法的定义 二、算法设计的原则 三、算法效率的衡量方法和准则 四、算法的存储空间需求 1.3 算法和算法分析 算法是对特定问题求解步骤的描述，是指令的有限序列。 1.有穷性 2.确定性 3.可行性 4.有输入 5.有输出 一、算法的定义 一个算法必须满足以下五个重要特性： 1.有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成。 2.确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。 3.可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 4.有输入：有零个或多个输入，取自特定的对象集合。 5.有输出：有一个或多个输出，是算法进行信息加工后得到的结果。 二、算法设计的原则 设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求 1.正确性：在合理的数据输入下，能在有限的运算时间内得到正确结果。 对算法是否“正确”的理解可以有以下四个层次： a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果； c．程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果； d．程序对于一切合法的输入数据都能得出满足要求的结果； 2.可读性：易于人对算法的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试； 3.健壮性：当输入的数据非法时，算法应当恰当地作出反映或进行相