数据结构（c#语言版）ppt

数据结构和算法简介,数据结构(C#语言版),目标,在本章中，你将达到如下目标： 了解问题求解的基本步骤 认识数据结构,熟悉其基本概念 熟悉算法的定义及特征 了解算法分析与度量的方法 初步了解本教材进行问题求解的基本思路,问题描述 某电信部门想开发一个查询知名电子企业服务电话号码的程序。要求对于任意给出的一个企业名称，若该企业已注册其服务电话号码，则迅速找到其电话号码；否则指出没有该企业的服务电话号码。,问题引入查找电话号码问题,问题引入查找电话号码问题,首先构造一张电话号码信息表。 接着将电话号码登记表存储到计算机中 。 然后确定解决问题的算法。 最后编程实现算法，写出C#的实现代码.,解决问题的步骤,问题引入问题求解的基本步骤,根据实际问题，确定数据及数据之间的关系，即对数据的结构进行设计 分析对数据结构可能进行的操作，设计算法； 用一种存储结构在计算机内部表示数据及数据之间的关系； 根据存储结构的存储方式及设计的算法实现算法的计算机表示； 使用己实现的存储结构及算法解决实际问题。,认识数据结构数据的概念,数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称,认识数据结构数据元素和数据项,数据元素是数据的基本单位，是计算机进行输入输出操作的最小单位。 数据元素可以由不可分割的数据项组成 。,认识数据结构数据结构的概念,数据结构是相互之间存在一种或多种特定关系的数据元素的集合 。 数据结构=数据元素+关系（结构） 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构 根据数据元素之间关系的不同特性，通常有四类基本结构 :集合、线性结构、树形结构、图状结构 四种关系是数据元素之间的逻辑关系，又称为逻辑结构,认识数据结构数据结构的存储,数据元素在计算机中的表示称为数据的存储结构。它包括数据元素的表示和关系的表示。 在计算机中数据元素是用一个由若干位组合起来形成的一个位串来表示 数据元素之间关系在计算机中有两种不同的表示方法：顺序存储和链式存储，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。 顺序存储结构借助元素在存储器中的相对位置来表示数据元素之间逻辑关系，数据元素存放在一片连续的存储空间里，通常用数组来实现 链式存储结构则借助于引用或指针来表示数据元素之间的逻辑关系，被存放的元素被随机的存放在内存中再用指针将它们链接在一起。,认识算法算法的定义及特征,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具用5个重要的特征： 有限性：算法必须在有限的步骤之后结束 确定性：算法的每一步都是确定的定义，无二义性。即在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出 输入：一个算法可接受零个或多个输入 输出：一个算法有至少一个或多个输出 有效性：算法由可实现的基本指令组成。,认识算法算法的性能分析与度量,一个算法的评价可以从算法执行的时间与算法的所占用的内存空间两个方面来进行 算法的执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而这种机器的消耗时间与下列因素有关： (1) 书写算法的程序设计语言； (2) 编译产生的机器语言代码的质量； (3) 机器执行指令的速度； (4) 问题的规模。 算法的效率只与问题的规模有关，或者说，算法的效率是问题规模的函数 一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。通常使用大O符号表示：T（n）=O(f(n),寻求问题求解的实现方法,抽象数据类型：一个抽象数据类型（ADT, abstract data type）是一个数据结构和可能在这个数据结构上进行的操作定义的。开发者们通过抽象数据类型的操作方法来访问抽象数据类型中的数据结构，而不管这个数据结构内部各种操作是如何实现的。 为了用C#实现抽象数据类型，本书遵循下面的解题步骤： (1) 用数据类型（包括值类型和引用类型）表示数据结构中的数据元素（后面也称结点）； (2) 用顺序存储结构或链式存储结构表示数据元素之间的关系； (3) 用接口定义在数据结构上的基本操作； (4) 将数据结构的表示代码及对接口所定义操作的实现代码封装在类中，用类表示某种数据结构所对应的抽象数据类型； （5）通过使用实现抽象数据类型的C#类解决实际应用的问题。,小结,数据是对客观事物的符号表示，数据元素是数据的基本单位，是计算机进行输入输出操作的最小单位； 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。可用公式表示为：数据结构=数据元素+关系（结构）； 通常有4类基本数据结构： 集合、线性结构、树形结构、图形结构 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，算法具用5个重要的特征 通常对一个算法的评价可以从算法执行的时间与算法的所占用的内存空间两个方面来进行 一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。通常使用大O符号表示：T（n）=O(f(n)。其中，f(n)是算法中基本操作重复执行的次数随问题规模n增长的增长率函数。,使用堆栈解决编程问题,数据结构(C#语言版),目标,在本章中,你将学到: 识别堆栈的特性 实施堆栈 运用堆栈来解决编程问题,学习情境用堆栈解决火车车厢重排问题的编程,问题描述 一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 -n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图3.1a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。在图3.1a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图3.1b 给出了按所要求的次序重新排列后的结果。,学习情境用线性表解决学生成绩表的编程,问题描述(续),根据上面的描述，编写程序实现下面的功能： 编写一算法实现火车车箱的重排； 编写程序模拟图3.1所示的具有9节车厢的火车入轨和出轨的过程。 程序主界面设计如图3.2所示。,让我们来玩Rummy（拉米纸牌）的游戏。,堆栈,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,认识堆栈分析堆栈的逻辑结构,堆栈(Stack)是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。 堆栈就是一个只能访问其末尾数据的数据集，这一端也叫做顶部。 数据仅能在顶部进行插入和删除操作。 最新插入的数据将被最先删除。 因此，堆栈也被称为后进先出数据结构（Last-In-First-Out）。,认识堆栈分析堆栈的逻辑结构,1. 堆栈的定义,2. 堆栈的特征,堆栈也被称为后进先出数据结构（Last-In-First-Out）。,初始化栈：也就是产生一个新的空栈； 入栈操作Push(T x):将指定类型元素x进到栈中； 出栈操作TPop(): 将栈中的栈顶元素取出来，并在栈中删除栈顶元素； 取栈顶元素GetTop():将栈中的栈顶元素取出来，栈中元素不变； 判断栈空IsEmpty():若栈为空，返回true，否则返回false； 清空操作Clear ( )：从栈中清除所有的数据元素。,认识堆栈识别堆栈的基本操作,堆栈的基本操作有以下几种：,下面描述堆栈的进栈操作,PUSH：它是在堆栈顶部插入新元素的过程。,Empty Stack,1,Push an Element 1,认识堆栈识别堆栈的基本操作,PUSH：它是在堆栈顶部插入新元素的过程。,下面描述堆栈的进栈操作,1,Push an Element 2,2,Push an Element 3,3,认识堆栈识别堆栈的基本操作,POP：它是从堆栈顶部删除元素的过程。,下面描述堆栈的出栈操作,1,POP an Element,3,2,3,POP an Element,2,认识堆栈识别堆栈的基本操作,堆栈中的元素按 _基础进行添加和删除。,课间思考,答案： LIFO,用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈(Sequence Stack)。 类似于顺序表，用一维数组来存放顺序栈中的数据元素 。 栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1 。,用顺序栈解决堆栈的编程问题用顺序栈表示堆栈,初始化顺序栈就是创建一个空栈，即调用SeqStack的构造函数，在构造函数中执行下面的步骤：,1. 初始化顺序栈,用顺序栈解决堆栈的编程问题对顺序栈进行操作,Push操作是将一个给定的项保存在堆栈的最顶端，顶端元素的索引保存在变量top中，因此要进行Push操作，需要执行下面的步骤：,2.入栈操作：Push(T elem),用顺序栈解决堆栈的编程问题对顺序栈进行操作,Pop操作就是从堆栈的顶部取出数据。要进行Pop操作，需要执行以下的步骤：,3. 出栈操作：T Pop( ),用顺序栈解决堆栈的编程问题对顺序栈进行操作,取栈顶元素操作与出栈操作相似，只是取栈顶元素操作不改变原有堆栈，不删除取出的元素。,4. 取栈顶元素：GetTop(),用顺序栈解决堆栈的编程问题对顺序栈进行操作,用链式存储结构存储的栈称为链栈(Linked Stack)。链栈通常用单链表来表示，它的实现是单链表的简化 。 链栈结点的结构与单链表结点的结构一样 。 LinkStack类中有一个字段top表示栈顶指示器和一个字段size表示栈的大小 。,用顺序栈解决堆栈的编程问题用链栈表示堆栈,初始化链栈就是创建一个空链栈，即调用LinkStack的构造函数，在构造函数中执行下面的步骤：,1. 初始化链栈,用顺序栈解决堆栈的编程问题对顺序栈进行操作,Push操作是将一个给定的项保存在堆栈的最顶端，在链栈中，就是在单链表的起始处插入一个结点。需要执行下面的步骤：,2.入栈操作：Push(T elem),用顺序栈解决堆栈的编程问题对顺序栈进行操作,Pop操作就是从堆栈的顶部取出数据，即从链栈的起始处删除一个结点。要进行Pop操作，需要执行以下的步骤：,3. 出栈操作：T Pop( ),用顺序栈解决堆栈的编程问题对顺序栈进行操作,取栈顶元素操作与出栈操作相似，只是取栈顶元素操作不改变原有堆栈，不删除取出的元素。,4. 取栈顶元素：GetTop(),用顺序栈解决堆栈的编程问题对顺序栈进行操作,小结,在本章中，你已经学到： 堆栈(Stack)是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。栈的主要特点是“后进先出”； 堆栈的插入操作也称为进栈或入栈，堆栈的删除操作称为出栈或退栈； 允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)； 堆栈的基本操作; 顺序栈用一片连续的存储空间来存储栈中的数据元素； 链栈是用链式存储结构存储的栈。,解决队列的编程问题,数据结构(C#语言版),目标,在本章中,你将学到: 识别队列的特性 实施队列 运用队列来解决编程问题,学习情境用队列解决银行排队叫号软件的编程,问题描述 目前，在以银行营业大厅为代表的窗口行业，大量客户的拥挤排队已成为了这些企事业单位改善服务品质、提