计算机软件技术基础-课件 01ch1-DS

计算机软件技术基础FundamentalsofComputerSoftwareTechnology线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构课程信息和内容计算机软件技术基础数据结构操作系统软件工程计算机软件技术基础数据结构（DataStructure）课程地位（算法与数据结构）计算机科学中的核心基础课程任何问题都离不开数据

数据是计算机化的信息数据结构是各类计算机软件（一般程序设计、系统程序和大型应用程序）的重要基础。课程目标学会如何有效地组织信息，以便支持高效的数据处理掌握常用的基本数据结构及其应用课程主要内容第1章概述第2章线性结构（线性表、栈与队列、 串、数组与特殊矩阵）第3章非线性结构（树与二叉树、图）第4章查找与排序

第一章概述什么是数据结构算法和算法分析

数值计算：

数学模型→选择计算机语言→编出程序→测试→最终解答关键——如何得出数学模型（方程）。

非数值计算：数据量大且具有一定的关系，数据元素之间的相互关系一般无法用数学方程加以描述。更多地是对数据进行组织管理和检索。计算机的主要用途：例1：学籍档案管理

模型：线性结构 一个学籍档案管理系统应包含如下表所示的学生信息。

非数值计算问题——线性结构特点：一种前后的排列顺序关系，这就是线性结构；对它的操作：插入、删除、更新、检索某个学生的信息等。例2：计算机和人对弈问题——井字棋 模型：树形结构

非数值计算问题——树形结构计算机操作的对象是对弈过程中可能出现的棋盘状态周全考虑对弈过程中所有可能发生的棋盘状态以及相应的对策。将从对弈开始到结束中，所有可能出现的棋盘状态进行综合，得到一棵倒长的“树”。…………井字棋对弈“树”对弈的过程就是从树根沿树叉到某个叶子的过程1.1.1有关概念和术语Q1什么是数据结构？Q2学习数据结构的意义？

Q3数据结构研究的主要内容？

是相互之间存在一种或多种特定关系的数据元素的集合，表示为：什么是数据结构？（形式定义）（数值或非数值）Data_Structure=（D,S）数据元素的有限集D上关系有限集亦可表示为：S＝（D,R）数据(data)——信息的符号表示。数据元素(dataelement)——是数据的基本单位

(又称元素、结点，顶点、记录等），由数据项组成。数据项(dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位。初等项：由一个数据项（DataItem）组成。如：学生的姓名、性别等；组合项：由多个数据项组成。如学生的生日，由年月日等数据项组成。三者之间的关系：数据>数据元素>数据项 例：班级通讯录>个人记录>姓名、年龄……基本术语（数据，数据元素，数据项）基本术语（数据对象）数据对象(dataobject)——是性质相同的数据元素的集合，又称为数据元素类，是数据的一个子集。如：整数数据对象集合N={0，±1，±2，…}

。在同一个数学模型中的数据元素必然具有相同特性。数据结构定义(Q1)数据结构（datastructure）是指按照某种逻辑关系组织起来的数据元素所组成的集合,以及作用于其上的操作（或运算）。涉及三个方面逻辑结构：表示数据元素之间的逻辑关系存储结构：数据在计算机中的存放方式，也称物理结构操作：作用于数据结构上的运算。例如：检索，插入，删除等数据结构三个方面的关系（1）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）数据的存储结构是逻辑结构在计算机存储器中的映像，必须依赖于计算机。（3）运算的定义直接依赖于逻辑结构，但其实现必依赖于存储结构。

这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。学习数据结构的意义？(Q2)★程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。数据结构研究的内容(Q3)1.1.2逻辑结构和存储结构解释1：什么叫数据的逻辑结构？解释2：什么叫数据的物理结构？解释3：什么是数据的运算？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 逻辑结构可细分为4类：解释1：什么叫数据的逻辑结构？集合线性结构树形结构图状结构解释1：什么叫数据的逻辑结构？集合结构：

仅同属一个集合线性结构:

一对一（1:1)树形结构:

一对多（1:n)图形结构:

多对多(m:n)非线性线性（1）线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。（2）非线性结构元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。从逻辑结构划分数据结构答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构主要有：顺序、链式、索引、散列解释2：什么叫数据的物理结构？(1)顺序存储所有元素存放在一片连续地存储单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式存储所有元素存放在可以不连续地存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。从存储结构划分数据结构(3)索引存储使用该方法在存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。(4)散列存储通过构造散列函数，用函数的值来确定元素存放的地址。例：字母表（a,b,c,d,e,f,g……）方法一地址内容顺序abcde……20012002200320042005……方法二地址内容链式a3003……b430020012002……30033004答：在数据的逻辑结构上定义的操作算法，它在数据的存储结构上实现。最常用的数据运算有： 遍历、插入、删除、修改、查找、排序解释3：什么是数据的运算？1.3.1什么是算法？如何评判一个算法的好坏？常用时间复杂度来衡量算法评价指标：正确性、可读性、健壮性、效率与低存储量需求常用空间复杂度来衡量

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。1.3.2算法的分析与度量（时间复杂度和空间复杂度如何表示？）一、时间复杂度二、空间复杂度算法的时间复杂度(TimeComplexity)

T(n)算法从开始到结束所需的时间。是该算法所求解问题规模n的函数。决定算法执行时间因素算法所用的策略、编程所用的语言执行算法机器的速度算法所解问题的规模n——算法求解问题的输入量，

一般用一个整数表示。一、时间复杂度：算法执行时间任何一个算法都是由控制结构和若干原操作（固有数据类型的操作）组成的，因此一个算法的时间复杂度可以看成是所有原操作的执行时间之和。N×N矩阵相乘for(i=1;i<=n;i++)for(j=1;j<=n;j++){ c[i][j]=0; for(k=1;k<=n;k++) c[i][j]+=a[i][k]*b[k][j];}一、时间复杂度：算法执行时间任何一个算法都是由控制结构和若干原操作（固有数据类型的操作）组成的，因此一个算法的时间复杂度可以看成是所有原操作的执行时间之和。整个算法的执行时间与该基本操作（乘法）的重复执行次数n3成正比，记作T(n)=O(n3)。“大O”表示法若T(n)和g(n)是定义在正整数集合上的两个函数，则

T(n)=O(

g(n))

表示存在正的常数C和n0，使得当问题规模n≥n0时都满足0≤T(n)≤C×g(n)。T(n)=O(

g(n))

表示：当n充分大时，算法的时间复杂度T(n)不大于g(n)的一个常数倍。用O记号表示的算法时间复杂度，称为算法的渐进时间复杂度（也简称为时间复杂度）。

按数量级递增排列，常见的时间

复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),...,k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。时间复杂度T(n)按数量级递增顺序为：

复杂度高复杂度低二、空间复杂度

算法的空间复杂度是指算法从开始到结束所需的存储空间量。算法执行期间所需要的存储空间包括：固定部分：程序本身所占空间可变部分：输入数据所占空间、辅助变量所占空间类似于算法的时间复杂度，定义算法空间复杂度为

S(n)=O(g(n))

表示随着问题规模n的增大，算法运行所需辅助存储量的