自考-数据结构导论第一章

数据结构导论开篇语1课程性质介于数学，计算机硬件和计算机软件三者之间的一门核心课程是计算机相关专业一门专业基础课在计算机软件的各个领域中均会使用到数据结构的有关知识开篇语2学习目标知识学习从数据结构与实现层次，系统学习基本数据结构掌握在各种常用的数据结构上实现的排列和查找运算技能培养掌握不同算法与设计思想提高分析问题以及解决问题的能力编程技能开篇语3课程内容第一部分：概论第二部分：各种数据结构及其实现方法（线性表、栈、队、树、图等）第三部分：数据结构的查找与排序开篇语4学习方法正确掌握本课程的知识体系纵横比较学习注意复习与重读注意循序渐进注意多练习第1章概论1.1引言1.1引言数据结构—计算机组织数据和存储数据的方式编程处理要求算法数据结构（逻辑结构）程序语句序列数据结构（存储结构）建立模型原始数据实际问题数学模型计算机程序实现学生档案信息表格程序实现档案管理功能（查找、读取、插入、删除、更新）计算机解决问题的步骤1.1引言学号姓名性别年龄入学成绩1001王韬男205891002潘小欣女215801003张艳女195681004赵李军男18580应用举例1——学生档案信息表1.1引言数据特点：每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；对它的操作通常是：在学生档案中查找出某人的档案，读取某个学生的信息，插入某个学生的信息，删除某个学生的信息，更新某个学生的信息等等。1.1引言应用举例2——制定教学计划在制定教学计划时，需要考虑：各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。计算机专业学生的必修课程课程编号课程名称需要的先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1应用举例2——制定教学计划第1章概论1.2基本概念和术语1.2基本概念和术语数据(Data)：是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项(DataItem)：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。（数据可由若干个数据元素组成，数据元素又可由若干数据项组成）1.2基本概念和术语1.2基本概念和术语学号姓名性别年龄入学成绩1001王韬男205891002潘小欣女215801003张艳女195681004赵李军男18580学生档案信息表数据元素数据项1.2基本概念和术语数据的逻辑结构：数据元素之间的结构关系。数据的逻辑结构是一种数学模型，体现了数据的组织方式。四类基本结构集合结构线性结构树型结构图状结构或网状结构1.2基本概念和术语特别注意：逻辑结构与数据元素本身形式、内容无关逻辑结构与数据元素的相对位置无关逻辑结构与所含结点个数无关1.2基本概念和术语数据的存储结构（物理结构）：数据的逻辑结构在计算机中的实现。四类存储方式:顺序存储方式：借助数据元素的相对存储位置来表示数据的逻辑结构；链式存储方式：借助数据元素地址的指针表示数据的逻辑结构；索引存储方式：借助索引表中的索引指示各存储节点的存储位置散列存储方式：用散列函数指示各节点的存储位置1.2基本概念和术语运算：对逻辑结构的加工。加工型运算：其操作改变原逻辑结构的值。如：结点个数、结点内容等。引用型运算：其操作不改变原逻辑结构的值基本运算：建立查找读取插入删除第1章概论1.3算法1.3算法算法规定了求解给定类型问题所需的所有处理步骤及执行顺序，使给定类型问题能在有限时间内被机械的求解。算法必须使用某种语言描述：程序伪语言算法非形式算法（自然语言）本教材采用类C语言描述算法printf表示输出，scanf表示输入第1章概论1.4算法分析1.4算法分析评价算法的好坏标准：正确性(Correctness)易读性(Readability)健壮性(Robustness)高效性(Effectiveness)一个算法的时空性是指算法的时间复杂度和空间复杂度（算法的计算量和存储量）。算法分析主要分析算法的时间复杂度和空间复杂度，目的是提高算法的效率。1.4算法分析1.合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作。2.确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量。以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况时间复杂度以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均情况时间复杂度最坏时间复杂度和平均时间复杂度，度量算法的性能第1章练习voidmax1(inta,b,c,d){a*=d;b*=d;c*=d;if(ab)x=a;elsex=b;if(cx)x=c;printf(%d\n,x);}voidmax2(inta,b,c,d){if(ab)x=a;elsex=b;if(cx)x=c;x*=d;printf(%d\n,x);}求算法max1和max2最坏情况时间复杂度设a、b、c、d中各含一个整数。求a、b、c中最大值与d的乘积第1章练习下列程序段的时间复杂度为________________。product=1;for(i=n;i0;i--)for(j=i;j=n;j++)product*=j;•基本操作执行次数T(n)=1+2+…+n=(n+1)n/2•时间复杂度量级为t(n)=O(n2)上节回顾基本概念：Data,DataElement,DataItem数据的逻辑结构：4类基本结构5种基本运算数据的物理结构：4类存储方式算法：基本要求C.R.R.E