计算机软件基础Thesoftwarebasicofcomputer主讲：刘志强讲解教学教案.ppt

《计算机软件基础Thesoftwarebasicofcomputer主讲：刘志强讲解教学教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件基础Thesoftwarebasicofcomputer主讲：刘志强西安交通大学计算机教学实验中心第2单元线性数据结构（一）第2单元线性数据结构（一）教学目标：了解数据结构的有关概念什么是线性DS、线性表了解线性DS的特点了解线性DS的逻辑结构、物理结构以及操作2学习要求通过本单元的学习，了解并掌握：有关数据结构（DS）的基本概念数据元素、DS、逻辑结构、物理结构、DS的分类及特点、算法、时间复杂度等线性DS的常用存储结构顺序、链表、索引、散列存储结构单向、双向、循环链表等线性DS的有

2、关算法增、删、改3涉及的章节第1章的1.1数据结构概述(P13~P17)1.2线性表(P17~P32)4数据结构问题的由来计算机求解问题过程步骤：实际问题求解问题模型算法分析抽象模型求解命令编程调试程序编制程序运行程序求解结果结果输出用户需求数据类型、格式、逻辑结构数据逻辑运算数据的物理操作5问题模型结构分析——线性方程组人口预报——微分方程优化问题——线性规划、非线性规划震动问题——矩阵分析；特征值、特征向量信息管理——二维数据表下棋——人工智能(树型结构)交通管理——最佳道路选择(图型结构)6下棋问题1

3、111111111111111117一、基本概念数据（Data）能存于计算机、并被计算机处理的符号的集合。它是客观事物的符号表示。数据元素（Element）是数据的基本单位、数据集合中的个体。数据结构（DataStructure）是带有结构特征的数据元素的集合；它有三个要素：DS=数据的逻辑结构+存储结构+数据的运算数据结构是以数据为加工对象，研究数据组织方式和相关操作方法的学问。也可以说：怎样去组织一批特定的数据。8数据结构分类线性表堆栈队列串数组树二叉树图线性结构非线性结构

4、数据结构DS91.数据的逻辑结构它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述：DS=（D，R）其中：D：是数据元素的有限集合；R：是数据元素之间关系的集合。10举例课题组由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={

5、1in,1n

6、3}R2={

7、1in,1jm,1n3,1m2}112.数据的存储结构又称物理结构是指数据结构在计算机中的表示(又称映象),即数据在计算机中的存放。12逻辑结构和物理结构的关系数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。13数据

8、存储结构分类顺序存储结构链式存储结构索引存储结构散列存储结构14顺序存储结构把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构:特点:连续存放;逻辑上相邻,物理上也相邻。结构简单，易实现。插入、删除操作不便（需大量移动元素）。d1d2……dn数据域15链式存储结构以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构:特点:非连续存放,借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存

9、储空间。d1...d2dn^数据域指针域16索引存储结构数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。数据结点结构:序号：1234567数据项：索引号：特点：非连续存放；检索速度快；增、删操作简单。1221352455104327165数据域索引顺序号17散列存储结构在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F（E）。哈希查找中的哈希表就是这样一种存储结构。特点：数据元素间

10、无内在联系；存储形式不定。183.数据运算数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。常见操作有：输入、检索、插入、删除、修改、排序等。194、算法与算法分析算法（Algorithm）是对特定问题求解步骤的一种描述；是一组指令的有限集合。算法和数据结构的关系为了充分地利用系统资源；既要效率高、速度快，又要存储空间少。显然，这是矛盾的。研究算法追求的目标是：时间和空间的适当和谐20算法的