《华科计算机学院数据结构课件1-绪论》由会员分享，可在线阅读，更多相关《华科计算机学院数据结构课件1-绪论（55页珍藏版）》请在金锄头文库上搜索。
1、1数据结构 Data structures 华中科技大学计算机学院 -2华中科技大学计算机学院华中科技大学计算机学院Instructor: 许贵平许贵平Email: TA: 杨浩杨浩 (QQ602928384)3本课程的意义与特征本课程的意义与特征 q传统数据结构与算法课程的意义传统数据结构与算法课程的意义算法和数据结构是计算机科学的两大支柱算法和数据结构是计算机科学的两大支柱数据结构是程序设计的基础数据结构是程序设计的基础Program=Algorithms+Data StructureKey abstractions computer scientists and engineers us
2、e almost every dayA big piece of what separates us from othersThis is the class where you begin to think like a computer scientist Prof. Dan Grossman UWq数据结构与算法课程的特征数据结构与算法课程的特征数据结构是计算机专业的一门综合性专业基础课数据结构是计算机专业的一门综合性专业基础课是介于数学、计算机硬件、计算机软件的一门核心课程是介于数学、计算机硬件、计算机软件的一门核心课程4本课程的任务本课程的任务1.基本数据结构的定义、特性、运算与算法
3、基本数据结构的定义、特性、运算与算法 1.1 线性结构：线性表；栈线性结构：线性表；栈,队列队列,双队列；数组双队列；数组,串。串。 1.2 非线性结构：树非线性结构：树,二叉树；图二叉树；图,网络。网络。 2.数据结构的存储结构与实现数据结构的存储结构与实现 选择存储结构选择存储结构,设计算法设计算法 3.查找算法：顺序查找算法：顺序,折半折半,分块分块,哈希哈希,二叉排序树等二叉排序树等 4.排序算法：内部排序排序算法：内部排序,外外部排序部排序 5.文文件件 6.并行并行算法与数据结构算法与数据结构 7.基本基本应用应用与综合与综合应用应用注注：第第8章章和和带带*号号的内的内容不作要求
4、容不作要求。5Why parallel algorithmsp A typical machine has 4 to 8 computing cores, and soon this number will be 16, 32, and 64. p While the number of cores grows at a rapid pace, theper- core speed hasnt increased much over the pastseveral years.6基本基本要求要求1.阅读教材阅读教材与与参考书参考书；2.完成完成一定数一定数量量的的书面作书面作业；业； 3.使用
5、使用C或或C+完成完成4或或5个以上个以上的的上上机机作作业 。业 。成绩成绩 考试（考试（约约70）+作作业、实业、实验验、考勤考勤和课和课堂堂表现表现（约约30 ）7数据结构数据结构教材教材与与参考书参考书1.数据结构数据结构（C语言版）语言版）严蔚敏 吴伟民严蔚敏 吴伟民清清华大学华大学出版社出版社 1997.42.数据结构数据结构题集题集严蔚敏严蔚敏等等清清华大学华大学出版社出版社 1999.23.数据结构与算法分数据结构与算法分析析张铭张铭等等译 电子工译 电子工业业出版社出版社 1998.84.数据结构实数据结构实用教用教程程（C/C+描述）描述）徐孝凯清徐孝凯清华大学华大学出版社
6、出版社 1999.128第第一一章绪论章绪论1.1 什么什么是数据、结构是数据、结构(关系关系)、数据结构、数据结构？建立建立数学数学模型模型是分是分析具体问题析具体问题的的过过程程，包括，包括：s分分析具体问题析具体问题中中操作对象操作对象s找找出这些对象间出这些对象间的的关系，并用关系，并用数学数学语言描述语言描述数学数学模型模型分两分两类类：1）数数值值计算计算类类：例例：Love modelwhereR is Romeos love for JulietJ is Juliets love for Romeo(or hate if negative)a, b, c, d are cons
7、tants that determine the “Romantic styles”dRaRbJdt dJcRdJdt=+ =+92）非数非数值值计算计算类类：例例1: 5个整个整数组数组成成的的集集合：合： D=20,-5，66, 15,44 其其中中:20,-5,66等等称为称为数据数据元素元素(元素元素)， 元素元素与与元素之元素之间关系间关系是是它们同属它们同属于于集集合合D。 元素元素与与元素元素间间无直接无直接关系关系。例例2: 一列一列整整数：数：(线性结构线性结构) L=(20,-5，66, 15,44） 其其中中:元素元素与与元素之元素之间间在在L中是中是前后前后关系或关系或
8、线性线性关系关系。 L=(20,-5,66,15,44)是一是一个个线性表线性表。10例例3 一一张张登记登记表表DL序序号号姓名姓名性性 别 年 龄别 年 龄1 李刚男李刚男25 记录记录1 2 王霞女王霞女29 记录记录23 刘刘大大海男海男40 记录记录34 李爱林男李爱林男44 记录记录4 其其中：中：姓名姓名、性、性别别、年龄年龄是是数据数据项项(item)、数据数据域域(field)；(姓名姓名，性性别别，年龄年龄)是是记录记录(record),C语言语言将将“记录记录“(record)定义定义为为”结构结构”(struct)；登记登记表表也也是一是一个个线性表线性表。11例例4树
9、树状状结构结构其其中中:A、B、C等是等是结结点点(node)；A与与B, B与与E, A与与C等等之之间间是是层次层次关系关系或或父父子关系子关系。华中科技大学(A)计算机学院(B)管理学院(C)成教学院(D)科学系(F) 应用系(G) 工程系(H)安全系(E)12多多叉叉路口交通灯管理路口交通灯管理问题问题CEDABABACADBABCBDDADBDCEAEBECED图13例例5 图图状状结构结构ABDCEFG其其中：中：A、B、C 等是等是顶点顶点(vertex),图中任意两图中任意两个个顶点之顶点之间间都可能有都可能有关系关系。图图可可以以表表示示许许多多应用应用： 交通路交通路网网
10、城市供水城市供水网网 网络网络路由路由 社社会会关系关系网网(Social network) 14数据结构的学科定义数据结构的学科定义:是一门是一门研究研究非数非数值值计算计算的程序设计的程序设计问题问题中计算中计算机的机的操作对象操作对象以以及它们之及它们之间间的的关系关系和和操作操作等等等等的学科。的学科。Data structures“Clever” ways to organize information in order to enable efficient computation over that information.151.2 基本基本概念概念和和术术语语1.数据数据（d
11、ata):所有能输入到所有能输入到计算机中计算机中并并被被计算机程序计算机程序加加工工、处理处理的的符符号号的的总称总称。如如：整整数、实数、数、实数、字符字符、声音声音、图、图象象、图、图形形等。等。2.数据数据元素元素(data element):数据的基本数据的基本单位单位。（元素元素、记录记录、结、结点点、顶点顶点）在在计算机程序中计算机程序中通常通常作作为为一一个整体个整体进进行考行考虑虑和和处理处理。3.数据数据项项(data item):是数据的是数据的不不可可分分割割的的最小单位最小单位。如如：姓名姓名、年龄年龄等等一一个个数据数据元素可由元素可由一一个或个或多多个个数据数据项
12、项组组成成。如如: (姓名姓名、年龄年龄)164.数据数据对象对象(data object)由由性性质相同质相同(类型类型相同相同)的数据的数据元素元素组组成成的的集集合合。数据数据对象对象是数据的一是数据的一个子集个子集。例例1 由由4个整个整数组数组成成的数据的数据对象对象D1=20,-30,88,45例例2 由正由正整整数组数组成成的数据的数据对象对象D2=1,2,3,.例例3 由由26个个字母字母组组成成的数据的数据对象对象D3=A,B,C,.,Z其其中：中：D1，D3是是有穷有穷集，集，D2是是无穷无穷集集。5.数据结构数据结构集集合合线性结构线性结构树树形形结构结构图图状状结构结构
13、相相互互之之间间存存在在一一种种或或多多种种特定特定关系关系的数据的数据元素元素的的集集合。合。数据数据元素之元素之间间的的关系关系称为称为结构结构。四四类类基本结构基本结构：仅仅同属同属 一一个集个集合合一一对对一一一一对对多多多多对对多多Data_Structure=（D, S）18数据结构数据结构6.数据的数据的逻辑逻辑结构结构抽抽象象地反映各地反映各数据数据元素之元素之间间的的逻辑逻辑关系关系。数据结构数据结构(逻辑逻辑结构结构)分分类类:线性结构线性结构非 线 性非 线 性 结结构构1.线性表线性表 2.栈栈 3.队列队列,双队列双队列 4.数组数组 5.字符字符串串1.树树,二叉树
14、二叉树 2.图图197.数据的存储结构数据的存储结构数据数据（逻辑逻辑）结构结构在在计算机存储计算机存储器器中的实现中的实现或或映映象象(mapping)。存储结构存储结构也称为也称为：存储表存储表示示,物物理理结构结构,物物理理表表示示。数据的逻辑结构与存储结构密切相关数据的逻辑结构与存储结构密切相关算法设计算法设计逻辑结构逻辑结构算法实现算法实现存储结构存储结构存储结构分为：存储结构分为： 顺序顺序存储结构存储结构借助元素在存储器中的借助元素在存储器中的相对位置相对位置来表示来表示 数据元素间的逻辑关系数据元素间的逻辑关系 链式链式存储结构存储结构借助指示元素存储地址的借助指示元素存储地址
15、的指针指针表示数据表示数据 元素间的逻辑关系元素间的逻辑关系20a+3a+2a+1a 内存储器DCBA.apaa3a2a1a0DCBAC语言语言实现实现方方法：法：char a4=A,B,C,D；(1)顺序存储结构顺序存储结构(向向量量,一一维维数组数组)例例. 线性表线性表L（A,B,C,D）；21(2)非顺序存储结构非顺序存储结构(链链接接表表）例例. 单单链链表：分表：分配配不不一定一定连续连续的的空空间间地址d地址c地址b地址a0DdCcBbAaHead地址d地址c地址b地址aDCBA建立建立数据数据 间间的的联联系系22(2)非顺序存储结构非顺序存储结构(链链接接表表）例例. 单单链链表表: 存存放放数据的数据的空空间间顺序顺序可可任意任意地址c地址a地址b地址ddCbAcB0DaHead一一般般表表达达形形式式： data next Head A B C D
