数据结构（C语言描述）

《数据结构（C语言描述）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构（C语言描述）计算机系刘延芳10/4/2021第一章绪论1.1引言1.2数据结构发展简史及学科地位1.3什么是数据结构1.4基本概念和术语1.5算法概念、算法的描述和算法评价练习2:38AM引言20世纪40年代(1946),为了解决弹道轨迹计算问题而产生计算机。早期，计算机应用范围局限于科学和工程计算,处理对象是纯数值性信息,人们称这类问题为“数值计算”。如今,计算机应用远远超出数值计算范围,渗透人类生活的一切领域。计算机处理对象也从纯数值发展到非数值性和具有一定结构的信息。现代计算机科学的观点，把计算机程序处理的一切

2、数值的、非数值信息、乃至程序统称数据（Data），而计算机只是处理数据的工具。处理对象的转变导致系统和应用程序的规模越来越大，结构也相当复杂，单凭程序员经验和技巧已难以设计效率高、可靠性强的程序。数据的表示方法和组织形式成为处理数据效率的关键。即研究数据的特性以及数据间存在的关系——数据结构（DataStructure）本章介绍了数据结构这门学科诞生的背景,发展历史以及在计算机科学中所处的地位,重点介绍了数据结构有关的概念和术语,读者学习本章后应能掌握数据,数据元素,逻辑结构,存储结构,数据处理,数据结构,算法设计等基本概念,

3、并了解如何评价一个算法的好坏。2:38AM发展简史及学科地位数据结构随着计算机产生和发展而发展起来的一门较新学科。1968年开始设立这门课，由美国教授开创数据结构的最初体系。观点是：认为程序设计的实质是对确定的问题选择一种好的结构，加上一种好的算法。研究内容：软件设计中常用的基本技术地位：核心课程之一，也是非计算机专业的主修课程之一数据结构是介于数学、计算机硬件和软件之间的学科。2:38AM什么是数据结构用计算机解决一个具体问题的步骤：1.从具体问题中抽象出一个适当的数学模型2.设计一个解此数学模型的算法3.编出程序、进行测试

4、、调整直至得到最终解答例如：在(有规律)学生通讯录中，1.按照索引查找某一学生2.插入和删除一个学生记录？数据结构直接影响算法的选择和效率。数据结构：研究程序设计中计算机操作对象及其关系和运算的一门学科2:38AM基本术语(1)1.数据:一切能够输入到计算机中并被其处理的信息(文字,表格图像等)。2.数据元素:也称结点,记录,顶点。是组成数据的基本单位。通常作为一个整体考虑和处理。如图：每一行作为基本单位考虑。3.字段:一个结点中含有若干个字段(也叫数据项).是构成数据的最小单位。4.逻辑结构：结点与结点间的逻辑关系。如图:逻

5、辑上是种线性关系。5.存储结构：数据在计算机中的存储表示。如图：表格数据可有多种存储表示(如：数组、文件等)6.数据结构：组成数据元素之间构造关系。登录号书号书名作者出版社价格00001TP22高等数学陈灯高等教育56.0000002TP23实用英语丁萍电子工业20.5000003TP24电子商务通江涛中央电大18.802:38AM数据逻辑结构1.逻辑结构的四种基本结构：(1)集合：结构中的数据元素除了同属于一种类型外，别无其它关系。(2)线性结构：结构中的数据元素间存在一对一的关系。(3)树形结构：结构中的数据元素间存在一对

6、多的关系。(4)图形或网状结构：结构中的数据元素之间存在多对多的关系。2.数据的逻辑结构分为线性结构和非线性结构两大类。(1)线性结构:包括数组、链表、栈、队列、优先级队列等;(2)非线性结构:包括树、图等.2:38AM存储结构常见存储结构：(1)顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构.即逻辑上相邻,物理上也相邻.(2)链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。(3)索引存储结构:(4)散列存储结构:2:38AM基本术语(2)一般：把数据的逻辑结构统称为数

7、据结构，把数据的物理结构统称为存储结构。说明：一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。我们的重点是算法的设计。数据数据元素字段数据结构分解描述逻辑结构:结点与结点间的逻辑关系。不依赖于具体形式存储结构：数据在计算机中的存储表示。运算：是最终目的2:38AM基本术语(3)7.数据处理：对数据进行查找、插入、删除、合并、排序统计及简单计算等操作过程。8.数据类型：指程序设计语言中各变量可取的数据种类。即是一个值的集合和定义在此值集上的一组操作总称按“数据类型”性质分类：(1)原子类型：其值是不

8、可分解的.(整,实,字,枚,指,空类型)(2)结构类型：其值按某种结构组成(由若干成分)，如：数组例如：C语言中，整型变量其值集：在某个区间上整数操作：加,减,乘,除,求模等运算2:38AM算法的概念1.算法——解决某一类问题的求解方法——执行特定计算的有穷过程（即指令的有限