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

《数据结构C语言版严蔚敏绪论.ppt》由会员分享，可在线阅读，更多相关《数据结构C语言版严蔚敏绪论.ppt（151页珍藏版）》请在三一办公上搜索。

1、数据结构,(C语言版),讲授：刘彩霞,Email：amy_,祝同学们新学期愉快、学习进步！,数据结构课程所处的地位：,介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,数据结构是计算机专业的一门综合性专业基础课是计算机专业本/专科生必修学位课程 是计算机研究生/升本入学考试必考科目 是软件人员水平考试内容是数学建模、ACM程序竞赛基础,学业基础,先修课程：高级语言程序设计(如 C/C+语言)后续课程：操作系统（例：打印机 队列管理）、数据库原 理、人工智能等。,课程安排,总学时：90(18周*5)讲课学时：72 实验学时：18,教学参考书 教 材：数据结构C语言版严蔚敏、吴伟民-清华大

2、学出版社数据结构C语言篇习题与解析 李春葆-清华大学出版社数据结构自学考试指导丁宝康等 清华大学出版社算法与数据结构，范策等，机械工业出版社,http:/210.44.232.53/ec/C70/Index.htm(我院精品课程)http:/一个很不错的站点，有丰富的编程题库和竞赛试题，也有很多有参考价值的文献。)http:/(烟台大学）http:/,助学网站,助学网站,http:/www.cs.sunysb.edu/algorith/(The Algorithm Design Manual 的作者Steven S.Skiena的主页，详细介绍算法和数据结构，十分专业！)http:/www.n

3、ist.gov/dads/(此网站是一本关于算法、数据结构、以及相关问题的电子字典，对各种算法有精确的定义和实现方法。)http:/www.acsl.org/(美国计算机科学协会)http:/(易自考)http:/(C语言编程宝典)http:/(C语言学习)http:/数据结构+精品课程,实 验,实验环境:Win-tc 或Turbo c 或VC+实验项目名称:一元稀疏多项式的加减运算栈和队列的抽象数据类型实现 二叉树的建立、遍历及典型算法实现 图的建立、遍历及典型算法实现典型查找算法实现内部排序算法实现,课程设计,题目（任选一）:迷宫问题求解 算术表达式求值 校园导游系统图书管理信息系统的设计

4、与实现 查找算法综合比较排序算法综合比较要求达到的目标:文档清晰、完整，学会分析解决问题 程序运行良好,本课程学习要求,自觉预习、遵守纪律、认真听课、及时复习；按时、独立、认真地完成每次作业；每一章有作业题，按时交。每次实验前做好准备工作,写好程序,实验后交实验报告（写在纸上）。期中布置课程设计3.积极回答课堂提问；成绩评定标准：平时表现：占30%，包括作业、课程设计、提问、学习纪律 期末考试：闭卷笔试，占70%,目 录Contents,第一章 绪 论(4学时),第二章 线性表(8学时),第三章 栈和队列(8学时),第四章 串、数组和广义表(6学时),第五章 树和二叉树(10学时),第六章 图

5、(6学时),第七章 查找(6学时),第八章 排序(6学时),数据结构课程的内容,逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构,1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型1.4 算法及算法分析（算法评价）,第一章 绪 论,计算机发展简史,众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。,近三十年来，电子计算机的发展异常迅猛表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降更重要的是计算机广泛地应用于情

6、报检索、企业管理、系统工程等方面，已远远超出了科技计算的范围，而渗透到人类社会活动的一切领域,计算机发展简史,与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息,计算机发展简史,“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”被列入美国一些大学计算机科学系的教学计划。,数据结构,D.Knuth 的巨著计算机程序设计艺术第一卷“基本算法”第二卷“半数字算法”第三卷“排序与搜索”197

7、4年获得图灵奖，是40届中唯一因一部影响巨大的书而获奖,数据结构,发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。,数据结构,数据结构是研究什么的？这是课程最基本的问题，关系到我们为什么要学习数据结构这门课程,1.1 什么是数据结构,从应用问题涉及的对象来分可分为数值问题 非数值问题数值问题就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积非数值问题就是问题中涉及的模型不能用数学方程来表达的那些问题,1.1 什么是数据结构,例 1（任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台

8、时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,数值问题与非数值问题有什么不同,1）数值问题,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,1）数值问题例2 已知：游泳池的长length和宽wide，求面积area。分析：,1.1 什么是数据结构,（1）问题涉及的对象：length,wide,area 是实数 可用数值表示；（2）对

9、象之间的关系：area=lengthwide 可用方程或 函数表示；（3）数据存储：可用程序设计语言中的实型变量存储；（4）问题求解：用某种计算方法求解；,程序：main()int len,wide,area;scanf(“%d%d%n”,可见，对于数值问题，对象之间的关系通常可以用方程或函数表达，只要能列出表达对象之间关系的方程或函数，找到求解方程或函数的方法，就可以编写程序了。,求一组（n个）整数中的最大值。算法：基本操作是两两比较，求两个数的大小模型：？,1.1 什么是数据结构,1.1 什么是数据结构,2）非数值问题应用举例1 电话号码查询系统应用举例2 学籍档案管理应用举例3 全排列问

10、题应用举例4 制定教学计划,数值问题与非数值问题有什么不同,举例1-电话号码查询系统,设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式(a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n)分别表示某人的名字和对应的电话号码 要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码;如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的反馈信息,举例2-学籍档案管理,假设一个学籍档案管理系统包含如下表1-1所示的学生信息,表1-1,特点?,特点:,每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格表中每个学生

11、的信息依据学号的大小存在着一种前后关系，这就是线性结构对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等,132 213 231 321 312 1234 1243 1324 1342 1423 1432 等,举例3输出n个对象的全排列,解决,图 1-1 3个对象的全排列过程,(a1)(a2)(a3)(a4)(a5),(a),计算机和人对奕问题,l在求解过程中，所处理的数据之间具有层次关系，这是树形结构l对它的操作有：建立树形结构，输出最低层结点内容等等,在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，

12、而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：,举例4制定教学计划,表1-2,课程先后关系的图形描述形式,图 1-2 计算机专业必修课程开设先后关系,1）问题涉及的对象：课程可用课程名表示 不能用数值表示2）对象之间的关系：需要考虑各门课程的开设顺序。有些课程是某些课程的 先导课程。必须先开先导课程，再开后续课程。课程之间的这种关系不能用方程或 函数表示3）数据及数据之间的关系如何存储？4）如何求解？,特点,课程之间的先后关系用图结构描述通过实施创建图结构，按要求将图结构中的顶点进行线性排序,从应用问题涉及的对象来分可分为数值问题 非数值问题数值问题就是我们

13、平时所说的计算问题，如已知圆的半径，要求圆的面积非数值问题就是问题中涉及的模型不能用数学方程来表达的那些问题,小结：,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科。,1.1 什么是数据结构,需求分析 总体设计 模块分割 建立数学模型 设计解数学模型的算法 程序编制 调试 结果数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法,一个课题的解决原则,求解梁架结构中应力的数学模型是线性方程组预报人口增长情况的数学模型是微分方程,分析问题提取操作对象找出操作对象之间的关系用数学的语言加以描述,45,数据结构研究什么,问题,数学模型,实现,机外表示,即外

14、表示,存储结构,实现,逻辑结构,基本运算,处理要求,机外表示,数据结构的研究内容：(1)要对所加工的对象进行逻辑组织。(2)如何把加工对象存储到计算机中去？(3)数据运算。,建模,求精,1.1 什么是数据结构,DS主要研究内容：数据的各种逻辑结构和物理结构，以及它们之间的相应关系并对每种结构定义相适应的各种运算设计出相应的算法分析算法的效率,常见的数据结构有：数组、栈、队列、表、串、树、图 和文件等,1.1 什么是数据结构,要求：掌握各类基本数据结构类型和相应的存储结构要求学生掌握典型算法思想及程序实现；能针对给定问题，选择相适应的数据结构，并能设计和分析算法，提高复杂程序设计的能力。提高阅读

15、算法的能力为后继课的学习及从事软件开发打好基础。,1.1 什么是数据结构,上节回顾：,逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科。,1.1 什么是数据结构,数据Data：客观对象的符号表示。在计算机科学中,数据的含义非常广泛，把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格,图象等，都称为数据。例如：课程名，地名，书名都是数据。再如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。,数据 数据元素 数据项,1.2 基本概念和术语,表 1-1 个人书库,数据元素Data

16、 Element：数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个数据元素构成。一般情况下，一个数据元素中含有若干个数据项.,1.2 基本概念和术语,数据对象 结构 数据结构,数据对象Data Object具有相同特性的数据元素的一个集合,是数据的子集.,例:整数数据对象是集合0,1,-1,2,-2,扑克牌上的点数的数据对象是2,3,4,5J,Q,K,A字母的数据对象是集合A,B,CX,Y,Z,1.2 基本概念和术语,数据对象可以是有限的,也可以是无限的,其中的数据不是孤

17、立的,而是彼此相关联的,这种数据元素相互之间的关系称为结构.,数据结构Data Structure相互之间存在一种或多种特定关系的数据元素的集合,即带结构的数据元素的集合.,1.2 基本概念和术语,数据逻辑结构,数据存储结构,运算,数据元素之间的逻辑关系分为（数据逻辑结构）1)元素之间没有关系-集合2)元素之间有线性关系-线性数据结构(线性表结构)3)元素之间有层次关系-层次数据结构(树结构)4)元素之间有网状关系-网状数据结构(图结构),1.2 基本概念和术语,例1：某班学生基本情况登记表，记录了每个学生的学号 姓名专业 政治 面貌，表中的记录是按学生的学号顺序排列的.,学号 姓名 专业 政

18、治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员 006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员,学生基本情况登记表的图示,学号关系是一种线性结构关系,1.2 基本概念和术语,例2 家族的族谱 家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。,这种分支结构关系被称为树结构。本例中树称为家族树，它很象一棵倒置的树，A 是树的根。,家族树的图示表示,1.2 基本概念和术语

19、,例3 教学计划编排问题,学生基本情况表的二元组表示（D，S）,二元组表示 二元组表示是用一个二元组（D，S）表示数据结构，其中 D 是数据元素集合，S 是 D 上关系的集合。,D=001，002，003，004，005，006，007，008S=R R=,1.2 基本概念和术语,家族的族谱 家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。,家族树的图示表示,1.2 基本概念和术语,D=S=R R=,家族树的二元组表示（D，S）,D=A，B，C，D，E，F，G，H，I，J S=R R=A,B,1.2 基

20、本概念和术语,课程先后关系的图形描述形式,图 1-2 计算机专业必修课程开设先后关系,例假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。则可以如下定义数据结构：Group=(D，S)其中:D=T，G1，Gn，S11Snm 1|1|1=i=n,1=j=m,1=n=3,1=m=2,数据的存储结构数据结构在计算机中的表示(映象),即数据结构在计算机中的组织形式.又称为数据的物理结构.,1.2 基本

21、概念和术语,数据元素在计算机中的映射-结点数据项在计算机中的映射-数据域,1.2 基本概念和术语,数据在计算机中的存储:只有两种形式顺序:数据元素逐个连续存放(通过物理相邻来确定关系)非顺序:数据元素任意存放(通过存储地址确定关系),数据结构的存储要把数据元素存放起来还必须把数据元素之间的逻辑关系也表示出来,数据元素的逻辑关系要么用数据元素在物理上相邻来表示逻辑关系要么用数据元素的存储地址(指针)来表示逻辑关系,1.2 基本概念和术语,存储结构（Storge Structure):数据结构在计算机中的表示(或称映象)称为数据的存储结构，又称为物理结构。四种基本的存储方法：（1）顺序存储方法（顺

22、序存储结构）（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=k

23、1,k2,k3,k4,k5 R=r R=,这是一个线性结构，链式存储如图所示,顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。,如何描述存储结构呢？我们可以借用高级程序语言中提供的“数据类型”来描述它.例如:可以用“一维数组”类型来描述顺序存储结构，以C语言提供的“指针”来描述链

24、式存储结构。,例：复数3.02.3i 的两种存储方式：,法1：地址 内容,法2：地址 内容,2字节,逻辑结构、存贮结构、运算这三个方面的关系为：（1）逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示；数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的存储结构。,数据类

25、型Data Type一个值的集合和定义在这个值集上的一组操作的总称.,(1)高级语言中的数据类型实际上包括:数据的逻辑结构,数据的存储结构及所定义的操作的实现.(2)高级语言中的数据类型按值的不同特性分为:原子类型(如整型,实型,字符型,布尔型)结构类型(如数组),1.2 基本概念和术语,(3)数据类型并不局限于高级语言,它实际上是一个广义的概念.例如:”教师”就是一个数据类型,他有值”教龄”,有操作”教书”等;如果具体说小学教师,大学教师,可以看作时一个具体的类型.(4)可以撇开计算机不考虑,现实中任何一个问题都可以定义为一个数据类型-称为抽象数据类型,1.2 基本概念和术语,抽象数据类型A

26、bstract Data Type ADT一个数学模型及定义在这个模型上的一组操作(或运算)的总称.,抽象思维方法:舍去复杂系统中非本质的细节,只把其中某些本质的,能反映系统重要宏观特性的东西提炼出来,构成系统的模型,并且深入研究这些特性.,例如:”平房”:本质特性包括墙体,门,窗,房顶等.再如:有一堆鸡蛋,进行了编号,我们可以对它们进行如下操作:找出最重的;取走某一个;全部搬走;这是一个抽象的定义,并没有考虑鸡蛋在哪里放着，有多大等等,1.3 抽象数据类型,一.抽象数据类型定义抽象数据类型=数学模型+操作=数据结构+操作,一个抽象数据类型的描述如下:,ADT 抽象数据类型的名称数据对象 数据

27、关系 基本操作ADT抽象数据类型名,什么是类C语言?,类C语言是介于伪码和C语言的一种描述工具.其语法基本上全部取自标准C语言,因而易于转化为C/C+的程序,但它是简化的,不严格的,不可以真正在计算机上运行,这主要反映在一下几点:可以采用伪码语言取代某些不必确切描述的语句或语句串.省略函数体中的简单变量的说明.输入/输出函数只说明输出什么,不考虑输入/输出的格式.强化赋值语句的功能.,1.预定义常量和类型格式:#define 标识符 字符串/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERF

28、LOW-2,*类C语言,数据结构的表示（数据的存储结构）用C的类型定义（typedef）描述。数据元素类型约定为ElemType,由用户在使用该数据类型时自行定义 typedef int ElemType;/Status 是函数的类型，其值是函数结果状态代码 typedef int Status;,*类C语言,基本操作的算法都用以下形式的函数描述：函数类型 函数名（函数参数表）/算法说明 语句序列/函数名 除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。一般而言，a、b、c、d、e等用作数据元素名，i、j、k、l、m、n等用作整型变量名，p、q、r等

29、用作指针变量名。当函数返回值为函数结果状态代码时，函数定义为Status类型。为了便于算法描述，除了值调用方式外，增添了C+语言的引用调用的参数传递方式。在形参表中，以&打头的参数即为引用参数。引用参数是实参的别名，所谓别名就是同一变量的另外一个名字。,void swap(int n,int m)/函数定义/参数为值参数 int temp;temp=n;n=m;m=temp;,void swap,main()int a=10,b=20,c=10,d=20;swap(a,b);/函数调用swap/函数调用,结果：a=10,b=20 c=20,d=10,例 交换两个整数变量的算法,下面通过例子来说

30、明引用参数的概念，值参和引用参数的区别,调用函数Swap(),参数传递,执行Swap(),值参函数Swap(a,b)的调用,*类C语言,调用函数Swap&(),执行Swap&(),参数传递,nm,引用参数函数Swap&()的调用,*类C语言,对于对数据有修改作用的操作（函数），要用引用参数作形参，而不能用值参作形参,*类C语言,赋值语句简单赋值 变量名=表达式；串联赋值 变量名1=变量名2=变量名k=表达式;成组赋值（变量名1，变量名k）=（表达式1，,表达式k）；结构名=结构名；结构名=（值1，值k）；变量名=表达式；变量名起始下标.终止下标=变量名起始下标.终止下标；交换赋值 变量名 变量

31、名；条件赋值 变量名=条件表达式？表达式T;表达式F;,条件语句1 if(表达式)语句；条件语句2 if（表达式）语句；else 语句；开关语句 1 switch（表达式）case值1：语句序列1；break；case值n：语句序列n；break；default：语句序列n+1；开关语句2 switch case条件1：语句序列1；break；case条件n：语句序列n；break；default：语句序列n+1；,选择语句,循环语句for 语句 for（赋初值表达式序列；条件；修改表达式序列）语句；while 语句 while(条件)语句；do-while 语句 do语句序列；while(条

32、件);结束语句函数结束语句 return 表达式；return;case 结束语句 break;异常结束语句 exit(异常代码),输入和输出语句输入语句scanf(格式串，scanf 变量1,，变量n);输出语句printf(格式串，表达式1，表达式n);通常省略格式串注释单行注释/文字,基本函数求最大值 max(表达式1，表达式n)求最小值 min(表达式1，表达式n)求绝对值 abs(表达式)求不足整数值 floor(表达式)求进位整数值 ceil(表达式)判定文件结束 eof(文件变量)或eof判定行束 eoln(文件变量)或eoln,*类C语言,逻辑运算约定与运算&：对于A&B，当A

33、的值为0时，不再对B求值。或运算|：对于A|B，当A的值为非0时，不再对B求值。,*C的数据类型,在本课程中，数据的存储结构是用C语言的数据类型描述(定义)的，主要用到：数组，结构，指针,1 数组1)数组类型变量（数组变量）由一组类型相同的数据元素组成2）数组的类型定义和变量定义typedef 数组元素类型名 数组类型名常量表达式;数组类型名 数组变量名；,例 某班40个学生的数学成绩，可以用有40个数组分量 的整型数组变量存储。Typedef int SCoreType40;SCoreType class1;,数组类型名,数组变量,*C的数据类型,3）数组在内存中的存储示意图,0 1 2 3

34、9,class,数组变量,*C的数据类型,4)数组分量(数组元素）的引用 数组变量下标例：for(i=0;i=39;+i)classi=0;,数组变量,class,数组元素下标,*C的数据类型,2 结构1）结构类型变量（结构变量）由一组类型可以不同的数据元素组成2）结构的类型定义和变量定义typedef 结构定义 结构类型名；结构类型名 结构变量名；,例 一本书可以用有2个数据成员（数据域）结构变量存储。Typedef struct int no;char title40;BookType;BookType book1;,结构类型名,结构变量名,*C的数据类型,3）结构变量在内存中的存储示意图

35、,4)结构变量的引用 结构变量名.成员名(结构变量名.域名）例：book1.no=1;scanf(“%s”,book1.title);,*C的数据类型,3、指针1）指针类型变量（指针变量）用于存储变量地址（或称指向该变量）2）指针的类型定义和变量定义(只介绍本课程用到的指向结构变量指针类型)typedef 结构定义*指针的类型名；指针的类型名 指针变量名,变量定义,类型定义,例 typedef struct int no;char title;*BookPtType;BookPtType pbook;,指向结构类型变量的指针类型,指向结构类型变量的指针变量,pbook是指针变量，存放结构类型变

36、量的地址，通常用箭头表示pbook中存放的是它所指向的结构变量的地址。,3)指针所指变量的引用指针变量-结构变量成员名(指针变量-结构变量的域名）,例 typedef struct int no;char title;*BookPtType;BookPtType pbook；pbook-no=1;scanf(“%s”,pbook-title);,给pbook所指结构变量的 no成员赋值 1,1,1.3 抽象数据类型,二.抽象数据类型举例例1:掷骰子(色子)游戏.问题描述:每次掷出N个骰子,统计每次的总点数和每个骰子的点数,看看谁的高.,问题分析:该问题的数据包括骰子个数,每个骰子的点数 和总点

37、数;骰子个数是大于0的整数N;每个骰 子的点数是1-6;总点数是N-6N;该问题的操作包括掷骰子,求总点数,输出各 个骰子的点数.,1.3 抽象数据类型,1.3 抽象数据类型,例2:计算圆的周长和面积问题描述:给定圆的半径,求出周长和面积,例3:复数的运算问题描述:在高级语言中,没有复数类型,但是可借助已 有的数据类型解决复数类型的问题.,1.3 抽象数据类型,二.数据类型的实现 一个问题抽象为一个抽象数据类型后,仅是形式上的抽象定义,还没有达到问题解决的目的要实现这个目标,就要把抽象的变成具体的,即抽象数据类型在计算机上的实现,变为一个具体的数据类型.,1.3 抽象数据类型,一个数据类型的实

38、现一般分为三个阶段1.ADT阶段,又称为定义阶段2.虚拟数据类型阶段,又称为表示阶段3.物理数据类型阶段,又称为物理实现阶段,例如:整数 C语言的整数 机器整数,一 算法的概念 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一种或多种操作。例 求10个正整数 中的最大数max的算法。描述算法的方法有很多流程图，自然语言，计算机语言用计算机语言表达的算法就是程序,1.4 算法与算法分析,若采用自然语言描述,则如下列步骤所示:(1)给10个元素a0-a9输入数值;(2)把第一个元素a0赋给用于保存最大值元素的变量max;(3)把表示下标的变量i赋初值1;(4)如果ima

39、x,则将ai赋给max,否则不改变max的值,这使得max始终保存着当前比较过的所有元素的最大值;(6)使下标i增1,以指示下一个元素;(7)转向第(4)步继续执行.,1.4 算法与算法分析,main()int i,max,a10;printf(“请输入10个整数:”);for(i=0;imax)max=ai;i+;printf(“10个整数中的最大值为:”,max);,C语言描述如下:,二 算法的基本特征1）输入：0个或多个输入2）输出：1个或多个输出3）有穷性：算法必须在有限步内结束4）确定性：组成算法的操作必须清晰无二义性5）可行性：组成算法的操作必须能够在计算机上实现,1.4 算法与算

40、法分析,算法与程序的区别算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。,主要区别在：有穷性、正确性和描述方法 程序可以是无穷的，例如OS，算法是有穷的；程序可以是错误的，算法必须是正确的；程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。,1.4 算法和算法分析,二、算法的描述和实现描述-可采用自然语言、数学语言或约定的符号语言。实现-必须借助程序设计语言提供的数据类型及其运算。本课的描述-采用C/C+语言。,1.4 算法和算法分析,算法研究涉及两方面内容：设计技术：如何设计一个有

41、效的算法分析技术：评价和判断已有算法的优劣,1.4 算法和算法分析,1.4 算法与算法分析,评价算法的好坏的标准有很多:如算法的正确性:“正确”的含义在通常的用法中有很大的差别，大体可分为四个层次,程序不含语法错误程序对于几组输入数据能够得出满足规格说明要求的结果程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果程序对一切合法的输入数据都能产生满足规格说明要求的结果,三算法分析衡量的四个尺度：正确性:问题的任何一个实例作为输入，算法都能得到正确的结果作为输出；时间特性:运行所花费的时间；空间特性:所占用存储空间的大小；其他（可读性、易调性、健壮性等）。时间和空间特

42、性的巨大改进源于更好的数据结构或算法。,1.4 算法和算法分析,正确性、可读性、健壮性、效率与低存储量需求,算法效率的度量1.事后统计的方法2.事前分析估算的方法,1.4 算法和算法分析,算法的时间特性的度量不应依赖算法运行的计算机和软件平台（操作系统、编程语言和编译系统），下面几种度量算法的时间特性的方法被废弃：算法运行的实际执行时间运行过程中所执行的指令条数运行过程中程序循环的次数算法的时间特性用执行基本操作次数来度量。,1.4 算法和算法分析,基本操作：是指算法运行中起主要作用且花费最多时间的操作。例如：实数矩阵乘法中，基本操作为实数元素之间的数乘；N个整数排序中，基本操作可以是整数间的

43、比较或数据元素的移动；,1.4 算法和算法分析,算法计算量或问题规模：是指算法运行中，输入的规模。例如：实数矩阵乘法中，问题规模为矩阵的阶数（n阶方阵）；排序问题中，问题规模是待排序元素个数；,1.4 算法和算法分析,一个特定算法”运行工作量”的大小,只依赖于问题的规模,算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作：T（n）=O（f（n）随问题规模的增大，算法执行时间的增长率和操作执行次数的增长率相同。称为时间复杂度。,O（n）,O（1）,T（n）=,T（n）=,判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。,

44、算法时间量度T(n),语句频度 原操作语句重复执行的次数当有若干循环语句时,算法的时间复杂度由嵌套层数最多的语句的频度决定,例1：程序段 x:=x+1语句频度 时间复杂度x:=x+1;1 O(1)常数阶FOR i:=1 TO n DO x:=x+1;n O(n)线性阶FOR i:=1 TO n DO n FOR j:=1 TO n DO x:=x+1;n(n)O(n2)平方阶,1.4 算法和算法分析,例2 分析以下程序段的时间复杂度for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;,/*1*/,/*2*/,1.4 算法和算法分析,分析：语句的频度指的是该语句重

45、复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：,则该程序段的时间复杂度：T(n)=,1.4 算法和算法分析,例3 分析以下程序段的时间复杂度i=1;while(i=n)i=i*2语句1的频度是：1设语句2的频度是f(n)，则有：即，取最大值则该程序段的时间复杂度为：,/*1*/,/*2*/,当有若干循环语句时,算法的时间复杂度由嵌套层数最多的语句的频度决定,例4x=1;for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+;由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从

46、内层向外层循环分析执行次数。,常见函数的时间复杂度按数量递增排列及增长率。P16图1.7,时间复杂度T(n)按数量级递增顺序为：,复杂度高,复杂度低,1.4 算法和算法分析,例5:有5个算法,A1,A2,A3,A4,A5,算法 T(n)时间复杂度 结论:A1 1000n O(n)21024 A1最好A5 2n O(2n),当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,1.4 算法和算法分析,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Publ

47、ic void bubble-sort(int a，int n)for(i=n-1;change=TURE;i1,最坏情况：1+2+3+n-1=n(n-1)/2 平均时间复杂度为:O(n2),最好情况：1次,四、设计好算法的必要性,一方面计算机性能在不断提高，另一方面用计算机解决应用问题也在不断变化：应用的范围不断扩张（由字符发展为多媒体）应用问题的规模不断增加应用问题本身也越来越复杂,1.4 算法和算法分析,以数据搜索为例：50年代，主要用于数值计算，编译系统中符号表的规模不超过1000字节，即为K级；70年代，开始数据管理，数据库中的记录较多，在1000000字节，即M级；90年代，Int

48、ernet 兴起，网上搜索的数据量又大幅增长，超过1000M字节经常遇到，即达到G级；这说明CPU性能的提高相对应用问题的变化，仍是“供不应求”,计算机技术的每一项重大进步都与算法研究的突破有关：多媒体技术与数据压缩算法的研究；声音文件的MP3压缩技术更说明压缩与解压算法的研究成果的巨大成功；信息安全中的关键技术-信息加密算法；许多组合优化问题中，时间复杂度是指数阶，只能靠算法研究来解决。,五、空间复杂度,与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n)我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘

49、述。,数据项(字段),数 据 结构,数据结构运算的实现,数据结构是指组成数据的元素之间的结构关系。线性结构、树型结构和图结构是数据结构中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合,基本概念,数 据,数据元素,逻辑结构,物理结构,数据中具有独立意义的个体，也称之为元素、记录、结点、顶点等,将线性结构、树型结构和图结构这几类结构称为逻辑结构，因为仅考虑了元素之间的逻辑关系，而没有考虑到其在计算机中的具体实现。,在选择了数据结构的存储结构之后，可实现所给出的运算(操作),数据是信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。,字段是对元素的详细描述，

50、通常情况下，元素可能包含多个字段。,为所涉及的数据结构选择一种存储形式，并将其存储到计算机中，这样就得到了数据结构在内存中的物理结构（存储结构）,本章小结,1.如下一些基本概念：数据：客观事物的符号表示。在计算机学科中，数据的概念被大大的扩充了，不仅包含数学中的整数实数，任何能用计算机识别的符号都可作为数据。数据元素：数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。数据项:构成数据元素的成分,是数据不可分割的最小单位,存储结构：数据结构在计算机中的表示(又称映象)称为数据的存储结构,又称物理结构逻辑结构：数据之间的结构关系，是具体关系的抽象。结点和结点之间的逻辑关系称为数据的逻辑结构