数据结构-软件基础概述.ppt

计算机软件技术基础 主讲：张 静 二系二教 学习内容及要求 数据结构 掌握数据结构的类型、算法及编程技巧，能用形式语言描述算法和简单评估算法性能，并且能用自己熟悉的语言(推荐：C语言)编程实现算法。 操作系统 掌握操作系统的基本功能、主要组成部分，多道程序环境下出现的问题及解决方法，以及并行程序设计的有关概念和方法。 课堂教学、思考题、上机实践、考试 《数据结构－C》唐策善等 高等教育出版社 《数据结构》严蔚敏 清华大学出版社 《操作系统精髓与设计原理》William Stallings 著，清华大学出版社 《操作系统设计与实现》(第二版) Andrew S.Tanenbarm 清华大学出版社 《数据结构》课程的地位和特点 是设计和实现编译程序、操作系统、数据库系统以及其他系统程序和应用程序的基础。 它不仅仅是计算机专业的核心课程，也是其他非计算机专业的主要选修课程之一。 课程抽象，内容丰富，学习难度较大。 解决具体问题的基本步骤： (1) 把具体问题抽象成相应模型，选择适当的数据结构(逻辑结构)； (2) 选择合适的存储结构，即如何将问题中所用到的数据存储到计算机中去； (3) 根据具体的问题在相应的存储结构上进行操作或运算，并得出结果； (4) 检查算法的正确性，进行效率分析。 2.1.2 概念、术语 数据(Data)：是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据(整数、定点数、浮点数) 非数值性数据(图像、声音、文字数据) 2.1.2 概念、术语 数据元素(Data Element)：数据的基本单位，即数据集合中的一个个体，又称为元素、结点、顶点、记录。 数据元素可由若干数据项(Data Item)组成：数据项是数据的最小单位。 数据项(Data Item) ? 2.1.2 概念、术语 数据对象(data object)：性质相同的数据元素集合。 如： 整数的数据对象N={0,?1,?2,…} 字母字符的数据对象C={A,B,…,Z}。 2.1.2 概念、术语 数据类型(data type)：是变量可能取的值和能做的运算的集合。即： 数据对象+操作(运算) 如：矩阵＋(求转置、加、乘、求逆、求特征值) 构成一个矩阵的数据类型 2.1.2 概念、术语 1) 基本数据类型(原子数据类型) 如：C语言中的基本数据类型 int char float double void 整型 字符型 浮点型 双精度型 无值 2) 结构数据类型 如：数组、结构、联合、枚举 struct student{ char name; int sex; float achievement; …} 2.1.2 概念、术语 数据结构(Data Structure) ： 是指同一数据对象的所有数据成员之间的关系。记为： Data_Structure = {D, R} 其中，D 是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 如：n维向量 x=(x1,x2,…xn) D={x1,x2,…xn} R={ x1,x2 , x2,x3 ,… xn-1,xn } 2.1.2 概念、术语 1) 逻辑结构— 描述数据元素间的逻辑关系，与存储无关，独立于计算机，为具体问题抽象出来的数学模型。 数据的逻辑结构有： 线性结构：有且仅有一个开始结点和一个终端结点，所有结点最多只有一个直接前趋和一个直接后继(线性表)。 非线性结构：一个结点可能有多个直接前趋和直接后继(树、图(网络))。 堆结构 2.1.2 概念、术语 2) 物理结构(存储结构) —数据的逻辑结构在计算机中的存储实现，其依赖于具体的计算机语言。