第二讲-程序设计-数据结构

程序设计计算机教研室1第二讲-程序设计-数据结构全文共50页，当前为第1页。2语言是人们交流思想、传达信息的工具。如汉语和英语等，通常称为自然语言。另一方面，人们为了某种专门用途，创造出种种不同的语言，例如旗语和哑语等，通常称为人工语言。专门用于人与计算机之间交流信息的各种人工语言称为计算机语言或程序设计语言。第二节程序设计基础第二讲-程序设计-数据结构全文共50页，当前为第2页。2.1程序设计的概念3用计算机解决一个问题，必须事先设计好计算机处理信息的步骤，把这些步骤用计算机能够识别的指令编写出来并送入计算机执行，计算机才能按照人的意图完成指定的工作。程序（Program）是用某种计算机能理解并执行的计算机语言来描述解决某一问题的方法和步骤，是一系列指令（Instruction）的集合。第二讲-程序设计-数据结构全文共50页，当前为第3页。4程序设计也不是简单的编写程序代码，它反映了利用计算机解决问题的全过程。先要对问题进行分析并建立数学模型或提出对数据处理的需求，然后进行算法设计，并用某一种程序设计语言编写程序，最后调试程序，使之运行后能产生预期的结果，这个过程称为程序设计。

程序设计＝算法+数据结构+方法+工具。第二讲-程序设计-数据结构全文共50页，当前为第4页。程序设计要经过以下4个基本步骤：（1）分析问题，确定数学模型。弄清问题的要求，输什么数据、得什么结果、输出什么。把实际问题简化，用数学语言来描述它，建立数学模型。选择计算方法（用计算机求解该数学模型的近似方法）。（2）设计算法（Algorithm），画出流程图。把问题的数学模型或处理需求转化为计算机解题的步骤。解决一个问题，可能有多种算法。通过分析、比较，挑选一种最优的算法。算法设计后，要用流程图把算法形象地表示出来。5第二讲-程序设计-数据结构全文共50页，当前为第5页。（3）选择编程工具，按算法编写程序。确定算法后，选择某种程序设计语言编写成程序，这个过程称为编码（Coding）。（4）调试程序，分析输出结果。完成的程序，不一定完全符合实际问题的要求，必须运行程序，排除其中可能的错误，这个过程称为调试（Debugging）。6第二讲-程序设计-数据结构全文共50页，当前为第6页。在程序设计中，第（2）步是核心。算法的优劣直接反映出解题思想和方法的好坏。一个好的算法可以很快解决问题，而一个稍微不好的算法需要很长时间甚至不能或不能按期解决问题。算法是程序设计中的核心。它不能仅从程序设计课程中学习到，更是一种方法、或是一种思想，我们需要从各个知识领域中学习，从我们已经具备的知识中总结。7第二讲-程序设计-数据结构全文共50页，当前为第7页。例：求5！步骤1:1*2=2步骤2:2*3=6步骤3:6*4=24步骤4:24*5=120S1：n=1S2：i=2S3：n*i→nS4：i+1→iS5：如果i的值不大于5，重新执行S3和S4，否则，算法结束。8第二讲-程序设计-数据结构全文共50页，当前为第8页。Y开始n=1i=2n*i→ni+1→ii>5结束N流程图9第二讲-程序设计-数据结构全文共50页，当前为第9页。2.2数据结构当今计算机数据处理的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。数据结构是指相互有关联的数据元素的集合。10第二讲-程序设计-数据结构全文共50页，当前为第10页。2.2数据结构数据结构主要研究和讨论以下三个方面的问题：一、数据集合中各数据元素之间所固有的逻辑关系----逻辑结构。11处理大量数据时，要找到这些数据之间的固有关系。如学生成绩处理：每一个元数据包含学号、姓名、分数等，查询分数时常常按学号值的次序查找，学号决定该数据元素在集合中的位置，位置的前后次序就是我们要找的固有关系，称之为数据的“逻辑结构”。第二讲-程序设计-数据结构全文共50页，当前为第11页。2.2数据结构数据结构主要研究和讨论以下三个方面的问题：二、数据处理时，数据元素在计算机中的存储关系-----存储结构。12处理数据时，要将这些数据存入计算机的存储器中，存储数据时要保留数据元素的固有关系，不能随意存储。存储数据的方式称之为数据的“存储结构”。常用的“存储结构”有：顺序存储和链式存储。第二讲-程序设计-数据结构全文共50页，当前为第12页。2.2数据结构数据结构主要研究和讨论以下三个方面的问题：三、对各种数据结构进行的运算。13“存储结构”确定后，程序员通过“存储结构”可以推导出数据的“逻辑结构”从而对数据实现：插入、删除、修改、查找、排序等操作。第二讲-程序设计-数据结构全文共50页，当前为第13页。大量具有固有逻辑关系的数据集是数据结构，其中包含的个体称为数据元素。在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系来描述。数据元素的逻辑结构常用图形表示。141.张三2.李四3.王五描述数据结构第二讲-程序设计-数据结构全文共50页，当前为第14页。线性有且只有一个根结点（没有前件的结点）。每一个结点最多只有一个前件，也最多只有一个后件。线性结构任意删除一个元素后，仍然是线性结构。15春夏秋冬描述数据结构第二讲-程序设计-数据结构全文共50页，当前为第15页。非线性如果数据结构不满足线性结构的条件，则称之为非线性结构。16父亲儿子女儿孙子描述数据结构第二讲-程序设计-数据结构全文共50页，当前为第16页。17全校学生档案管理的组织方式非线性结构——树形结构第二讲-程序设计-数据结构全文共50页，当前为第17页。18线性表线性表的定义

线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：

a1，a2，……，ai，……，an其中n称作表的长度，当n=0时，称作空表。如：英文小写字母表（a,b,…,z）是一个长度26的线性表。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。第二讲-程序设计-数据结构全文共50页，当前为第18页。19学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结ABC张卓刘忠赏胡孝臣第二讲-程序设计-数据结构全文共50页，当前为第19页。20线性表的特点：1.线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前件和一个后件。第一个数据元素无前件，最后一个数据元素无后件。3.数据元素在表中的位置只取决于它自身的序号。在线性表上常用的运算有：初始化、求长度、取元素、修改、前插、删除、检索、排序。ABCD第二讲-程序设计-数据结构全文共50页，当前为第20页。21线性表的顺序存储结构线性表顺序存储结构的特点：

1、线性表所有元素所占的存储空间是连续的。

2、线性表各数据元素在存储空间中是按逻辑顺序依次存放的。

在计算机中存放线性表，采用顺序存储是一种简单方便的方法。学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号第二讲-程序设计-数据结构全文共50页，当前为第21页。首地址ADR(a1)22元素an……..元素ai……..元素a2元素a1存储地址内存状态顺序存储结构示意图(顺序表)：每个元素所占用的存储单元个数ADR(a1)

+kADR(a1)

+(i-1)*

kADR(a1)

+(n-1)*

kADR(ai)=ADR(a1)

+(i-1)*

k第二讲-程序设计-数据结构全文共50页，当前为第22页。线性表的插入和删除运算示意图ai-1…..a2a1an…ai+1aix插入运算23ai-1…..a2a1

aiai+1…anx删除运算ai-1…..a2a1

aiai+1…anx注：线性结构中插入或删除任何一个结点后还应是线性结构。第二讲-程序设计-数据结构全文共50页，当前为第23页。24元素n……..元素i……..元素2元素1存储内容缺点：1.作插入或删除操作时，需移动大量元素。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。优点：1.结构简单，节省存储空间。2.可随机定位其中的元素。线性表顺序存储第二讲-程序设计-数据结构全文共50页，当前为第24页。线性表的链式存储结构将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。25指针第二讲-程序设计-数据结构全文共50页，当前为第25页。26线性链表表示法:0第二讲-程序设计-数据结构全文共50页，当前为第26页。链式存储结构的特点

插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入删除时使用。

链表的查找只能从头指针开始顺序查找。27第二讲-程序设计-数据结构全文共50页，当前为第27页。28xbaHbaH线性链表的插入运算在H所指向的结点之后插入新的结点线性链表的运算第二讲-程序设计-数据结构全文共50页，当前为第28页。线性链表的删除运算在H所指向的结点之后删除新的结点线性链表的运算29baxHbaxH第二讲-程序设计-数据结构全文共50页，当前为第29页。30H1536D1400A1346BnullC1345

线性表链式存储链式存储结构特点：1.缺点：比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。定位时必须按顺序进行。2.优点：逻辑上相邻的节点物理上不必相邻。插入、删除灵活(不必移动节点，只要改变节点中的指针)。存储地址数据域指针域1345A14001536B13461346Cnull1400D1536第二讲-程序设计-数据结构全文共50页，当前为第30页。顺序查找（线性查找）查找过程：对给定的关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。

在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。最坏情况为n。ABCDEF12345631第二讲-程序设计-数据结构全文共50页，当前为第31页。32顺序查找（线性查找）在下面两种情况下只能采取顺序查找：

a.线性表为无序表（元素排列是无序的）。

b.即使是有序线性表，但采用的是链式存储结构。498215H1536D1400A1346BnullC1345第二讲-程序设计-数据结构全文共50页，当前为第32页。33二分法查找（折半查找）思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。三种情况：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值，则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找效率高。最坏的情况下，需要比较log2n次。第二讲-程序设计-数据结构全文共50页，当前为第33页。34查找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+1highmid第二讲-程序设计-数据结构全文共50页，当前为第34页。35栈和队列栈和队列的定义

栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。第二讲-程序设计-数据结构全文共50页，当前为第35页。栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为先进后出(FILO)或后进先出(LIFO)设栈s=（a1，a2，...,ai，...，an）其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。约定用指针top始终指向栈顶的位置，用指针bottom指向栈底。topbottom进栈……a1a2….ai出栈36第二讲-程序设计-数据结构全文共50页，当前为第36页。栈的顺序存储结构及其基本运算a1a2top用顺序存储结构表示的栈

顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向栈顶元素的位置。基本运算：压(进)栈：PUSH出栈：POP读栈顶元素37第二讲-程序设计-数据结构全文共50页，当前为第37页。top空栈ABAKEDCBAKEDCBAtoptoptoptopA进栈B进栈K进栈L进栈溢出……栈满：栈顶指针指向存储空间的最后一个位置进栈示例38第二讲-程序设计-数据结构全文共50页，当前为第38页。KEDCBAtopK出栈EDCBADCBABAtoptoptoptopE出栈D出栈A出栈空栈……出栈示例39第二讲-程序设计-数据结构全文共50页，当前为第39页。40队列(

Queue)的定义定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。队列示意图队头队列只允许在队尾插入，在队头删除。队头指针：front：指向排头元素的前一个位置队尾指针：rear：指向队尾元素此种结构称为先进先出（FIFO）或后进后出(LILO)。a1a2a3……an-1an队尾插入删除第二讲-程序设计-数据结构全文共50页，当前为第40页。41队列的主要运算（1）插入一个新的队尾元素，称为进队；（2）删除队头元素，称为出队；（3）读取队中元素（检索）；当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素前一个位置，而尾指针始终指向队尾元素的位置。第二讲-程序设计-数据结构全文共50页，当前为第41页。front空队ABADCBA进队B进队CD进队A出队队列的进队和出队示例rearFEDCBfrontrearfrontrearfrontrearfrontrearfrontrearEF进队

进队时队尾指针先进：rear=rear+1，再将新元素按rear指示位置加入。

出队时队头指针先进：front=front+1，再将下标为front的元素取出。

队满时再进队将溢出出错；队空时再出队将队空处理。队满：队尾指针指向存储空间的最后一个位置ABDCA42第二讲-程序设计-数据结构全文共50页，当前为第42页。43树与二叉树全校学生档案管理的组织方式第二讲-程序设计-数据结构全文共50页，当前为第43页。44树的定义由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。在树结构中，每一个节点只有一个前件，称为它的父节点，每一个节点可以有多个后件，称为它的子节点。没有前件只有后件的节点只有一个，称为树的根节点，简称树的根。没有后件只有前件的节点称为叶子节点。ABCD第二讲-程序设计-数据结构全文共50页，当前为第44页。45结点(node)结点的度(degree)叶子(lea