文章目录数据结构一、数据结构介绍1.1 基本概念和术语1.2 数据结构1.3 抽象数据类型二、算法2.1 数据结构与算法的关系2.2 算法的定义及特性2.3 算法设计要求2.4 算法效率的度量方法2.5 函数的渐近增长2.6 算法时间复杂度2.7 常见的时间复杂度2.8 最坏情况和平均情况2.9 算法空间复杂度三、线性表3.1 线性表的定义3.2 线性表的抽象数据类型3.3 线性表的顺序存储结构3.4 线性表的链式存储结构数据结构一、数据结构介绍1.1 基本概念和术语数据定义数据是描述客观事物的符号是计算机中可以操作的对象是能被计算机识别并输入给计算机处理的符号集合。注数据其实就是符号其必须具备两个条件可以输入到计算机中。能被计算机处理。数据元素定义是组成数据的、有一定意义的基本单位在计算机中通常作为整体处理也被称为记录。例如禽类的数据元素就有牛、马、羊等等。数据项一个数据元素可以由若干项数据项组成。数据项是数据不可分割的最小单位。数据对象定义是性质相同的数据元素的集合是数据的子集1.2 数据结构定义是相互之间存在一种或多种特定关系的数据元素的集合。数据结构分为逻辑结构和物理结构。逻辑结构定义是指数据对象中数据元素之间的相互关系。集合结构集合结构中的数据元素除了同属于一个集合外它们之间没有其他关系。线性结构数据元素之间是一对一的关系。树形结构数据元素之间存在一种一对多的层次结构。图形结构数据元素是多对多的关系。注意在用示意图表示数据逻辑结构时需要将每个数据元素看作一个节点用圆圈表示元素之间的逻辑关系用结点之间的连线表示如果这个关系是有方向的那么用带箭头的连线表示。物理结构定义数据的逻辑结构在计算机中的储存形式。顺序储存结构定义是把数据元素存放在地址连续的储存单元里其数据间的逻辑关系和物理关系是一致的。链式储存结构定义是把数据元素存放在任意的储存单元里这组储存单元可以是连续的也可以是不连续的。所以链式储存更加灵活只需要一个指针存放了相应的地址就能够找到它。1.3 抽象数据类型数据类型定义是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。数据类型可分为两类原子类型不可再分解的基本类型例如整型、实型、字符型等。结构类型由若干个类型组合而成可以再分解例如整型数组等。抽象数据类型Abstract Data Type, ADT举个例子各个计算机不管是大型机、小型机、PC、平板电脑、PDA甚至智能手机都拥有“整数”类型也需要整数间的运算那么整型其实就是一个抽象数据类型尽管它在上面提到的这些在不同计算机中实现方法上可能不一样但由于其定义的数学特性相同在计算机编程者看来它们都是相同的。定义是指数学模型及定义在该模型上的一组操作。意义数据类型的抽象特性。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。下面是描述抽象数据类型的标准格式ADT抽象数据类型名 Data 数据元素之间逻辑关系的定义 Operation 操作1初始条件 操作结果描述 操作2......操作n......endADT二、算法2.1 数据结构与算法的关系数据结构 数据怎么存算法 数据怎么操作数据结构是载体算法是操作手段二者一体解决计算问题。通俗一点解释数据结构 箱子、货架、抽屉东西怎么放算法 拿东西、整理东西、找东西的方法想快速取货既要货架设计合理数据结构也要取货路线高效算法。2.2 算法的定义及特性定义算法是解决特定问题求解步骤的描述在计算机中表现为指令的有限序列并且每条指令表示一个或多个操作。特性输入算法具有零个或多个输入。输出算法至少有一个或多个输出。有穷性算法在执行有限的步骤后自动结束而不会出现无线循环并且每个步骤在可接收的时间内完成。确定性算法每一步骤都具有确定的含义不会出现二义性。可行性算法的每一步都必须是可行的也就是说每一步都能够通过执行有限次数完成。2.3 算法设计要求正确性算法至少应该具有输入输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。可读性算法设计的目的之一就是为了便于阅读、理解和交流。健壮性当输入数据不合法时算法也能做出相关处理而不是产生异常或莫名其妙的结果。时间效率高和储存量低2.4 算法效率的度量方法事后统计方法定义通过设计好的测试程序和数据利用计算机计时器对不同算法编制的程序的运行时间进行比较从而确定算法效率的高低。注由于此方法的实现需要消耗大量精力和时间并且十分依赖计算机和软件等环境因素此外还和测试数据的规模有很大关系。所以我们不用此方法。事前分析估算方法定义在计算机程序编制前依据统计方法对算法进行估算。程序运行时间主要受到下面四个因素影响1、算法采用的策略、方法。2、编译产生的代码质量。3、问题的输入规模。4、机器执行指令的速度。其中1是算法好坏的根本2是由软件来支持的4要看硬件性能。所以一个程序的运行时间依赖于算法的好坏和问题的输入规模。举个例子inti,sum0,n100;//执行1次for(i1;in;i)//执行n1次{sumsumi;//执行n次}printf(%d,sum);//执行1次intsum0;n100;//执行1次sum(1n)*n/2;//执行1次printf(%d,sum);//执行1次显然第一种算法执行了2n3次而第二种算法只执行了3次。算法好坏显而易见。所以在分析程序运行时间时最重要的是把程序看成独立于程序设计语言的算法或一系列步骤。在分析一个算法的运行时间时重要的是把基本操作的数量与输入规模关联起来即基本操作的数量必须表示成输入规模的函数如下图所示2.5 函数的渐近增长定义给定两个函数f(n)和g(n)如果存在一个正数N使得对于所有的nNf(n)总是比g(n)大那么我们说f(n)的增长渐近快于g(n)。来看这个例子次数算法 C4n8算法 C’n算法 D2n2算法 D’n2n112131n216294n3203199n104810201100n1004081002000110000n10004008100020000011000000不难发现常数项和与最高次项的系数并不重要。即判断一个算法的效率时函数中的常数和其他次要项常常可以忽略更应该关注主项最高阶项的阶数。2.6 算法时间复杂度定义在进行算法分析时语句总的执行次数T(n)是关于问题规模n的函数进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度也就是算法的时间量度记作T(n)O(f(n))。它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称作算法的渐近时间复杂度简称为时间复杂度。其中fn是问题规模n的某个函数。显然通过此定义可知三个求和算法的时间复杂度分别为O(n)O(1),O(n2)。我们给他们取了非官方的名称O(1)叫做常数阶O(n)叫线性阶O(n2)叫平方阶。推导大O阶方法用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不为1则去除与这个项相乘的常熟。这样得到的结果就是大O阶。常数阶以下面求和代码为例这种与问题的大小无关n的多少执行时间恒定的算法我们就称之为具有O(1)的时间复杂度又叫常数阶。intsum0,n100;//执行1次sum(1n)*n/2;//执行2次printf(%d, sum);//执行3次intsum0,n100;/* 执行1次 */sum(1n)*n/2;/* 执行第1次 */sum(1n)*n/2;/* 执行第2次 */sum(1n)*n/2;/* 执行第3次 */sum(1n)*n/2;/* 执行第4次 */sum(1n)*n/2;/* 执行第5次 */sum(1n)*n/2;/* 执行第6次 */sum(1n)*n/2;/* 执行第7次 */sum(1n)*n/2;/* 执行第8次 */sum(1n)*n/2;/* 执行第9次 */sum(1n)*n/2;/* 执行第10次 */printf(%d,sum);/* 执行1次 */线性阶其运行次数如线性函数例如nxm,x为次数一样我们便称其时间复杂度为线性阶即O(n)。对数阶其运行次数如对数函数例如log2x,x为次数一样我们便称其时间复杂度为线性阶即O(logn)。平方阶inti,j;for(i0;in;i){for(j0;jn;j){//时间复杂度为O(1)的程序步骤序列}}就像上面的例子一样像这样要执行**n2**次就称为平方阶即时间复杂度就为O(n2)。还有一些此处就不一一列举了可以继续向下学习。2.7 常见的时间复杂度执行次数函数阶非正式术语12O(1)常数阶2n3O(n)线性阶3n²2n1O(n²)平方阶5log₂n20O(logn)对数阶2n3nlog₂n19O(nlogn)nlogn 阶6n³2n²3n4O(n³)立方阶2ⁿO(2ⁿ)指数阶按照所耗费的时间从小到大依次是O(1) O(logn) O(n) O(nlogn) O(n²) O(n³) O(2ⁿ) O(n!) O(nⁿ)注意像O(n3)过大的n都会使得结果变得不现实。同样指数阶O(2)和阶乘阶O(n!)等除非是很小的n值否则哪怕n只是100都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度一般我们都不去讨论它。2.8 最坏情况和平均情况最坏情况最坏情况运行时间是一种保证那就是运行时间将不会再坏了。在应用中这是一种最重要的需求通常除非特别指定我们提到的运行时间都是最坏情况的运行时间。平均情况平均运行时间也就是从概率的角度看这个数字在每一个位置的可能性是相同的所以平均的查找时间为n/2次后发现这个目标元素。注平均运行时间是所有情况中最有意义的因为它是期望的运行时间。一般在没有特殊说明的情况下都是指最坏时间复杂度。2.9 算法空间复杂度算法的空间复杂度通过计算算法所需的存储空间实现算法空间复杂度的计算公式记作:S(n) O(f(n))其中n为问题的规模f(n)为语句关于n所占存储空间的函数。举个例子若算法执行时所需的辅助空间相对于输入数据量而言是个常数则称此算法为原地工作空间复杂度为O(1)。三、线性表3.1 线性表的定义零个或多个数据元素的有限序列。若将线性表记为a₁…aᵢ₋₁aᵢaᵢ₊₁…aₙ则表中 aᵢ₋₁ 领先于 aᵢaᵢ 领先于 aᵢ₊₁称 aᵢ₋₁ 是 aᵢ 的直接前驱元素aᵢ₊₁ 是 aᵢ 的直接后继元素。当 i12…n−1 时aᵢ 有且仅有一个直接后继当 i23…n 时aᵢ 有且仅有一个直接前驱。如图 3-2-1 所示。线性元素的个数n(n0)定义为线性表的长度当n0时称为空表。在较为复杂的线性表中一个数据元素可以由若干个数据项组成。例如学号姓名性别出生年月家庭地址1张三男1995.3东街西巷1号203室2李四女1994.8北路4弄5号6室3王五女1994.12南大道789号…………………………3.2 线性表的抽象数据类型定义ADT 线性表List Data 线性表的数据对象集合为{a₁,a₂,……,aₙ}每个元素的类型均为DataType。其中除第一个元素a₁外每一个元素有且只有一个直接前驱元素除了最后一个元素aₙ外每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。 Operation InitList(*L) 初始化操作建立一个空的线性表L。 ListEmpty(L) 若线性表为空返回true否则返回false。 ClearList(*L) 将线性表清空。 GetElem(L,i,*e) 将线性表L中的第i个位置元素值返回给e。 LocateElem(L,e) 在线性表L中查找与给定值e相等的元素如果查找成功返回该元素在表中序号表示成功否则返回0表示失败。 ListInsert(*L,i,e) 在线性表L中的第i个位置插入新元素e。 ListDelete(*L,i,*e) 删除线性表L中第i个位置元素并用e返回其值。 ListLength(L) 返回线性表L的元素个数。 endADT3.3 线性表的顺序存储结构定义线性表的顺序结构指的是用一段地址连续的存储单元依次存储线性表的数据。顺序存储方式一维数组线性表顺序存储的结构代码#define MAXSIZE 20 /*存储空间初始分配量*/ typedef int ElemType; /*ElemType 类型根据实际情况而定这里假设为 int*/ typedef struct { ElemType data[MAXSIZE]; /*数组存储数据元素最大值为 MAXSIZE*/ int length; /*线性表当前长度*/ }SqList;顺序存储结构的三个属性存储的起始位置数组data它的存储位置就是存储空间的存储位置。线性表的最大存储容量数组长度MaxSize。线性表的当前长度length。数据长度与线性表长度区别数组的长度是存放线性表的存储空间的长度存储分配后这个量一般是不变的。高级语言中动态数组除外线性表的长度是线性表中数据元素的个数随着线性表插入和删除操作的进行这个量是变化的。注意在任意时刻线性表的长度都应该小于等于数组的长度。地址计算方法地址的定义存储器中的每个存储单元都有自己的编号这个编号称为地址。LOC表示获得存储位置的函数。顺序存储结构的插入与删除获得元素操作#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintStatus;//Status 是函数的类型其值是函数结果状态代码如 OK 等//初始条件顺序线性表 L 已存在1≤i≤ListLengthL//操作结果用 e 返回 L 中第 i 个数据元素的值StatusGetElem(SqList L,inti,ElemType*e){if(L.length0||i1||iL.length)returnERROR;*eL.data[i-1];returnOK;}插入操作删除操作线性表顺序存储结构的优缺点3.4 线性表的链式存储结构与顺序存储结构的最大区别顺序存储结构需要一段连续的内存空间但链式存储结构则不需要。定义为了表示每个数据元素a i a_iai与其直接后继数据元素a i 1 a_{i1}ai1之间的逻辑关系对数据元素a i a_iai来说除了存储其本身的信息之外还需存储一个指示其直接后继的信息即直接后继的存储位置。我们把存储数据元素信息的域称为数据域把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素a i a_iai的存储映像称为结点Node。n nn个结点a i a_iai的存储映像链结成一个链表即为线性表a 1 a_1a1a 2 a_2a2… \dots…a n a_nan的链式存储结构因为此链表的每个结点中只包含一个指针域所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起如图所示头指针链表中第一个结点存储位置叫做头指针。当然线性链表的最后一个节点指针自然为“空”通常用NULL或^表示头节点为了方便对链表进行操作我们便在单链表的第一个节点前附设了一个节点这个节点就称为头节点。头节点的数据域可以不存储任何信息。头指针和头结点的异同头指针头节点头指针是指链表指向第一个结点的指针若链表有头节点则是指向头节点的指针头节点是为了操作的统一和方便而设立的放在第一元素的结点之前其数据域一般无意义也可存放链表的长度头指针具有表示作用所以常用头指针冠以链表的名字有了头节点对在第一元素的结点前插入结点和删除第一结点其操作与其他结点的操作就统一了无论链表是否为空头指针均不为空。头指针是链表的必要元素头结点不一定是链表的必须要素