章数据结构与算法

第1章数据结构与算法数据结构案例教程案例提出——高斯的巧妙解题1787年高斯巧妙解题：1787年，在德国一所乡村小学的三年级课堂里，数学老师为了惩罚吵闹的学生，出了一道计算题：1＋2＋3＋4＋5＋…＋98＋99＋100。。。请根据时间复杂度分析法比较高斯和他的小伙伴们的算法优劣。Page

2案例提出——高斯的巧妙解题时间穿越到了2014年，在德国一所乡村小学的三年级信息技术课堂里，计算机老师为了惩罚吵闹的学生，出了一道编程题：先用文本文件记录100个没有规律的数字，然后将文件分发给学生，要求学生利用计算机编程求出它们的和。请根据时间复杂度分析法比较高斯和他的小伙伴们的算法优劣。Page

31.2知识点学习——1.2.1数据结构

1.2.1.1数据结构相关概念数据是用符号对现实世界的事物及活动做出的抽象描述，其中符号可以是文字符号、数字符号以及其他规定的符号。数据元素是数据的基本单位。例如，201302班点名册中的每个学生记录都是一个数据元素。数据元素也可称为元素、结点、顶点、记录等，在计算机中通常被作为一个整体来进行考虑和处理。Page

41.2知识点学习——1.2.1数据结构

数据结构是指数据和数据之间的关系，可以看成是相互之间存在着某种特定关系的数据元素的集合。数据结构包括数据的逻辑结构、数据的物理结构和数据的运算3个方面。逻辑结构物理结构（存储结构）Page

5Page

6《数据结构案例教程》Page

7哥，我们这么好的组合，咋总打败仗呢？【例1.1】表1.1所示的学生表中的数据元素是学生记录，每个数据元素由4个数据项(即学号、姓名、性别和年龄)组成。试讨论其存储结构。Page

8学

号姓

名性

别年

龄3张飞男182刘备男2314关羽男195小乔女1826吕布男2112貂婵女17表1.1学生表数据元素数据数据数据项逻辑结构【例1.1】学生表中，每个学生记录采用一个StudType类型的结点存储，一个学生结点的next域指向逻辑结构中其后继学生对应的结点，从而构成一个链表，其存储结构如图1.1所示。Page

9图1.1学生的链表存储结构【例1.2】采用二元组表示例1.1中的学生表。学生表中共有6个结点，依次用s1～s6表示，则对应的二元组表示为B=(D,R)，其中：D={s1,s2,s3,s4,s5,s6}R={r}r={<s1,s2>,<s2,s3>,<s3,s4>,<s4,s5>,<s5,s6>}Page

10用图形可以形象地表示这种数据结构，如图1.2所示，图形中的每个结点对应着一个数据元素，两结点之间的连线对应着关系中的一个序偶。Page

11图1.2学生表数据结构图示1.2.1.2数据的逻辑结构

集合集合是指数据元素同属于一个集合，别无其他关系。线性结构树形结构图形结构Page

12本书的一级目录正是按照这种逻辑结构排列的，如图1.3所示。Page

13【例1.3】有一种数据结构B1=(D，R)，其中：D={1，5，8，12，20，26，34}R={r}r={<1，8>，<8，34>，<34，20>，<20，12>，<12，26>，<26，5>}画出其逻辑结构图示。Page

14对应的图形如图1.4所示。Page

15【例1.4】有一种数据结构B2=(D,R)，其中：D={a,b,c,d,e,f,g,h,f,j}R={r}r={<a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<c,g>,<d,h>,<d,i>,<d,j>}画出其逻辑结构图示。Page

16对应的图形如图1.5所示。Page

17【例1.5】有一种数据结构B3=(D,R)，其中：D={a,b,c,d,e}R={r}r={(a,b),(a,c),(b,c),(c,d),(c,e),(d,e)}画出其逻辑结构图示。Page

18解：对应的图形如图1.6所示。Page

19【例1.6】有一种数据结构B4=(D,R)，其中：D={48,25,64,57,82,36,75}R={r1,r2}r1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}画出其逻辑结构图示。Page

20

解：对应的图形如图1.7所示。它是一种图形结构，其中，r1(对应图中虚线部分)为线性结构，r2(对应图中实线部分)为树形结构。Page

211.2.1.3数据的存储结构1.顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，在算法的C/C++实现中，顺序存储结构是用数组来描述的。2.链式存储方法该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由结点中的指针域来表示的。在算法的C/C++实现中，链式结构要借助于指针类型来描述。3.索引存储方法该方法通常用来存储线性结构。索引表，像图书的目录一样。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。其中，关键字唯一标识一个结点，地址作为指向结点的指针。这种带有索引表的存储结构可以大大提高数据查找的速度。4.哈希(或散列)存储方法该方法的基本思想是根据结点的关键字，通过哈希函数(也称散列函数)计算出一个值作为该结点的存储地址。Page

221.2.1.4数据结构和数据类型1.数据类型在C/C++程序中出现的每个变量、常量或表达式，都需要明确声明它们所属的数据类型。不同类型的变量，其所能取的值的范围不同，所能进行的操作也不同。例如在C语言中，用int声明的变量，在内存中占2个字节，能进行加、减、乘、除、求余等运算；用char声明的变量，在内存中占1个字节，存储的是一个字符，一般不用来做算术运算。Page

23C／C++语言中常用的数据类型下面回顾C／C++语言中常用的数据类型。(1)C/C++语言中的基本数据类型(2)C/C++语言中的指针类型(3)C/C++语言中的数组类型(4)C/C++语言中的结构体类型(5)C/C++语言中的自定义类型(6)引用运算符Page

241.2.2算法

1.2.2.1什么是算法

算法是对特定问题求解步骤的一种描述。简单地说，一个算法就是一个解题方法和步骤，是指令的有限序列，其中每一条指令表示计算机的一个或多个操作。一个算法具有以下5个重要的特性：有穷性确定性可行性有输入有输出Page

251.2.2.2算法描述本书采用C/C++语言来描述，它的优点是类型丰富、语句精炼，编写的程序结构化程度高、可读性强。下面是常用的用于描述算法的C/C++语言基本语句：(1)输入语句scanf(<格式控制字符串>，<输入项表>);(2)输出语句printf(<格式控制字符串>，<输出项表>);(3)赋值语句变量名=表达式;(4)条件语句if<条件><语句>;或者if<条件><语句1>else<语句2>;Page

26(5)循环语句①while<表达式>{}

②do{}while<表达式>;

③for(<赋初值表达式1>;<条件表达式2>;<步长表达式3>)(6)返回语句return(<返回表达式>);(7)定义函数语句

(8)调用函数语句Page

271.2.2.3算法分析算法效率分析在一个算法中，进行基本运算的次数越少，其运行时间也就相对越少；基本运算次数越多，其运行时间也就相对越多。所以，通常把算法中包含基本运算次数的多少称为算法的时间复杂度，也就是说，一个算法的时间复杂度是指该算法的基本运算次数。算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))其中，记号“O”读作“大O”，即Order（数量级）的缩写，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。T(n)称为算法的时间复杂度。Page

28O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)大O表示法有两个重要规则：加法规则当两个并列的算法段的时间代价分别为f1(n)=O(g1(n))和f2(m)=O(g2(m))时，两个算法段连在一起的算法段时间代价为：f(n,m)=f1(n)+f2(m)=O(max(g1(n),g2(m)))乘法规则如果存在循环嵌套，关键操作应该在最内层循环中。首先自外向内层层分析每一层的渐近时间复杂度，然后利用大O表示法的乘法规则来计算其时间复杂度。当两个嵌套时间复杂度的时间代价分别为f1(n)=O(g1(n))和f2(m)=O(g2(m))时，那么整个算法段时间代价为：f(n,m)=f1(n)*f2(m)=O(g1(n)*g2(m))Page

29【例1.10】设计一个算法，求含n个整数元素的序列中前i个元素的最大值。并分析算法的平均时间复杂度。解：对应算法如下：intfun(inta[],intn,inti){Intj,max=a[0];s=0;for(j=0;j<=i-1;j++) if(a[j]>max)max=a[j];return(max);}Page

30分析算法可知，i的取值范围为1~n；对于求前i个元素的最大值时，需要元素比较(i-1)-1+1=i-1次。在等概率的情况下：本算法的平均时间复杂度为O(n)。Page

311.2.3数据结构+算法=程序

N.Wirth的“数据结构+算法=程序”公式对计算机科学的影响程度足以媲美物理学中爱因斯坦的E=MC2——一个公式展示出了程序的本质。程序设计是必须认真规划的系统工程，从数据结构的设计到算法的设计，都应在可行性的基础上充分考虑其效率、扩展、异常和可维护性等。Page

321.3案例问题解决

1.3.11787年高斯算法——比较算法优劣【源程序】voidmain(){ intsum=0; //高斯的算法sum=(1+100)*100/2;printf("sum=%d\n",sum);sum=0; //其小伙伴的算法for(inti=1;i<=100;i++)sum+=i;printf("sum=%d\n",sum);}比较两个算法可知，高斯算法的时间复杂度为O(1)，而其小伙伴们的算法的时间复杂度为O(n)。Page

331.3.22014年高斯算法——比较结构优劣

【源程序】voidmain(){constintN=100inta[N]={12,23,34,45,56,76,34,23,67……},sum=0;for(inti=0;i<N;i++) sum+=a[i];printf("Sum=%d\n",sum);}虽然此处高斯算法的时间复杂度为O（n），而其同学直接累加的时间复杂度为O(1)，但采用数组的循环编写程序比用直接累加100个变量或用计算器累加100个常数要方便得多。更重要的是，由于数据与算法耦合较小，前者比后者更容易理解和维护。Page

341.4知识与技能扩展

1.ACM程序设计大赛ACM程序设计大赛是大学级别最高的脑力竞赛，素来被冠以“程序设计的奥林匹克”之称。大赛自1970