数据结构第一次课

《数据结构第一次课》由会员分享，可在线阅读，更多相关《数据结构第一次课（31页珍藏版）》请在金锄头文库上搜索。

1、 有三个犯人要被关进监狱三年，监狱长说可以满足他 们每人一个要求。美国人爱抽雪茄，要了三箱雪茄；法国 人最浪漫，要一个美女相伴；而犹太人说，他要一部与外 界沟通的电话。三年过后，第一个冲出来的是美国人，嘴 里鼻孔里塞满了雪茄，大喊道：“给我火，给我火！”原来 他忘了要火了。接着出来的是法国人。只见他手里抱着一 个小孩子，美女手里牵着一个小孩子，肚子里还怀着第三 个。最后出来的是犹太人，他紧紧握住监狱长的手说：“ 这三年来我每天与外界联系，我的生意不但没有停顿，反 而增长了200，为了表示感谢，我送你一辆劳施莱斯！” 这个故事告诉我们，什么样的选择决定什么样的生活。今 天的生活是由多年前我们的选

2、择决定的，而今天我们的抉 择将决定我们多年后的生活。我们要从现在开始做起，选 择接触最新的信息，了解最新的趋势，从而更好的创造自 己的将来。手机：13997686926 E-mail： QQ： 674307846姜敏老师的联系方式：课时安排： 数据结构 80学时 时间：117 周，周一12节 L2516周三56节 L2408116双周，周四56节 L2317教材： 周鹏等,数据结构与算法,湖北科学技术出版社 参考书： 严蔚敏. 数据结构. 北京: 清华大学出版社 李春葆. 数据结构习题与解析.清华大学出版 社第一章 绪 论1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与

3、实现*1.4 算法和算法分析* 1.1 什么是数据结构Q1：数据结构的定义？Q3：学习数据结构有什么用？Q2：数据结构涵盖的内容？ 1.1.1 数据结构的定义人脑： 感受 判断 计算 记忆 反应电脑： 输入 控制 运算 存储 输出1. 从计算机工作的特点说起科学计算 事务处理人工智能 算法复杂度计算机问题求解信息表示信息处理程序设计数据结构算 法数据结构主要解决计算机中的信息表示及关系定义问题数值型数据 字符、表格、图形图像 对象复杂度 1.1 什么是数据结构 例1 书目自动检索系统登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格：书目卡片书目文件按书名按作者名按分类号索引表

4、线性表 例2 人机对奕问题. 交通图的连通问题 数据结构定义: 是一门研究非数值计算 的程序设计问题中计算机的操作对象以及 它们之间的关系和操作等等的学科2. 可以直接地认为：数据结构就是研究数据的逻 辑结构和物理结构以及它们之间相互关系，并对 这种结构定义相应的运算，而且确保经过这些运 算后所得到的新结构仍然是原来的结构类型。通过以上几例可以看出: 1. 描述非数值计算问题的数学模型不再是数学方 程，而是诸如表、树、图之类的数据结构。 1.1.2 数据结构涵盖的内容 1.1.3 学习数据结构有什么用 1. 计算机系列课程之间的联系 1.1.3 学习数据结构有什么用2. 数据结构课程的地位是介

5、于数学、计算机硬件和计算机软件 三者之间的一门核心课程关系物理 存储数学软件硬件逻辑结构 与操作 1.1.3 学习数据结构有什么用2. 数据结构课程的地位地位：专业基础课，应用范围广、作用大 1.1.3 学习数据结构有什么用同样的数据对象，用不同的数据结构 来表示，运算效率可能有明显的差异。3. 有助于提高程序设计能力优秀程序设计好数据结构好算法程序设计数据结构算 法计算机问题求解信息表示信息处理武林高手计算机高手基础练得好站桩、劈掌等程序设计基础知识C 、C+ 、Java、C#等内功内功心法如易筋经、 太极内功心法等软硬件技术基础 专业知识（物理、力学）武器、 门派招式刀、剑、钩等 华山剑法

6、、少林拳等可视化开发工具Vc、Vb、 Delphi、VJ、VC#等武林高手 VS 计算机高手大家想不想成为 计算机高手呢？ 这门课的特点和学习方法武林高手和计算机高手的共同特性大抵都很聪明，悟性奇高。不管是什么，都能做到举一反三。 好动。总是会把自己的疑问通过实战来获得答案。 不断修炼基础和内功。除传统意义内功外，内功还包括经验值 。执著。不管是练功的时候，还是实战的时候，不管是对自己的信 念还是自己所从事的事情。这门课的特点和学习方法 注重理解举一反三。 注重实践通过实践加深理解，眼过千遍不如手过一遍。 有一定难度相信通过努力能学好不畏艰难，执着追求。 1.2 基本概念和术语数据(Data)

7、: 是对信息的一种符号表示。在计算机 科学中是指所有能输入到计算机中并被计算机程序 处理的符号的总称。数值型非数值型 数据元素(Data Element):是数据的基本单位，在 计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数 据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的 集合，是数据的一个子集。 数据结构(Data Structure)：是相互之间存在一种 或多种特定关系的数据元素的集合。数据数据对象数据结构数据元素 数据项性质相 同存在一种或多 种特定关系数据基本 单位数据结构的形式化定义：数据结构是一个二元

8、组 ：Data-Structure=(D，S)其中D是数据元素的有限集,S是D上关系的有限 集。 例 复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别 表示复数的实部和虚部。R=P，P是定义在集合 上的一种关系C1，C2。根据数据元素间关系的基本特性，有四种基本数据结构（集合）数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图状结构多个对多个，如图解释1： 什么叫数据的逻辑结构？ 答：指数据元素之间的逻辑关系。即从逻辑 关系上描述数据，它与数据的存储无关，是 独立于计算机的。逻辑结构可细分为4

9、类：例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。（1） S=(D, R)D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d)解： 上述表达式可用图形表示为： b c a e f d此结构为线性的。（2） S=(D, R)D=di | 1i5R=(di , dj ), ijd1d5 d2d4 d3该结构是非线性的图。解：上述表达式可用图形表示为：数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构最常用的存储结构为： 顺序存储结构借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储

10、结构借助指示元素存储地址的指针表示数据元素间的逻辑关系解释2：什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑 结构在计算机存储器内的表示（或映像）。 它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列元素n元素i元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3元素41345 h存储地址 存储内容 指针1345 元素1 14001346 元素4 . .1400 元素2 1536. .1536 元素3 1346链式存储 h解释3：什么是数据的运算（操作或处

11、理）？答：在数据的逻辑结构上定义的操作,它在 数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序 数据结构是从具体到抽象的过程中产生 的。核心是分解与抽象。 1) 通过分解，可以划分出数据的三个层次：数据 、数据元素、数据项；再通过抽象，舍去数据元素的具 体内容而关注它们的逻辑关系，就得到逻辑结构。 2) 通过分解，可以划分出处理要求的各种功能； 再通过抽象，舍去实现细节，就得到运算定义。 3) 归纳1)、2)可把问题变换为数据结构。程序=数据结构+算法 程序是从抽象到具体的过程中产生的。1) 通过对数据存储实现的考虑，得到存储结构；2) 通过对运算实现细节的考虑，得到解决问题的程序。 解释4：逻辑结构、存储结构、操作及算法的关系？如何应用数据结构知识求解决实际问题？课堂学习内容（动脑）课外练习内容（动手）理论与实践相结合数据结构算法设计层次方面数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同结构的比较及算法分析 数据结构课程包括三个层次的五个要素：