最新数据结构绪论教学讲义PPT课件.ppt

《最新数据结构绪论教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构绪论主要教学内容：1.1本课程的研究对象；1.2数据结构的有关基本概念；1.3数据结构的分类及表示；1.4算法及算法分析（算法评价）1.1本课程研究的问题计算机的发展软件硬件应用领域数据处理的种类和能力数据数值数据非数值数据数(整数,实数)字符字符串文字图形图象声音数据：客观对象的符号表示数学中的整数、实数，课程名，地名、书名程序原始数据结果数据城市间交通网问题1.1本课程研究的问题数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。本课程讨论的问题：应用中常用的几种数据间的结构关系，及如何表示,如何存储，如何处理。1．2数据结构的有关概念数据：客观对

2、象的符号表示。例如：学号，姓名，班名都是数据。数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理数据项:相当于记录的“域”,是数据的不可分割的最小单位,如学号数据对象：性质相同的数据元素的集合.例如:所有班名相同的记录集合数据结构：是相互间存在关系的数据元素集合。1.2数据结构的有关概念对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。1．2数据结构的有关概念数据结构的基本操作：指对数据结构的加工处理数据的存储结构(物理结构)：数据

3、结构在计算机内存中的表示数据结构基本操作的实现：基本操作在计算机上的实现（方法)某班学生基本情况登记表，记录了每个学生的学号姓名专业政治面貌，表中的记录是按学生的学号顺序排列的。学号姓名专业政治面藐001王洪计算机党员002孙文计算机团员003谢军计算机团员004李辉计算机团员005沈祥福计算机党员006余斌计算机团员007巩力计算机团员008孔令辉计算机团员学生基本情况登记表的图示001003002004006005008007学生间学号顺序关系是一种线性结构关系例一常用的数据结构1）集合2）线性结构3）树结构4）图结构5）其它复杂结构1.3数据结构的分类及表示家族的族谱

4、假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE1．3数据结构的分类及表示例数据结构的表示图示表示图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；001003002004006005008007学生基本情况表的图示表示JIACBDHGFE家族树的图示表示1．3数据结构的分类及表示学生基本情况表的二元组表示（D，S）二元组表示二元组表示是用一个二元组（D，S）表示数据结构，其中D是数据元素集合，S是D上关系的集合。D={001，002，003，004，005，006，007，008}S={R}R={

5、<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}家族树的二元组表示（D，S）D={A，B，C，D，E，F，G，H，I，J}S={R}R={〈A,B>,,,,,,,,}1．3数据结构的分类及表示JIACBDHGFE0010030020040060050080071．4算法与算法分析1.4算法与算法分析一算法的概念算法是求解问题的操作序列算法的基本特征：1）输入：0个或多个输入；2）输出：1个或多个输出；3）有穷性：算

6、法必须在有限步内结束；4）确定性：组成算法的操作必须清晰无二义性。5）可行性：组成算法的操作必须能够在计算机上实现。求两个正整数m，n中的最大数MAX的算法（1）若m>n则max=m（2）若m<=n则max=n例描述算法的书写规则所有算法均以函数形式给出,算法的输入数据来自参数表参数表的参数在算法之前均进行类型说明有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明评价算法标准算法的正确性，可读性，可维护性，健壮性等，1算法时间复杂度T（n）本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。1．4算法与算法分析O（n3）称为矩阵相乘算法时间复杂度；O（n3

7、）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；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例矩阵相乘的基本运算：乘法加法；有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑（1）算法平均时