资源描述:
《数据结构与算法第1章》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、教材和参考书教材:数据结构(C语言版)严蔚敏,吴伟民参考书:数据结构与算法教程李春葆C语言数据结构软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程承上启下作业及考核作业:时间:周五数量:每次交一半,单双号考核:笔试:70-80%作业:20-30%课件courseware_ds@126.comwww.126.com帐号:courseware_ds密码:123456联系方式盛立杰电话13772002172邮件ljsheng@x
2、idian.edu.cn第1章绪论1.1什么是数据结构(定义)1.2数据结构的内容1.3算法1.4算法描述的工具1.5对算法作性能评价1.6关于学习数据结构第一章绪论计算机的应用:科学计算;控制、管理及数据处理等非数值计算的处理工作;计算机加工的对象:纯粹的数值;文本、表格和图像数据;如何表示、处理这些新的、具有一定结构的数据?《数据结构》是一门什么课程数据结构是一门研究非数值计算的程序设计问题时处理的操作对象以及它们之间的关系和操作等等的学科。解决数值计算问题的中心:建立适当的数学模型。解决非数值计算问题的中心:寻找适当的数据结构。数值问题:例1,求解梁架结构中的应力。数学模型:
3、KU=Ma11ann×x1xn…=b1bn…例2,预报人口增长情况。数学模型:dN(t)dt=rN(t)N(t)
4、t=t=N00N(t)=N0ert非数值问题:例1,图书馆的书目检索系统自动化问题。通过提供书名、作者或分类信息,你就可以从图书馆中检索某一本书。数据结构:线性表。D01曲守宁数据库004S01王永燕数据结构003L01潘玉奇程序设计002S01周劲数据结构001………………………004数据库002程序设计001,003数据结构…004曲守宁003王永燕002潘玉奇001周劲004D002L001,003S…例2,计算机和人对奕问题。计算机可以根据当前棋盘格局,来预测棋局发展
5、的趋势,甚至最后结局。数据结构:对弈树。O××O当前格局派生格局O××O××O××O×O××O×O××O×O××O例3,地图的着色问题。对地图上的每个区域染一种颜色,并且要求相邻的两个区域不能具有相同颜色。数据结构:图。12435671234567红绿绿蓝红黑绿1243567用最少的颜色染色数学计算机硬件计算机软件数据结构1.数据(Data)对客观事物的符号描述,能输入到计算机中并被计算机程序处理的符号的总称;能被计算机识别、存储和加工处理的信息的载体。例,数字:自然数、整数字母:a~z,单词图像:视频、音频信号等表格:2.数据元素(DataElement)数据元素是组成数据的基本单位
6、,是数据集合的个体,在计算机中通常作为一个整体进行考虑和处理。例,“对弈树”中的一个格局书目信息中的一条书目数据项:一个数据元素可由若干个数据项组成。例,一条书目信息是由书名、作者名、分类等多个数据项组成的数据项是数据的不可分割的最小单位。例如有一个学生表如下所示。这个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和班号)组成。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女99013.数据结构(DataStructure)数据结构是指相互之间存在一种或多种特定关系的数据元素集合,结
7、构(Structure)数据元素相互之间的关系。在形式上可用二元组表示:Data_Structure=(D,S)D:数据元素的有限集S:D上关系的有限集D={ki
8、1≤i≤n,n≥0}ki表示集合D中的第i个结点或数据元素n为D中结点的个数若n=0,则D是一个空集,表示D无结构可言,有时也可以认为它具有任意的结构S={rj
9、1≤j≤m,m≥0}rj表示集合S中的第j个二元关系(简称关系)m为S中关系的个数若m=0,则S是一个空集,表明集合D中的元结点间不存在任何关系,彼此是独立的例如,用二元组表示学生表,学生表中共有7个结点,依次用k1~k7表示,则对应的二元组表示为Data_Stru
10、cture=(D,S)其中:D={k1,k2,k3,k4,k5,k6,k7}S={,,,,,}逻辑结构图:可以将数据结构用图形形象地表示出来,图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶。上述“学生表”数据结构用下图的图形表示。例1,内部关系,复数Complex=(C,R)其中:C是含两个实数的集合{c1,c2};R={