数据结构CC++第一章绪论

1、数据结构,第一章 绪论,第一章 绪论,知 识 点 数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法复杂性的分析方法 要 求 了解数据的逻辑结构和物理结构，算法的基本概念，它们对于程序设计的重要性以及相互关系 掌握算法复杂性的概念及分析方法,第一章目录,1.1 基本概念 1.2 算法的描述 1.3 算法的评价 1.4 应用举例及分析 小 结 习题与练习,分析程序处理的数据的特性及数据之间的关系，这就是“数据结构”这门学科形成和发展的背景。 数据结构主要研究非数值应用问题中数据之间的逻辑关系和对数据的操作，同时还研究如何将具有逻辑关系的数据按一定的存储方式存放在计算机内。 例: 某

2、单位职工档案的管理。 图1.1中的职工档案表就是一个数据结构。如果把表中的一行看成一个记录并称为一个结点，则在此表中，结点和结点之间的关系是一种最简单的线性关系。,某学校教师的名册。虽然可以用例1.1中的二维表格将全校教师的名单列出，但采用图1.2所示的结构更好。它像一棵根在上而倒挂的树，清晰地描述了教师所在的系和教研组，这样一来可以从树根沿着某系某教研组很快找到某个教师，查找的过程就是从树根沿分支到某个叶子的过程。,例 在n个城市之间建立通信网络，要求在其中任意两个城市之间都有直接的或间接的通信线路，在已知某些城市之间直接通信线路预算造价的情况下，使网络的造价最低。,通过上面三个例子可以看出

3、：数据结构中元素和元素之间存在着逻辑关系，而线性表，树，图是三种基本的逻辑结构，其他各类的数据结构都是由这三种基本结构派生的。 数据结构就是解决如何分析数据元素之间的关系、如何确立合适的逻辑结构、如何存储这些数据，并对为完成数据操作所设计的算法做出时间和空间的分析。 “数据结构”在计算机科学中是一门综合性的专业基础课，它不仅是一般程序设计(特别是非数值计算的程序设计)的基础，而且也是设计和实现编译程序、操作系统、数据库系统及大型应用程序的重要基础。,1.1 基本概念(1),数据(Data)：一切能够由计算机接受和处理的对象。 数据元素(Data element)：是数据的基本单位，在程序中作为

4、一个整体加以考虑和处理。 数据项(Data item)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。,1.1 基本概念(2),数据结构(Data structure)：数据之间的相互关系，即数据的组织形式。 研究数据结构，是指研究数据的逻辑结构和物理结构 数据的逻辑结构：数据元素之间的逻辑关系 数据的物理结构：数据元素在计算机存储器中是如何存储的,四类基本逻辑结构的示意图,定义一组有关数据元素的运算。在讨论各种数据结构时，针对其逻辑结构和具体的存储结构给出对应的数据类型，进一步在确定的数据类型上实现各种操作。,数据的存储结构是逻辑结构在计算机存储器中的实现。数据元素在计算机

5、中主要有两种不同的存储方法：顺序存储结构和链式存储结构。,顺序存储的特点是在内存中开辟一组连续的空间(高级语言中的数组)来存放数据。 链式存储的特点是通过指针反映数据元素之间的逻辑关系，又称动态存储。,1.1 基本概念(3),算法(Algorithm)：对特定问题求解步骤的一种描述。 程序 = 数据结构 + 算法”。 算法是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。 由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。,返回,1.2 算法的描述,1、框图算法描述：这种描述方法在算法研究的早期曾流行过。它的优点是直观、易懂，但用来

6、描述比较复杂的算法就显得不够方便，也不够清晰简洁。 例：求两个整数m,n(mn)的最大公因子,算法的描述方法有很多，根据描述算法语言的不同，可将算法分为以下四种：,2、非形式算法描述 ： 用中文语言，同时还使用一些程序设计语言中的语句来描述算法，这称为非形式算法描述。,a. 求余数 以n 除m， 并令r为余数 (0 r n)； b. 余数是零否 若r = 0 则结束算法，n 就是最大公因子； c. 替换并返回a 若r 0 则m n, n r返回 a。,例：求两个整数m,n(mn)的最大公因子,3、C语言描述： 这是可在计算机上运行并获得结果的算法，使给定问题能在有限时间内被求解，通常这种算法也

7、称程序。 本书将采用C语言描述算法，所有算法都以如下所示的函数形式表示： 函数类型 函数名（参数表） 语句序列 例：求两个整数m,n(mn)的最大公因子 int max_common_factor (int m, int n) int r ; r = m % n; while (r != 0) m = n ; n = r ; r = m % n; return n ;,1.3.1 评价算法的一般原则,正确性：算法应能正确地实现处理要求 。 易读性：有助于对算法的理解，便于纠正和扩充 。 简单性：使证明其正确性比较容易，对算法进行修改也比较方便。 高效率：达到所需的时、空性能。,1.3.2 算法

8、复杂性的分析,算法的复杂性包括时间复杂性（所需运算时间）和空间复杂性（所占存储空间) 。 一个算法所需的运算时间通常与所解决问题的规模大小有关。是该算法中所有语句执行次数之和。 用n 表示问题规模的量 ，把算法运行所需的时间T表示为n的函数，记为T(n)。 时间复杂性：当n逐渐增大时T(n)的极限情况，一般简称为时间复杂性。 时间复杂性常用数量级的形式来表示，记作T(n)=O(f(n)。 其中，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。,算法的运行时间往往还与具体输入的数据有关，通常用以下两种方法来确定一个算法的运算时间： 1. 平均时间复杂性：研究同

9、样的n值时各种可能的输入，取它们运算时间的平均值。 2. 最坏时间复杂性：研究各种输入中运算最慢的一种情况下的运算时间。,例1.1,计算下面交换i和j内容程序段的时间复杂性。 temp=i; i=j; j=temp; 解：以上三条单个语句均执行1次，该程序段的执行时间是一个与问题n无关的常数，因此，算法的时间复杂度为常数阶,记作T(n)=O(1).,例1.2,计算下面求累加和程序段的时间复杂性 （1） sum=0； （一次） （2） for(i=1;i=n;i+) （n次 ） （3） for(j=1;j=n;j+) （n2次 ） （4） sum+； （n2次 ） 解：T(n)=2n2+n+1 =O(n2) 当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。,返回,一般地，对于足够大的n，常用的时间复杂性存在以下顺序： O(1) O(logn) O(n) O(n*logn) O(n2) O(n3)O(2n)O(3n)O(n!) 其中,O(1)为常数数量级,小 结,本章介绍了贯穿全书的基本概念和基本思想。 数据 数据结构 逻辑结构 物理结构 算法 算法的时间复杂性,返回,试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。,实验目的： 了解程序设计的一般步骤 实验要求： 1、掌握C语言算法的