数据结构第一章概论.pptVIP

数据结构 第一章 概论 重庆一中 葛静 本章的主要内容 问题一：数据结构讨论的范畴 问题二：基本概念 问题三：算法及其度量 问题一：数据结构讨论的范畴 尼克劳斯·沃斯(Niklaus Wirth)：生于瑞士，求学 美洲，立业瑞士。苏黎世联邦理工学院教授，Pascal系 列语言之父，世界闻名的计算机科学家。Algorithm+Data Structures=Programs 算法 + 数据结构 = 程序 程序：为计算机处理问题编制的一组指令集。 算法：处理问题的策略。 数据结构：问题的数学模型。 数值计算的程序设计问题 全球天气预报 ——环流模式方程（数学模型） 进行大量的数值运算，这是计算数学要讨 论的问题。 非数值计算的程序问题 例1：求n个数中的最大值 算法？： 两两比较 数据结构？： n 的范围？如果n达到10^12，如何表示这个整数？ 非数值计算的程序问题 例2：人机对弈 算法？： 对弈的规则和策略 数据结构？： 棋盘、棋子怎么表示？ 非数值计算的程序问题 例3：足协数据库管理 算法？： 需要管理哪些项目？用户的界面？条例、规则等等。 数据结构？： 各种各样的表格和数据库。 综合各种程序设计的问题，抽出其具体的物理含义，就可得到几类数学模型： 1、和数值计算相关的数学模型，如线性代数方程、非线性代数方程和常微分方程等，他们的数值解问题就是计算数学要解决的问题。 2、非数值计算问题，其数学模型的表示和求解就是数据结构要研究的内容。 概括的说： 数据结构要研究的就是： 非数值型计算的程序设计问题中描述现实世 界实体的数学模型 和 在计算机中表示的方法 以及 这些数学模型进行的操作如何在计算机中 实现。 问题二：基本概念 数据：是计算机要处理的信息集合，是信息的某 种特定的符号表示形式。其含义随着计算机的发 展不断扩大。 数据元素：是数据中的一个“个体”，是数据结构 中讨论的基本单位。但不是最小单位。 如：学生（数据元素） 姓名、性别、出生日期（年月日）、入学日期、 班级…… 数据项才是数据结构中要讨论的最小单位。 数据结构：带结构的数据元素的集合。 结构：就是数据元素之间存在的约束关系。 例1：一个含有12位数的十进制整数可以用三个4位的十进制整数表示。 1548，4913，7875——a1(1548),a2(4913),a3(7875) 在a1,a2,a3之间存在次序关系 a1,a2,a2,a3 4973,7875,1548≠ 1548,4913,7875 a2 a3 a1 ≠ a1 a2 a3 数据结构：带结构的数据元素的集合。 例2：2行3列的二维数组{a1,a2,a3,a4,a5,a6} 行的次序关系：row={a1,a2,a2,a3,a4,a5,a5,a6} 列的次序关系：col={a1,a4,a2,a5,a3,a6} a1 a3 a4 a1 a2 a3 ≠ a2 a6 a5 a4 a5 a6 数据结构：带结构的数据元素的集合。 例3：一位数组{a1,a2,a3,a4,a5,a6}，这6个数据元 素还可以存在单纯的次序关系{ai,ai+1∣i=1,2,3,4,5} 所以：相同的数据元素，不同的约束关系，构成 了不同的数据结构。 例3 人机对奕问题 多叉路口交通灯管理问题 数据的逻辑结构 数据在逻辑上的联系，叫做数据的逻辑结构。 数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 数据逻辑结构的定义 定义为一个二元组： Data_structures=(D,S) 其中： D是数据元素的有限集， S是D上关系的有限集。 如：线性结构： 数据对象：A={ai︱1=i=n,n=0,ai∈elemtype} 其中n为线性表的表长，n=0时线性表为空表。 数据关系：R={r} R={ai,ai+1︱1=i=n-1} 数据的物理结构（存储结构） 数据的在计算机上的存储表示称作数据的物 理结构或存储结构。 数据元素的映像方法： 用二进制位（bit）的位串表示数据元素。 （321）10=（101000001）2 A=(001000001)2 数据的物理结