(c语言详细版)第一章什么是数据结构.ppt

第一章绪论重点:数据结构的基本概念难点:ADT、算法复杂度-1--2-,二十世纪四十年代,电子数字计算机问世的直接原因是解决弹道学的计算问题。在电子计算机发展的初期阶段,人们用计算机主要处理数值计算问题,用以解决人们用手工或机械计算机难以胜任的数值计算。当时涉及的数据对象还比较简单,不外乎是整型、实型、布尔型等。——数学软件。随着计算机使用领域的扩大和深入,解决“非数值性问题”越来越引起人们的重视和关注。例如:-3- 神经元和模式识别网络与通信图形化用户界面等等-4-,而更多地用到离散数学和计算机的有关知识,所涉及的对象也更为复杂,其突出的特点是:数据元素之间所具有的特定联系已不能用分析数学的方程式来简单描述。现代计算机科学的观点,计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题:-5- 信息的表示直接关系到处理信息的程序的效率。随着计算机的普及,信息量的增加,信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂。因此,为了编写出一个“好”的程序,必须分析待处理的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题。-6-·E·Knuth发表:“puterprogramming”IEEE68教程1983IEEE83教程1991IEEE91教程2000IEEE2000教程国内在78年开设、相应地有93教程等。计算机科技的两大支柱Algorithm+DataStructures=Programs——NiklausWirthAlgorithm:求解问题的策略DS: 问题的数学模型Programs:为计算机处理问题编制的一组指令-7-:银行帐号共100000个如图所示,组成一个顺序存储的结构,存于计算机之中。插入新帐号45怎样进行呢?插入新帐号45:1、查找位置2、移表3、插入合适位置移动一个结点,需100us,移动100000个结点需100us×100000=10秒。每天处理10000个帐号,需30小时,无法接受。如何快速地进行插入?节省访问外存的时间,是一个很重要的问题。-8-:1、“数据结构”在计算机科学中是一门综合性的专业基础课。2、数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3、数据结构这一门课的内容不仅是一般程序设计(特别是非数值性程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。-9-,要想有效地使用计算机,仅掌握计算机语言而缺乏数据结构和算法的有关知识,难以应付众多复杂的应用课题。-10-