数据结构绪论

第一章绪论教学目标：通过这一章的学习，使读者全面了解数据结构的定义、研究内容以及这门课程的知识体系，从而为后面章节的学习打下基础。难
重点：数据结构的定义；算法描述的工具；算法性能的评价；1.1数据结构的起源一、数据结构起源于程序设计1946年第一台
计算机问世，主要用于军事和科学研究方面的科学计算，人们把计算机理解为数值计算的工具，使用计算机的目的主要是处理数值计算问题。用计
算机解决一个具体问题的步骤：抽象数学模型?设计算法?编制程序,上机调试寻求数学模型：分析问题?提取操作对象?对象之间关系?数学的
语言描述随着计算机科学与技术的不断发展，计算机的应用领域已不再局限于科学计算，而更多地应用于控制、管理等非数值处理领域。与此相
应，计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据，处理的数据量也越来越大，这就给程序设计带
来一个问题：应如何组织待处理的数据以及数据之间的关系（结构）。1968年克努思教授开创了数据结构的最初体系，他所著的《计算机程
序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。随后，相继出现了用Pascal、Jav
a、C、C++、C#等语言编写的数据结构方面的书。70年代初，数据结构作为一门独立的课程开始进入大学课堂。二、数据结构随着程序设计
的发展而发展程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：40~60年
代60~80年代始于80年代初⑴无结构阶段。40~60年代，计算机的应用主要针对科学计算，程序设计技术以机器语言
/汇编语言为主，程序处理的数据是纯粹的数值，数据之间的关系主要是数学公式或数学模型。这一阶段，在人类的自然语言与计算机编程语言之
间存在着巨大的鸿沟，程序设计属于面向计算机的程序设计，设计人员关注的重心是使程序尽可能地被计算机接受并按指令正确执行，至于程序能否
让人理解并不重要。⑵结构化阶段。60~80年代，计算机开始广泛应用于非数值处理领域，数据表示成为程序设计的重要问题，人们认
识到程序设计规范化的重要性，提出了程序结构模块化，并开始注意数据表示与操作的结构化。数据结构及抽象数据类型就是在这种情况下形成的。
数据结构概念的引入，对程序设计的规范化起到了重大作用。图灵奖获得者沃思给出了一个著名的公式：数据结构+算法=程序从这个
公式可以看到，数据结构和算法是构成程序的两个重要的组成部分，一个软件系统通常是以一个或几个关键数据结构为核心而组织的。随着软件
系统的规模越来越大、复杂性不断增加，人们不得不对结构化技术重新评价。由于软件系统的实现依赖于关键数据结构，如果这些关键数据结构的一
个或几个有所改变，则涉及到整个系统，甚至导致整个系统彻底崩溃。⑶面向对象阶段。面向对象技术（首先是面向对象程序设计）始于
80年代初，是目前最流行的程序设计技术。由于对象（类）将密切相关的属性（数据）和方法（操作）定义为一个整体，从而实现了封装和
信息隐藏。使用类时，无需了解其内部的实现细节，一旦数据（结构）修改了，只需修改类内部的局部代码，软件系统的其余部分无需修改。数
据结构主要强调两个方面的内容：①数据之间的关系；②针对这些关系的基本操作。三、数据结构的发展并未终结值得注意的是，数据结
构的发展并未终结。一方面，数据结构将继续随着程序设计的发展而发展；另一方面，面向各专门领域的数据结构得到研究和发展，各种实用的高级
数据结构被研究出来，各种空间数据结构也在探索中。“数据结构”在计算机科学中是一门综合性的专业基础课，是介于数学、计算机硬件和计算
机软件三者之间的一门核心课程，其内容不仅是一般程序设计(特别是非数值性程序设计)的基础，而且是设计和实现编译程序、操作系统、数据库
系统及其他系统程序的重要基础。1.2什么是数据结构1.数据描述客观事物的符号，是信息的载体，它是能够被计算机识
别、存储和加工处理的对象。数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。数据不仅仅包括
整型、实型等数值类型，还可以是文字、表格、图像、声音等非数值类型。比如，我们现在离不开的“百度”，其中有网页、音乐、图片、视频等分
类，音乐就是音频数据，图片是图像数据，网页则包括数值、文字、图片等多种数据。总之，我们这里所说的数据，其实就是具备以下两个条件的
符号：①可以输入到计算机；②能被计算机程序处理。2.数据元素一个数据元素是由用来描述一个特定事物的名称、数量
、特征、性质的一组相关信息组成的，在计算机中通常把数据元素作为一个整体进行考虑和处理。3.数据项多数情况下，一个数据元素可由若
干个数据项组成，有时也把数据项称为数据元素的域、字段、关键字。具有独立含义的最小单位例如，一所学校对学生的信息管理，其中管理对象就
是学生数据。其数据元素就是一个学生的信息；每一个学生的所有信息形成了一个数据元素，通常可以称为一个学生记录。学生的学号、姓名、性别
、专业等就是其数据项(或称字段)。学号姓名性别专业年级……130102彭凤姣女信息与计算科学13级……130103李丽女软
件工程13级……130104张汉涛男信息与计算科学13级……130105何颖文女计算机应用13级……130106高媛女计算机应
用13级……………………数据项是数据不可分割的最小单位，但是在讨论问题时，数据元素才是数据结构中建立数学模型的着眼点。4.数据对
象我们把具有相同性质的数据元素的集合称为数据对象，它是数据的一个子集。例如，(1)字母字符数据对象的集合C?=?{''A'',
''B'',…,''Z''}，它是字符数据的一个子集；(2)偶数数据对象的集合N?=?{0,±2,±4,…}是整数数据的子
集；(3)学生表中的学生信息是学生数据的子集。在具体问题中，数据元素都具有相同的性质(元素值不一定相等)，且属于同一数据对象
(数据元素类)。数据元素是数据对象的一个实例。5.数据结构数据结构——是指互相之间存在着一种或多种关系的数据元素的集合。数据结构两
要素：一个是数据元素的集合，另一个是关系的集合。讨论数据结构的目的是为了在计算机中实现其所需的各种操作。数据结构的操作与其具体
问题要求有关。基本的操作主要有以下几种：插入、删除、修改、查找、排序根据插入、删除、修改、查找、排序等操作的特性，所有的操作
可以分为两大类：一类是加工型操作，其操作改变了结构的值；另一类是引用型操作，其操作不改变结构的值。数据结构包含三部分：数据、数据
之间的关系及在数据集合上的一组操作。数据结构是一门研究非数值计算的程序设计问题中的操作对象、对象之间的关系以及在此之上的一系列
操作的学科。1.3逻辑结构与物理结构逻辑结构是面向问题的，而物理结构是面向计算机的，其基本目标就是将数据及其关系存储到计算机
的内存中。1.逻辑结构数据的逻辑结构是指数据元素之间的逻辑关系。逻辑结构有两个要素：数据元素集合、关系的集合。在形式
上，逻辑结构通常可以采用一个二元组来表示：Data_Structure=(D，R)其中，D是数据元素的有限集，R是D上关系的
有限集。集合线形表树图根据数据元素间关系的不同特性，通常有下列四类基本的结构：集合结构：元素属于或不属于同一个集合线性结构：元素
之间存在着一对一的关系。树形结构：元素之间存在着一对多的关系。图状结构：元素之间存在着多对多的关系。2.存储结构（又称物理结构
）物理结构是指数据的逻辑结构在计算机中的存储形式，是逻辑结构在计算机中的实现，包括数据元素的存储及元素之间关系的组织。数据的存
储结构要能正确反映数据元素之间的逻辑关系。如何存储数据元素之间的关系，是实现物理结构的重点和难点。数据元素的存储结构形式有两种：
顺序存储结构链式存储结构顺序存储结构顺序存储结构是把数据元素存放在地址连续的存储单元中，其数据元素之间的逻辑关系和物理位置一致。
（a1,a2,a3,……,an）链式存储结构链式存储结构是把数据元素存放在任意的存储单元中，这组存储单元可以连续也
可以不连续。其数据元素之间的物理位置不能反映其逻辑关系，用指针来反映数据元素之间的逻辑关系。例如，百家姓的部分姓氏表(zhao,
qian,sun,li,zhou,wu,zheng,wang)，是一个线性结构，用链式存储结构存储，1.4抽象数据类
型1、数据类型数据类型是指一个值的集合和定义在这个值集上的一组操作的总称。数据类型决定了数据占内存的字节数、数据的取值范围、可进
行的操作。例如，C语言中inta,b;规定了变量a、b在内存中所占的字节数、取值范围以及施加于a、b上的运算。在使用in
t类型时，既不需要了解在计算机内部是如何表示的，也不需要知道其操作如何实现。如a?+?b，设计者仅仅关注其“数学上求和”的抽象特
征。我们可以将数据类型进一步抽象，即抽象数据类型。2、抽象数据类型抽象数据类型(AbstractDataType，ADT)
是指一个数学模型以及定义在此数学模型上的一组操作。是将“数据”、“结构”、“处理操作”封装在一起而形成的复合体。抽象数据类型实
际上就是对数据结构的逻辑定义。例如，将与有序表有关的数据和处理操作封装成一个ADT，包含数据元素及其关系，操作有初始建表、插入、
删除、查找，其描述如下：ADTOrdList//OrdList为抽象数据类型的名字{数据对象：D?=?{ai|a
i∈ElemSet,i=1,2,…,n,n≥0}//ElemSet为数据元素集合数据关系：R?=?{,ai>|ai-1,ai∈D,i=2,…,n}基本操作：InitList(&L) //构造一个空的有
序表LListLength(L) //输出L中数据元素个数LocateElem(L,e) //在表L
中查找与给定值e相等的元素ListInsert(&L,i,e) //在表L中第i个位置之前插入新的数据元素eList
Delete(L,i,e) //删除表L的第i个数据元素}ADTOrdList3、抽象数据类型的实现方法实现
ADT的方法有三种：封装法、分散法、半封装法。封装法：数据及其操作封装成一个整体，比如C++?中的类。分散法：将数据和处理数据
的函数各自分开。无法从程序的物理结构(即代码的物理次序)上区分哪些数据和函数属于哪个ADT。例如，用一个数组elem[?]存储栈中
的元素，再用一个整型变量top表示栈顶位置，其操作用一个一个的函数实现。datatypeelem[MAXSIZE];int
top;半封装法：将数据和为处理数据需要而定义的相关变量封装在一起形成一个结构，有关处理函数定义在结构之外。这种方法仅做到了
对数据存储结构的封装，其特点介于封装法和分散法之间。例如，实现栈的抽象数据类型时，我们把存储栈中元素的数组elem[]?和栈顶位
置变量top封装在一起，其操作函数实现如下：#defineMAXSIZE<最大元素数>typedefstruct
{datatypeelem[MAXSIZE];inttop;}SeqStack1.5算法用C语言编写程序计
算1?+?2?+?3?+?4?+?…?+?100，大家都会写出这样一段代码：main(){inti,sum=0,
n=100;for(i=1;i计算机程序，它就是一种算法。这个算法效率怎样呢?实际上对于这个问题，据说高斯在上小学时就给出了一个高效算法：sum?=
1?+??2??+??3??+…+100sum?=?100+?99?+?98?+…+12
sum=?101?+?101?+?101?+…+?101共100个所以sum=5050。程序如下：main(){
inti,sum=0,n=100;sum=(1+100)100/2;printf(″%d″,sum);}
1.5.1算法的基本概念算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法的特性(
1)有穷性：有限步骤之内完成,不能形成无穷循环。(2)确定性：每一个步骤必须有确定含义,无二义性。(3)可行性：操作可通过
已实现的基本运算执行有限次完成。(4)输入：有多个或0个输入。(5)输出：至少有一个或多个输出。算法与程序算法的含义
与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，
它仍处于动态等待中，因此操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题
的求解过程，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相成的。
解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率；反之，一种数据结构的优劣由各种算法的执行效果
来体现。算法要求：正确、可读、健壮、高效率低存储(1)正确。算法“正确”的含义大体上可分为四个层次：一是所设计的程序没有语
法错误；二是所设计的程序对于几组输入数据能够得出满足要求的结果；三是所设计的程序对于精心选择的典型、苛刻而且带有刁难性的几组输
入数据能够得到满足要求的结果；四是所设计的程序对于一切合法的输入数据都能产生满足要求的结果。对于这四层含义，其中达到第四层含义下
的正确是极其困难的。一般情况下，以达到第三层含义的正确性作为衡量一个程序是否正确的标准。例如，要求n个数的最大值问题，算法如下：
max:=0;for(i=1;i<=n;i++){scanf(″%f″,&x);if(x>max)max
=x;}此算法无语法错误，请考虑，如果输入的数全为负数时，会产生什么结果?其正确性达到了第几层。算法要求：正确、可读、健
壮、高效率低存储(2)可读。算法首先应该便于人们理解和相互交流，其次才是机器可执行。所以一个算法应当思路清晰，层次分明，简单
明了，易读易懂。(3)健壮。作为一个好的算法，当输入不合法数据时，应能适当地做出正确反应或进行相应的处理，而不至于产生一些莫名
其妙的输出结果。(4)高效率低存储。算法效率通常指算法的执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法其效率
高。所谓存储量的要求，是指算法在执行过程中所需要的最大存储空间。这两者都与问题规模有关。1.5.2算法的性能评价算法的时间
复杂度与空间复杂度1.算法效率的度量方法算法的效率，大都指算法的执行时间。其度量方法有两种：一种方法叫做事后统计法，一种是
事前分析估算法。事后统计法：通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率
的高低。这种方法显然有很大的缺陷：(1)必须依据算法编制好程序，这通常需要花费大量的时间和精力，如果编制出来之后发现有很大缺陷
，就会前功尽弃。(2)时间的比较依赖于计算机硬件和软件的环境因素，有时会遮盖算法本身的优劣。(3)算法的测试数据设计困难，
并且程序运行时间往往还与测试数据规模有很大关系，效率高的算法在小规模的测试数据面前往往得不到体现。比如，10个数字的排序，不管用什
么算法，差异几乎为零。而如果有一百万个随机数字排序，那不同的算法差异就非常大。那么我们为了比较算法，到底用多少数据来测试，这是很难
判断的问题。事前分析估算法：在计算机程序编制前，依据统计方法对算法进行估算。经过分析发现，一个用高级程序设计语言编写的程序在计
算机上运行时所消耗的时间取决于下列因素：(1)算法采用的策略、方法；(2)编译产生的代码质量；(3)问题的输入规模；
(4)机器执行指令的速度。上述第(1)条当然是算法好坏的根本，第(2)条是要系统软件来支持，第(4)条要看硬件性能。如果抛开
与计算机相关的软、硬件因素，一个特定算法的运行工作量的大小就只依赖于问题的规模(通常用正整数n表示)，或者说它是问题规模的函数。所
谓问题的规模，就是指输入量的大小。一个算法是由一条条指令构成的，算法的指令通常称为语句。所以，算法的执行时间和算法中所有语句执行
次数的总和成正比。再来看看我们上节举的例子，求1?+?2?+?3?+?4?+?…?+?100。用第一种方法：main(){
inti,sum=0,n=100; /执行1次/for(i=1;i<=n;i++)
/执行n+1次/sum=sum+i; /执行n次/pri
ntf(″%d″,sum); /执行1次/}用第二种方法：main(){inti,sum=0,n
=100; /执行1次/sum=(1+100)100/2; /执行1次/printf(″%d″,su
m); /执行1次/}那么，第一种算法执行时间为1?+?(n?+?1)?+?n?+?1?=?2n?+?3而第
二种算法执行时间是1?+?1?+?1?=?3事实上两种算法的第一句和最后一句是一样的，我们关注的代码其实是中间的那部分，我们把
循环看做一个整体，忽略头尾循环判断的开销，那么这两个算法其实就是n和1的差距。算法好坏显而易见了两个n×n阶矩阵相乘的算法。1
for(i=0;ij /执行n2次/4for(k=0;k/执行n2(n+1)次/5c[i][j]=c[i][j]+a[i][k]b[k][j]; /执行
n3次/6}上述算法中语句的总的执行次数为2n3?+?3n2?+?2n?+?1。显然，算法执行时间与语句的执行次数成
正比，我们可以用语句的执行次数来描述算法的执行时间。可以看出，算法的执行时间是问题规模n的函数f(n)，n就是给定的问题规模。2.
算法时间复杂度算法:控制结构(顺序、分支、循环)+原操作（固有数据类型的操作）算法执行时间取决于两者的综合效果。以
原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。引入渐进时间复杂度在
数量上估计一个算法的执行时间算法中语句的执行次数T(n)，它是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)
的数量级(orderofmagnitude)。记作：T(n)?=?O(f(n))表示随问题规模n的增大，算法的执行时间
的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。表1.12n2、3n?+?1、2n2?+?3n?+?
1的增长率次数算法A(2n2)算法B(3n?+?1)算法C(2n2?+?3n?+?1)n?=?1246n?=?28715n?=?1
020031231n?=?10020?00030120?301n?=?10002?000?00030012?003?001n?=?
10?000200?000?00030?001200?030?001n?=?100?00020?000?000?000300?00
120?000?300?001n?=?1000?0002?000?000?000?0003?000?0012?000?003?00
0?001从表1.1的数据变化可以清楚地看到，当n值越来越大时（百万），3n?+?1的增长和2n2相差甚远，最终几乎可以忽略不计。
也就是说，随着n的增大，2n2趋近于2n2?+?3n?+?1。结论：如果得出了基本操作执行的次数的函数f(n)，判断一个算法效率时
，函数f(n)中的常数和其他次要项常常可以忽略，关注最高阶的项即可。下面给出推导大O方法。第一步，找到原操作的执行次数。第二步，用
常数1取代运行时间中的所有加法常数。第三步，在修改后的执行次数中，只保留最高阶项。第四步，如果最高阶项存在与这个项相乘的常数，则去
掉这个常数。这样就可得到大O阶。(1)顺序结构的时间复杂度。inti,sum=0,n=100;
/执行1次/sum=(1+100)100/2; /执行1次/printf(″%d″,sum);
/执行1次/这个算法的运行次数为f(n)?=?3。顺序结构、分支结构的程序，不管代码有多少行，执行次数不
会随着n的变化而发生变化，它与问题规模n的大小无关，执行次数是恒定的，我们用O(1)来表示其时间复杂度。通常称之为常量阶。(2)
单循环结构的时间复杂度。for(i=1;i /原操作执行n次/其时间复杂度为O(n)，我们称之为线性阶。(3)多重循环结构的时间复杂度。for(i=
1;i<=n;i++) /执行n+1次/for(j=1;j<=n;j++) /执行n+1次/x=x+1;
/原操作执行n2次/其时间复杂度为O(n2)，我们称之为平方阶。如果是三重循环，其时间复杂度为O(n3)，我们
称之为立方阶，以此类推。inti,j;for(i=0;ix+1;/原操作/当i?=?0时，内循环执行了n次，当i?=?1时，内循环执行了n-1次……当i?=?n-1时，执行1
次。所以总的执行次数为n?+?(n-1)?+?(n-2)?+?…?+?1?=?n(n+1)/2?=?n2/2?+?n/2。用推
导大O阶的方法，第一，n2/2?+?n/2没有加数常数，可以不予考虑；第二，保留最高项n2/2；第三，去掉这个项相乘的常数，最终得
到n2，所以，这段代码的时间复杂度为O(n2)。(4)下面代码时间复杂度又是多少?intc=1;while(cc=c2;/原操作/由于每次c乘以2之后，就离n更近，也就是说，多少个2相乘后大于n，才会退出循环。
由2x?=?n得到x?=?lb?n。可以得出，循环的执行次数为lb?n，时间复杂度为O(lb?n)。我们称之为对数阶。lb就是
logbasedbinary，即以2为底的对数。(5)递归程序的时间复杂度的分析。intBinrec(intn)
{ifn=1return1;elsereturnBinrec(n/2)+1;/原操作
/}用A(n)表示所做的加法次数，建立递推关系如下:设n?=?2k，当k?>?0时，A(2k)?=?A(2k-1)?+?1?=
?[A(2k-2)?+?1]?+?1?=?A(2k-2)?+?2=?…?=?A(2k-i)?+?i?=?…?=?A(2k-k)
?+?k?=?k因为n?=?2k，所以k?=?lb?n。因此A(n)?=?lb?n。其时间复杂度为O(lb?n)我们称之为对
数阶。常用的时间复杂度：常量阶O(1)、线性阶O(n)、平方阶O(n2)、对数阶O(lb?n)。此外，算法还能呈现的时间复杂度有
二维阶O(n?lb?n)、立方阶O(n3)、指数阶O(2n)、阶乘阶O(n!)等，数据结构中常用的时间复杂度关系如下：O(1)?
nn)常见的T(n)随着问题规模n不断增大时的变化情况。渐进分析法，用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。大
O符号德国数论学家保罗·巴赫曼（PaulBachmann）在其1892年的著作《解析数论》首先引入的。大O复杂度并不具体表示代
码真正的执行时间代表的是代码执行时间随数据规模增长的变化趋势一些常见的大O运行时间O(logn)，也叫对数时间，二分查找。O(n
)，也叫线性时间，简单查找。O(nlogn)，快速排序——一种速度较快的排序算法。O(n2)，选择排序——一种速度较慢的排
序算法。O(n!)，旅行商问题的解决方案——一种非常慢的算法。3.算法的最优、最差与平均时间复杂度算法的效率不仅依赖于问题的规
模，还与问题的初始输入数据集有关。例如，在数组a[1..n]?中查找值为k的元素，若找到，则输出位置i(1≤i≤n)；否则输出0。
算法描述如下：i=n;while(i>0)&&(a[i]!=k)i=i-1;printf(″%d″,i);whil
e循环的执行次数不仅与问题规模有关，还与k和数组a中各分量的取值有关。最坏情况下，即数组a中不含值为k的元素，while循环执行
n次；最好情况下，即数组中值为k的元素为a[n]，while循环执行1次；平均情况下，while循环执行(n+1)/2次，时间
复杂度为线性阶。最优时间复杂度是指在输入规模为n时，算法在最优情况下的时间复杂度。最差时间复杂度是指在输入规模为n时，算法在最
差情况下的时间复杂度。最差情况的运行时间是一种保证，那就是运行时间将不会再坏了。平均时间复杂度是指在“典型”或“随机”输入的情
况下，算法具有的时间复杂度。平均时间复杂度是从概率的角度进行分析的，研究它的直接方法就是将规模为n的实例划分为几种类型，需要得到或
者假设各种输入类型的概率分布，以便推导出基本操作的平均执行次数。但是，这个方案的技术实现一般都不简单，而且在各种特定的情况下，它所
包含的概率假设也往往很难验证。本书中如不作特殊说明，所讨论的各种算法的时间复杂度均指最坏情况下的时间复杂度。4.空间复杂度类
似于算法的时间复杂度，采用空间复杂度作为算法所需存储空间的量度，记作：S(n)?=?O(f(n))其中n为问题的规模。在存储空间
使用方面，对于处理同一问题的不同算法，其对存储空间的需求有较大的差异。例如：将存放在一维数组a中的n个整数反向存放，即原始数组a
为123…n-2n-1na[1]a[2]a[3]…a[n-2]a[n-1]a[n]反向存放后数组a为123…n-2n-1na[n]
a[n-1]a[n-2]…a[3]a[2]a[1]对于这一问题，可以用一组工作单元，即设置一个数组b[1..n]算法实现：fo
r(i=1;i<=n;i++)b[n-i+1]=a[i];for(i=1;i<=n;i++)a[i]=b[i];但也
可以只使用一个工作单元temp，算法如下：for(i=1;i<=n/2;i++){temp=a[i];a[i]=
a[n-i+1];a[n-i+1]=temp;}显然，采用后一种算法比前一种算法所需的存储空间要节省得多。一个程序的空间复杂
度是指程序运行从开始到结束所需的存储量。程序的一次运行是针对所求解的问题的某一特定实例而言的。程序运行所需的存储空间包括以下两部分
：(1)固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长
成分的结构变量所占的空间。(2)可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，100个数据元
素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。1.5.3算法描述常用的算法描述方法有如下几种：自然
语言操作步骤都是顺序执行时，比较直观、容易理解包含判断、循环结构，操作步骤较多时，则不够直观清流程图类程序设计语言用程序设计语言
的流程控制结构来表示处理步骤的执行流程和方式，用自然语言和各种符号来表示所进行的各种处理及所涉及的数据某种程序设计语言本书采用类
C语言作为算法描述工具，类C语言是一种伪码语言。1.6“数据结构与算法设计”课程的地位及主要内容1.“数据结构与算法设计”课程
的地位是计算机专业中的一门专业基础必修课,是一门理论与实践相结合的课程。它是程序设计(特别是非数值计算的程序设计)的基础，也
是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。因此，“数据结构”是数学、计算机硬件、计算机软件
三者之间的一门核心课程，是提高学生软件设计水平的一门关键课程。该课程多年来一直是计算机相关专业研究生考试必考专业课之一，是反映学生
数据抽象能力、编程能力的重要体现。介于数学、计算机硬件和计算机软件三者之间的一门核心课程线性表栈、队列线性结构逻辑结构唯一存
储结构不唯一运算的实现依赖于存储结构串、数组数据的逻辑结构树形结构非线性结构图形结构顺序存储数据的存储结构链式存储
数据的运算：插入、删除、修改、查找、排序2.“数据结构与算法设计”课程的主要内容名称特点存储结构线性表数据元素
之间的关系是一对一顺序存储结构、链式存储结构栈插入操作和删除操作位置在线性表的一端进行，具有先进后出的特点顺序栈、链栈队列插入操作
在线性表的一端、删除操作在线性表的另一端进行，具有后进先出的特点顺序队列、链队列、循环队列串数据元素是字符的线性表，操作对象是数
据元素的序列顺序串、块链结构、堆存储串数组线性表的推广，数据元素可以是一个表，如二维数组、三维数组……以行为主序或者以列为主序的
顺序存储。特殊矩阵的压缩存储；稀疏矩阵的三元组表存储、十字链表存储广义表线性表的推广，数据元素可以是一个表，也可以是一个元素广
义表链式存储树数据元素之间存在一对多的关系，具有清晰的层次关系双亲表示法、孩子表示法、孩子链表表示法、孩子兄弟表示法二叉树数据
元素之间存在一对多的关系，具有清晰的层次关系。每个结点最多有两个孩子结点，而且有序顺序存储结构、二叉链表存储结构、三叉链表存储结构
图数据元素之间存在多对多的关系，也称网状结构邻接矩阵、邻接表、十字链表、多重邻接表(2)查找与排序。查找方法包含有：静态查找表
的查找方法(顺序查找、折半查找、分块查找)、动态查找表的查找方法(二叉排序树、平衡二叉树、B树)、哈希表的查找。排序方法包括：简
单的排序方法(简单选择排序、直接插入排序、希尔排序、冒泡排序)、先进的排序方法(快速排序、归并排序、堆排序)、基数排序方法。(3)
经典算法。经典算法包括分治法、贪婪法、回溯法、动态规划法。学习方法1本课程的特点理论与实践并重理论学习要严谨、方法掌握要灵活
提高自学能力2理论与技术的关系适应飞速变化的技术的根本是注重基础理论学习理论的演变是缓慢的、理论基础是相通的相同的原理可以应用于
不同的技术3勤动手、多实践、提高学习能力1)学到的知识是死的，总有过时的时候。只有通过学习知识提高学习能力，才是立于不败之地的保证。2)记笔记：好记性不如烂笔头，通过动手加深理解和记忆。3)做作业、做上机题。在学习过程中，建议学生注意以下几个方面：(1)非数值计算，这是数据结构这门学科的应用范围。比如，学生信息管理中的学生信息，每个学生信息包含学号、姓名、性别、年龄等，无法用具体的数值表达。(2)操作对象，具体问题中的数据及其表示的形式。比如，学生信息管理中的学生记录就是操作对象。(3)关系，即数据间的关系。比如，学生信息管理中的学生记录之间可以按学号逐个表示到计算机中，学生记录之间存在着线性关系。(4)操作，即针对数据元素的操作。比如，学生信息管理中，查找、插入、删除某个学生信息等。(5)算法复杂度，即对操作实现的算法进行性能分析。可略讲C语言复习1)C语言的基本数据类型有三种由硬件系统直接支持实现的基本数据类型：char型、int型、float型。2)C语言的指针类型C语言允许直接对存放变量的地址进行操作。如：inta，则&a表示a的地址，也称指向变量a的指针。Ll123…n-2n-1na[n]a[n-1]a[n-2]…a[3]a[2]a[1]3)C语言的数组类型数组是同一类型的一组数据的集合。数组名代表了这一组数的起始地址。如：inta[10],p;4)C语言的字符串在C语言中，没有字符串变量，字符串是作为一维字符数组来处理的。5)C语言的结构体类型C语言的结构体由一组称为结构体成员的项组成。定义一个结构体类型变量由两步组成。第一步，定义结构体类型；第二步，定义结构体类型变量。或写作：例如：typedefstruct{charname[20];floatscore[5];floataverage;}studenttype;studenttypestu1,stu2[100],p;structstudent{charname[20];floatscore[5];floataverage;};structstudentstu1,stu2[100],p;