第2章数据结构及应用概念及顺序表

《第2章数据结构及应用概念及顺序表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章数据结构及应用概念及顺序表西安交通大学计教中心ctec.xjtu.edu.cn思考问题数据结构要研究什么问题？什么是线性数据结构和线性表？如何描述线性表？线性表在计算机中如何存放？有几种存储形式？它们的特点是什么？如何处理线性数据结构中的数据？……2数据结构问题的由来计算机求解问题的过程步骤：调试程序编制程序求解结果运行程序结果输出用户需求数据类型、格式、逻辑结构数据逻辑运算数据的物理操作分析抽象实际问题模型求解问题模型命令编程求解算法3数据结构数据结构是计算机的专业技术基础课。它研究的主要问题有：分析数据（计算机加工的对象）的特征选择适当逻

2、辑存储结构和物理存储结构在存储结构的基础上实现对数据的操作42.1数据结构基本概念1．数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。2．数据元素（dataelement）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位5数据结构（datastructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。6数据的逻辑结构它是描述数据间的顺序

3、（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述：DS=（D，R）其中：D：是数据元素的有限集合；R：是数据元素之间关系的集合。与数据在计算机中的存放的物理位置无关7举例课题组由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。定义DS如下：Group=（D，R）其中：D={T，G1，…,Gn,S11,…Snm}1n3,1m2R={R1,R2}R1={

4、1in,1n3}R2={

5、1in,1jm,1n3,1

6、m2}8数据的存储结构又称物理结构是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放。数据库中的数据存放在计算机中的物理位置9逻辑结构和存储结构的关系数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。10数据存储结构分类顺序存储结构链式存储结构索引存储结构散列存储结构11顺序存储结构把数据元素按某种顺

7、序存放在一块连续的存储单元中的存储形式。数据结点结构:d1d2……dn数据域特点:连续存放;逻辑上相邻,物理上也相邻。结构简单，易实现。插入、删除操作不便（需大量移动元素）。12链式存储结构以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构:d1...d2dn^数据域指针域特点:非连续存放,借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。13索引存储结构数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之

8、间的对应关系。数据结点结构:1221352455104327165数据域索引顺序号特点：非连续存放；检索速度快；增、删操作简单。序号：1234567数据项：索引号：14散列存储结构在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。哈希查找中的哈希表就是这样一种存储结构。特点：数据元素间无内在联系；存储形式不定。15数据运算数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。常见操作有：输入、检索、插入、删除、修改、排序等。16数据结构分类线性表堆栈队列串数组树二叉树图线性结构非

9、线性结构数据结构DS17数据结构基本类型线性结构——通迅录、成绩单、花名册树形结构——电子字典、家谱、目录图状结构——交通线路、通信网络18算法（algorithm）通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：⑴输入：具有0个或多个输入的外界量（算法开始前的初始量）⑵输出：至少有一个输出，是算法执行完后的结果。⑶有穷性：每条指令的执行次数必须是有限的。⑷确定性：每条指令的含义都必须明确，无二义性。⑸可行性：每条指令的执行时间都是有限的。191．时间复杂度一个算法花费的时间与算法

10、中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。