程序设计数据结构

程序设计计算机教研室2语言是人们交流思想、传达信息的工具。如汉语和英语等，通常称为自然语言。另一方面，人们为了某种专门用途，创造出种种不同的语言，例如旗语和哑语等，通常称为人工语言。专门用于人与计算机之间交流信息的各种人工语言称为计算机语言或程序设计语言。第二节程序设计基础2.1程序设计的概念3用计算机解决一个问题，必须事先设计好计算机处理信息的步骤，把这些步骤用计算机能够识别的指令编写出来并送入计算机执行，计算机才能按照人的意图完成指定的工作。程序（Program）是用某种计算机能理解并执行的计算机语言来描述解决某一问题的方法和步骤，是一系列指令（Instruction）的集合。4软件和程序并不是同一个概念（软件≠程序）。软件是程序、数据和相关的文档资料的总和。软件=程序+数据+相关文档资料编制程序的工作就是程序设计（Programming），而软件开发（Softwaredevelopment）包括需求文档、设计概要、详细设计、编码、测试、发布，而程序设计则主要是指程序代码的编写，是软件开发的一部分。5程序设计也不是简单的编写程序代码，它反映了利用计算机解决问题的全过程。先要对问题进行分析并建立数学模型或提出对数据处理的需求，然后进行算法设计，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果，这个过程称为程序设计。程序设计＝算法+数据结构+方法+工具。程序设计要经过以下4个基本步骤：（1）分析问题，确定数学模型。弄清问题的要求，输什么数据、得什么结果、输出什么。把实际问题简化，用数学语言来描述它，建立数学模型。选择计算方法（用计算机求解该数学模型的近似方法）。（2）设计算法（Algorithm），画出流程图。把问题的数学模型或处理需求转化为计算机解题的步骤。解决一个问题，可能有多种算法。通过分析、比较，挑选一种最优的算法。算法设计后，要用流程图把算法形象地表示出来。（3）选择编程工具，按算法编写程序。确定算法后，选择某种程序设计语言编写成程序，这个过程称为编码（Coding）。（4）调试程序，分析输出结果。完成的程序，不一定完全符合实际问题的要求，必须运行程序，排除其中可能的错误，这个过程称为调试（Debugging）。在程序设计中，第（2）步是核心。算法的优劣直接反映出解题思想和方法的好坏。一个好的算法可以很快解决问题，而一个稍微不好的算法需要很长时间甚至不能或不能按期解决问题。算法是程序设计中的核心。它不能仅从程序设计课程中学习到，更是一种方法、或是一种思想，我们需要从各个知识领域中学习，从我们已经具备的知识中总结。例：求5！•步骤1:1*2=2•步骤2:2*3=6•步骤3:6*4=24•步骤4:24*5=120•S1：n=1•S2：i=2•S3：n*i→n•S4：i+1→i•S5：如果i的值不大于5，重新执行S3和S4，否则，算法结束。Y开始n=1i=2n*i→ni+1→ii5结束N流程图2.2数据结构当今计算机数据处理的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。112.2数据结构数据结构主要研究和讨论以下三个方面的问题：1.数据集合中各数据元素之间所固有的逻辑关系----逻辑结构。12处理大量数据时，要找到这些数据之间的固有关系。如学生成绩处理：每一个元数据包含学号、姓名、分数等，查询分数时常常按学号值的次序查找，学号决定该数据元素在集合中的位置，位置的前后次序就是我们要找的固有关系，称之为数据的“逻辑结构”。2.2数据结构数据结构主要研究和讨论以下三个方面的问题：2.数据处理时，数据元素在计算机中的存储关系-----存储结构。13处理数据时，要将这些数据存入计算机的存储器中，存储数据时要保留数据元素的固有关系，不能随意存储。存储数据的方式称之为数据的“存储结构”。常用的“存储结构”有：顺序存储和链式存储。2.2数据结构数据结构主要研究和讨论以下三个方面的问题：3.对各种数据结构进行的运算。14“存储结构”确定后，程序员通过“存储结构”可以推导出数据的“逻辑结构”从而对数据实现：插入、删除、修改、查找、排序等操作。描述数据结构大量具有固有逻辑关系数据集是数据结构，其中包含的个体称为数据元素。在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系来描述。数据元素的逻辑结构常用图形表示。15ABC线性有且只有一个根结点（没有前件的结点）。每一个结点最多只有一个前件，也最多只有一个后件。线性结构任意删除一个元素后，仍然是线性结构。16ABCD非线性如果数据结构不满足线性结构的条件，则称之为非线性结构。17ABCD18全校学生档案管理的组织方式非线性结构——树形结构19线性表线性表的定义线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：a1，a2，……，ai，……，an其中n称作表的长度，当n=0时，称作空表。20学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结ABC张卓刘忠赏胡孝臣21线性表的特点：1.线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前件和一个后件。第一个数据元素无前件，最后一个数据元素无后件。3.数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序。ABCD22线性表的顺序存储结构线性表顺序存储结构的特点：1、线性表所有元素所占的存储空间是连续的。2、线性表各数据元素在存储空间中是按逻辑顺序依次存放的。在计算机中存放线性表，采用顺序存储是一种简单方便的方法。学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号首地址ADR(a1)23元素an……..元素ai……..元素a2元素a1存储地址内存状态顺序存储结构示意图(顺序表)：每个元素所占用的存储单元个数ADR(a1)+kADR(a1)+(i-1)*kADR(a1)+(n-1)*kADR(ai)=ADR(a1)+(i-1)*kn-1线性表的插入和删除运算示意图ai-1…..a2a1an…ai+1aixai-1…..a2a1aiai+1…alengthan……ai+1aix删除运算插入运算25元素n……..元素i……..元素2元素1存储内容缺点：1.作插入或删除操作时，需移动大量元素。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。优点：1.结构简单，节省存储空间。2.可随机定位其中的元素。线性表顺序存储线性表的链式存储结构将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。2627线性链表表示法:0链式存储结构的特点•插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。•适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。•链表的查找只能从头指针开始顺序查找。2829xbaHbaH线性链表的插入运算在H所指向的结点之后插入新的结点线性链表的运算30baxHbaH线性链表的删除运算在H所指向的结点之后删除新的结点线性链表的运算baxH31baxHbaH线性链表的删除运算在H所指向的结点之后删除新的结点线性链表的运算baxH32h1536元素21400元素11346元素30元素41345线性表链式存储1.缺点：比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。定位时必须按顺序进行。2.优点：逻辑上相邻的节点物理上不必相邻。插入、删除灵活(不必移动节点，只要改变节点中的指针)。链接存储结构特点：顺序查找（线性查找）查找过程：对给定的关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。最坏情况为n。ABCDEF12345634顺序查找（线性查找）在下面两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）。b.即使是有序线性表，但采用的是链式存储结构。498215h1536元素21400元素11346元素30元素4134535二分法查找（折半查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。三种情况：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找效率高。最坏的情况下，需要比较log2n次。36查找23的过程如下图：mid=(low+high)/2不进位取整(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid37栈和队列栈和队列的定义栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为先进后出(FILO)或后进先出(LIFO)设栈s=（a1，a2，...,ai，...，an）其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。约定用指针top始终指向栈顶的位置，用指针bottom指向栈底。topbottom进栈a1a2….ai出栈39栈的顺序存储结构及其基本运算a1a2top用顺序存储结构表示的栈顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向栈顶元素的位置。基本运算：压(进)栈：PUSH出栈：POP读栈顶元素top空栈ABAKEDCBAKEDCBAtoptoptoptopA进栈B进栈K进栈L进栈溢出……栈满：栈顶指针指向存储空间的最后一个位置进栈示例KEDCBAtopK出栈EDCBADCBABAtoptoptoptopE出栈D出栈A出栈空栈……出栈示例42队列(Queue)的定义定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。队列示意图队头队列只允许在队尾插入，在队头删除。队头指针：front：指向排头元素的前一个位置队尾指针：rear：指向队尾元素此种结构称为先进先出（FIFO）或后进后出(LILO)。a1a2a3……an-1an队尾插入插入43队列的主要运算（1）插入一个新的队尾元素，称为进队；（2）删除队头元素，称为出队；（3）读取队中元素（检索）；当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置。front空队ABADCBA进队B进队CD进队A出队队列的进队和出队示例rearFEDCBfrontrearfrontrearfrontrearfrontrearfrontrearEF进队进队时队尾指针先进：rear=rear+1，再将新元素按rear指示位置加入。出队时队头指针先进：front=front+1，再将下标为front的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。队满：队尾指针指向存储空间的最后一个位置ABDCA45树与二叉树全校学生档案管理的组织方式46树的定义由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。在树结构中，每一个节点只有一个前件，称为它的父节点，每一个节点可以有多个