数据结构与算法(二级培训)

数据结构与算法第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法与算法分析1.1什么是数据结构一、计算机解决问题的一般过程。1、建立数学模型。2、根据数学模型，设计算法。3、编写程序，调试直至问题的最终解决。二、数值问题与非数值问题。数值问题就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积。非数值问题就是问题中涉及的对象不能用数来表达的那些问题。1）数值问题例1已知：游泳池的长length和宽wide，求面积area。分析：问题涉及的对象：游泳池的长length宽wide，面积area；对象之间的关系：area=lengthwide；main(){intlen,wide,area;scanf(“%d%d%\n”,&l,&w);area=len*wide;printf(“area=%d”,area);}2）非数值问题例2已知研究生选课情况，安排课程考试的日程。研究生选课情况表姓名选修课1选修课1选修课1张ABE王CEF李DFA赵BF分析：◆问题涉及的对象：课程；◆课程之间的关系：同一个研究生选修的不能按排在同一时间内考试；课程及课程之间的关系可用如下所示的图表示：DEFCBA顶点：表示课程；边：同一研究生选修的课程用边连接课程考试安排问题转化为图的着色问题用尽可能少的颜色为该图的每个顶点着色，使相邻的顶点着上不同的颜色；每一种颜色代表一个考试时间，着上相同颜色的顶点是可以按排在同一时间考试的课程；DEFCBAACEFBD课程着色的过程红色：a，c；黄色：b，d；绿色：e；蓝色：f即a,c可安排在同一时间考试，b,d可安排在同一时间考试;设G表示课程关系图，集合V包含图G中所有尚未着色的顶点，NEW表示可以用新颜色着色的顶点集合。I=1；WHILEV非空DO置NEW为空集合；FOR每个vVDOIFv与NEW中所有的结点间都没有边从V中去掉v；将v加入NEW；（第I天考试课程为NEW中顶点所对应的课程）以某种形式输出NEW中顶点所对应的课程；I=I+1；通过对上个问题的分析，在这个问题的分析解决的过程中我们遇到了以下几个问题：1、如何表示节点以及它们之间的关系（相邻接）2、在计算机中如何存储。3、相应的操作如何描述。（染色过程）3）数值问题与非数值问题的比较数值问题已知游泳池的长length,和宽wide,求面积area。（1）问题涉及的对象：length,wide,area是实数可用数值表示；（2）对象之间的关系：area=lengthwide可用方程或函数表示；（3）数据存储：可用程序设计语言中的实型变量存储；（4）问题求解：用某种计算方法求解；已知研究生选课情况，安排课程考试的日程。1）问题涉及的对象：课程可用课程名表示,不能用数值表示2）对象之间的关系：同一研究生选修的课程不能安排在同一时间考试，同一研究生选修的课程之间有某种“冲突”关系——课程之间的这种关系不能用方程或函数表示3）数据及数据之间的关系如何存储？4）如何求解？非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间关系和操作等的学科。1.2基本概念和术语1、数据：一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。2．数据元素数据元素（也叫节点），它是组成数据的基本单位。在程序中通常作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。表1-1个人书库3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象的集合N={0，±1，±2，……}，字母数据对象的集合C={‘A’,’B’,……’Z’}。4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。根据数据结构之间关系，通常有下列4类基本结构。集合线性结构树型结构图状结构数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集合。5、数据的逻辑结构：数据元素之间的逻辑关系。数据的存储结构：数据结构在计算机中的表示。本课程中介绍的存储结构有：顺序存储结构链式存储结构索引结构散列结构6、数据类型：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。7、抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型可以用下面的三元组来表示（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。本书采用以下格式定义抽象数据类型：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据名。1.4算法和算法分析算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；它有5个重要特征。有穷性：确定性：相同的输入得到相同的输出。可行性：输入：输出：算法设计的要求：正确性：正确的含义，有四个层次。可读性：健壮性：效率和低存储量的要求：一个用高级语言编写的程序在计算机上运行所需要的时间取决于下列因素：⑴依据算法所选用的策略。⑵问题的规模。一般情况下，处理的数据量越大，执行的时间相对也越长。⑶书写程序的语言。语言的级别越高，其执行效率就越低。⑷编译程序所生成目标代码的质量。⑸机器指令执行的速度（硬件的速度）。与硬件的配置高低有关。通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执行的次数作为算法的时间度量。为此，一个特定算法的运行时间长短就只依赖于问题的规模n，或者说它是问题规模n的函数f(n)。【例】求累加求和intsum(intb[]，intn）｛intsum=0;/*第1条定义并赋初值语句执行1次*/for（inti=0；in；i++）sum+=b[i];/*n次*/returnsum;/*返回语句执行1次*/｝要精确地计算f(n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作T(n)=Ο(f(n))它表示随问题的规模n的增大，算法执行时间的增长率和f(n)相同。使用大Ο记号，Ο(f(n))称为算法的渐进时间复杂度，简称时间复杂度。例如，一个程序的实际执行时间为2.7n3+3.8n2+5.3。则T(n)＝Ο(n3)。例、求下面程序段的时间复杂度。s=0;for(j=1;j=n;j++)for(x=1,k=1;k=n;k++){x=x*k;s+=x;}{++x;a=0;}T(n)=O(1);//常量阶for(i=1;i=n;++i){++x;s+=x;}T(n)=O(n);//线性阶for(j=1;j=n;++j)for(k=1;k=n;++k){++x;s+=x;}T(n)=O(n2)//平方阶通常将称Ο(1)为常数阶，Ο(n)为线性阶，O(n2)为平方阶。算法还可能呈现的复杂度有：对数阶Ο(log2n)，指数阶Ο(2n)等，不同数量级时间复杂度的关系有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)常见函数的增长率第2章线性表2.1线性表概念及基本操作2.2线性表的顺序存储和实现2.1线性表概念及基本操作例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电话号码簿。姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...说明：设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前趋，ai+1是ai的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号；2.2线性表的顺序表示和实现线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的。假没线性表中每个数据元素占用k个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai)=Loc(a1)+(i–1)k这里Loc(ai)是第i个元素的存储位置,Loc(a1)是第1个元素的存储位置，也称为线性表的基址；线性表的顺序存储的基本操作1）初始化操作InitList_Sq(SqList&L)2）销毁操作DetroyList_Sq(SqList&L){功能：回收为顺序表动态分配的存储空间3）置空操作ClearList_Sq(SqList&L)功能：若L已存在，重新将其置成空表5）插入操作ListInsert_Sq(&L,i,e)参数：L：顺序表，i插入位置，e被插入元素;因为插入操作对顺序表进行修改,所以用了引用参数&L;i的取值范围在1-ListLength_Sq(L)+1;功能：在顺序表L的第i个元素之前插入一个新元素e;6)删除操作ListDelete_sq(SqList&L,inti,ElemType&e)功能：删除顺序表L的第i个元素，并用e返回3.1栈3.1.1栈的概念3.1.2栈的顺序存储和实现第3章栈和队列3.1.1抽象数据类型栈的定义栈是限定仅能在表尾一端进行插入、删除操作的线性表说明：设（a1,a2,a3,…,an）是一个栈1）表尾称为栈顶，表头称为栈底，即a1为栈底元素，an为栈顶元素。2）在表尾插入元素的操作称进栈操作，在表头删除元素的操作称为出栈操作;（a1,a2,...,ai-1,ai,ai+1,…,an）栈底栈顶进栈出栈cbafed栈操作演示3）元素按a1,a2,a3,…,an的次序进栈,第一个进栈的元素一定在栈底，最后一个进栈的元素一定在栈顶,第一个出栈的元素为栈顶元素；4）栈的元素具有后进先出的特点,所以栈又称为后进先出表（LIFO表）5）由于进栈、出栈操作总是在栈顶一端进行，通常设置称为栈顶指针的变量指示栈顶的位置。栈的基本操作1）初始化操作InitStack(&S)操作结果：构造一个空栈S；2）销毁栈操作DestroyStack(&S)初始条件：栈S存在。操作结果：销毁一个已存在的栈;3）置空栈操作ClearStack(&S)初始条件：栈S存在。操作结果：将栈S置为空栈;4）判空操作StackEmpty(S)初始条件：栈S存在。操作结果：若栈S为空，则返回True，否则返回False;5）求栈长度操作StackLength(S）初始条件：栈S存在。操作结果：返回S元素的个数，即栈的长度。6）取栈顶元素操作GetTop(S,&e)初始条件：栈S存在，且非空。操作结果：取栈顶元素，并用e返回;7）进栈操作Push(&S,e)初始条件：栈S存在。操作结果：元素e进栈;8）退栈操作Pop(&S,&e)操作结果：栈顶元素退栈，并用e返回;9）栈的遍历操作StackTraverse（S，visit（））初始条件：栈S存在。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦visit()失败，则操作失败。3.1.2栈的顺序