数据结构教程与题解

数据结构教程与题解第1页，课件共38页，创作于2023年2月数据结构一、概论二、顺序表单链表其它链表，练习三、栈.队列.串四、数组.广义表链表综合实验五、二叉树性质.遍历递归遍历举例.生成递归消除.线索二叉树树.森林.哈夫曼树阶段练习六、矩阵.邻接表.遍历生成树.最小生成树拓扑.关键.练习七、直插.希尔.冒泡.快速直选.堆.归并.分配八、静态查找二叉排序树,B.B+树排序综合实验散列表总复习少学时参考：40(理论)+8(实验)第2页，课件共38页，创作于2023年2月1.1引言1.2数据结构的概念1.3算法分析第1章概论不论计算机作何用途，每一项应用总是某个程序的运行，用计算机解决任何问题都离不开程序设计。程序设计的实质就是数据的表示和数据的处理。数据结构就是研究这两个方面的一些基本问题的，包括如何组织数据、数据元素之间是什么关系、数据在计算机中如何表示以及如何对数据进行操作等。第3页，课件共38页，创作于2023年2月数值型

非数值型

整数实数…

程序原始数据1.1引言数据的加工处理数据表示、数据处理程序程序设计的实质字符字符串文字图形图象声音…结果数据第4页，课件共38页，创作于2023年2月(1)数值问题求面积、体积S=a×bV=a×b×c◆建模型◆设计解法◆编程数据对象比较简单，如整型、实型或布尔型等，数据结构的问题不突出，程序设计的主要精力集中在程序设计的技巧上，解决问题的关键是数值计算方法(算法)，程序以算法为中心。

也要用到数据结构知识方程求根f(x)=a2x2＋a1x＋a0=0变量名？零系数？前后顺序？快慢？内存？数组压缩线性效率评价f(x)=anxn＋an−1xn−1＋…＋a1x＋a0=0第5页，课件共38页，创作于2023年2月赛程安排AEDBFC(2)非数值问题JIACBDHGFE族谱（血缘关系）学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机2

00102石磊男83/12/21汕头51200计算机1

……………档案管理数据对象非数值型，数据间关系复杂、处理复杂（不能用数学公式表示），如何有效表示关系、如何有效处理数据，成为问题的关键。选择合适的数据结构表示问题，再写出算法

程序＝数据结构＋算法有序索引线性第6页，课件共38页，创作于2023年2月数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。第7页，课件共38页，创作于2023年2月1.2数据结构的概念1.2.1数据1.2.2数据类型1.2.3逻辑结构1.2.4存储结构1.2.5运算1.2.6算法1.2.7数据结构第8页，课件共38页，创作于2023年2月1.2.1数据数据(Data)：凡能被计算机存储、加工处理的对象。是计算机程序加工处理的对象和原料。数值型、非数值型，含有某种信息，信息的载体。信息：加工处理后的数据，数据的内涵，信息通过数据表示。数据元素(DataElement)：数据的基本单位，在程序中作为一个整体加以考虑和处理，常具有完整确定的实际意义。有时称元素、结点、顶点、记录。数据项(DataItem)：数据不可分割的最小标识单位，有独立含义，但常不具完整确定的实际意义，或不被当作一整体看待有时称字段、域。第9页，课件共38页，创作于2023年2月学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21汕头51200计算机1

……………例学生信息表数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干数据元素组成，数据元素又可由若干数据项组成。第10页，课件共38页，创作于2023年2月1.2.2数据类型数据类型(DataType)是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作的总称，它显式或隐式地规定了数据的取值范围和操作特性。

原子类型：值不可分解，一般由程序语言直接提供，int、char…结构类型：值可分解为若干成分(分量)，一般用户定义(借助语言有关数据组织功能，数组、结构…)抽象数据类型(AbstractDataType或ADT)是指一个数学模型以及定义在该模型上的一组操作的总称。“抽象”的含义是指其逻辑特征与具体的软硬件实现(即计算机内部的表示和实现)无关。第11页，课件共38页，创作于2023年2月－使用与实现分离，－封装和信息隐藏。在C++中通过类来描述。ADT

<抽象数据类型名>

isData:<数据描述>Operations:<操作声明>end

<抽象数据类型名>抽象数据类型一般由用户定义：将一组数据和施加于这些数据上的一组操作封装在一起，用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息的隐藏。

struct学生{intheight;}class学生{intheight;public:intget_height();voidstudy();}学生a;x=a.height;struct学生a;x=a.height;×第12页，课件共38页，创作于2023年2月1.2.3逻辑结构数据元素对应客观世界中的实体，其间必然存在各种各样的关系数据元素之间的关系称为结构。其中，数据元素之间的关联方式(或称邻接关系)称作数据的逻辑关系，数据元素之间逻辑关系的整体称为逻辑结构(LogicalStructure)直接前趋(ImmediatePredecessor)：与之相邻且在其前的结点直接后继(ImmediateSuccessor)：与之相邻且在其后的结点。圆圈表示数据，连线表示逻辑关系第13页，课件共38页，创作于2023年2月(1)集合：任两点之间不考虑邻接关系或没有邻接关系，或称没有关系的关系。数据组织形式松散，元素之间“平等”，除了“同属于一个集合”的关系外，别无其它关系。(2)线性结构：有且仅有一个开始结点和一个终端结点，任何结点最多一个直接前趋和一个直接后继。开始结点没有前趋，终端结点没有后继。元素之间存在1：1的关系。(3)树形结构：除一个特殊元素(根)外，每个元素只有一个直接前趋，但可有多个直接后继，结点之间具有分支、层次特性。元素之间存在1：n的关系。(4)图状结构：任何两点之间都可能邻接，结点之间形成网状结构。任一元素可有多个直接前趋和多个直接后继，元素之间存在m：n的关系。图状结构集合线性结构树形结构第14页，课件共38页，创作于2023年2月(1)逻辑结构与数据本身的形式、内容无关。(2)逻辑结构与数据元素的相对位置无关。(3)逻辑结构与所含结点的个数无关。一些表面上很不相同的数据可以有相同的逻辑结构，逻辑结构是数据组织的某种“本质性”的东西。事实上，逻辑结构是数据组织的主要方面。第15页，课件共38页，创作于2023年2月1.2.4存储结构(物理结构)存储结构(StorageStructure)、物理结构：数据的机内表示(存储实现)。数据元素的机内表示＋逻辑结构的机内表示(1)内容存储：存储各数据元素的内容(值)，每个数据元素占据独立的可访问的存储区。(2)关系存储：直接或间接地(显式或隐式地)存储各数据元素间的逻辑关系。(3)附加存储：一般是为便于运算实现而设置的辅助结点。前两部分必须，第三部分根据需要设置。元素内部组织形式一般较简单，内容存储就较简单，逻辑关系的表示是存储结构的主要内容。元素存储后，逻辑关系由存储结点间的关联方式间接表示。第16页，课件共38页，创作于2023年2月(1)顺序存储：所有结点相继存放到一片连续的存储区中，元素之间的逻辑关系通过物理位置关系间接表示。(2)链接存储：结点之间的物理位置不一定连续，它们之间的逻辑关系通过附加的指针来表示。(3)索引存储：在存储结点信息的同时，还建立附加的索引表。(4)散列存储：以结点的关键字值为自变量，通过某个函数计算出该结点的存储位置(或位置区间端点)。顺序存储方式和链接存储方式是最基本的。四种存储方法，既可单独使用，也可组合使用。有时同一种逻辑结构可采用不同的存储结构。第17页，课件共38页，创作于2023年2月1.2.5运算运算：在逻辑结构上施加的操作，即对逻辑结构的加工。如：查找、插入、删除等。加工型：改变原逻辑结构的“值”，如结点数、结点内容等。引用型：不改变原逻辑结构，只从中提取某些信息。运算与逻辑结构紧密相连，每种逻辑结构都有一个运算的集合。运算的种类很多，随不同的应用而不同。第18页，课件共38页，创作于2023年2月基本运算：其实现不能利用其它运算，而其它运算可以或需要利用该运算。如更新不是基本运算，可先用查找，找到该该点后再修改有关内容；而查找是基本运算，它不能利用其它运算。每种逻辑结构都有自己的基本运算集，逻辑结构不同，基本运算集一般也不同。一般地，先将较复杂的运算分解为若干较简单的运算，有利于降低程序设计的难度，同时也有利于提高程序设计的效率。在简单运算中，再分解出一些基本运算，当基本运算实现后，其它运算就可通过调用基本运算来实现，进而完成整个程序。第19页，课件共38页，创作于2023年2月1.2.6算法算法(Algorithm)：解决问题的方法和步骤；规则的有穷集合，这些规则规定了一个指令的有限序列，其中每条指令表示一个或多个操作。求3个数a，b,c中的最大值例运算定义在逻辑结构上，只指出“做什么(功能)”，而不考虑“怎么做(细节)”。运算实现的这个细节问题就是算法。(1)若a>b则max=a,否则max=b(2)若c>max则max=c有些步骤可重复多次执行，但整个步骤总数应有限，整个过程可终止。－可执行－可终止第20页，课件共38页，创作于2023年2月

算法的基本特征：(1)输入：0个或多个输入；(2)输出：1个或多个输出；(3)有穷性：在有限步内结束；(4)确定性：每步清晰无二义性。(5)可行性：每步可执行，并且执行时间是有限的。算法＝程序？程序不一定满足有穷性，即不一定是算法。如操作系统。程序中的指令必须是机器可执行的，而算法中的指令虽要求可执行，但不一定是“机器可执行”。第21页，课件共38页，创作于2023年2月算法描述图形描述：如流程图、N−S图自然语言：非形式算法，可结合其它语言

不严格，易二义性

伪语言：伪语言算法程序设计语言：运行终止的程序可执行部分

严格

语言描述原则上说，任何算法都可用任一种程序设计语言来实现，但显然具体实现的难易程度和效果会有所不同。Y=a+b?中国的煤都是＿＿?第22页，课件共38页，创作于2023年2月C语句C++语句#include<stdio.h>…scanf(”%d%c”,&i,&ch);printf(”%d%c\n”,i,ch);#include<iostream.h>…cin>>i>>ch;cout<<i<<ch<<endl;#definemaxsize100constintmaxsize=100;for(i=0;i<n;i++)s=s+a[i];/*元素求和*/for(i=0;i<n;i++)s=s+a[i];

//数组元素求和int*p,*q;p=malloc(10*sizeof(int));q=malloc(sizeof(int));…free(p);free(q);int*p,*q;p=newint[10];//动态分配10个整数空间(数组)q=newint;//动态分配1个整数空间…delete[]p;//释放数组空间deleteq;第23页，课件共38页，创作于2023年2月1.2.7数据结构数据结构(DataStructure)是指相互间存在着一种或多种关系的数据元素的集合，它们按照某种逻辑关系组织起来，并用计算机语言，按一定的存储方式存储在计算机的存储器中，同时在这些数据上定义了一个运算的集合。由一个逻辑结构S、一个定义在S上的基本运算集Δ和S的一个存储实现D所构成的整体(S,Δ,D)由一个逻辑结构S和定义在S上的一个基本运算集Δ构成的整体(S,Δ)简单地说，一个数据结构就是一类数据的表示及其相关操作，它一般包括三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。不混淆时，常将逻辑结构简称数据结构。第24页，课件共38页，创作于2023年2月逻辑结构是数据本身所固有的，与计算机无关。每种逻辑结构都有自己的一组基本运算，它规定了数据的基本操作方式。由一种逻辑结构和一组基本运算构成的整体，与数据的存储无关，独立于计算机，可看成具体问题抽象出来的数学模型。将数据和数据间逻辑关系存储起来，就得到存储结构。数据的运算定义在逻辑结构上，只指出“做什么”，而不考虑“怎么做”，当确定了存储结构后，才能考虑如何将运算具体实现，即“怎么做”，这就是算法问题。存储结构是逻辑结构的实现，算法是运算的实现，故可认为数据结构的基本任务就是数据结构的设计和实现第25页，课件共38页，创作于2023年2月对一个数据结构，将其三个方面的内容搞清楚了，也就搞清楚了这个数据结构。另外，这三方面中即使只有某一个不同，我们也将其称作不同的数据结构。逻辑结构不同：集合、线性表、树、图。逻辑结构相同，存储结构不同：顺序表、链表。逻辑结构相同，运算不同：栈、队列。逻辑结构相同，存储结构相同，运算不同：顺序栈、顺序队列；链栈、链队列。第26页，课件共38页，创作于2023年2月用顶点和边构成的图形表示数据结构，其中顶点表示数据，边表示数据之间的结构关系；学生基本情况表家族树(1)图形表示JIACBDHGFE0104060508070203第27页，课件共38页，创作于2023年2月用一个二元组(D,S)表示数据结构，其中D是数据元素集合，S是D上关系的集合。D={01，02，03，04，05，06，07，08}S={R}R={<01,02>,<02,03>,<03,04>,<04,05>,<05,06>,<06,07>,<07,08>}D={A,B,C,D,E,F,G,H,I,J}

S={R}

R={(A,B),(A,C),(A,D),(B,E),(B,F),(C,G),(D,H),(D,I),(D,J)}

家族树的二元组表示(D,S)JIACBDHGFE学生基本情况表的二元组表示(D,S)

(2)二元组表示0104060508070203第28页，课件共38页，创作于2023年2月1.3算法分析正确性：正确实现预定功能（处理要求）。易读性：被理解的难易程度，便于交流、修改、查错健壮性：对非法输入的抵抗能力，不产生不需要结果高效率：较好的时空性能。算法评价算法分析：确定一个算法时空性能的工作。空间复杂性/度(SpaceComplexity)：算法的空间耗费，即需要的存储量时间复杂性/度(TimeComplexity)：算法的时间耗费，即包含的计算量第29页，课件共38页，创作于2023年2月(1)时间复杂度时间耗费＝所有语句执行时间之和。各语句执行时间是其执行次数(即频度，FrequencyCount)与每次执行时间的乘积。即语句执行时间与软、硬件有关，难以给出绝对时间，并且环境不同绝对时间也不同。为突出算法本身性态而排除之外其它因素，假定语句抽象运行，不依赖具体软硬件环境；进一步假定各语句每次执行时间均是单位时间。于是，时间耗费就是算法中所有语句频度之和有时取占主导、关键作用的“标准操作”分析。注：“语句”指描述算法的基本语句，它的执行，在语法意义上不可再分割。如循环语句的整体、函数调用语句等不算基本语句，因为它们还包括由多个语句组成的循环体或函数体。第30页，课件共38页，创作于2023年2月时间复杂度是规模的函数。两个方阵相乘Cn×n=An×n×Bn×n

for(i=0;i<n;i++) //n+1

for(j=0;j<n;j++){

//n(n+1)

c[i][j]=0.;

//n2

for(k=0;k<n;k++)

//n2(n+1)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

//n3

}例例矩阵相乘T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1一般地，我们将问题输入数据量(或初始数据量)的大小，或与之相关的某个量，称为问题的规模(Size，大小)，并用一个整数表示。第31页，课件共38页，创作于2023年2月当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐近时间复杂度(AsymptoticTimeComplexity)。时间复杂度的解析形式常常难求，或非常复杂。但问题规模较大时，复杂度表示式中实际上只有一些占主导地位的项有意义，其它低次项可忽略不计。所以通常用某些简单函数来近似表示其大致性能。T(n)=2n3+3n2+2n+1=O(n3)(1)若语句很少执行，且与规模无关，则可忽略不计。(2)若所有语句都与规模无关，即使有上千条语句，其执行时间也不过是一个较大的常数，时间复杂度也只是O(n0)=O(1)。(3)一般可只考虑与程序规模有关的频度最大的语句，如循环语句的循环体，多重循环的内循环等。第32页，课件共38页，创作于2023年2月tmp=a;

a=b;

b=tmp;sum=0;

for(i=1;i<=n;i++)

sum+=i;sum=0;

for(i=1;i<=n;i*=2)

sum+=i;sum=0;

for(i=0;i<n;i++)

for(j=0;j<=i;j++)

A[i][j]=0;O(1)O(n)O(log2n)O(n2)sum=0;

for(i=1;i*i<=n;i++)

sum+=i;O(n1/2)sum=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

A[i][j]=0;O(n2)第33页，课件共38页，创作于2023年2月例例行列式计算设CPU

GHz，每时钟计算1次行列式计算，设直接展开，有n!项，每项n个因子，乘法次数为：n!*(n-1)。体验O(n!)。100n＝25阶，所需要时间：T＝25！100×1091365×24×3600＝4.92×106（年）≈500万年！×n＝20阶，所需时间：T=0.77年n＝15阶，所需时间：T=13秒n＝10阶，所需时间：T=3.63×10-5秒增长太快，n稍大不可行实际行列式都是先化简再计算，并不直接展开。第34页，课件共38