数据结构第一章小节

《数据结构第一章小节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构计算机基础软件教研室张翼飞E-mail：sauzyf@gmail.com数据结构目录第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章内部排序第十一章外部排序第十二章文件课程内容本课程是计算机专业的一门专业技术基础课。主要介绍线性表、栈和队列、串、数组和广义表、树和二叉树以及图等几种基本类型的数据结构，以及在程序设计中经常遇到的两个问题——查找和排序。教学重点熟练掌握线性表、栈和队列、串、数组和广义表、树和二叉树、图等基本类型的数据结构的逻辑结构、存储结构以及基本操作的实现，熟练掌

2、握查找和排序的基本算法及其实现；培养综合运用基本结构类型和基本算法建立问题模型，用计算机解决实际问题的能力。教学要求学会分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的时间分析和空间分析的技巧。学时安排本课程总学时72学时，其中课堂讲授56学时，上机实验16学时。教材：本讲义以清华大学出版社出版，严蔚敏、吴伟民编著的《数据结构》教材为蓝本。数据结构的学习方法本学科重要性方向不同，学习方法不同考研工作参考用其它语言描述算法的书籍第一章绪论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.1数据结构讨论

3、的范畴(数据结构在软件开发中的地位)系统分析系统设计系统实现系统维护系统设计NiklausWirth（Pascal之父）Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型结构静力分析计算例如:数值计算的程序设计问题─━线性代数方程组─━环流模式方程(球面坐标系)全球天气预报非数值计算的程序设计问题登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例1书目自动检索系统例2人机对奕问题树……..……..…...….

4、..…...…...例三：多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图概括地说，数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。数据元素:如:整

5、数“5”,字符“N”等。----是不可分割的“原子”其中每个款项称为一个“数据项”它是数据结构中讨论的最小单位数据元素也可以由若干款项构成。例如：描述一个学生的数据元素称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项数据结构：带结构的数据元素的集合有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系数据结构是相互之间存在着某种逻辑关系的数据元素的集合。不同的“关系”构成不同的“结构”从关系或结构分，数据结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构包括“逻辑结构”和“物

6、理结构”两个方面(层次):逻辑结构是对数据元素之间的逻辑关系的描述，它可以应一个数据元素的集合和定义在此集合上的若干关系来表示;物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。数据结构的形式定义描述为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象

7、方法：（表示x,y的方法）顺序映象借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式映象借助指示元素存储地址的指针表示数据元素间的逻辑关系在不同的编程环境中，存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型，typedefintLong_int[3]定义长整数为:typedefstruct{inty;//年号Yearintm;//月号Monthintd;//日号Day}DateType;//日期类型定义“日期”为:定义

8、“学生”为