数据结构(C语言版)

1总学时：32讲课学时：24教材：《数据结构C语言版》严蔚敏、吴伟民-----清华大学出版社《数据结构题集》严蔚敏，清华大学出版社参考书：《数据结构》（用面向对象方法与C++描述），殷人昆等，清华大学出版社辅导每周五下午：信息科技大厦1901课程安排2编程基础考研课程计算机等级考试课程程序员考试课程课程重要性3第一章绪论1.1数据结构的概念1.2基本概念和术语1.3抽象数据类型1.4算法和算法分析4为什么要学习数据结构？什么是程序、软件？N.沃思（NiklausWirth)教授提出：1.1数据结构的概念程序=算法+数据结构以上公式说明了如下两个问题：(1)数据上的算法决定如何构造和组织数据(算法→数据结构)(2)算法的选择依赖于作为基础的数据结构(数据结构→算法)。软件=程序+文档（软件工程的观点）5电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。1.1数据结构的概念6数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述1.1数据结构的概念7–例书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001，003……理论力学002，……..线性代数004，………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性表8树……..……..…...…...…...…...–例井字棋9例电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。非数值计算问题：1.1数据结构的概念10–例多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图11例田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。姓名项目1项目2项目3丁一跳高跳远100米马二标枪铅球张三标抢100米200米李四铅球200米跳高王五跳远200米1.1数据结构的概念非数值计算问题：12(1)设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF(2)用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。(3)某选手比赛的项目必定有边相连(不能同时比赛)。非数值计算问题：----田径赛的时间安排问题解法1.1数据结构的概念13姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BFAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛14在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。综上，描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现.1.1数据结构的概念15求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。1.1数据结构的概念16数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。1.1数据结构的概念17《数据结构课程》所处的地位：1.1数据结构的概念18数据(Data):对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数值型数据非数值型数据1.2基本概念和术语19数据元素(DataElement):数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小标识单位。1.2基本概念和术语职位业绩入队日期出生日期年月日俱乐部名称姓名20数据对象(DataObject)：性质相同的数据元素的集合。是数据的一个子集。整数数据对象N={0,1,2,…}字母字符数据对象C={‘A’,‘B’,‘C’,…‘F’}1.2基本概念和术语21定义1----是相互之间存在一种或多种特定关系的数据元素的集合。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。什么是数据结构22数据结构的三个方面的含义：逻辑结构---数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）----数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言。运算（算法）1.2基本概念和术语23数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：1.2基本概念和术语24数据结构3方面含义之——逻辑结构逻辑结构---划分方法一（1）线性结构----有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串（2）非线性结构----一个结点可能有多个直接前趋和直接后继。例如：树、图、多维数组、广义表等。1.2基本概念和术语25逻辑结构---划分方法二一、集合：结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构：结构中的数据元素之间存在一对一的关系，如线性表、栈、队列。三、树型结构：结构中的数据元素之间存在一对多的关系，如树。四、图状结构或网状结构：结构中的数据元素之间存在多对多的关系，如图。1.2基本概念和术语26四个基本结构•集合•线性结构•树形结构•网状结构27bindevetclibuser2114131211234678910315871011998745662313155线性结构树形结构树二叉树二叉排序树28堆结构123548711102916125643125436113318146651921图结构网络结构29数据结构3方面含义之——存储结构存储结构两方面的内容：（1）数据元素自身值的表示（数据域）（2）该结点与其它结点关系的域（链域）四种基本的存储方法：（1）顺序存储方法（结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。1.2基本概念和术语30元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储311536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h32逻辑结构存储结构小结：（1）数据的逻辑结构、存储结构和数据的运算（算法）构成了数据结构三个方面的含义。（2）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。1.2基本概念和术语331.3抽象数据类型(ADT)数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义341.3抽象数据类型(ADT)抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作数据结构+定义在此数据结构上的一组操作=抽象数据类型例如：矩阵+（求转置、加、乘、求逆、求特征值）构成一个矩阵的抽象数据类型35抽象数据类型的描述抽象数据类型可用（D，S，P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名1.3抽象数据类型(ADT)36其中,数据对象、数据关系用伪码描述；基本操作定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。1.3抽象数据类型(ADT)37数据结构的三个方面的含义之——算法算法的概念和描述：什么是算法？所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。1.4算法和算法分析38算法的概念和描述：一个算法必须满足以下五个准则：（1）有穷性---执行了有限条指令后一定要终止。（2）确定性（无二义）---算法的每一步操作都必须有确切定义，不得有任何歧义性。（3）可（能）行性---算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。（4）输入数据---一个算法有n（n=0)个初始数据的输入。（5）输出数据---一个算法有一个或多个与输入有某种关系的有效信息的输出。1.4算法和算法分析39例一个不是算法的例子(1)begin(2)n=0(3)n=n+1(4)repeat(3)(5)end例一个不超过100次计数的算法(1)begin(2)n=0(3)n=n+1(4)ifn=100do(5),elserepeat(3)(5)outputn(6)end1.4算法和算法分析40算法的描述和实现描述---可采用自然语言、数学语言或约定的符号语言。实现---必须借助程序设计语言提供的数据类型及其运算。本课的描述---采用类C语言。1.4算法和算法分析41算法的评价准则（首先，算法必须是“正确”的）（1）执行算法所耗费的时间（效率要高）。（2）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。（3）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。1.4算法和算法分析42程序正确性的四个层面：（1）不含语法错误（2）程序对于n组输入数据能够得出满足规格说明要求的结果。（3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。（4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。1.4算法和算法分析43算法效率的度量1.程序运行所耗费的时间(由下列因素决定)：算法所选用的策略问题的规模书写程序所采用的语言编译程序所产生的机器代码的质量机器执行指令的速度一个算法耗费的时