数据结构与(C语言版) .pptVIP

数据结构（C语言版） 计算机技术系 宫伟娅 “数据结构”学科形成和发展背景 自1946年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料。如今，计算要已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图象等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写一些“好”的程序，必须分析待处理对象的特性以及各处理对象间的关系。这就是“数据结构”这门学科形成和发展的背景。 1.1什么是数据结构 数值计算解决问题的一般步骤： 数学模型→选择计算机语言→编出程序→测试→最终解答。 数值计算的关键是：如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 非数值计算问题 数据元素之间的相互关系一般无法用数学方程加以描述 例1-1 书目自动检索系统 例1-2 井字棋 例1-3 多叉路口交通灯管理问题 通常，这类交通、道路问题的数学模型是一种称谓“图”的数据结构。例如在此例的问题中，可以图中一个顶点表示一条通路，而通路之间互相矛盾的关系以两个顶点之间的连线表示。 综上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。 《数据结构课程》 所处的地位： 数据(Data): 对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数值型数据 非数值型数据 数据元素(Data Element): 数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小标识单位。 数据对象(Data Object)： 性质相同的数据元素的集合。是数据的一个子集。 整数数据对象 N = { 0, ?1, ?2, … } 字母字符数据对象 C={ ‘A’, ‘B’, ‘C’, … ‘F’ } 定义1---- 是相互之间存在一种或多种特定关系的数据元素的集合。 定义2---- 按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。 四个基本结构 集合 线性结构 树形结构 网状结构 数据结构的形式定义为：数据结构是一个二元组 Data__Structure(D,S) 其中：D是数据元素的有限集 S是D上关系的有限集 例：在计算机科学中，复数可取如下定义：复数可取如下定义：复数是是一种数据结构 Complex=(C,R) 例：假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象——课题小组设计一个数据结构。 假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究指导一至两名本科生。则可以如下定义数据结构： Group=(P,R) 其中：P={ T，G1，……，Gn，S11…Snm} 1≦n ≦, 1 ≦m ≦2, R={R1,,， R2} R1,,={ 〈T，GI〉∣1≦i≦ n , 1≦n≦ 3} R2 ={〈GI，SIJ ∣1≦i≦ n ， 1≦J≦ m , 1≦n≦ 3, 1≦m≦ 2} 逻辑结构--- 数据元素间抽象化的相互关系（简称为数据结构）。 与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。 存储结构（物理结构）---- 数据元素及其关系在计算机存储器中的存储方式。 是逻辑结构用计算机语言的实现，它依赖于计算机语言。 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储：顺序存储结构和链式存储结构。 数据类型：是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）操作对象的特性。 按“值”的不同特性，高级程序