数据结构和算法课件_数据结构

数据结构与算法For软件学院08级本科生2009-2010秋Ch1概论刘馨月[e-mail]概论2/31课程性质与教学目的•计算机科学中一门综合性的专业基础课，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。•深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，•培养基本的、良好的程序设计技能，编制高效可靠的程序概论3/31课程重要性•程序=数据结构+算法•本课程为后续课程提供了必要的知识基础。先修课程：高级语言程序设计（C/C++）、离散数学后续课程：操作系统、数据库原理、编译原理等•对清华大学计算机系历届毕业生和部分研究生追踪调查显示：几乎所有的学生都认为“数据结构”是他们在学校里学过的最有用的课程之一。国内外许多软件开发机构要求考核的基本课程之一。公司面试或笔试考核的绝大部分内容是数据结构或算法。计算机科学与技术、软件工程等专业研究生考试必考科目。概论4/31基本要求•掌握常用的数据结构的逻辑结构、存储结构和数据的运算.•掌握在各种常用的数据结构上实现的排序和查找运算。•对算法的时间和空间复杂性有一定的分析能力。•针对应用问题，应能选择合适的数据结构及设计有效的算法解决。概论5/31教材及参考书目•教材–许卓群等著《数据结构与算法》高等教育出版社•参考书–严蔚敏等著《数据结构》清华大学出版社–陈曙辉译《数据结构与算法-C++版》清华大学出版–殷人昆著《数据结构》清华大学出版社概论6/31本次课程的特点•与配合•CMU的一套SSD–CarnegieMellonUniversity–SoftwareSystemsDevelopmentCourse–大量的练习–软件工程师的摇篮概论7/31上机实验安排•12，13，14，15，17，19周，共六周•每周三次•12，17，19周周日测试概论8/31学习要求•熟练掌握基本内容：熟知概念，理解算法，熟练编程，灵活使用－－上课＋上机•学有余力的同学：扩展学习教材内容•准备找工作的同学：大量编程•准备考研的同学：在基本内容的基础上，针对目标学校适当扩展.概论9/31课程考核•成绩评定:–学期总评=期末卷面成绩（占60%）+平时成绩（占40%）–平时成绩：书面作业和出勤、回答问题等情况占10%；上机实验占20%（包括上机出勤、上机练习完成情况）；上机考试占10%（考试共三次）–助教:每小班一个助教，负责考勤、书面和上机作业批改，上机指导、答疑等。概论10/31助教联系方式徐子川[e-mail]0805班高亮[e-mail]0806班李洁[e-mail]0807班吴尧[e-mail]0808班张俊[e-mail]0818班王亮[e-mail]0819班朱少萍[e-mail]0820班概论11/31具体要求•作业：–独立完成，作业纸干净、整齐•上机要求：–每次的上机任务当次完成，不能拖欠•出勤要求：–每天上课前5分钟助教点名，三次缺勤取消考试资格–两次迟到相当于一次缺勤•勤学多练，独立完成作业，上机实验认真对待。概论12/31什么是数据结构用计算机解决一个具体的问题，需要以下几个步骤：从具体问题抽象出一个适当的数学模型；设计一个解此数学模型的算法；编出程序；进行测试、调整直至得到最终解答。寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。概论13/31什么是数据结构•很多问题求解最后都转化为求解数学方程或数学方程组。•如：求解梁架结构中应力的数学模型为线性方程组。•预报人口增长情况的数学模型为微分方程。•然而：当计算机进入非数值计算领域，特别是用在管理上的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。非数值计算问题的数学模型正是本课程要讨论的数据结构。概论14/31例1：计算机和人对奕问题。计算机可以根据当前棋盘格局，来预测棋局发展的趋势，甚至最后结局。数据结构:对弈树。O××O当前格局派生格局O××O××O××O×O××O×O××O×O××O概论15/31例2：地图的着色问题。对地图上的每个区域染一种颜色，并且要求相邻的两个区域不能具有相同颜色。数据结构:图。12435671234567红绿绿蓝红黑绿1243567用最少的颜色染色概论16/31例如例3：图书馆的书目检索自动化问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片概论17/31例如001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001，003……理论力学002，……..线性代数004，………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性的数据结构概论18/31数学计算机硬件计算机软件数据结构数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。概论19/31数据结构•数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。–解决数值计算问题的中心:建立适当的数学模型。–解决非数值计算问题的中心:寻找适当的数据结构。概论20/31数据结构研究的内容•数据结构的讨论一般涉及以下三个方面的内容：1数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；2数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；3施加于该数据结构上的操作。概论21/31逻辑结构（数据结构）•相互之间存在一种或多种特定关系的数据元素的集合。•四类基本结构：•集合•线性结构•树形结构•图形结构概论22/31集合线性结构树形结构图状结构（网状结构）概论23/31数据结构的形式定义•数据结构的形式定义–数据结构是一个二元组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概论24/31物理结构（存储结构）•数据逻辑结构在计算机中的表示和实现。•包含数据元素的表示和关系的表示。概论25/31数据元素的表示•数据元素的表示:通常用位串表示一个数据元素–例，用八位表示一个字符、三十二位表示一个整数请问:在C++语言中表示一个学生的基本信息(姓名、年龄、性别)，最少需要多少位？概论26/31数据元素之间关系的表示•顺序存储结构–结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。•链式存储结构–不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的。概论27/31元素n……..元素i……..元素2元素1存储内容LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址顺序存储结构概论28/311536元素21536元素21346元素31346元素3∧元素4∧元素4存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素313461400元素1h1400元素1h链式存储结构概论29/31逻辑结构与存储结构数据的逻辑结构与存储结构密切相关•算法设计取决于选定的逻辑结构。•算法实现依赖于采用的存储结构。概论30/31数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图形结构数据结构研究内容一览概论31/31•数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。•数据的存储结构是数据逻辑结构在计算机中的映象，有两类存储结构：顺序存储结构，链式存储结构。小结