《Data Structure1》由会员分享，可在线阅读，更多相关《Data Structure1（39页珍藏版）》请在金锄头文库上搜索。
1、Data Structure数 据 结 构主讲：周颖颖办公室：宏博楼311数据结构和计算机系统的关系你知道吗？o操作系统内核中怎样管理内存o操作系统中的进程如何管理o一个程序是如何运行的课程性质o计算机应用专业一门专业基础课o在计算机各处领域中均会使用到数据结构的有关知识o全面地掌握各种常用的数据结构o内容多、难度大o较强的程序设计能力（C语言和数学基础）考核目标oP240 闭卷、笔试、150分钟o共6学分，考前修完实验1学分P237oP239 考题覆盖到章节o并分能力层次和考题难易课程内容及掌握程度要求1.绪论2.线形结构包括线形表、栈、队列和数组等内容3.非线形结构包括树、图等内容4.排序
2、5.查找6.文件掌握程度掌握程度各章不同各章不同实践考核说明1.书后实践环节实验须在课程考试前完成2.学期结束前实践考核，上机考试o120分钟，包括修改程序（或填写语句）和上机调试程序 oWindows环境下的Turbo C 系统 o考题一般为三道题左右，涵盖实验内容的三分之二以上，由主考学校批改 上机环境说明oVC 6.0oTurbo c for windows oCfreeo其他基本要求o从数据结构的逻辑结构、存储结构和数据运算三个方面去掌握线性表、栈、队列、串、数组、广义表、树、图和文件等常用的数据结构。o掌握在各种常用的数据结构上实现的排序和查找的运算o对算法的时间和空间复杂性有一定的
3、分析能力o针对简单应用问题，应能选择合适的数据结构及设计有效的算法之一。学习方法o熟知课程要求，有的放矢o掌握每章考核知识点和要求、掌握重点o掌握各种数据结构的定义和实现o熟记教材重点算法o自行强化程序设计经验（多动手）第一章 绪 论o学习目标和要求P228o考核知识点1.数据结构的基本概念和术语。要求达到“识记”层次。2.数据结构在软件系统中的作用，要求达到“识记”层次。3.算法的描述和分析，要求达到领会层次主要内容1.2 数据结构及计算机系统中作用 （记）1.1 基本概念和术语（记）1.3 算法描述和分析 （领会）重点：数据结构的逻辑结构、存储结构及数据运算的概念和关系难点：算法复杂度分析
4、1.2数据结构o计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：o 信息的表示 信息的处理o信息的表示和处理又直接关系到处理信息的程序的效率。o必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。什么是数据结构o计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。o数据结构在各种软件系统中所起的作用o程序=算法+数据结构o选择合适的数据结构是解决应用问题的关键步骤 例1、电话号码查询系统o设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按
5、如下形式安排：o (a1，b1)(a2，b2)(an，bn)o其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。o算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。o数据的结构，直接影响算法的选择和效率。o上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据
6、结构还要提供每种结构类型所定义的各种运算的算法。例2 田径赛时间安排o六个项目比赛，每人最多参加3个o有5名选手报名o抽象为对无向图进行着色操作：即用尽可能少的颜色去给图中每个顶点着色，使得任意两个有边连接的相邻顶点着上不同的颜色。每一种颜色表示一个比赛时间赛时间，着上同一种颜色的顶点是可以安排在同一时间内竞赛的项目。 1.2 基本概念和术语基本概念和术语o数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机 程序处理的符号的总称。o数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。o 一个数据元素可由若
7、干个数据项组成。数据项是数据的不可分割的最小单位。o数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。o数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。o数据类型：在一种程序设计语言中，变量所具有的数据种类。o例、在C语言中o数据类型：基本类型和构造类型o基本类型：整型、浮点型、字符型o构造类型：数组、结构、联合、指针、枚举型、自定义o数据对象：某种数据类型元素的集合。o例、英文字符类型的数据对象是A，B，C，D，E，F，数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系o逻辑结构独立与计算机的硬件结构的一种抽象
8、抽象的数学模型的数学模型o存储结构也就是逻辑结构逻辑结构在计算机中的具体实的具体实现现，它是一个依赖与计算机硬件的结构。o基本运算即定义在某种逻辑结构上的具体操作，关心它“做什么”。 运算实现就是如何去实现某种具体的运算，即让我们知道该“怎么做”。o算法评价每一种运算实现的不同方法，所对应的时间性能、空间性能都是不同。o数据结构的数据结构的逻辑结构，逻辑结构，简称简称数据结构数据结构 数据之间的相互关系称为逻辑结构。通常分为2类基本结构：o一、线性结构 结构中的数据元素之间存在一对一的关系。（1-4章）o二、非线性结构 结构中的数据元素之间存在一对多的关系（5-7章）学生成绩表数据结构o直接前
9、趋o直接后趋o开始结点o终端结点o结点间的关系构成了逻辑结构o计算机如何表示各结点间的关系？o如何进行查找、删除、插入等数学运算？数据存储结构的四种方法o顺序存储 数组 逻辑相邻的结点存储在物理相邻的存储单元o链式存储指针 不要求物理相邻o索引存储 存储结点并附加索引表（稠密索引、稀疏索引）o散列存储 根据结点关键字计算存储地址o算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表示一个或多个操作。o算法是一系列将输入装换为输出的计算步骤o基本运算和实现（2-7中针对不同数据结构+ 8-9章）用语言描述计算过程1.3 算法的描述与分析算法的特点（理解）o（1）有穷性 一
10、个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。o（2）确定性 算法中每一条指令必须有确切的含义，且算法只有一个入口和一个出口。o（3）可行性 算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 o4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。o5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。算法设计的要求算法设计的要求o评价一个好的算法有以下几个标准:o(1) 正确性(Correctness ) 算法应满足具体问题的需求。o(2)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存
11、储空间。 (3)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。o(4) 健壮性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。o算法耗费的时间 =语句执行时间之和o每条语句执行时间=频度语句执行一次时间 o假设每条语句执行一次均为单位时间o频度：是指该语句重复执行的次数算法的时间特性例、for(i=0；in; i+) n+1 for(j=0;jn; j+) n(n+1) cij=0; n2 for(k=1;k+， T(n)的数量级称为渐进时间复杂度，记作 T(n)=O(f(n) o渐进时间复杂度是算
12、法的时间性能主要评价标准o例 temp=i;j=j;j=temp 语句频度为，即时间复杂度为(1)o例、for(i=1;in+1;+i) +x;s+=x; 语句频度为：2n其时间复杂度为：O(n) 即时间复杂度为线性阶。o例、for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x;o 语句频度为：2n2o其时间复杂度为：O(n2)o 即时间复杂度为平方阶。o定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)o语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2
13、-3n+2 时间复杂度为O(n2)o 即此算法的时间复杂度为平方阶例例for(i=2;i=n;+I) for(j=2;j=i-1;+j) +x;ai，j=x;渐进时间复杂度从宏观上评价oT1(n)=100n2和T2(n)=5n3(1)n20习题1.5算法时间复杂度还依赖于输入示例的初始状态在数值A0n-1中查找给定值K的算法：i=n-1;while(i=0&(Ai!=K) i- ;return i;考虑（1）A中没有与K相等的元素 （2）A中最后一个元素An-1=K最坏时间复杂度/平均时间复杂度o以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(lgn)O(n)O(nlgn) O
14、(n2)O(n3)o指数时间的关系为： O(2n)O(n!)O(nn)o 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊算法的存储空间需求o空间复杂度:算法所需存储空间的度量，记作:o S(n)=O(f(n) o其中n为问题的规模(或大小)C语言知识点o数组o结构体o指针例：输入5个学生的姓名、学号、性别和3门课成绩，并计算平均分o1若一个算法的时间复杂度用T(n)表示，其中n的含义是（ ）A问题规模B语句条数C循环层数D函数数量1.数据的四种存储结构是( A )oA.顺序存储结构、链接存储结构、索引存储结构和散列存储结构oB.线性存储结构、非线性存储结构、树型存储结构和图型存储结构oC.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构oD.顺序存储结构、树型存储结构、图型存储结构和散列存储结构o1按值可否分解，数据类型通常可分为两类，它们是（C）oA静态类型和动态类型oB原子类型和表类型oC原子类型和结构类型oD数组类型和指针类型
