数据结构第一章绪论

《数据结构第一章绪论》由会员分享，可在线阅读，更多相关《数据结构第一章绪论（39页珍藏版）》请在金锄头文库上搜索。

1、数据结构第一章绪论本课程讲述的主要内容：分别讲述数据结构的基本概念、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序等内容。学习本课程的基本方法：l上课认真听讲；l仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；l独立完成每个章节的练习题和作业题。 1.1 1.1 什么是数据结构 1.2 1.2 基本概念和术语 1.3 1.3 抽象数据类型 1.4 1.4 算法和算法分析第一章 绪论1.1 什么是数据结构著名计算机科学家、PascalPascal语言发明者N.N.沃思教授提出： 程序 = = 算法 + + 数据结构 程序: : 处理问题编制一组指令集 算法: :

2、 处理问题的策略数据结构: :问题的数学模型也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。数值计算的程序设计问题：例 如 ： 结 构 静 力 分 析 计 算 线 性 代数方程组 预报人口增长情况 微分方程例1 1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表算法：需要检索的书目？如何检索？用户界面？ 模型：？非数值计算的程序设计问题：例2 2 人机对奕问题树.算法：对奕的规则 和策略模型：？教学计划编排问题 图课程代号课程名称先修课程C1C1计算机导论无C2C2数据结构C1,C4C1,C4C3C3

3、汇编语言C1C1C4C4C C语言C1C1C5C5计算机图形学C2,C3,C4C2,C3,C4C6C6接口技术C3C3C7C7数据库原理C2,C9C2,C9C8C8编译原理C4C4C9C9操作系统C2C2C1C3C4C7C6C5C2C8C9 算法：如何确定课程的次序关系? ? 模型：？数据结构研究的主要内容： 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据（data)data)所有能被输入到计算机中，且被计算机处理的符号的集合 ，是计算机操作的对象的总称。数据元素（data elementdata element）是数据的基本单位，由若干个数

4、据项组成，也称结点、元素、顶点或记录。数据项（data itemdata item）是数据的不可分割的最小单位，有时也称为域（fieldfield），即数据表中的字段。数据对象(data (data object)object)：性质相同的数据元素的集合，是数据的一个子集。如大写字母字符数据对象是集合C=C=A A, ,B B, ,C C, ,，Z Z ，整数数据对象是集合 N = 0, 1, 2, N = 0, 1, 2, 1.2 基本概念和术语根据数据元素间关系的基本特性，有四种基本数据结构：（集合）数据元素间 “同属于一个集合”线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如

5、树图状结构多个对多个，如图数据结构(data (data structure)structure)：是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。例：一个含1212位数的十进制数可以用三个4 4位的十进制数表示 3214,6587,9345 3214,6587,9345 a1(3214),a2(6587),a3(9345) a1(3214),a2(6587),a3(9345)在a1a1、a2a2和a3 a3 之间存在“次序”关系 a1,a2a1,a2 、 a2,a3a2,a3 a1 a2 a3 a3 a2 a1 a1 a2 a3 a3 a2 a1数据结构的形式定

6、义：数据结构是一个二元组 Data-Structure=（D，S） 其中：D是数据元素的有限集，S是D上关系的有限集。例：在计算机科学中，复数可取如下定义：复数是一种数据结构 Complex=（C，R） 其中，C是含两个实数集合c1，c2；R=P，P是定义在集合C上的一种关系，其中有序偶表示c1是复数的实部，c2是复数的虚部。数据的逻辑结构只抽象反映数据元素的逻辑关系。数据的存储（物理）结构数据的逻辑结 构在计算机存储器中的存储形式（或称映象）。 元素/ /结点：用于表示数据元素的二进制位(bit)(bit)的位串。 数据域：用于表示数据项的二进制位(bit)(bit)的位串。例：（32132

7、1）1010（501501）8 8（101000001101000001）2 2 A A（101101）8 8（001000001001000001）2 2存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据元素间的逻辑关系元素n n.元素i i.元素2 2元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素2 21400元素1 11346元素3 3 元素4 41345h存储地址 存储内容 指针 1345 1345 元素1 1 1400

8、1400 1346 1346 元素4 4 . . . . . 1400 1400 元素2 2 1536 1536 . . . . . 1536 1536 元素3 3 1346 1346 链式存储 h 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表栈和队列串树形结构图形结构数据结构的三个方面：数组和广义表数据类型一个值的集合和定义在这个值集上一组操作的总称。例：C语言中，提供int, char, float, double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可

9、用typedef 自己定义数据类型typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p;1.3 抽象数据类型抽 象 数 据 类 型 ADTADT（ Abstract Abstract Data Type)Data Type)v定义：指一个数学模型以及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。 例：矩阵 + +（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型 数据结构 + + 定义在此数据结构上的一组操作 = = 抽象数据类型v描述方法形式定义：我们用一

10、个三元组 （D，S，P）来表示一个 抽象数据类型 ，其中D是数据对象，S是D上的关系集，P是对D的基本操作集。 格式： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 v基本操作的定义格式： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 赋值参数引用参数，以“”打头例：抽象数据类型三元组的定义： ADT Triplet 数据对象：D=e1,e2,e3 |e1,e2,e3Elemset 数据关系：R1=, 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T，

11、元素e1，e2和e3分别被赋以 参数v1,v2和v3的值。 DestroyTriplet（&T） 操作结果：三元组T被销毁。 Get（T,i,&e） 初始条件：三元组T已存在， 1=i=3. 操作结果：用e返回T的第i元的值。 Put(&T,i,e) 初始条件：三元组T已存在，1=i=3. 操作结果：改变T的第i元的值为e。 IsAscending(T) 初始条件：三元组T已存在。 操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。IsDescending(T) 初始条件：三元组T已存在。 操作结果：如果T的3个元素按降序排列，则 返回1，否则返回0。Max(T,&e) 初始条件：三

12、元组T已存在。 操作结果：用e返回T的3个元素中的最大值。Min(T,&e) 初始条件：三元组T已存在。 操作结果：用e返回T的3个元素中的最小值。ADT Triplet 1.4 算法和算法分析v有穷性：对于任意一组合法输入值，在执行有穷步之后结束，即算法中的每个步骤都能在有限时间内完成；v确定性：每条指令都有确切的含义，在任何条件下算法都只有一条执行路径；算法五个重要特性：算法：是对特定问题求解步骤的描述，是指令的有限序列。v可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；v有输入：有零个或多个输入，取自特定的对象集合v有输出：有一个或多个输出，是算法进

13、行信息加工后得到的结果。算法设计的原则v正确性：在合理的数据输入下，能在有限的运算时间内得到正确结果；对算法是否“正确”的理解可以有以下四个层次： a程序中不含语法错误； b程序对于几组输入数据能够得出满足要求的结果； c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果； d程序对于一切合法的输入数据都能得出满足要求的结果；v可读性：易于人对算法的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；v健壮性： 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错

14、误或错误性质的值，以便在更高的抽象层次上进行处理。v高效率与低存储量需求： 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。 算法效率的衡量方法和准则 有两种衡量算法效率的方法: : 1. 1.事后统计法：利用计算机内记时功能，用一组或多组相同的统计数据区分。 2.2.事前分析估计法：求出算法的一个时间界限函数。和算法执行时间相关的因素： 算法选用的策略 问题的规模 编写程序的语言 编译程序产生机器代码质量 机器执行指令速度v时间复杂度：程序运行从开始到结束所需要的时间。 设解决一个问题的规模为n，基本操作被重复执行的次数是n的一个函数 f（

15、n），假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n) 其中T(n)叫算法的渐进时间复杂度，简称时间复杂度。 算法控制结构+原操作（固有数据类型的操作） 算法的执行时间原操作（i）的执行次数 原操作（i）执行时间 从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法运行时间度衡量准则。例1 1：NXNNXN矩阵相乘for(i=1; i=n; i+) for(j=1; j=n; j+) cij=0; for(k=1; k=n; k+) cij=cij+aik*bkj; 显然，被称做问题的基本操作的

16、原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下是最深层循环内的语句中的原操作，它的执行次数和包含它的语句频度相同。例2 2+x;s=0;+x;s=0;例for(i=1; i=n; +i)for(i=1; i=n; +i) +x; s+=x; +x; s+=x;例. for(i=2; i=n; +i). for(i=2; i=n; +i) for(j=2; j=i-1; +j) for(j=2; j=1 & change; - -i) change=false; for(j=0; jaj+1) aj aj+1; change=TURE； 最好情况：0次最坏情况：1+2+3+n-1 = n(n-1)/2平均时间复杂度为：O(n2)