清华大学《数据结构与算法》赵玉兰等编著第1章

本文由1990sunshuai贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。计算机专业本科主干基础课数据结构与算法DATASTRUCTUREANDARITHMETIC1数据结构与算法——C++描述教材赵玉兰等编著清华大学出版社2参考书目1.《数据结构》1.《数据结构》（C语言版）严蔚敏吴伟民编著语言版）清华大学出版社2.《数据结构》2.《数据结构》殷人昆等编著清华大学出版社3.《数据结构与算法》张铭、王腾蛟、3.《数据结构与算法》张铭、王腾蛟、赵海燕编著高等教育出版社4.《4.《ComputerAlgorithms–IntroductiontoDesignandAnalysis》Analysis》Sarabase高等教育出版社影印Algorithms》5.《DataStructuresandAlgorithms》AlfredV.Aho6.《数据结构》刘大有，唐海鹰等著高等教育出版社数据结构》刘大有，7.网上阅读材料……3作业1、书面作业：习题或课堂小测验、书面作业：?2、上机实验：从第三周起每周2次.、上机实验：从第三周起每周次4考核方式总成绩:书面作业、总成绩书面作业、出勤占10%上机实验占20%~25%期末考试成绩占65%~70%5第1章章1.11.21.31.41.51.61.7概述数据结构的发展数据结构数据的逻辑结构抽象数据类型数据的存储结构算法与算法分析ADT的表示与实现间的关系的表示与实现间的关系61.1数据结构的发展早期：早期：1946年，数值计算年如：弹道计算v0,α,…矩阵运算M1*M2*M3…*Mn函数计算y=f(x)方程组求解定积分∫152(3x+5x)dx271.1数据结构的发展早期数据的特点:早期数据的特点:数据量少，计算比较复杂，数据量少，计算比较复杂，当时人们只注重求解方法，方法，并不注重数据的组织。在这一阶段，数据结构》在这一阶段，《数据结构》还未形成一门系统的学科，而是零星地分布在程序设计、图论、集合、学科，而是零星地分布在程序设计、图论、集合、代数、操作系统和编译原理等课程中。操作系统和编译原理等课程中。81.1数据结构的发展中期：70’s80’s中期：70s-80s非数值计算猛增70’s80’s90’s91.1数据结构的发展非数值数据的特点：非数值数据的特点：数据量大，计算比较简单。数据量大，计算比较简单。人们不得不把注意力集中于分析数据间的关系、人们不得不把注意力集中于分析数据间的关系、数据的组织形式和数据的表示方法。数据的组织形式和数据的表示方法。70年代中期《数据结构》形成了一门课程。70年代中期《数据结构》形成了一门课程。年代中期101.1数据结构的发展目前：计算机应用领域不断扩大，目前：计算机应用领域不断扩大，信息量越来越大，问题越来越复杂。越大，问题越来越复杂。它们的特点是数据量异常庞大;它们的特点是数据量异常庞大;关系十分复杂;关系十分复杂;因此不仅要注重求解方法,而且要注重数据因此不仅要注重求解方法,而且要注重数据求解方法间的关系。间的关系。两者不可偏废一者。两者不可偏废一者。11课程介绍地位:数学、软件、地位:数学、软件、硬件之间相关的课程数学代数系统离散数学程序设计编码理论算子关系操作系统数据类型数据表示数据运算编译原理硬件数据结构软件数据库数据存储文件系统存储装置…机器组织系统设计是核心专业基础课！是核心专业基础课！数据组织信息检索程序设计121.2数据结构例1.1电话号码本1电话号码本党政机关党政机关党政机关党政机关6845678是谁的电是谁的电太难找了！话？太难找了！大专院校大专院校大专院校大专院校党委总机4811122党委总机4811122党委总机4811122党委总机4811122宣传部4811234宣传部4811234宣传部48112344811234宣传部组织部4812345组织部4812345组织部48123454812345组织部内蒙古大学内蒙古大学内蒙古大学内蒙古大学校务办公室4991234校务办公室4991234校务办公室4991234校务办公室4991234计算机学院4992930计算机学院4992930计算机学院4992930计算机学院4992930131.2数据结构电话号码结构：电话号码结构：按照单位排列电话号码呼和浩特市电话号码簿党政机关医疗卫生交通运输大专院校内蒙古党委内蒙古政府内蒙古大学内蒙古工业大学理工学院计算机学院计算机系网络中心计算中心14电话号码结构：电话号码结构：按电话号码的大小排列电话号码本2电话号码本党政机关党政机关党政机关110…………匪警党委总机48111226845678是老朋友是老朋友Tom的电话？太的电话？的电话容易找了！容易找了！大专院校1234567….大专院校大专院校内蒙古大学内蒙古大学…….内蒙古大学党委总机4811122党委总机4811122宣传部4811234119………火警宣传部4811234宣传部4811234组织部4812345120………急救组织部4812345组织部4812345校务办公室4991234校务办公室4991234校务办公室49912346845678….Tom计算机学院4992930计算机学院4992930计算机学院4992930………数据的安排直接影响到工作效率。数据的安排直接影响到工作效率。15例1.2假设要在n个城市之间建立通信联络网，连通假设要在个城市之间建立通信联络网，连通n个城市个城市之间建立通信联络网最少需要n-1条线路，如何在最节省经费的前提下建立条线路，最少需要条线路这个通信网。这个通信网。281101421662472518312522416例1.3A,B,C,D4个球队进行循环比赛，规定一个队在一天个球队进行循环比赛，个球队进行循环比赛中最多进行一场比赛，和已进行过比赛已进行过比赛，中最多进行一场比赛，C和D已进行过比赛，问至少还需比赛几天？需比赛几天？场比赛：解：因为还有5场比赛：AB,AC,AD,BC,BD。因为还有场比赛。每一场比赛表示图中的一个顶点。每一场比赛表示图中的一个顶点。如边(AB,AC)表示和AC不能在同一天进行。表示AB和不能在同一天进行不能在同一天进行。如边表示AB关系图见图，从图可以看出，关系图见图，从图可以看出，实线连AC接的顶点表示不可以同一天举行比赛，接的顶点表示不可以同一天举行比赛，由虚线连接的顶点表示比赛可以在同一BC天举行，天举行，所以四个球队进行的循环赛至AD少需要三天:少需要三天AB，AC—BD，AD—BC。球队比赛图17，，。BD基本概念数据(Data)：：数据能被计算机表示、存储和加工处理的一切信息。能被计算机表示、存储和加工处理的一切信息。18基本概念数据元素(DataElement)：数据元素：数据的基本单位，相对独立，通常作为一个整体看待。数据的基本单位，相对独立，通常作为一个整体看待。例1.3姓名王小林陈红刘建平……..学生信息登记表性别男女男…….年龄182019…….民族汉族蒙族回族……系计算机计算机计算机……专业计算机科学计算机应用电子商务入学时间2006,92006,92006,9…….学号060631060632060633……..每一行是一个数据元素，学生数据元素的集合是一个数据对象.每一行是一个数据元素，学生数据元素的集合是一个数据对象数据元素是一个数据对象19基本概念数据项(DataItem)：数据项：组成数据元素的不可分割的最小单位。组成数据元素的不可分割的最小单位。如：学号，姓名，年龄…学号，姓名，年龄姓名王小林陈红刘建平学号060631060632060633性别男女男年龄182019民族汉族蒙族回族系计算机计算机计算机专业计算机科学计算机应用电子商务入学时间2006,92006,92006,9……..……..…….…….……………….每一列是一个数据项每一列是一个数据项是一个20基本概念数据对象(DataObject)：数据对象：性质相同的数据元素的集合。性质相同的数据元素的集合。是一个数据对象.如{‘A’,’B’,…’Z’,’a’,’b’,…,’z’}是一个数据对象‘是一个数据对象{0,±1,±2,±3,……,±n,……}是一个数据对象。21基本概念数据类型(DataType)：数据类型：指定一种数据对象的类型.指定一种数据对象的类型字母数据对象.包括包括{‘如字母数据对象包括‘A’,’B’,…’Z’,’a’,’b’,…,’z’}整数数据对象.包括包括{0,1,如整数数据对象.包括{0,±±2,±3,…,±n}定义为一个值的集合以及定义在该值集合上的一值的集合以及定义在该值集合上的定义为一个值的集合以及定义在该值集合上的一组操作的总称操作的总称.的总称22基本概念整型实型字符型枚举型指针型基本类型C++语言的数据类型语言的数据类型结构类型数组型结构型共用体类23数据结构的概念：数据结构的概念：数据结构研究的对象包括三个方面:数据结构研究的对象包括三个方面数据的逻辑结构指数据之间的逻辑关系,即指数据元素之间的关联方指数据之间的逻辑关系式或邻接关系。式或邻接关系。数据的存储结构指数据在计算机中存储的位置，指数据在计算机中存储的位置，如某个电话号码在号码本上的位置。号码本上的位置。运算的集合定义在逻辑结构上的一组操作。定义在逻辑结构上的一组操作。如输入/读取检索/查找插入、删除、更新等。读取、逻辑关系组织起来的一批数据查找、如输入读取、检索查找、插入、删除、更新等数据结构:按照某种逻辑关系组织起来的一批数据,按一数据结构:按照某种逻辑关系组织起来的一批数据。定的存储方法把它存储在计算机中,定的存储方法把它存储在计算机中并在这些数据上定存储方法把它存储在计算机中24义了一个运算的集合运算的集合.义了一个运算的集合1.3数据的逻辑结构1.3根据数据元素间的不同特性,通常有以下4种基本逻辑结构种基本逻辑结构：根据数据元素间的不同特性通常有以下种基本逻辑结构：1.线性结构逻辑结构2.集合3.树型结构4.图型或网状结构非线性结构数据元素间的逻辑结构可形式描述为：数据元素间的逻辑结构可形式描述为：结构可形式描述为DS=(D,R)其中：是数据元素的有限集合；其中：D是数据元素的有限集合；R是D上的关系有限集合；上的关系有限集合；是上的关系有限集合251.3数据的逻辑结构1.3线性结构(LinearStructure)：LS=(D,R)线性结构：D={d1,d2,…,dn}R={di,di+1|i=1,2,3,…,n-1}例1.4：DS=(D,R1)：线性结构的特点：线性结构的特点：特点结构中的数据元素具有D={d1,d2,d3,d4,d5,d6}一对一”“一对一”的关系R1={d1,d2,d2,d3,d3,d4,d4,d5,d5,d6}d1d2d3d4线性结构d5d6261.3数据的逻辑结构1.3集合例1.5DS=(D，R2)，D={d1,d2,d3,d4,d5,d6}d1∈D,d2∈D,d3∈D,d4∈D,d5∈D,d6∈Dd1d4d2d5d3集合特点：集合特点：d6集合结构中的数据元素只具有同属于一个集合”“同属于一个集合”的关27系1.3数据的逻辑结构1.3树型结构例1.6：DS=(D,R3)D={d1,d2,d3,d4,d5,d6,d7}R3={d1,d2,d1,d3,d3,d7,d2,d4,d2,d5,d2,d6}281.3数据的逻辑结构1.3d1d2d3d7根结点:无前驱的结点，根结点无前驱的结点，无前驱的结点如d1叶结点:无后继的结点，叶结点无后继的结点，如d4,d5,d6,d7树型结构的特点：树型结构的特点：有且仅有一个根结点，有且仅有一个根结点，其它结点有且仅有一个前驱结点，前驱结点，对于非根结点都存在从根到该结点的一条路径。的一条路径。结构中的数据元素存在一对多的关系存在一对多的关系一对多29d4d5d6树型结构1.3数据的逻辑结构1.3图型或网状结构例1.7：DS=(