计算机程序设计竞赛-第1讲.ppt

,计算机程序设计竞赛,信科系专职教师：赵小蕾邮箱：,中山大学新华学院,课程介绍及要求,课程类别：全校公选课总学时数：36（实操课）开课目的：为信息科学系竞赛项目：第六届“蓝桥杯软件人才与设计大赛”培养人才。主要培养学生解决实际问题的编程能力、培养学生的创新思维。程序是自己设计出来的，而不是某个固定的方程式。,主要内容,1.1 什么是算法,一个程序应包括两个方面的内容:,对数据的描述：数据结构(data structure)对操作的描述：算法(algorithm),数据结构+算法=程序,数据结构算法程序设计方法语言工具,算法是解决“做什么”和“怎么做”的问题。即是为解决一个问题而采取的方法和步骤。,1.2 简单算法举例,步骤1：先求12，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120,1.2 简单算法举例,何为算法“烧水泡茶”有如下五道工序：1、烧开水2、洗茶壶3、茶杯4、拿茶叶5、泡茶。烧开水、洗茶壶、茶杯，拿茶叶是泡茶的前提。其中烧开水需要15分钟，洗茶壶需要2分钟，洗茶杯需要1分钟，拿茶叶需要1分钟，泡茶需要1分钟。下面是两种“烧水泡茶”的方法。方法1：第一步：烧水；第二步：水烧开后，洗刷茶具，拿茶叶；第三步：沏茶。方法2：第一步：烧水；第二步：烧水过程中，洗刷茶具，拿茶叶；第三步：水烧开后沏茶。,1.3 算法的特性,有穷性,一个算法应包含有限的操作步骤，而不能是无限的。,确定性,算法中的每一个步骤都应当是确定的，不能含糊。,输入,有零个或多个输入，从外界获取必要信息。,输出,有一个或者多个输出，得到问题的解。,有效性,每一个步骤有效执行，得到确定的结果。,1.4 算法的表示,算法的表示自然语言传统流程图N-S流程图伪代码计算机语言,1.4 算法的表示,传统流程图（流程图）美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：,1.4 算法的表示,1t,i5,开始,2i,t*it,i+1i,结束,N,Y,1t,i5,开始,2i,t*(2*i-1)t,i+1i,结束,N,Y,图1,图2,1.4 算法的表示,流程图的连接点举例,位置不够,防止交叉,1.4 算法的表示,流程图表示三种基本结构顺序结构,A,B,1.4 算法的表示,流程图表示三种基本结构选择结构,A,B,Y,N,A,Y,N,1.4 算法的表示,流程图表示三种基本结构循环结构,A,Y,N,A,Y,N,当型循环结构,直到型循环结构,1.4 算法的表示,N-S流程图（N-S图）由I.Nassi和Shneiderman提出的新的流程图形式，称为N-S流程图。其三种基本结构的N-S图表示：,顺序结构,选择结构,循环结构（当型）,循环结构（直到型）,1.4 算法的表示,例2 求12345：即求5!的N-S图算法表示：,直到i5,1t,输出t,2i,t*it,i+1i,1t,i5,开始,2i,t*it,i+1i,结束,N,Y,输出t,N-S图,VS,1.4 算法的表示,例3 输入50名学生的学号和成绩，并将50名学生中成绩高于80分者的学号和成绩输出。算法用N-S图表示，如右图。练习：使用流程图表示算法。,直到i50,1i,1i,i+1i,输入ni、gi,i+1i,直到i50,gi80,否,是,输出ni,gi,1.4 算法的表示,1i,i50,开始,i+1i,结束,N,Y,输入ni、gi,1i,gi80,输出ni、gi,i+1i,i50,N,Y,Y,N,例3 流程图如下：,1.4 算法的表示,例4 判定2000-2500年中的每一年是否闰年，并将结果输出。闰年的条件：能被4整除，但不能被100整除的年份 都是闰年，如2008、2012、2048年。能被400整除的年份是闰年，如2000年。,year不能被4整除,非闰年,year被4整除，但不能被100整除,闰年,year被100整除，又能被400整除,闰年,其他,非闰年,逐渐缩小判断的范围,1.4 算法的表示,例4 判定2000-2500年中的每一年是否闰年，并将结果输出。,N,Y,N,Y,Y,N,Y,N,1.4 算法的表示,例4 判定2000-2500年中的每一年是否闰年，并将结果输出。,直到year2500,2000year,year+1year,否,是,year%4为0,否,是,输出year非闰年,year%100不为0,year%400为0,是,否,输出year非闰年,输出year闰年,输出year闰年,1.4 算法的表示,用伪代码表示算法概念：伪代码是用介于自然语言和计算机语言之间的文字和符号，用来描述算法。特点：如一篇文章，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。,23,1.4 算法的表示,例5：“打印x的绝对值”，用伪代码表示算法。,用英文伪代码表示：IF x is positive THEN print x ELSE print-x也可以用汉字伪代码表示：若 x为正 打印 x 否则 打印-x也可以中英文混用，如：IF x 为正 print x ELSE print-x,1.4 算法的表示,用计算机语言表示算法概念：用计算机语言描述算法，就是用计算机语言编写程序。计算机是无法识别流程图和伪代码的。只有用计算机语言编写的程序才能被计算机执行。特点：设计算法的目的是为了实现算法。用计算机语言表示算法，必须严格遵循所用的语言的语法规则。,1.4 算法的表示,例6：求5!用C语言表示。N-S图为：,#include int main()int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(%dn,t);return 0;,当i=5,1t,输出t,2i,t*it,i+1i,1.4 算法的表示,算法广义地说，为解决一个问题而采取的方法和步骤，称为“算法”。对同一个问题，可以有不同的算法。计算机算法可分为两大类别：数值运算算法，目的是求数值解。非数值运算算法，包括的面十分广泛，最常见的是用于事务管理领域。注意：,写出了C程序，仍然只是描述了算法，并未实现算法。只有运行程序才是实现算法。,1.5 算法复杂度的分析,算法的复杂性越高，所需的计算机资源越多。最重要的计算机资源是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效率。,1.5 算法复杂度的分析,一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。,1.5 算法复杂度的分析,算法的执行频数的数量级直接决定算法的时间复杂度。,1.5 算法复杂度的分析,2个语句各执行1次，共执行2次。时间复杂度为O(1),(1)x=x+1;s=s+x;,(2)for(k=1;k=n;k+)x=x+y;y=x+y;s=x+y;,“k=1”执行1次；“k=n”与“k+”各执行n次；3个赋值语句，每个赋值语句各执行n次；共执行5n+1次.时间复杂度为O(n).,1.5 算法复杂度的分析,例1-3 试计算下面三个程序段的执行频数,(3)for(t=1,k=1;k=n;k+)t=t*2;for(j=1;j=t;j+)s=s+j;,“t=1”与“k=1”各执行1次；“k=n”与“k+”各执行n次；“t=t*2”执行n次；“j=1”执行n次；“j=t”、“j+”与内循环的赋值语句“s=s+j”各执行频数为:总的执行频数为：,1.5 算法复杂度的分析,在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算各循环设计语句及其它语句的执行次数，这样简化处理不影响算法的时间复杂度。,例1-4 估算以下程序段所代表算法的时间复杂度。for(k=1;k=n;k+)for(j=1;j=k;j+)x=k+j;s=s+x;,每个赋值语句执行频率为n(n+1)/2,该算法的时间复杂度为:O(n2),1.5 算法复杂度的分析,一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与静态变量等所占的空间。可变空间需求包括局部作用域非静态变量所占用的空间、从堆空间中动态分配的空间与调用函数所需的系统栈空间等。,算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。,1.6 学好算法的秘诀,（1）学的要深入，基础要扎实 基础的作用不必多说，在大学课堂上曾经讲过了很多次，在此重点说明“深入”。职场不是学校，企业要求你能高效的完成项目功能，但是现实中的项目种类繁多，我们需要从根上掌握C语言算法技术的精髓。走马观花式的学习已经被社会所淘汰，入门水平不会被开发公司所接受，他们需要的是高手。（2）恒心、演练、举一反三 学习编程的过程是枯燥的过程，我们需要将学习算法当成是自己的乐趣，只有做到持之以恒才能有机会学好。另外编程最注重实践，最害怕闭门造车。每一个语法，每一个知识点，都要反复用实例来演练，这样才能加深对知识的理解。并且要做到举一反三，只有这样才能对知识的深入理解。（3）语言之争的时代更要学会坚持,2.经典算法,九大大算法思想枚举算法思想递推算法思想递归算法思想分治算法思想贪心算法思想试探法算法思想迭代算法思想动态规划算法思想模拟算法思想,2.1 经典算法枚举法,比较笨的枚举算法思想 枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。枚举算法一般按照如下三个步骤进行。（1）题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。（2）判断是否是真正解的方法。（3）使可能解的范围降至最小，以便提高解决问题的效率。,2.1 经典算法枚举法,使用枚举算法解题的基本思路如下所示。（1）确定枚举对象、枚举范围和判定条件；（2）逐一枚举可能的解，验证每个解是否是问题的解。,2.1 经典算法枚举法,2.枚举的框架描述,n=0;for(k=;k;k+)/控制枚举范围 if()/根据约束条件实施筛选 printf();/输出解 n+;/统计解的个数,2.1 经典算法枚举法,举例：完美综合式 案例提出：把数字1,2,.,9这9个数字分别填入以下含加、减、乘、除与乘方()的综合运算式中的9个中+-=0 要求数字1,2,.,9这9个数字在式中出现一次且只出现一次，且约定数字“1”不出现在乘、乘方的一位数中。,2.1 经典算法枚举法,设置整数变量，其中ab用a自乘b次实现。即要求的综合运算式为:ab+z/c-d*e=0 设置a,b,c,d,e循环，对每一组a,b,c,d,e，计算z=(d*e-ab)*c，省略z循环。检测z是否为二位数。若z非二位数，则返回。对6个整数进行数字分离，设置f数组对分离的9个数字进行统计，f(x)即为数字x(19)的个数。若某f(x)不为1，标记t=1，则返回。若所有f(x)全为1，保持标记t=0,则输出。,1.枚举设计要点,2.1 经典算法枚举法,for(a=2;a98)continue;m1=a;m2=b;m3=c;m4=d;m5=e;m6=z;,2.1 经典算法枚举法,for(x=0;x0)x=y%10;fx=fx+1;y=y/10;for(t=0,x=1;x=9;x+)if(fx!=1)t=1;break;if(t=0)则输出一个解；,2.2 经典算法递推算法,聪明一点的递推算法思想递推算法犹如稳重的有经验的老将，使用“稳扎稳打”的策略，不断利用已有的信息推导出新的东西。在日常应用中有如下两种递推算法。（1）顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。（2）逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。,递推数列,案例提出：已知递推数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)（i为正整数）试求该数列的第n项与前n项中哪些项最大?最大值为多少?。,2.2 经典算法递推算法,1.递推设计要点,（1）设置a数组,赋初值a(1)=1。（2）根据递推式,在i循环中据项序号i(2n)为奇或偶作不同递推:若 mod(i,2)=0,a(i)=a(i/2)+1 若 mod(i,2)=1，a(i)=a(i+1)/2)+a(i-1)/2)（3）每得一项a(i),与最大值max作比较：如果 a(i)max,则 max=a(i)。（4）在得到最大值max后，最后在所有n项中搜索哪些项为最大项(因最大项可能多于一项),并输出最大值max及所有搜索得到的最大项。,2.2 经典算法递推算法,2.递推设计描述,scanf(%d,猴子爬山,案例提出：一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。,2.2 经典算法递推算法,设爬k级台阶的不同爬法为f(k)种。（1）探求f(k)的递推关系。上山最后一步到达第30级台阶，共有f(30)种不同的爬法；到第30级之前位于哪一级呢？无非是位于第29级（上跳1级即到），有f(29)种；或位于第27级（上跳3级即到），有f(27)种；于是有 f(30)=f(29)+f(27)一般地有递推关系：f(k)=f(k-1)+f(k-3)（k3）（2）确定初始条件f(1)=1；即1=1f(2)=1；即2=1+1f(3)=2；即3=1+1+1；3=3,1.递推设计要点,2.2 经典算法递推算法,2.递推设计描述,printf(请输入台阶总数n:);scanf(%d,2.2 经典算法递推算法,2.3 经典算法递归算法,充分利用自己的递归算法思想 在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。（1）递归过程一般通过函数或子过程来实现。（2）递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。（3）递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。,2.3 经典算法递归算法,在使用递归算法时，读者应该注意如下4点。（1）递归是在过程或函数中调用自身的过程。（2）在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。（3）递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。（4）在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。,排队购票,案例提出：一场球赛开始前，售票工作正在紧张进行中。每张球票为50元，有m+n个人排队等待购票，其中有m 个人手持50元的钞票，另外n个人手持100元的钞票。求出这m+n个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数。（约定：开始售票时售票处没有零钱，拿同样面值钞票的人对换位置为同一种排队。）,2.3 经典算法递归算法,1.递归设计要点,令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的排除总数。分以下3种情况来讨论。(1)n=0 n=0意味着排队购票的所有人手中拿的都是50元的钱币，注意到拿同样面值钞票的人对换位置为同一种排队，那么这m个人的排队总数为1，即f(m,0)=1。(2）mn 当mn时，即购票的人中持50元的人数小于持100元的钞票，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，这时排队总数为0，即f(m,n)=0。,2.3 经典算法递归算法,(3）其它情况 1）第m+n个人手持100元的钞票，则在他之前的m+n-1个人中有m个人手持50元的钞票，有n-1个人手持100元的钞票，此种情况共有f(m,n-1)。2）第m+n个人手持50元的钞票，则在他之前的m+n-1个人中有m-1个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)。由加法原理得到f(m,n)的递归关系：f(m,n)=f(m,n-1)+f(m-1,n)初始条件：当mn时，f(m,n)=0 当n=0时，f(m,n)=1,2.3 经典算法递归算法,2.购票排队的递归描述,long f(int j,int i)long y;if(i=0)y=1;else if(ji)y=0;/确定初始条件 else y=f(j-1,i)+f(j,i-1);/实施递归 return(y);,2.3 经典算法递归算法,2.4 经典算法分治算法,各个击破的分治算法思想 在编程过程中，我们经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，我们可以采用“各个击破”的方法。具体做法是先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。,2.4 经典算法分治算法,各个击破的分治算法思想 使用分治算法解题的一般步骤如下所示。（1）分解，将要解决的问题划分成若干个规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。,2.5 经典算法贪心算法,贪心算法思想并不贪婪 贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3个问题：（1）不能保证最后的解是最优的；（2）不能用来求最大或最小解问题；（3）只能求满足某些约束条件的可行解的范围。,2.5 经典算法贪心算法,贪心算法的基本思路如下所示。（1）建立数学模型来描述问题；（2）把求解的问题分成若干个子问题；（3）对每一子问题求解，得到子问题的局部最优解；（4）把子问题的解局部最优解合成原来解问题的一个解。实现该算法的基本过程如下所示。（1）从问题的某一初始解出发；（2）while能向给定总目标前进一步；（3）求出可行解的一个解元素；（4）由所有解元素组合成问题的一个可行解。,案例：可拆背包问题,2.3 经典算法递归算法,2.3 经典算法递归算法,/已对n件物品按单位重量的效益降序排序cw=c;s=0;/cw为背包还可装的重量 for(i=1;icw)break;xi=1.0;/若w(i)cw,装入一部分)s=s+pi*xi;,3.贪心算法描述,2.3 经典算法递归算法,2.6 经典算法试探法,试探法算法思想是一种委婉的做法使用试探算法解题的基本步骤如下所示。（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,试探法为了求得问题的正确解，会先委婉的试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉的退回一步重新选择，然后继续向前试探，如此厥驴般的反复进行，直至得到解或证明无解时才死心。,2.7 经典算法迭代法,迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点。在使用迭代算法解决问题时，需要做好如下三个方面的工作。（1）确定迭代变量在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。（2）建立迭代关系式迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。（3）对迭代过程进行控制,2.7 经典算法迭代法,在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：所需的迭代次数是个确定的值，可以计算出来。可以构建一个固定次数的循环来实现对迭代过程的控制；所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。,2.8 经典算法动态规划算法,动态规划的概念(1)动态规划（Dynamic programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。(2)动态规划处理的对象是多阶段决策问题。(3)多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。,2.8 经典算法动态规划算法,动态规划的步骤：（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。（2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。（3）应用递推求解最优值。递推计算最优值是动态规划算法的实施过程。（4）根据计算最优值时所得到的信息，构造最优解。构造最优解就是具体求出最优决策序列。,2.9 经典算法模拟算法,模拟算法思想模拟算法是一种最基本的算法思想，是对程序员基本编程能力的一种考查，其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟。在解决模拟类问题时，需要注意字符串处理、特殊情况处理和对题目意思的理解。我们知道在C语言中，通常使用函数srand()和rand()来生成随机数。其中函数srand()用于初始化随机数发生器，然后使用函数rand()来生成随机数。如果要使用上述两个函数，则需要在源程序头部包含time.h文件。在程序设计过程中，可使用随机函数来模拟自然界中发生的不可预测情况。在解题时，需要仔细分析题目给出的规则，要尽可能地做到全面地考虑所有可能出现的情况，这是解模拟类问题的关键点之一。,2.10 算法的综合举例,案例提出给定由n个整数（可能有负整数）组成的序列a(1),a(2),a(n)（约定：n个整数中至少存在一个正整数）,求该序列的子段和的最大值，并确定最大子段的位置。分别应用枚举、递归与动态规划三种算法求解。,1.枚举求解,（1）枚举设计要点 设序列子段的首项为i(1n)，尾项为j(in)，该子段和为s。设置i,j二重循环枚举，可确保所有子段既不重复也不遗漏。每一子段和s与最大变量值smax比较，可得最大子段和，同时应用变量i1,j1分别记录最大子段的首尾标号。最后输出最大子段和smax，同时输出最大子段的位置i1,j1。,input a1:n smax=0;for(i=1;ismax)smax=s;i1=i;j1=j;print(i1:j1,smax),（2）枚举设计描述,2.递归求解,3.动态规划求解,/输入序列中n个正负数 b0=0;smax=0;for(j=1;jsmax)/比较得bj的最大值 smax=bj;k=j;/记录最大和子段尾标j printf(n 最大子段和为：%ldn,smax);,（2）动态规划设计描述,4.三种求解算法的时间复杂度,3 简单的数据结构知识,学习编程的注意事项（1）在学习知识之前要有足够的理解，也就是说盖房打地基之前要先有一个大概的了解、规划。（2）做什么事情都有捷径可寻，但是有时候，在学习编程的过程中走捷径并不是一件很好的事情,3.1 线性表,线性表的特性线性表是一个线性结构，它是一个含有n0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且仅有一个前驱和一个后继节点。线性结构的特征在编程领域中，线性结构具有如下两个基本特征。（1）集合中必存在唯一的一个“第一元素”和唯一的一个“最后元素”；（2）除最后一个元素之外，均有唯一的后继(后件)和唯一的前驱(前件)；由n(n0)个数据元素(节点)a1，a2，an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表，我们通常将非空的线性表(n0)记作：(a1，a2，an)数据元素ai(1in)没有特殊含义，大家不必去“剖根问底”的研究它，它只是一个抽象的符号，其具体含义在不同的情况下可以不同。,3.1 线性表,线性表的基本操作过程线性表虽然只是一对一的单挑，但是其操作功能非常强大，具备了很多操作技能。线性表的结构特点均匀性：虽然不同数据表的数据元素是各种各样的，但同一线性表的各数据元素必须有相同的类型和长度；有序性：各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，即存在唯一的“第一个”和“最后一个”的数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前趋，后面只有一个直接后继。,3 简单的数据结构知识,在现实应用中，有两种实现线性表数据元素存储功能的方法，分别是顺序存储结构和链式存储结构。顺序表操作是最简单的操作线性表的方法，此方式的主要操作功能如下所示。（1）计算顺序表的长度（2）清空操作（3）判断线性表是否为空（4）判断顺序表是否为满（5）附加操作（6）插入操作（7）删除操作（8）获取表元（9）按值进行查找,3 简单的数据结构知识,链表操作链比顺序表要复杂一点，对于同一个数据，它可以和不相邻的数据发生关系。例如农民通常将收获的水果卖给商贩，商贩将收购的水果卖给加工厂。这是一条水果加工产业链，可以得出商贩是农民的财神、加工厂是商贩的财神这一论调。在那一年的某一天，老实的农民发现利润较低，于是拉着自己的水果不远万里的亲自卖给了加工厂。这样农民伯伯获得了更大的利润，而商贩也不能怎么着，这个产业链还得继续下去。由此可见，链式存储结构不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系。所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无需移动元素就而提高了运行效率。链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。,3 简单的数据结构知识,3.3 守规矩的先进先出的队列3.3.1 队列基础队列和栈一样，只允许在断点处插入和删除元素，循环队的入队算法如下所示。（1）tail=tail+1；（2）如果tail=n+1，则tail=1；（3）如果head=tai，即尾指针与头指针重合，则表示元素已装满队列，会施行上溢出错处理；否则Q(tail)=X，结束整个过程，其中X表示新入出元素。3.3.2 链队列和循环队列使用C语言定义链队列的格式如下所示。typedef struct QNodeElemTypedata;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;/*队头指针，指向头元素*/QueuePtr rear;/*队尾指针，指向队尾元素*/LinkQueue;,3 简单的数据结构知识,3.3.3 队列的基本操作（1）初始化队列Q的目的是创建一个队列（2）入队的目的是将一个新元素添加到队尾，相当于到队列最后排队等候。（3）出队的目的是取出队头的元素，并同时删除该元素，使后一个元素成为队头。（4）获取队列第1个元素，即将队头的元素取出，不删除该元素，队头仍然是该元素。（5）判断队列Q是否为空3.3.4 队列的链式存储当使用链式存储结构表示队列时，需要设置队头指针和队尾指针，这样做的好处是可以设置队头指的针和队尾的指针。在入队时需要执行如下三条语句。s-next=NULL;rear-next=s;rear=s;在C语言中，实现队列链式存储结构类型的代码如下所示。type struct linklist/链式队列的节点结构Elemtype Entry;/队列的数据元素类型struct linklist*next;/指向后继节点的指针LINKLIST;typedef struct queue/链式队列LINKLIST*front;/队头指针LINKLIST*rear;/队尾指针QUEUE;,3 简单的数据结构知识,3.4 后进先出的栈3.4.1 什么是栈栈允许在同一端进行插入和删除操作，允许进行插入和删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。栈底是固定的，而栈顶浮动的；如果栈中元素个数为零则被称为空栈。插入操作一般被称为进栈（PUSH），删除操作一般被称为退栈（POP）。在栈中有两种基本操作，分别是入栈和出栈。（1）入栈（Push）将数据保存到栈顶。在进行入栈操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。入栈（Push）操作的算法如下：如果TOP，则给出溢出信息，作出错处理。在进栈前首先检查栈是否已满，如果满则溢出；不满则进入下一步骤；设置TOP=TOP+1，使栈指针加，指向进栈地址；S(TOP)=X，结束操作，X为新进栈的元素。（2）出栈（Pop）将栈顶的数据弹出，然后修改栈顶指针，使其指向栈中的下一个元素。出栈（Pop）操作的算法如下：如果TOP0，则输出下溢信息，并实现出错处理。在退栈之前先检查是否已为空栈，如果是空则下溢信息，如果不空则进入下一步骤；X=S(TOP)，退栈后的元素赋给X；TOP=TOP-1，结束操作，栈指针减，指向栈顶。,3 简单的数据结构知识,3.4.2 栈的基本操作1.顺序栈顺序栈是栈的顺序存储结构的简称，它是一个运算受限的顺序表。假设S是SeqStack类型的指针变量，如果栈底位置在向量的低端，则S-data0是栈底元素。2.链栈链栈是指栈的链式存储结构，是没有附加头节点的、运算受限的单链表，栈顶指针是链表的头指针。,3 简单的数据结构知识,复杂的数据结构：树和图在竞赛中也常运用。请大家自觉积累，学习。,