《数据结构第1章绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构第1章绪论.ppt（37页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论课程背景n计算机=软件 + 硬件n软件=程序+文档（软件工程的观点）n程序=算法+数据结构（Niklaus Wirth，图灵奖获得者)n数据结构=计算机程序设计技巧(Kunth，图灵奖获得者)n熟悉c语言写出好的程序n学习数据结构=编写高水平的程序n数据结构：计算机类专业8大核心课程之一 注：教育部计算机教指委认定的8大核心课程：计算机语言、数据结构、离散数学、计算机网络、计算机组成原理、操作系统、数据库、软件工程 图灵奖：1966年设置，每年奖励1-2名杰出的计算机科学家，被誉为计算机领域的诺贝尔奖基本学习方法n课前预习、上课认真听讲n课后多做习题n多上机编程（熟练掌握c、c+）
2、勤学勤练勤学勤练教材和参考书n教材n数据结构（c语言版）秦锋编著 中国科技大学出版社n主要参考书n数据结构例题详解及课程设计指导 秦锋、袁志祥等 中国科技大学出版社n数据结构C语言版严蔚敏、吴伟民 清华大学出版社nC程序设计谭浩强 清华大学出版社本章主要内容n什么是数据结构n基本概念和术语n算法1.1 什么是数据结构n早期的计算机主要用于数值计算n现在的计算机更多地是用于非数值数据处理（字符、表格、图像）n对非数值数据的处理：分析数据的逻辑特征抽象出合适的数学模型合理地存储到计算机设计出算法编写出程序 请看例请看例请看例请看例1 13 3 例1 学生信息查询系统 首先要构造学生信息表，表1-1
3、表达出学生数据的逻辑关系，它就是一个数学模型，这张表如何构造、在计算机内如何存储将直接影响查找算法的设计以及算法的效率表表表表1-11-1 学生信息表的特点n每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格n表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构，现实中这类关系的数据有很多。n通常的操作n插入某个学生的信息插入某个学生的信息n删除某个学生的信息删除某个学生的信息n更新某个学生的信息更新某个学生的信息n按条件查找某个学生的信息按条件查找某个学生的信息 中国象棋、国际象棋的人机大战，核心技术是人编写的对弈程序。对弈步骤和过程可以用树型结构表
4、达出来（数学模型）例2 人机对弈图图 1-1 井子棋对弈树井子棋对弈树树形应用树形应用树形应用树形应用 树型结构的特点n所处理的数据之间具有层次关系，这是我们所说的树形结构,还有如：基因遗传关系等，它是一种非线性结构。n对它的操作有：建立树形结构、存储树、访问树中的每个结点例3 排课子系统 排课系统中各门课程的先后关系可以用一个图表达出来，这个图表达了数据的逻辑关系（数学模型） 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。如何安排每学期的课程？ 计算机专业课程的开设情况如下表所示： 计算机专业学生的必修课程课程编号课程
5、名称需要的先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1 ， C2C4汇编语言C1C5算法分析与设计C3 ， C4C6计算机组成原理C11C7编译原理C5 ， C3C8操作系统C3 ， C6C9高等数学无C 10线性代数C9C11普通物理C9C12数值分析C9 ， C10 ， C1 课程先后关系的图型描述c1c9c4c2c12c10c11c5c3c6c7c8图结构的特点n关系比较复杂，用例1和例2的结构表达不出来，必须用图结构描述（离散数学中的图论）n通过实施创建图结构，存储图结构，可以对图结构中的顶点进行线性排序，从而找出每学期应该上的课程。 n现实中，这类关系的数据非常多。
6、如：网络规划、交通、通讯规划等，这里典型的非线性关系。 n操作对象的关系复杂多样n操作不再是单纯的数值计算，更多的是非数值问题求解，需要对数据（不是数值）进行分析、组织及管理。n必须对数据进行有效的组织、存储，才能对数据进行有效的操作返回返回结论1.2 基本概念和术语n数据 n是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合n数据元素n是数据集合中的一个实体，是计算机程序中加工处理的基本单位（记录、结构体）数据元素的分类n简单型数据元素n由一个数据项组成，数据项就是数据中不可再分割的最小单位n复杂型数据元素n复杂型数据元素由多个数据项组成，它通
7、常携带着一个概念的多方面信息n数据结构是相互之间存在一种或多种特定 关系的数据元素的集合。n常见的数据结构n线性结构n树形结构n图形结构n数据结构主要研究n数据的逻辑结构n数据的存储结构n对数据的操作（运算算法）数据结构的定义数据结构的定义n逻辑结构n数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构 n存储结构（物理结构）n是指数据结构在存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构n数据运算n对数据施加的操作。运算的定义依赖于逻辑结构，但运算的实现必依赖于存储结构（真正理解）n顺序
8、存储结构：n特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构n链式存储结构：n特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构返回返回常见的存储结构1.3 什么是算法n 算法的定义 算法是解决某个特定问题的一种方法或一个过程，是指令的有限序列。n 算法具有五大特性： 1）有穷性： 一个算法必须在执行有穷步之后结束 2）确定性： 算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性 3）可行性： 算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现 4）输入： 一个算法应该有零个或多个输入 5）输出： 一个算法应该有一个或多个输出 思考：烹调过程、程序、
9、操作系统等是不是算法？算法的5大特性n使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读,缺点是不够严谨，容易产生二义性。n可以使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。n用一种伪语言（类pascal、类c ）n用c、c+ 等标准的程序设计语言如何描述算法n正确性：n要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求（有四个层次的正确）n可读性：n为了便于理解、测试和修改算法，算法应该具有良好的可读性（注意程序设计风格，如：空行、伸缩、注释、命名、对齐等）n健壮性：n当输入数据非法运行环境改变时，算法能恰当地作出反应或进行处理，不会产生慕名
10、其妙的输出结果n时间与空间效率：n算法对应的程序在计算机上运行时所花费的时间及所占据空间（辅助数据所占）的度量 如何评价算法 n硬件的速度硬件的速度n例如使用486机还是使用586机。n书写程序的语言书写程序的语言n实现语言的级别越高，其执行效率就越低n编译程序所生成目标代码的质量。编译程序所生成目标代码的质量。n对于代码优化较好的编译程序其所生成的程序质量较高n问题的规模问题的规模n例如，求100以内的素数与求1000以内的素数其执行的时间必然是不同的n算法设计的好坏算法设计的好坏 结论：不能用实际的时间来考量、应该用指令执行的总次数。影响算法运行所需时间的因素n求两个N阶方阵的乘积C=A*
11、B的算法#define N 100void MatrixMultiply(int A NN，int BNN，int CNN) for(i=0;iN; i+) n+1 for(j=0; jN;j+) n(n+1) Cij=0; n2 for(k=0;kN;k+) n2(n+1) Cij=Cij+Aik*Bkj; n3 例1：n语句1是循环控制语句，它的循环次数决定，故是n+1，但是它的循环体却只执行n次n语句2作为语句1的循环体内的语句应执行n次，但每次执行时它本身又要执行n+1次， 故语句2的频度为n(n+1)。n 3、4、5语句的频度可类似得到。n 综合分析，可以确定上述算法的执行时间（即语
12、句的频度之和）是 T(n)=2n3+3n2+2n+1；它是方阵阶数n立方的函数。例1的时间效率分析例1的时间效率分析n算法的执行时间是求解问题的规模n（如矩阵的阶数，线性表的长度）的函数，我们考察它的数量级量度，即它与什么简单函数f(n)是同一数量级的，即T(n)=O(f(n)。 对于前例，当n时 T(n)/n3 = (2n3+3n2+2n+1)/ n32 按“O”的定义我们可知T(n)=O(n3) 特别说明：算法的空间效率度量定义和时间效率一样，不过一个算法的空间效率是对算法运行中所需的辅助空间的度量，操作对象所占的空间不计入空间效率的度量之中。具体可见例2n数量级递增排序有数量级递增排序有
13、n常数阶O（1）n对数阶O（log2n）n线性阶O（n）n平方阶O（n2）n立方阶O（n3）n指数阶O（2n）n指数阶算法的执行时间（辅助空间）随n 的增大而迅速地放大，其时间（空间）性能很差 常见的时间空间复杂度例2 本例主要说明用牺牲空间本例主要说明用牺牲空间代价换取时间效率上的提高代价换取时间效率上的提高n矩阵Amxn中存在某个元素aij满足：aij是第i行中最小值且是第j行列中的最大值，则称该元素为矩阵A的一个鞍点，试编写算法找出A中的所有鞍点。算法一：穷举法算法思想：对每一个元素aij进行判别n若aij是第i行的最小数，则继续判别，看它是否也是第j列的最大数，如果成立则是鞍点。n当a
14、ij不是第i行的最小数或者不是第j列的最大数则选择下一个元素继续。 #define m 10 #define n 10 void saddle ( int Amn) /*求m行n列矩阵的鞍点*/ int i,j,k，smin,smax；/* smin 为true时表示Aij是第i行最小 数，smax 为true时表示Aij是第j列的最大数 */ for (i=0；im；i+ ) /* 用枚举法对矩阵的每个元素进行判断*/ for (j=0；jn；j+ ) k=0； 算法的C语言描述 while ( k= Aij ) /*是否是第是否是第i行最小数行最小数*/ k+; if (kn) smin=
15、false; else smin=true; if ( smin =true) /*是第是第i行最小数行最小数时继续判断判断*/ k=0； while (km) & (A k j=A ij ) /*是否是第是否是第j列最大数列最大数*/ k+; if (km) smax=false; else smax=true; if ( smin=true & smax=true ) printf ( “nA%d%d是鞍点是鞍点” ,i,j) ; /* A i j 是鞍点。是鞍点。*/ /end for j /end for i效率分析n时间效率n双重循环体内有两个并列的while循环语言。第一个whil
16、e循环执行O (n )次，第二个while循环最多执行O（m）次。所以总的时间效率应该是O (m*n*( m+n)n空间效率n除矩阵A用二维数组存贮外，用了几个辅加空间作为中间变量。所以空间效率为O(1)算法二算法二 算法思路：增加两个辅助数组，将矩阵每行最小数和每列的最大数求出来，并存放在Bn和Cm两个一维数组中见下图。 n 然后对Bn和Cm的每对元素进行比较，假定Bj和Ci相等（见下图），则Aij一定是鞍点。 算法C语言描述void Saddle ( int Amn) int i ，j ，k； int B n，Cm； for ( i=0；im；i+ ) /* 求每行的最小数求每行的最小数
17、*/ Ci=Ai0； for ( j=1；jAij Ci=Aij for (j = 0；jn；j+ ) /*求每列的最大数求每列的最大数*/ Bj = A0j； for ( i = 1；im；i+ ) if (BjAij) Bj = Aij； for ( i = 0；im；j+ ) /*求所有鞍点求所有鞍点 */ for ( j = 0；jn；j+ ) if ( Ci = =Bj) printf ( “nA%d%d是鞍点是鞍点” ,i,j) ; /* A i j 是鞍点。是鞍点。*/ 算法效率分析n本算法共有三个循环n求每行的最小数时间效率 O ( M*N )n求每列的最大数时间效率 O (M*N)n打印所有鞍点时间效率 O (M*N)n总的时间效率 O (M*N )n空间效率为： O (M + N ) n比较这两种算法，显然算法二的时间效率 大大优于算法一，但空间效率较差。n算法二是典型的空间换时间返回返回
