数据结构0学习方法与概念

1、讲师：尹成QQ:77025077博客:http:/ 传智播客传智播客http:/高薪就业高薪就业第0章 学习方法与概念概述概 论3/44课程性质课程性质m“数据结构与算法”是计算机专业的核心课程之一，本科教学的重中之重。m本课程q上承“程序设计”，q下启“算法分析与设计 ，q是操作系统、软件工程、数据库概论、编译技术、人工智能、计算机图形学等专业课程的必修先行课。m所有应用软件都要使用到各种数据结构和算法编写程序。 概 论4/44概 论5/44m程序 = 数据结构 + 算法m对清华大学计算机系历届毕业生和部分研究生追踪调查显示：几乎所有的学生都认为“数据结构”是他们在学校里学过的最有用的课程之

2、一。 国内外许多软件开发机构要求考核的基本课程之一。 公司面试或笔试考核的绝大部分内容是数据结构或算法。 计算机科学与技术、软件工程等专业研究生考试必考科目。概 论6/44教学目的教学目的m程序=数据结构+算法q基本的数据结构的逻辑结构、存储结构和数据的运算.q算法设计和分析技术m解决问题能力q抽象能力：问题-数据-算法q合理组织数据、有效表示数据、有效处理数据m提高程序设计的质量概 论7/44学习要求m熟练掌握基本内容：熟知概念，理解算法，熟练编程，灵活使用上课上机m学有余力的同学：扩展学习教材内容m准备找工作的同学：大量编程概 论8/44学习可能遇到的问题m问题一：太抽象，听不懂m建议：主

3、动学习q树立信心活着没打到，上课小CASEq预习聪明鸟先飞早入林q提问式学习我遇到这样的问题，怎么解决？q复习总结、提高、实践q请教老师、同学：会哭的孩子有奶吃，没人说你笨，别不好意思概 论9/44学习可能遇到的问题m问题二：算法思想能懂，但代码看不懂m建议：多写多想q多读代码先弄懂思想，再看代码q找个实例，手工执行代码q上机调试，用不同的数据看输入输出q经典代码要能写出来（不是背，是用自己的风格写）概 论10/44学习可能遇到的问题m问题三：不会编写代码，或代码质量不高m建议：多写多练q有思想，写不出代码简化条件，先写简单的，再扩展q边界处理不周到：举出各种出现边界情况的实例，抽象边界问题q

4、代码不清晰：学习养成好的编程风格概 论11/44学习可能遇到的问题m问题四：学习吃力，但不好意思问问题m建议：锻炼开朗的性格q交流、沟通是必要的素质q情商比智商更重要q虚心学习的人大家都欢迎q前提：自己做了最大的努力概 论12/44什么是数据结构什么是数据结构用计算机解决一个具体的问题，需要以下几个步骤：q 从具体问题抽象出一个适当的数学模型；q 设计一个解此数学模型的算法；q 编出程序；q 进行测试、调整直至得到最终解答。寻求数学模型的实质：寻求数学模型的实质： 分析问题，从中分析问题，从中提取操作的对象提取操作的对象，并找出这些，并找出这些操作对象之操作对象之间含有的关系间含有的关系，然后

5、用，然后用数学的语言加以描述数学的语言加以描述。概 论13/44什么是数据结构什么是数据结构m很多问题求解最后都转化为求解数学方程或数学方程组。m如：求解梁架结构中应力的数学模型为线性方程组。m预报人口增长情况的数学模型为微分方程。m然而：当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。非数值计算问题的数学模型正是本课程要讨论的数据结构。非数值计算问题的数学模型正是本课程要讨论的数据结构。概 论14/44例例1：计算机和人对奕问题。计算机和人对奕问题。计算机可以根据当前棋盘格局，来预测棋局发展的趋计算机可以根据当前棋盘格局，来预测棋局发

6、展的趋势，甚至最后结局。势，甚至最后结局。数据结构数据结构:对弈树对弈树。OO当前格局当前格局派生格局派生格局OOOOOOOOOO概 论15/44例例2：地图的着色问题。地图的着色问题。对地图上的每个区域染一种颜色，并且要求相邻的两对地图上的每个区域染一种颜色，并且要求相邻的两个区域不能具有相同颜色。个区域不能具有相同颜色。数据结构数据结构:图图。12435671234567红红绿绿绿绿蓝蓝红红黑黑绿绿1243567用最少的颜色染色用最少的颜色染色概 论16/44例例3 3：图书馆的书目检索自动化问题：图书馆的书目检索自动化问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片概

7、 论17/44例如例如书目文件按书名按作者名按分类号索引表线性的数据结构线性的数据结构概 论18/44数学数学计算机计算机硬件硬件计算机计算机软件软件数据数据结构结构数据结构是介于数学、计算机硬件和计算机软件三者之间的一门数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程核心课程。概 论19/44数据结构m数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。q解决数值计算问题的中心: 建立适当的数学模型。q解决非数值计算问题的中心: 寻找适当的数据结构。概 论20/44m数据结构的讨论一般涉及以下三个方面的内容：1 数据成员以及它们相互之

8、间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；2 数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；3 施加于该数据结构上的操作。概 论21/44概 论22/44逻辑结构（数据结构）m相互之间存在一种或多种特定关系的数据元素的集合。m元素（结点）类型：q基本数据类型：整型、实型、布尔型q复合数据类型：数组、结构体、类概 论23/44逻辑结构（数据结构）m结点间的关系结构q先明确结点，再刻画结点之间的关系q自顶向下的设计概 论24/44集合集合线性结构线性结构树形结构树形结构图状结构图状结构（网状结构）（网状结构）概 论25/44数据结构的形式定义m数据结构

9、的形式定义q数据结构是一个二元组 Data_Structure=(K,R) 其中，K是数据元素的有限集，R是K上关系的有限集。 例如：list=(K,R) 其中：K=1,2,3,4,5,6,7 R=,图形表示图形表示1234567概 论26/44物理结构（存储结构）m数据逻辑结构在计算机中的表示和实现。m包含数据元素的表示和关系的表示。概 论27/441.2.2 数据的存储结构m计算机的主存储器的特性q其存储空间提供了一种具有非负整数地址编码的，相邻单元的集合，其基本的存储单元是字节q计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同 概 论28/44数

10、据元素的表示m数据元素的表示: 通常用位串表示一个数据元素q例，用八位表示一个字符、三十二位表示一个整数请问: 在C+语言中表示一个学生的基本信息(姓名、年龄、性别)，最少需要多少位？概 论29/44数据元素之间关系的表示m顺序存储结构q结点间的逻辑关系由存储单元的邻接关系来体现。 通常顺序存储结构是借助于语言的数组来描述的。m链式存储结构q不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的。 概 论30/44顺序（sequential）的方法 m用一块无空隙的存储区域存储数据称为顺序存储m顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑后继关系用存储

11、单元的自然顺序关系来表达 m顺序存储法为使用整数编码来访问数据结点提供了便利 概 论31/44元素n.元素i.元素2元素1存储内容存储内容LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址顺序存储结构概 论32/44链接（linked）的方法 m利用指针，在结点的存储结构中附加指针字段称为链接法。两个结点的逻辑后继关系可以用指针的指向来表达m任意的逻辑关系r，也可以使用这种指针地址来表达。一般的做法是将数据结点分为两部分:q一部分存放结点本身的数据，称为数据字段q另一部分存放指针，称指针字段，链接到某个后继结点，指向它的存储单元的开始地址。多个相关结点的依次链接就会形成链索概

12、 论33/441536元素21536元素21346元素31346元素3 元素4 元素4存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 13461400元素1h1400元素1h链式存储结构概 论34/44索引（indexing）的方法 m索引法是顺序存储法的一种推广，它也使用整数编码来访问数据结点位置m索引方法是要建造一个由整数域Z映射到存储地址域D的函数Y：ZD，把结点的整数索引值 zZ映射到结点的存储地址 dD 。它称为索引函数，一般而言它并不象数组那样，是简单的线性函数。概 论35/44索引（in

13、dexing）的方法概 论36/44散列（hashing）的方法 m散列方法是索引方法的一种延伸和扩展m利用一种称为散列函数(hash functions)进行索引值的计算，然后通过索引表求出结点的指针地址m散列函数是将字符串s映射到非负整数z的一类函数h: S Z ， 对任意的 s S，散列函数 h(s)=z，z Z概 论37/44逻辑结构与存储结构数据的逻辑结构与存储结构密切相关m算法设计取决于选定的逻辑结构。m算法实现依赖于采用的存储结构。概 论38/44 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等