数据结构与算法-概论

Ch1概论概论2/44课程性质“数据结构与算法”是计算机专业的核心课程之一，本科教学的重中之重。本课程上承“计算科学导论”与“程序设计”，下启“算法分析与设计”和“计算复杂性理论”，是操作系统、软件工程、数据库概论、编译技术、人工智能、计算机图形学等专业课程的必修先行课。所有应用软件都要使用到各种数据结构和算法编写程序。

概论3/44概论4/44课程重要性程序=数据结构+算法对清华大学计算机系历届毕业生和部分研究生追踪调查显示：几乎所有的学生都认为“数据结构”是他们在学校里学过的最有用的课程之一。

国内外许多软件开发机构要求考核的基本课程之一。公司面试或笔试考核的绝大部分内容是数据结构或算法。计算机科学与技术、软件工程等专业研究生考试必考科目。概论5/44教学目的程序=数据结构+算法基本的数据结构的逻辑结构、存储结构和数据的运算.算法设计和分析技术解决问题能力抽象能力：问题-数据-算法合理组织数据、有效表示数据、有效处理数据提高程序设计的质量概论6/44教材及参考书目教材张铭等著《数据结构与算法》高等教育出版社参考书严蔚敏等著《数据结构》清华大学出版社陈曙辉译《数据结构与算法-C++版》清华大学出版殷人昆著《数据结构》清华大学出版社概论7/44上机实验安排共18次（含考试2次）前八周6次上机，后八周12次具体时间另行通知上机考试第1次：每位同学随机抽取前8次上机题目之一，现场编程演示第2次：每位同学随机抽取后8次上机题目之一，现场编程演示概论8/44学习要求熟练掌握基本内容：熟知概念，理解算法，熟练编程，灵活使用－－上课＋上机学有余力的同学：扩展学习教材内容准备找工作的同学：大量编程准备考研的同学：我们的授课紧扣考研大纲，但请大家多做习题.概论9/44课程考核成绩评定:学期总评

=期末卷面成绩（占70%）+平时成绩（占30%）平时成绩：书面作业和上机作业20%；上机考试（考试共2次）10%助教:每小班一个助教，负责考勤、书面和上机作业批改，上机指导、答疑等。概论10/44具体要求作业：独立完成，作业纸干净、整齐上机要求：每次的上机任务当次完成，不能拖欠出勤要求：每天上课前5分钟助教点名三次缺勤取消考试资格两次迟到相当于一次缺勤勤学多练，独立完成作业，上机实验认真对待杜绝抄袭：发现抄袭和被抄袭者，本次上机作业双倍倒扣分三次被发现抄袭和被抄袭，取消考试资格概论11/44资料下载教学课件、上机题目等相关资料下载

概论12/44学习可能遇到的问题问题一：太抽象，听不懂建议：主动学习树立信心——高考都没打倒，上课小CASE预习——聪明鸟先飞早入林提问式学习——我遇到这样的问题，怎么解决？复习——总结、提高、实践请教老师、同学：会哭的孩子有奶吃，没人说你笨，别不好意思概论13/44学习可能遇到的问题问题二：算法思想能懂，但代码看不懂建议：多写多想多读代码——先弄懂思想，再看代码找个实例，手工执行代码上机调试，用不同的数据看输入输出经典代码要能写出来（不是背，是用自己的风格写）概论14/44学习可能遇到的问题问题三：不会编写代码，或代码质量不高建议：多写多练有思想，写不出代码——简化条件，先写简单的，再扩展边界处理不周到：举出各种出现边界情况的实例，抽象边界问题代码不清晰：学习养成好的编程风格概论15/44学习可能遇到的问题问题四：学习吃力，但不好意思问问题建议：锻炼开朗的性格交流、沟通是必要的素质情商比智商更重要虚心学习的人大家都欢迎前提：自己做了最大的努力概论16/44什么是数据结构用计算机解决一个具体的问题，需要以下几个步骤：从具体问题抽象出一个适当的数学模型；设计一个解此数学模型的算法；编出程序；进行测试、调整直至得到最终解答。寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。概论17/44什么是数据结构很多问题求解最后都转化为求解数学方程或数学方程组。如：求解梁架结构中应力的数学模型为线性方程组。预报人口增长情况的数学模型为微分方程。然而：当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。非数值计算问题的数学模型正是本课程要讨论的数据结构。概论18/44例1：计算机和人对奕问题。计算机可以根据当前棋盘格局，来预测棋局发展的趋势，甚至最后结局。数据结构:对弈树。O××O当前格局派生格局O××O××O××O×O××O×O××O×O××O概论19/44例2：地图的着色问题。对地图上的每个区域染一种颜色，并且要求相邻的两个区域不能具有相同颜色。数据结构:图。12435671234567红绿绿蓝红黑绿1243567用最少的颜色染色概论20/44例如例3：图书馆的书目检索自动化问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片概论21/44例如书目文件按书名按作者名按分类号索引表线性的数据结构概论22/44数学计算机硬件计算机软件数据结构数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。概论23/44数据结构数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。解决数值计算问题的中心:建立适当的数学模型。解决非数值计算问题的中心:寻找适当的数据结构。概论24/44数据结构研究的内容数据结构的讨论一般涉及以下三个方面的内容：1数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；2数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；3施加于该数据结构上的操作。概论25/44概论26/44逻辑结构（数据结构）相互之间存在一种或多种特定关系的数据元素的集合。元素（结点）类型：基本数据类型：整型、实型、布尔型……复合数据类型：数组、结构体、类概论27/44逻辑结构（数据结构）结点间的关系——结构先明确结点，再刻画结点之间的关系自顶向下的设计概论28/44集合线性结构树形结构图状结构（网状结构）概论29/44数据结构的形式定义数据结构的形式定义数据结构是一个二元组Data_Structure=(K,R)

其中，K是数据元素的有限集，R是K上关系的有限集。

例如：list=(K,R)

其中：K={1,2,3,4,5,6,7}

R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>}图形表示1234567概论30/44物理结构（存储结构）数据逻辑结构在计算机中的表示和实现。包含数据元素的表示和关系的表示。概论31/441.2.2数据的存储结构计算机的主存储器的特性其存储空间提供了一种具有非负整数地址编码的，相邻单元的集合，其基本的存储单元是字节计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同概论32/44数据元素的表示数据元素的表示:

通常用位串表示一个数据元素例，用八位表示一个字符、三十二位表示一个整数请问:

在C++语言中表示一个学生的基本信息(姓名、年龄、性别)，最少需要多少位？概论33/44数据元素之间关系的表示顺序存储结构结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。链式存储结构不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的。

概论34/44顺序（sequential）的方法用一块无空隙的存储区域存储数据称为顺序存储顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑后继关系用存储单元的自然顺序关系来表达顺序存储法为使用整数编码来访问数据结点提供了便利概论35/44元素n……..元素i……..元素2元素1存储内容LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址顺序存储结构概论36/44链接（linked）的方法利用指针，在结点的存储结构中附加指针字段称为链接法。两个结点的逻辑后继关系可以用指针的指向来表达任意的逻辑关系r，也可以使用这种指针地址来表达。一般的做法是将数据结点分为两部分:一部分存放结点本身的数据，称为数据字段另一部分存放指针，称指针字段，链接到某个后继结点，指向它的存储单元的开始地址。多个相关结点的依次链接就会形成链索概论37/441536元素21536元素21346元素31346元素3∧元素4∧元素4存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素313461400元素1h1400元素1h链式存储结构概论38/44索引（indexing）的方法索引法是顺序存储法的一种推广，它也使用整数编码来访问数据结点位置索引方法是要建造一个由整数域Z映射到存储地址域D的函数Y：Z

D，把结点的整数索引值

z∈Z映射到结点的存储地址

d∈D。它称为索引函数，一般而言它并不象数组那样，是简单的线性函数。概论39/44索引（indexing）的方法概论40/44散列（hashing）的方法散列方法是索引方法的一种延伸和扩展利用一种称为散列函数(hashfunctions)

进行索引值的计算，然后通过索引表求出结点的指针地址散列函数是将字符串s映射到非负整数z的一类函数h:S

Z，对任意的s∈S，散列函数h(s)=z，z∈Z概论41/44逻辑结构与存储结构数据的逻辑结构与存储结构密切相关算法设计取决于选定的逻辑结构。算法实现依赖于采用的存储结构。概论42/44

数据的逻辑结构

数据的存