数据结构C语言版严蔚敏绪论教案.ppt

数据结构C语言版严蔚敏绪论 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望祝同学们新学期愉快、学习进步！祝同学们新学期愉快、学习进步！数据结构课程所处的地位：介于数学、计算介于数学、计算机硬件和计算机机硬件和计算机软件三者之间的软件三者之间的一门核心课程。一门核心课程。数据结构数据结构是计算机专业的一门综合性专业基是计算机专业的一门综合性专业基础课础课是计算机专业本是计算机专业本/专科生必修学位课程专科生必修学位课程是计算机研究生是计算机研究生/升本入学考试必考科目升本入学考试必考科目是软件人员水平考试内容是软件人员水平考试内容F是数学建模、是数学建模、ACM程序竞赛基础程序竞赛基础 学业基础n先修课程：高级语言程序设计先修课程：高级语言程序设计 (如如 C/C+C/C+语言语言)n后续课程：操作系统（例：打印机后续课程：操作系统（例：打印机 队列管理）、数据库原队列管理）、数据库原 理、人工智能等。理、人工智能等。课程安排课程安排n总学时：总学时：90(1890(18周周*5)5)讲课学时：讲课学时：72 72 实验学时：实验学时：1818教学参考书教学参考书教教材：材：数据结构数据结构C语言版语言版严蔚敏、吴伟民严蔚敏、吴伟民-清华大学出版社清华大学出版社n数据结构数据结构C语言篇语言篇习题与解析习题与解析李春葆李春葆-清华大学出版社清华大学出版社n数据结构自学考试指导数据结构自学考试指导丁宝康等丁宝康等清华大学出版社清华大学出版社n算法与数据结构算法与数据结构，范策等，机械工业出版社，范策等，机械工业出版社 http:/210.44.232.53/ec/C70/Index.htm(我院精品课程我院精品课程)n http:/ 数据结构数据结构+精品课程精品课程实 验u实验环境实验环境:Win-tc或或Turboc或或VC+u实验项目名称实验项目名称:一元稀疏多项式的加减运算一元稀疏多项式的加减运算栈和队列的抽象数据类型实现栈和队列的抽象数据类型实现二叉树的建立、遍历及典型算法实现二叉树的建立、遍历及典型算法实现图的建立、遍历及典型算法实现图的建立、遍历及典型算法实现典型查找算法实现典型查找算法实现内部排序算法实现内部排序算法实现课程设计u题目（任选一）题目（任选一）:迷宫问题求解迷宫问题求解算术表达式求值算术表达式求值校园导游系统校园导游系统图书管理信息系统的设计与实现图书管理信息系统的设计与实现查找算法综合比较查找算法综合比较排序算法综合比较排序算法综合比较u要求达到的目标要求达到的目标:文档清晰、完整，学会分析解决问题文档清晰、完整，学会分析解决问题程序运行良好程序运行良好1.1.自觉预习、遵守纪律、认真听课、及时复习；自觉预习、遵守纪律、认真听课、及时复习；2.2.按时、独立、认真地完成每次作业；按时、独立、认真地完成每次作业；每一章有作业题，按时交。每一章有作业题，按时交。每次实验前做好准备工作每次实验前做好准备工作,写好程序写好程序,实验后交实验报告（写在纸实验后交实验报告（写在纸上）。上）。期中布置课程设计期中布置课程设计3.3.积极回答课堂提问；积极回答课堂提问；4.4.成绩评定标准：成绩评定标准：5.5.平时表现：占平时表现：占30%30%，包括作业、课程设计、提问、学习纪律，包括作业、课程设计、提问、学习纪律6.6.期末考试：闭卷笔试，占期末考试：闭卷笔试，占70%70%目 录Contents 第一章第一章 绪绪 论论 (4(4学时学时)第二章第二章 线性表线性表 (8(8学时学时)第三章第三章 栈和队列栈和队列 (8(8学时学时)第四章第四章 串、串、数组和广义表数组和广义表 (6(6学时学时)第五章第五章 树和二叉树树和二叉树 (10(10学时学时)第六章第六章 图图 (6(6学时学时)第七章第七章 查找查找 (6(6学时学时)第八章第八章 排序排序 (6(6学时学时)数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖于运算的实现依赖于存储结构存储结构1.1 1.1 什么是数据结构什么是数据结构1.1.2 2 基本概念和术语基本概念和术语1.1.3 3 抽象数据类型抽象数据类型1.41.4 算法及算法分析（算法评价）算法及算法分析（算法评价）第一章第一章绪绪论论计算机发展简史计算机发展简史众众所所周周知知，二二十十世世纪纪四四十十年年代代，电电子子数数字字计计算算机机问问世世的的直直接接原原因因是是解解决决弹弹道道学学的的计计算算问问题。题。早早期期，电电子子计计算算机机的的应应用用范范围围，几几乎乎只只局局限限于于科科学学和和工工程程的的计计算算，其其处处理理的的对对象象是是纯纯数数值值性性的的信信息息，通通常常，人人们们把把这这类类问问题题称称为为数数值计算。值计算。近三十年来，电子计算机的发展异常迅猛近三十年来，电子计算机的发展异常迅猛表表现现在在计计算算机机本本身身运运算算速速度度不不断断提提高高、信信息息存存储储量量日益扩大、价格逐步下降日益扩大、价格逐步下降更更重重要要的的是是计计算算机机广广泛泛地地应应用用于于情情报报检检索索、企企业业管管理理、系系统统工工程程等等方方面面，已已远远远远超超出出了了科科技技计计算算的的范范围，而渗透到人类社会活动的一切领域围，而渗透到人类社会活动的一切领域计算机发展简史计算机发展简史与此相应，与此相应，计算机的处理对象也从计算机的处理对象也从简单的简单的纯数值性纯数值性信息信息发展到发展到非数值性非数值性的和具有一定结构的信息的和具有一定结构的信息计算机发展简史计算机发展简史“数据结构数据结构”作为一门独立的课程在国外是从作为一门独立的课程在国外是从1968年才开始设立的。年才开始设立的。1968年美国唐年美国唐欧欧克努特教授开创了数据结构克努特教授开创了数据结构的最初体系，他所著的的最初体系，他所著的计算机程序设计技巧计算机程序设计技巧第第一卷一卷基本算法基本算法是第一本较系统地阐述数据的逻是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。辑结构和存储结构及其操作的著作。“数据结构”被列入美国一些大学计算机科学系的教学计划。数据结构数据结构D.Knuth的巨著的巨著计算机程序设计艺术计算机程序设计艺术n第一卷第一卷“基本算法基本算法”n第二卷第二卷“半数字算法半数字算法”n第三卷第三卷“排序与搜索排序与搜索”1974年获得图灵奖，是年获得图灵奖，是40届中唯一因一部影响巨大的书届中唯一因一部影响巨大的书而获奖而获奖数据结构数据结构 发展阶段：发展阶段：数据结构的概念不断扩充，包括了网络、集合数据结构的概念不断扩充，包括了网络、集合代数论、关系等代数论、关系等“离散数学结构离散数学结构”的内容。的内容。70年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设该课程。数据结构数据结构 数据结构是研究什么的？这是课程最基本的问数据结构是研究什么的？这是课程最基本的问题，关系到我们为什么要学习数据结构这门课程题，关系到我们为什么要学习数据结构这门课程1.1什么是数据结构什么是数据结构从应用问题涉及的对象来分可分为从应用问题涉及的对象来分可分为数值问题数值问题 非数值问题非数值问题数值问题数值问题就是我们平时所说的计算问题，如已知圆的就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积半径，要求圆的面积非数值问题非数值问题就是问题中涉及的模型不能用数学方程来就是问题中涉及的模型不能用数学方程来表达的那些问题表达的那些问题1.1什么是数据结构什么是数据结构n例例1（任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车（任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为床的可用台时数分别为800和和900，三种工件的数量分别为，三种工件的数量分别为400、600和和500，且已知用，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？的加工任务，才能既满足加工工件的要求，又使加工费用最低？数值问题与非数值问题有什么不同数值问题与非数值问题有什么不同1）数值问题）数值问题n解解设在甲车床上加工工件设在甲车床上加工工件1、2、3的数量分别为的数量分别为x1、x2、x3，在乙车床上加工工件，在乙车床上加工工件1、2、3的数量分别为的数量分别为x4、x5、x6。可建立以下线性规划模型：。可建立以下线性规划模型：1）数值问题）数值问题例例2 已知：游泳池的长已知：游泳池的长length和宽和宽wide，求面积求面积area。分析：分析：1.1什么是数据结构什么是数据结构（1）问题涉及的对象：问题涉及的对象：length,wide,area是实数是实数可用数值表示可用数值表示；（2）对象之间的关系）对象之间的关系：area=length wide可用方程或可用方程或函数表示函数表示；（3）数据存储：）数据存储：可用程序设计语言中的实型变量存储；可用程序设计语言中的实型变量存储；（4）问题求解：）问题求解：用某种计算方法求解；用某种计算方法求解；程序：main()int len,wide,area;scanf(“%d%d%n”,&len,&wide);area=len*wide;printf(“area=%d”,area);可见，对于数值问题，可见，对于数值问题，对象之间的关系通常可以用对象之间的关系通常可以用方程或函数表达方程或函数表达，只要能列出表达对象之间关系的，只要能列出表达对象之间关系的方程或函数，找到求解方程或函数的方法，就可以方程或函数，找到求解方程或函数的方法，就可以编写程序了。编写程序了。n求一组（求一组（n个）整数中的最大值。个）整数中的最大值。n算法：基本操作是两两比较，求两个数的大小算法：基本操作是两两比较，求两个数的大小n模型：？模型：？1.1什么是数据结构什么是数据结构1.1什么是数据结构什么是数据结构2）非数值问题）非数值问题应用举例应用举例1 电话号码查询系统电话号码查询系统应用举例应用举例2 学籍档案管理学籍档案管理应用举例应用举例3 全排列问题全排列问题应用举例应用举例4 制定教学计划制定教学计划数值问题与非数值问题有什么不同数值问题与非数值问题有什么不同举例举例1-电话号码查询系统电话号码查询系统设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的名字和个人的名字和其相应的电话号码，假定按如下形式其相应的电话号码，假定按如下形式(a1，b1)(a2，b2)(an，bn)其中其中ai，bi(i=1，2n)分别表示某人的名字和分别表示某人的名字和对应的电话号码对应的电话号码要求设计一个算法，当给定任何一个人的名字时，要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码该算法能够打印出此人的电话号码;如果该电话簿中如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人根本就没有这个人，则该算法也能够报告没有这个人的反馈信息的反馈信息举例举例2-学籍档案管理学籍档案管理假设一个学籍档案管理系统包含如下表假设一个学籍档案管理系统包含如下表1-1所示的学生信息所示的学生信息表表表表1-11-1特点特点?特点特点:每个学生的信息占据一行，所有学生的信息按学号每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格顺序依次排列构成一张表格表中每个学生的信息依据学号的大小存在着一种前表中每个学生的信息依据学号的大小存在着一种前后关系，这就是后关系，这就是线性结构线性结构对它的操作通常是插入某个学生的信息，删除某个对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等个学生的信息等等123123 132 213 231 321 312 132 213 231 321 312 1241241234 1243 1324 1342 1423 1432 1234 1243 1324 1342 1423 1432 等等举例举例3输出输出n个对象的全排列个对象的全排列解决解决图图 1-1 3个对象的全排列过程个对象的全排列过程(a1)(a2)(a3)(a4)(a5)(a)计算机和人对奕问题l l 在求解过程中，所处理的数据之间具有层次关系，这是在求解过程中，所处理的数据之间具有层次关系，这是树形结构树形结构l l 对它的操作有：建立树形结构，输出最低层结点内容等等对它的操作有：建立树形结构，输出最低层结点内容等等在制定教学计划时，需要考虑各门课程的开设在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表机专业课程的开设情况如下表1-2所示：所示：举例举例44制定教学计划制定教学计划表表表表1-21-2课程先后关系的图形描述形式c1c9c4c2c12c10c11c5c3c6c7c8图图 1-2 计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系1 1）问题涉及的对象：问题涉及的对象：课程课程可用课程名表示可用课程名表示 不能用数值表示不能用数值表示2 2）对象之间的关系对象之间的关系：需要考虑各门课程的开设顺序。有些课程是某些课程的需要考虑各门课程的开设顺序。有些课程是某些课程的先导课程。必须先开先导课程，再开后续课程。先导课程。必须先开先导课程，再开后续课程。课程之间的这种关系不能用方程或课程之间的这种关系不能用方程或 函数表示函数表示3 3）数据及数据之间的关系如何存储？数据及数据之间的关系如何存储？4 4）如何求解如何求解？特点特点n课程之间的先后关系用课程之间的先后关系用图结构图结构描述描述n通过实施创建通过实施创建图结构图结构，按要求将图结构，按要求将图结构中的顶点进行线性排序中的顶点进行线性排序从应用问题涉及的对象来分可分为从应用问题涉及的对象来分可分为数值问题数值问题 非数值问题非数值问题数值问题数值问题就是我们平时所说的计算问题，如已知圆的就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积半径，要求圆的面积非数值问题非数值问题就是问题中涉及的模型不能用数学方程来就是问题中涉及的模型不能用数学方程来表达的那些问题表达的那些问题小结：小结：n数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计问题的程序设计问题中计算机的中计算机的操作对象操作对象及其之间及其之间关系与操作关系与操作的学科。的学科。1.1 1.1 什么是数据结构需求分析需求分析总体设计总体设计模块分割模块分割建立数学模型建立数学模型设计解数学模型的算法设计解数学模型的算法程序编制程序编制调试调试结果结果n数据结构涉及到：数学模型的建立和对该模型具体数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法实现的对应的算法一个课题的解决原则一个课题的解决原则求解梁架结构中应力的数学模型是线性方程求解梁架结构中应力的数学模型是线性方程组组预报人口增长情况的数学模型是微分方程预报人口增长情况的数学模型是微分方程分析问题分析问题提取操作对象提取操作对象找出操作对象之间的关系找出操作对象之间的关系用数学的语言加以描述用数学的语言加以描述45 数据结构研究什么问题问题数学模型数学模型实现实现机外表示机外表示即外表示即外表示存储结构存储结构实现实现逻辑结构逻辑结构基本运算基本运算处理要求处理要求机外表示机外表示数据结构的研究内容：数据结构的研究内容：(1)要对所加工的对象进行逻辑组织。要对所加工的对象进行逻辑组织。(2)如何把加工对象存储到计算机中去？如何把加工对象存储到计算机中去？(3)数据运算。数据运算。建模建模求精求精1.1 1.1 什么是数据结构要求：要求：掌握各类基本掌握各类基本数据结构类型数据结构类型和相应的和相应的存储结构存储结构要求学生掌握要求学生掌握典型算法典型算法思想及程序实现；思想及程序实现；能针对给定问题，选择相适应的能针对给定问题，选择相适应的数据结构数据结构，并能，并能设计和分析设计和分析算法，提高复杂程序设计的能力。算法，提高复杂程序设计的能力。提高提高阅读算法阅读算法的能力的能力为后继课的学习及从事软件开发打好基础。为后继课的学习及从事软件开发打好基础。1.1 1.1 什么是数据结构上节回顾：逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖于运算的实现依赖于存储结构存储结构 n数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计问题的程序设计问题中计算机的中计算机的操作对象操作对象及其之间及其之间关系与操作关系与操作的学科。的学科。1.1 1.1 什么是数据结构 数据数据DataData：客观对象的符号表示。客观对象的符号表示。在计算机科学中在计算机科学中,数据的含义非常广泛，把一切能够输入到计算机中数据的含义非常广泛，把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格并被计算机程序处理的信息，包括文字、表格,图象图象等，都称为数据。等，都称为数据。例如：课程名，地名，书名都是数据。例如：课程名，地名，书名都是数据。再如，一个个人书库管理程序所要处理的数据可能再如，一个个人书库管理程序所要处理的数据可能是一张如是一张如表表1-1所示的表格。所示的表格。数据数据数据元素数据元素数据项数据项1.2基本概念和术语基本概念和术语表表1-1个人书库个人书库数据元素数据元素DataElement：数据的基本单位。在数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。计算机程序中通常作为一个整体考虑和处理。如，在如，在表表1-1所示的个人书库中，为了便于处理，所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由来考虑，故该数据由10个数据元素构成。个数据元素构成。一一般般情情况况下下，一一个个数数据据元元素素中中含含有有若若干干个个数数据据项项.1.2基本概念和术语基本概念和术语数据对象数据对象结构结构数据结构数据结构数据对象数据对象DataObject具有相同特性的数据元素的一具有相同特性的数据元素的一个集合个集合,是数据的子集是数据的子集.例例:整数数据对象是集合整数数据对象是集合0,1,-1,2,-2,扑克牌上的点数的数据对象是扑克牌上的点数的数据对象是2,3,4,5J,Q,K,A字母的数据对象是集合字母的数据对象是集合A,B,CX,Y,Z1.2基本概念和术语基本概念和术语数据对象可以是有限的数据对象可以是有限的,也可以是无限的也可以是无限的,其中的数其中的数据不是孤立的据不是孤立的,而是彼此相关联的而是彼此相关联的,这种数据元素相互之这种数据元素相互之间的关系称为间的关系称为结构结构.数据结构数据结构DataStructure相互之间存在一种或相互之间存在一种或多种特定关系的数据元素的集合多种特定关系的数据元素的集合,即带结构的数即带结构的数据元素的集合据元素的集合.1.2 基本概念和术语数据逻辑结构数据逻辑结构数据存储结构数据存储结构运算运算数据元素之间的逻辑关系分为数据元素之间的逻辑关系分为（数据逻辑结构）（数据逻辑结构）1)元素之间没有关系元素之间没有关系-集合集合2)元素之间有线性关系元素之间有线性关系-线性数据结构线性数据结构(线性表结构线性表结构)3)元素之间有层次关系元素之间有层次关系-层次数据结构层次数据结构(树结构树结构)4)元素之间有网状关系元素之间有网状关系-网状数据结构网状数据结构(图结构图结构)1.2 基本概念和术语例例1 1：某班学生基本情况登记表，记录了每个学生的学号某班学生基本情况登记表，记录了每个学生的学号 姓名姓名专业专业 政治政治 面貌面貌，表中的记录是按学生的学号顺序排列的，表中的记录是按学生的学号顺序排列的.学号学号 姓名姓名 专业专业 政治面藐政治面藐 001 001 王洪王洪 计算机计算机 党员党员 002 002 孙文孙文 计算机计算机 团员团员 003 003 谢军谢军 计算机计算机 团员团员 004 004 李辉李辉 计算机计算机 团员团员 005 005 沈祥福沈祥福 计算机计算机 党员党员 006 006 余斌余斌 计算机计算机 团员团员 007 007 巩力巩力 计算机计算机 团员团员 008 008 孔令辉孔令辉 计算机计算机 团员团员学生基本情况登记表的图示学生基本情况登记表的图示 001001003003002002004004006006005005008008007007学号关系学号关系是一种线性结构关系是一种线性结构关系1.2 基本概念和术语例例2 2 家族的族谱家族的族谱 家族的族谱反映的是家族成员之间的血缘关系，假设家族的族谱反映的是家族成员之间的血缘关系，假设某家族有某家族有1010个成员个成员A A，B B，C C，D D，E E，F F，G G，H H，I I，J J，他们之间的血缘关系可以用如下图表示。他们之间的血缘关系可以用如下图表示。这种分支结构关系被称为树结构。本例中树称为家族这种分支结构关系被称为树结构。本例中树称为家族树，它很象一棵倒置的树，树，它很象一棵倒置的树，A A 是树的根。是树的根。J JI IA AC CB BD DH HG GF FE E家族树的图示表示家族树的图示表示1.2 基本概念和术语例3 教学计划编排问题学生基本情况表的二元组表示学生基本情况表的二元组表示（D D，S S）二元组表示二元组表示 二元组表示是用一个二元组（二元组表示是用一个二元组（D D，S S）表示数据结表示数据结构，构，其中其中 D D 是是数据元素数据元素集合，集合，S S 是是 D D 上上关系关系的集合。的集合。D=001D=001，002002，003003，004004，005005，006006，007007，008008S=R S=R R=,R=,1.2 基本概念和术语家族的族谱家族的族谱 家族的族谱反映的是家族成员之间的血缘关系，假设家族的族谱反映的是家族成员之间的血缘关系，假设某家族有某家族有1010个成员个成员A A，B B，C C，D D，E E，F F，G G，H H，I I，J J，他们之间的血缘关系可以用如下图表示。他们之间的血缘关系可以用如下图表示。J JI IA AC CB BD DH HG GF FE E家族树的图示表示家族树的图示表示1.2 基本概念和术语 D=S=RR=家族树的二元组表示（D，S）D=AD=A，B B，C C，D D，E E，F F，G G，H H，I I，JJ S=R S=R R=R=A,B,A,B,1.2 基本概念和术语课程先后关系的图形描述形式c1c9c4c2c12c10c11c5c3c6c7c8图图 1-2 计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系例例假假设设我我们们需需要要编编制制一一个个事事务务管管理理的的程程序序，管管理理学学校校科科学学研研究究课课题题小小组组的的各各项项事事务务，则则首首先先要要为为程程序序的的操操作作对对象象课课题题小小组组设设计计一一个个数数据据结结构构。假假设设每每个个小小组组由由一一位位教教师师、一一至至三三名名研研究究生生及及一一至至六六名名本本科科生生组组成成，小小组组成成员员之之间间的的关关系系是是：教教师师指指导导研研究究生生，而而由由每每位位研研究生指导一至两名本科生。究生指导一至两名本科生。则可以如下定义数据结构：则可以如下定义数据结构：Group=(DGroup=(D，S)S)其其中中:D D=TT，G G1 1，G Gn n，S S1111SSnmnm 1=n=31=n=3，1=m=21=m=2，S=RS=R1 1,R,R2 2 R R1 1=T,G=|1=i=n,1=n|1=i=n,1=n=3 R R2 2=G=|1=i=n,1=j|1=i=n,1=j=m,1=n=3,1=m=2 1=n=3,1=m=2 数据的存储结构数据的存储结构数据结构数据结构在计算机中的在计算机中的表示表示(映映象象),即数据结构在计算机中的组织形式即数据结构在计算机中的组织形式.又称为数又称为数据的物理结构据的物理结构.1.2 基本概念和术语数据元素数据元素在计算机中的在计算机中的映射映射-结点结点数据项数据项在计算机中的在计算机中的映射映射-数据域数据域1.2 基本概念和术语数据在计算机中的存储数据在计算机中的存储:只有两种形式只有两种形式顺序顺序:数据元素逐个连续存放数据元素逐个连续存放(通过物理相邻来确定关通过物理相邻来确定关系系)非顺序非顺序:数据元素任意存放数据元素任意存放(通过存储地址确定关系通过存储地址确定关系)数据结构的存储数据结构的存储要把要把数据元素数据元素存放起来存放起来还必须把还必须把数据元素之间的逻辑关系数据元素之间的逻辑关系也表示出来也表示出来数据元素的逻辑关系数据元素的逻辑关系要么要么用数据元素在用数据元素在物理上相邻物理上相邻来表示逻辑关系来表示逻辑关系要么要么用数据元素的用数据元素的存储地址存储地址(指针指针)来表示逻辑关系来表示逻辑关系1.2 基本概念和术语存储结构（存储结构（Storge Structure):数据结构在计算机中的表示数据结构在计算机中的表示(或称映象或称映象)称为数据的存储称为数据的存储结构，又称为物理结构。结构，又称为物理结构。四种基本的存储方法：四种基本的存储方法：（1）顺序存储方法（顺序存储结构）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）链接存储方法（链式存储结构）（3）索引存储方法）索引存储方法 （4）散列存储方法）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。一或组合），这主要考虑的是运算方便及算法的时空要求。1 顺序存储顺序存储将将数数据据存存储储在在连连续续存存储储区区域域M的的相相邻邻的的存存储储单单元元中中，使使得得逻逻辑辑相相邻邻的的结结点点一一定定是是物物理位置相邻理位置相邻。对于一个数据结构对于一个数据结构B=（K，R）其中其中K=k1,k2,k3,k4,k5,k6,k7,k8,k9 R=r r=,它的顺序存储方式如图所示它的顺序存储方式如图所示 2 链式存储链式存储给每个结点附加一个地址域，一个结点给每个结点附加一个地址域，一个结点的地址域所指的是该结点的后继的存储的地址域所指的是该结点的后继的存储地址，逻辑相邻的数据元素在物理上地址，逻辑相邻的数据元素在物理上(内存存储位置内存存储位置)不一定相邻不一定相邻。例例 数据的逻辑结构数据的逻辑结构B=（K，R）其中其中 K=k1,k2,k3,k4,k5 R=r R=,这是一个线性结构，链式存储如图所示这是一个线性结构，链式存储如图所示 u顺序存储结构顺序存储结构:用数据元素在存储器中的用数据元素在存储器中的相对位置相对位置来表示数据元素之间的来表示数据元素之间的逻辑关系。逻辑关系。所有元素存放在一片所有元素存放在一片连续连续的存贮单元的存贮单元中，逻辑上相邻的元中，逻辑上相邻的元素存放到计算机内存仍然相邻。素存放到计算机内存仍然相邻。u链式存储结构：链式存储结构：在每一个数据元素中在每一个数据元素中增加一个存放地址的指针增加一个存放地址的指针，用此指针，用此指针来表示数据元素之间的来表示数据元素之间的逻辑关系逻辑关系。所有元素存放在所有元素存放在可以可以不连续的存贮单元中不连续的存贮单元中，但元素之间的，但元素之间的关系可以通过关系可以通过地址地址确定，逻辑上相邻的元素存放到计算机内存确定，逻辑上相邻的元素存放到计算机内存后后不一定不一定是相邻的。是相邻的。如何描述存储结构呢？如何描述存储结构呢？我我们们可可以以借借用用高高级级程程序序语语言言中中提提供供的的 “数数据据类类型型”来描述它来描述它.例例如如:可可以以用用 “一一维维数数组组”类类型型来来描描述述顺顺序序存存储储结构，以结构，以C C语言提供的语言提供的“指针指针”来描述链式存储结构。来描述链式存储结构。例：复数例：复数3.02.3i 的两种存储方式：的两种存储方式：2.303023.00300041503023.0030004152.3法法1：地址：地址 内容内容法法2：地址：地址 内容内容2字节字节逻辑结构、存贮结构、运算逻辑结构、存贮结构、运算这三个方面的关系为：这三个方面的关系为：（1 1）逻辑结构逻辑结构是对数据元素之间的逻辑关系的描述，它可以用是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示；一个数据元素的集合和定义在此集合上的若干关系来表示；数据的逻辑结构独立于计算机，是数据本身所固有的。数据的逻辑结构独立于计算机，是数据本身所固有的。（2 2）存贮结构存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。于计算机。（3 3）运算运算是指所施加的一组操作总称。运算的定义直接依赖于是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。逻辑结构，但运算的实现必须依赖于存贮结构。u数据的逻辑结构和物理结构是密切相关的两个方面，任何一个数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计算法的设计取决于选定的数据取决于选定的数据(逻辑逻辑)结构，而结构，而算法的实现算法的实现依赖于依赖于采用的存储结构。采用的存储结构。数据类型数据类型DataType一个一个值的集合值的集合和定义在和定义在这个值集上的这个值集上的一组操作一组操作的总称的总称.(1)高级语言中的数据类型实际上包括高级语言中的数据类型实际上包括:数据的逻辑结数据的逻辑结构构,数据的存储结构数据的存储结构及所定义的及所定义的操作操作的实现的实现.(2)高级语言中的数据类型按值的不同特性分为高级语言中的数据类型按值的不同特性分为:原子类型原子类型(如整型如整型,实型实型,字符型字符型,布尔型布尔型)结构类型结构类型(如数组如数组)1.2 基本概念和术语(3)数据类型并不局限于高级语言数据类型并不局限于高级语言,它实际上是一个广它实际上是一个广义的概念义的概念.例如例如:”教师教师”就是一个数据类型就是一个数据类型,他有值他有值”教龄教龄”,有操作有操作”教书教书”等等;如果具体说小学教师如果具体说小学教师,大学教师大学教师,可以看可以看作时一个具体的类型作时一个具体的类型.(4)可以撇开计算机不考虑可以撇开计算机不考虑,现实中任何一个问题都可现实中任何一个问题都可以定义为一个数据类型以定义为一个数据类型-称为称为抽象数据类型抽象数据类型1.2 基本概念和术语抽象数据类型抽象数据类型AbstractDataTypeADT一个数学模型及定义在这个模型上的一个数学模型及定义在这个模型上的一组操作一组操作(或运算或运算)的总称的总称.抽象思维方法抽象思维方法:舍去复杂系统中非本质的细节舍去复杂系统中非本质的细节,只把其中只把其中某些本质的某些本质的,能反映系统重要宏观特性的东西提炼出来能反映系统重要宏观特性的东西提炼出来,构成系统的模型构成系统的模型,并且深入研究这些特性并且深入研究这些特性.例如例如:”平房平房”:本质特性包括墙体本质特性包括墙体,门门,窗窗,房顶房顶等等.再如再如:有一堆鸡蛋有一堆鸡蛋,进行了编号进行了编号,我们可以对它我们可以对它们进行如下操作们进行如下操作:找出最重的找出最重的;取走某一个取走某一个;全部搬走全部搬走;这是一个抽象的定义这是一个抽象的定义,并没有考虑鸡蛋在哪里并没有考虑鸡蛋在哪里放着，有多大等等放着，有多大等等1.3 抽象数据类型一一.抽象数据类型定义抽象数据类型定义抽象数据类型抽象数据类型=数学模型数学模型+操作操作=数据结构数据结构+操作操作一个抽象数据类型的描述如下一个抽象数据类型的描述如下:ADT抽象数据类型的名称抽象数据类型的名称数据对象数据对象数据关系数据关系基本操作基本操作ADT抽象数据类型名抽象数据类型名什么是类C语言?类类C C语言语言是介于伪码和是介于伪码和C C语言的一种描述工具语言的一种描述工具.其其语法基本上全部取自标准语法基本上全部取自标准C C语言语言,因而易于转化为因而易于转化为C/C+C/C+的程序的程序,但它是简化的但它是简化的,不严格的不严格的,不可以真正在计算机不可以真正在计算机上运行上运行,这主要反映在一下几点这主要反映在一下几点:可以采用伪码语言取代某些不必确切描述的语句或可以采用伪码语言取代某些不必确切描述的语句或语句串语句串.省略函数体中的简单变量的说明省略函数体中的简单变量的说明.输入输入/输出函数只说明输出什么输出函数只说明输出什么,不考虑输入不考虑输入/输出的输出的格式格式.强化赋值语句的功能强化赋值语句的功能.1.预定义常量和类型预定义常量和类型格式格式:#define 标识符标识符 字符串字符串/函数结果状态代码函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2*类C语言2数据结构的表示（数据的存储结构）用数据结构的表示（数据的存储结构）用C的类的类型定义（型定义（typedef）描述。数据元素类型约定为描述。数据元素类型约定为ElemType,由用户在使用该数据类型时自行定由用户在使用该数据类型时自行定义义3typedefintElemType;4/Status是函数的类型，其值是函数结果状态代码是函数的类型，其值是函数结果状态代码typedefintStatus;*类C语言3基本操作的算法都用以下形式的函数描述：基本操作的算法都用以下形式的函数描述：函数类型函数类型函数名（函数参数表）函数名（函数参数表）/算法说明算法说明语句序列语句序列/函数名函数名除了函数的参数需要说明类型外，算法中使用的辅助变量可除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。以不作变量说明，必要时对其作用给予注释。一般而言，一般而言，a、b、c、d、e等用作数据元素名，等用作数据元素名，i、j、k、l、m、n等用作整型等用作整型变量名，变量名，p、q、r等用作指针变量名。等用作指针变量名。当函数返回值为函数结当函数返回值为函数结果状态代码时，函数定义为果状态代码时，函数定义为Status类型。为了便于算法描述，类型。为了便于算法描述，除了值调用方式外，增添了除了值调用方式外，增添了C+语言的引用调用的参数传递方语言的引用调用的参数传递方式。在形参表中，以式。在形参表中，以&打头的参数即为引用参数。引用参数是打头的参数即为引用参数。引用参数是实参的别名，所谓别名就是同一变量的另外一个名字。实参的别名，所谓别名就是同一变量的另外一个名字。void swap(int n,int m)/函数定义函数定义/参数为值参数参数为值参数 int temp;temp=n;n=m;m=temp;void swap&(int&n,int&m)/函数定义函数定义,参数为引用参数参数为引用参数 int temp;temp=n;n=m;m=temp;main()int a=10,b=20,c=10,d=20;swap(a,b);/函数调用函数调用swap&(c,d);/函数调用函数调用结果结果：a=10,b=20 c=20,d=10例例 交换两个整数变量的算法交换两个整数