吉林农业科技学院《计算机基础》课件-第3章数据结构与算法

Page

1绪论线性结构

树形结构123查找4第三章数据结构与算法排序5吉林农业科技学院《计算机基础》Page

2第三章数据结构与算法数据结构与算法数据结构查找与排序绪论其它结构树形结构线性结构查找排序串文件图数组Page

3绪论1第三章数据结构与算法利用计算机解决问题的步骤分析问题

确定已知和未知，确定数据类型方案设计数学模型

数值问题要建立数学模型，非数值问题要应用数据结构处理2026/10/30计算机基础教学部4回忆第一节绪论5要使计算机能更有效地处理非数值性问题，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。程序:数据结构:算法:为计算机处理问题编制的一组指令集处理问题的策略问题的数学模型非数值问题：程序＝数据结构＋算法第一节绪论Page

61.1算法和算法分析算法1.算法（Algorithm）是对特定问题求解步骤的一种描述，是操作的有限序列。2.算法的特性：（1）有穷性。一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成；（2）确定性。算法的每一步必须有确切的含义，无二义性（3）可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行来实现；（4）零个或多个输入（5）一个或多个输出if(x>=y)cout<<“yes”<<endl;else(x<=y)

cout<<“no”<<endl;

Page

71.1算法和算法分析算法

算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而选择的恰当与否将直接影响到算法的效率。

3.衡量一个算法的性能主要有以下几个标准：（1）正确性。算法的执行结果应当满足预先规定的功能和性能要求；（2）可读性。一个算法应当思路清晰、层次分明、简单明了、易读易懂；（3）健壮性。当输入不合法数据时，应能作适当处理，不至引起严重后果；（4）高效性。有效使用存储空间和有较高的时间效率。84、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:4.1事后统计法4.2事前分析估算法两个缺陷：

a.必须先运行程序；b.运行时间依赖于计算机软硬件环境算法的优劣可以通过一个算法的时间复杂度与空间复杂度来评价。算法分析1.1算法和算法分析94.算法效率的衡量方法和准则（效率的度量）4.2事前分析估算法1).程序运行所耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之和。决定因素：

算法所选用的策略问题的规模书写程序所采用的语言编译程序所产生的机器代码的质量机器执行指令的速度1.1算法和算法分析算法分析104.算法效率的衡量方法和准则（效率的度量）4.2事前分析估算法1).程序运行所耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句的执行次数(即频度(FrequencyCount))×语句执行一次所需时间不考虑机器软硬件环境时算法的时间耗费,设执行每条语句所需时间为单位时间，则：一个算法耗费的时间=所有语句的频度之和。算法分析1.1算法和算法分析1.1算法和算法分析4.2事前分析估算法时间复杂度f(n)即：时间耗费，它是算法求解问题n的函数。渐近时间复杂度即当问题的规模n→∞时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n))评价一个算法的时间性能，主要标准是算法的渐近时间复杂度Page

11orderPage

121.1算法和算法分析算法分析4.算法效率的衡量方法和准则（效率的度量）（2）时间复杂度一般情况下，算法中原操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作：T(n)=O(f(n))它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称为算法的渐进时间复杂度（AsymptoticTimeComplexity），简称时间复杂度。这里的“O”表示量级（Order），常用大O记法表示时间复杂度，表示说只是有上界。13【例】求两个n阶方阵的乘积C=A×B

constintn=100;voidMatrixMultiply(intA[n][n]，intB[n][n]，intC[n][n])//红色为各语句的频度

{inti,j,k;

(1)for(i=0;i＜n;i++)

/*

次数n+1*/

(2)

for(j=0;j＜n;j++)/*

次数n(n+1)*/

(3)

{ C[i][j]=0;/*

次数n2*/

(4)

for(k=0;k＜n;k++)/*

次数n2

(n+1)*/

(5)

C[i][j]=C[i][j]+A[i][k]*B[k][j];/*

次数n3*/

}

}该算法中所有语句的频度之和(即算法的时间耗费)为：

T(n)=2n3+3n2+2n+1

1.1算法和算法分析14

这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法的渐近时间复杂度。

1.1算法和算法分析4.算法效率的衡量方法和准则（效率的度量）同阶无穷大一般，当有若干循环语句时，时间复杂度(即算法的时间耗费)是由嵌套层次最多的循环语句中最内层语句的频度决定

15常见的时间复杂度有：O（1）常数阶

O（log2n）对数阶O（n）线性阶

O（n2

）平方阶

O（2n）指数阶4.算法效率的衡量方法和准则（效率的度量）1.1算法和算法分析例：temp=a；a=b;b=temp;三条语句的执行频度均为1,T(n)=O(1)Page

161.1算法和算法分析

随着问题规模n的增大，其时间消耗T(n)也在增大。常见的渐进时间复杂度有：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)

其中线性阶Ο(n)、平方阶Ο(n2)和对数阶Ο(log2n)是“数据结构”算法分析常见的重要方法。不同数量级时间复杂度的性状如图4.算法效率的衡量方法和准则（效率的度量）【例】《汉诺塔》的游戏规则:1、把组成“金塔”的圆片按照下大上小依次放在中央的柱子上；2、每次只能移动一个圆；3、在移动过程中，大圆不能压在小圆上面；4、每次移动的圆只能放在左中右的位子；5、将整座“金塔”移到另外任意一根柱子上即告胜利。

1.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

1步

规律：

1＝0×2＋1＝21－11.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

3步

规律：

3＝1×2＋1＝22－11.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

7步

规律：

7＝3×2＋1＝23－11.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

31步

规律：

31＝15×2＋1＝25－11.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

63步

规律：

63＝31×2＋1＝26－11.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

127步

规律：

127＝63×2＋1＝27－11.1算法和算法分析【例】《汉诺塔》的游戏

走出这个图形的步数：

255步

规律：

255＝127×2＋1＝28－1总结出时间复杂度为：T(n)=O（2n)1.1算法和算法分析移动64个金片需要多长时间？253)、算法的空间复杂度一个算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度（SpaceComplexity）是指这个算法执行过程中所需的存储空间，记作：S(n)=O(f(n))表示随着问题规模n的增大，算法运行所需的存储量的增长率与f(n)的增长率相同。若所占空间量依赖于特定的输入，按最坏情况来分析。1.1算法和算法分析4.算法效率的衡量方法和准则（效率的度量）3）空间复杂度一个算法所占用的存储空间包括：算法程序所占的空间算法的输入/输出数据占用的空间算法执行过程中所需要的额外空间原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。Page

264.算法效率的衡量方法和准则（效率的度量）1.1算法和算法分析冒泡排序排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为S(n)=O(1)274)、算法性能选择

要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：

①若该程序使用次数较少，则力求算法简明易懂；

②对于反复多次使用的程序，应尽可能选用快速的算法；

③若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。1.1算法和算法分析4.算法效率的衡量方法和准则（效率的度量）Page

281.2什么是数据结构什么是数据结构非数值计算实例

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及操作对象之间的关系和操作的学科。例1：学籍管理（线性结构）例2：操作系统的目录结构（树形结构）例3：制定教学计划（图或网状结构）Page

291.2什么是数据结构例1：学籍管理（线性结构）学生基本情况学号姓名性别出生年月政治面貌0905024101董灿女90．6团员0905024102张晓杰男90．2团员0905024103郭雨婷女90．9党员…………………………0905024150王鹏男89．12团员Page

301.2什么是数据结构例2：操作系统的目录结构（树形结构）操作系统的树形目录结构Page

311.2什么是数据结构例3：制定教学计划（图或网状结构）计算机专业学生的必修课程课程编号课程名称需要的先修课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1课程先后关系的图形描形式Page

321.3基本概念和术语1、数据数据（Data）是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。它是计算机加工处理的对象，可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。Page

331.3基本概念和术语2、数据元素

数据元素（DataElement）是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。一个数据元素可由一个或多个数据项组成，数据项（DataItem）是有独立含义的最小单位，此时的数据元素通常称为记录（Record）。例如：描述一个学生信息的数据元素称之为组合项年月日姓名学号班号性别出生日期入学成绩原子项Page

341.3基本概念和术语3、数据对象

数据对象（DataObject）是性质相同的数据元素的集合，是数据的一个子集。只要性质相同，都是同一个数据对象。例：无限集：整数数据对象是集合N={0，±1，±2，…}，有限集：大写字母字符数据对象是集合

C={‘A’，‘B’，…，‘Z’}，多个数据项组成的复合数据元素集：

13050541班学生基本情况也可看作一个数据对象。Page

351.3基本概念和术语4、数据结构数据结构（DataStructure）是指数据元素之间存在着一种或多种关系的数据元素的集合。数据之间存在着某种特定的关系，数据元素之间的关系，称为“结构”。数据结构=关系+实体根据数据元素间关系的不同特性，数据间关系有以下四类结构：（1）集合结构。在集合结构中，数据元素间除了“同属于一个集合”的关系外，别无其他关系。集合是元素关系极为松散的一种结构。（2）线性结构。数据元素之间存在着一对一的关系（3）树形结构。数据元素之间存在着一对多的关系（4）图状结构。数据元素之间存在着多对多的关系，图状结构也称作网状结构。Page

361.3基本概念和术语37例：在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:注意：row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6

a1a2a3a4a5a6

a1a2a3a4a5a6≠1.3基本概念和术语表示两个元素是前后排列关系38数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构：

是对数据元素之间的逻辑关系的描述。它对应一个数据元素的集合和定义在此集合上的若干关系;与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。物理结构：

是逻辑结构在计算机中的表示和实现，故又称“存储结构”

。是逻辑结构用计算机语言的实现，它依赖于计算机语言。4、数据结构1.3基本概念和术语Page

39存储结构的基本组织方式：（1）顺序存储（数组）（2）链式存储（结构=数据域+指针域）4、数据结构1.3基本概念和术语40

顺序存储结构特点：

(1)连续存放;逻辑上相邻,

物理上也相邻。

(2)结构简单，易实现。

4、数据结构1.3基本概念和术语41链式存储结构特点：(1)非连续存放,借助指针来表示元素间

的关系;

(2)结构较复杂，需要额外存储空间。4、数据结构1.3基本概念和术语42逻辑结构和物理结构的关系(1)数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。(2)数据的存储结构是逻辑结构在计算机中的实现，依赖于计算机；离开了机器，则无法进行任何操作。(3)任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。4、数据结构1.3基本概念和术语43数据结构的表示二元关系表：

数据结构是一个二元组Data_Structures=(D,R)其中:D是数据元素的有限集，

R是D上关系的有限集。4、数据结构1.3基本概念和术语44例：家庭成员数据结构B=(D,R)

D={父亲，儿子，女儿}R={(父亲，儿子),

(父亲，女儿)}图形表示：父亲儿子女儿例：一年四季的数据结构B=(D,R)

D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}图形表示：春夏秋冬1.3基本概念和术语Page

451.3基本概念和术语5、数据类型

数据类型（DataType）是和数据结构密切相关的一个概念。数据类型是一个值的集合和定义在该值的集合上的一组操作的总称。Page

461.3基本概念和术语6、抽象数据类型

抽象数据类型（AbstructDataType，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型的描述为：ADTname{

数据对象：D={……}

数据关系：R={……}

基本操作：创建；输出；插入；删除；等等;}ADTname;Page

471.3基本概念和术语6、抽象数据类型举例抽象数据类型的描述为：ADTname{

数据对象：D={……}

数据关系：R={……}

基本操作：创建；输出；插入；删除；等等;}ADTname;复数的抽象数据类型：ADTComplex{

数据对象：D={c1,c2|c1,c2∈float}

数据关系：R={<c1,c2>|c1,c2分别代表复数的实部和虚部}

基本操作：

创建一个复数；输出一个复数；求两个复数的和；求两个复数的积；等等;}ADTComplex;作业教材p124一、二、三Page

48Page

49线性结构

2第二节线性结构Page

501.线性表1.线性表的定义

线性表（LinearList）是n(n≥0)个数据元素的有限序列。在表中，元素之间存在着线性的逻辑关系：表中有且仅有一个开始结点；有且仅有一个终端结点；除开始结点外，表中的每个结点均只有一个前驱结点（Predecessor）；除终端结点外，表中的每个结点均只有一个后继结点（Successor）。根据它们之间的关系可以排成一个线性序列，记作(a1，a2，…，an)这里ai(1≤i≤n)表示数据元素，具有相同的数据类型。n代表线性表的表长，即线性表中数据元素的个数。当n=0时，线性表为空表。对于ai，当1＜i≤n时，它有一个直接前驱ai−1；当1≤i＜n时，它有一个直接后继ai+1。Page

511.线性表的定义1.线性表例1、26个英文字母组成的字母表（A，B，C、…、Z）

例2、一组数字（6，17，28，50，92，188）例3、线性表举例1.线性表1.线性表的抽象数据类型Page

53线性表的抽象数据类型定义为：ADTLinear_list{

数据对象：D={ai|ai∈ElemType,i=1,2,…,n,n≥0；}

数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}

基本操作：

初始化空线性表；求线性表表长；取线性表的第i个元素；在线性表的第i个位置插入元素x；删除线性表的第i个元素；修改线性表中的第i个元素；按某种要求重排线性表中各元素的顺序；按某个特定值查找线性表中的元素；

……}ADTLinear_list；其中，ElemType表示有数据元素具有的数据类型。1.线性表Page

542.线性表的顺序存储结构线性表有两种基本的存储结构：顺序存储结构和链式存储结构2.1线性表的顺序存储结构（1）线性表的顺序存储结构（2）顺序表类定义（3）顺序表的插入和删除算法1.线性表Page

552.线性表的顺序存储结构2.1线性表的顺序存储结构线性表采用顺序存储的方式存储就称之为顺序表。线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。顺序存储结构的特点：①利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构依赖于存储结构（物理结构）的物理连续来表示；

1.线性表2.1线性表的顺序存储结构顺序存储结构的特点：②在访问线性表时，只要确定了线性表的起始位置，线性表中任一数据元素的位置均可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。Page

561.线性表一般用数组实现对线性表的连续存储。设最多存储Maxsize个元素，可用数组elem[Maxsize]来存储数据元素，整型变量length保存线性表的长度。线性表的第l，2，…，n个元素分别存放在此数组下标为1，…，length数组元素i-1...

2.1线性表的顺序存储结构1.线性表012i线性表的顺序存储结构至少需要两个分量：数组elem[Maxsize]和表长度lengthC++中，为了更好地体现信息隐蔽原则以及数据抽象原则，数组和线性表长度可以作为类的数据成员(私有成员)，对线性表的各种操作可作为类的成员函数成员函数多是公有函数，提供类的对外接口在C++中，可用下述类定义来描述顺序表：2.2顺序表类定义1.线性表1.线性表Page

592.线性表的顺序存储结构2.2顺序表类定义constintMAXSIZE=100;//数组的容量typedefintElemType;//假设线性表中元素为整型classSqList{private:ElemTypeelem[MAXSIZE];//一维数组

intlength; //线性表长度

public:SqList(){length=0;};//构造函数初始化空表

~SqList(){};//析构函数

voidCreat(intn);//创建一个线性表

voidPrintOut(); //输出线性表

voidInsert(inti,ElemTypee);//插入函数

ElemTypeDelete(inti);//删除函数……;//其他成员函数;}；sequence2.3线性表顺序存储结构运算实现(1)初始化线性表(构造一个空表)用构造函数构造一个空表，表长度为0，即为建立空表

SqList::SqList(){length=0;}//构造函数构造空表1.线性表1.线性表(2)建立一个长度为length的新表

voidSqList::Creat(intn)//创建非空线性表

{intk=1;

length=n;

if(length>0){cout<<"\nInputData:\n";for(k=1;k<=length;k++)//从下标1开始存储数据

cin>>elem[k];}

else

cout<<"LengthError!"<<endl;}Page

61(3)输出线性表函数

voidSqList::PrintOut()

{intk;cout<<"\nlength="<<length;cout<<"\nPrintOutData:\n";for(k=1;k<=length;k++)cout<<setw(6)<<elem[k];cout<<endl;}2.3顺序存储结构运算实现1.线性表

(4)线性表的插入

在长度为length的顺序表的第i个数据元素之前插入一个新的数据元素x，需将第i个元素及其后元素依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，顺序表的长度增加1。

1

a1

2

a2┇┇

i-1

ai-1

i

ai

i+1

ai+1

i+2

ai+2┇┇

n

an

1

a1

2

a2

┇┇

i-1

ai-1

i

x

i+1

ai

i+2ai+1

┇┇nan

插入x2.3顺序存储结构运算实现1.线性表voidSqList::Insert(inti,ElemTypee){intj;

if(i<0||i>length+1)cout<<“iError!”<<endl;//判断插入位置

else{for(j=length+1;j>i;j--)elem[j]=elem[j-1]; //移动元素

elem[i]=e;//插入元素

length++;//线性表长加1}}2.3顺序存储结构运算实现(4)线性表的插入1.线性表(5)顺序表的删除运算删除运算将表中第i个元素从线性表中去掉，原表长为n的线性表(a1，a2，…，ai-1，ai，ai+1，…，an)，删除后线性表长变为n-1的表(a1，a2，…，ai-1，ai+1，…，an)。

如下图所示

0

a0

1

a1

2

a2┇┇

i-1

ai-1

i

ai+1

i+1

ai+2┇┇

n

an

0

1

a1

2

a2┇┇

i-1

ai-1

i

ai

i+1ai+1┇┇

nan

1.线性表

n-1(5)．顺序表的删除运算1.线性表

线性表的删除运算通过以下两个操作来实现：(1)线性表中第i+1个至第n个元素依次向前移动一个位置。(2)线性表长度减1。

ElemTypeSqList::Delete(inti){ElemTypex;intj;

if(i<1||i>length){cout<<"iError!"<<endl;}//判断删除位置

else{x=elem[i];//保存将被删除数据元素for(j=i;j<length;j++)elem[j]=elem[j+1]; //向前移动数据元素

length--;}//线性表长减1returnx;

//返回被删除数据元素}67voidmain(){SqListL;L.Creat(3);cout<<“FirstList:\n";L.PrintOut();cout<<"\n第i个位置插入值为x的元素:\n";L.Insert(1,10);L.PrintOut();cout<<"\n删除第i个位置的元素:\n";L.Delete(2);L.PrintOut();}1.线性表2.3顺序存储结构运算实现运行情况：Page

681.线性表2.3顺序存储结构运算实现Page

692.4顺序表的算法分析顺序表的时间复杂度在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在数据元素的移动上。而移动元素的次数取决于插入或删除元素的位置。在分析算法时采用移动元素的平均次数，来估算时间复杂度。插入时数据元素平均移动次数为：

1.线性表删除时数据元素平均移动次数为：

在顺序表中插入或删除一个元素时，平均移动表中大约一半的数据元素。根据上述两式(n/2和(n-1)/2)，忽略常数项以及常系数，若表长为n，则两个算法的时间复杂度都为：T(n)

=

O(n)。Page

702.4顺序表的算法分析1.线性表2.4顺序表的分析优点顺序表的结构简单顺序表的存储效率高，是紧凑结构顺序表是一个随机存储结构（直接存取结构）缺点在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。过大浪费过小溢出原因：数组的静态特性造成1.线性表Page

723.线性表的链式存储结构3.1线性表的链式存储结构3.2单链表类定义3.3单链表的插入和删除算法1.线性表Page

733.1线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了表示数据元素之间的逻辑关系，不仅需要存储数据元素本身的信息，还需存储一个指示其直接后继的信息。每个结点由:数据域和指针域组成头指针：指向第一个结点；第一个结点指向第二个结点…….表尾结点的指针域存放NULL1.线性表^指针为空Page

743.线性表的链式存储结构3.1线性表的链式存储结构（1）链式存储结构的特点：

①线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；②在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。1.线性表（2）单链表

(SinglyLinkedList)线性链表（单链表）：

链表的每个结点只包含一个指针域存储其后继的地址

Head头指针^指针为空1.线性表3.1线性表的链式存储结构Head

（3）相关术语：头指针：指向链表中第一个结点开始结点：第一个数据元素结点（真正结点）头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。说明：头结点的next域指向链表中的第一个数据元素结点。对于头结点数据域的处理：

a.加特殊信息

b.置空

c.如数据域为整型，则在该处存放链表长度信息1.线性表3.1线性表的链式存储结构（5）带头结点的单链表示意图无论链表是否为空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操作的实现。非空表 空表1.线性表3.1线性表的链式存储结构Head

Head

1.线性表3.2单链表类定义C++语言中，可将链表设计成一个类。首先定义一个结构体类型表示结点。链表中结点结构的定义如下：typedefintElemType;structNodeType//结点类型定义

{ElemTypedata;NodeType*next;};单链表的头指针Head作为链表类LinkList的私有数据成员，对链表中各数据结点的访问都将从Head开始，然后将线性表的各种操作设计成类的成员函数，构成单链表类。1.线性表Page

79线性表的链式存储结构3.2单链表类定义classLinkList{private:NodeType*Head; //链表头指针

public:LinkList();//构造函数，初始化空链表

~LinkList();//析构函数

voidCreat(intn);//创建一个非空链表

voidPrintout();//输出链表的数据元素

voidInsert(inti,ElemTypex);//插入

ElemTypeDelete(inti);//删除第i个结点

};

//类定义结束80①初始化单链表：使用构造函数实现LinkList::LinkList(){Head=new

NodeType;

Head->next=0;}

3.3单链表的算法实现1.线性表头结点Head^81②创建长度为n的单链表：voidLinkList::Creat(intn){inti;NodeType*p,*q;if(n>0)q=head;for(i=1;i<=n;i++){ p=newNodeType; cin>>p->data; p->next=NULL;q->next=p;q=p;

}1.线性表^dataP^Pqq->nextdataHeadqq->next82③输出单链表：voidLinkList::PrintOut()

{

NodeType*p;p=Head->next;//p指向第一个数据结点while(p!=NULL){cout<<setw(6)<<p->data;p=p->next;}cout<<endl;}1.线性表83s=newNodeType;s->data=x;(b)申请新结点s，数据域置xxsheada1a2...ai-1p...aian∧xsheada1a2×...ai-1p...aian∧②①(a)找到插入位置s->next=p;q->next=s;(c)修改指针域，将新结点s插入关键语句：qq④在第i个位置插入值为x的结点：第二节线性结构1.线性表⑦在第i个位置插入值为x的结点：3.3单链表的算法实现84voidLinkList::Insert(inti,ElemTypex){NodeType*p,*q,*s;intk=1;//计数器k，用于寻找i位置

q=Head;p=Head->next;//q指向头指针，//p指向第一个数据结点

while(k<i&&p!=NULL){q=p;p=p->next;k++;}if(k==i){s=newNodeType;s->data=x;s->next=p;q->next=s;cout<<"\n插入成功。"<<endl;}elsecout<<"\ni不存在。"<<endl;}85x=p->data；(b)返回被删除结点数据xxpheada1a2...ai-1q...aian∧(a)找到删除位置pheada1...(c)修改指针域，将结点p删除qai-1pai...an∧ai+1①②关键语句：q->next=p->next；deletep；⑤删除第i个结点：3.3单链表的算法实现1.线性表第二节线性结构3.3单链表的算法实现⑧删除第i个结点：86ElemTypeLinkList::Delete(inti)

{NodeType*p,*q;ElemTypex;intk=1; //k为计数器

q=Head;//q指向头指针，

p=Head->next;//p指向第一个数据结点

while(k<i&&p!=NULL)//查找第i个数据结点

{q=p;p=p->next;k++;}if(p!=NULL){x=p->data;//保存将被删除结点的数据元素的值q->next=p->next;deletep;cout<<"\n删除结点成功。"<<endl;}else{cout<<"\ni不存在。"<<endl;x=-1;}

returnx;}Page

87获取单链表长度：intLinkList::GetLength(){intnum=0;NodeType*p;p=Head->next;while(p!=NULL){num++;p=p->next;}return(num);}1.线性表88查找值为x的结点：NodeType*LinkList::Locate(ElemTypex){NodeType*p;p=Head->next;//p指向第一个数据结点while(p!=NULL&&p->data!=x)p=p->next;returnp;}

1.线性表89查找第i个结点：NodeType*LinkList::GetElem(inti){NodeType*p;

intpos=1;p=Head->next;//p指向第一个数据结点if(i<1||i>GetLength())return0;while(pos<i){p=p->next;

pos++;}returnp;}1.线性表

90LinkList::~LinkList(){

NodeType*p,*q; if(Head->next!=0){ q=Head->next; while(q!=NULL) { p=q; q=q->next; deletep;}}

deleteHead;}释放链表所有结点的内存（用析构函数）：1.线性表91voidmain(){LinkListL;L.Creat(3);cout<<"初始的线性表:\n";L.PrintOut();

L.Insert(2,3);L.PrintOut();L.Delete(1);L.PrintOut();}3.3单链表的算法实现1.线性表L.Insert(5,3);L.PrintOut();L.Delete(5);L.PrintOut();Page

921.线性表Page

933.4单链表插入和删除算法的时间复杂度

在顺序存储结构的线性表中插入/删除一个元素时会大量移动数据元素，其时间复杂度为O(n)。而在链表中插入/删除一个元素时却不需大量移动数据元素(只移动指针)，其时间复杂度可以视为O(1)。如果每个数据元素占用字节数比较多，链表结构在时间方面具有明显优势。3.4单链表的算法分析1.线性表

3.4单链表插入和删除算法的时间复杂度但是，为了存取某个指定位置的数据元素，顺序结构可以直接存取，其时间复杂度可以视为O(1)。而链表结构则需设一指针从链表的头结点开始向后查找，如果将指针的移动视为影响时间效率的主要因素，则时间复杂度可以视为O(n)。Page

943.4单链表的算法分析1.线性表95优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，进行数据插入或删除时不需要移动数据元素。缺点：①每个结点中的指针域需额外占用存储空间②链式存储结构是一种非随机存储结构。对任一结点的操作都要从指针链查找到该结点，增加了算法的复杂度。1.线性表3、4线性表的链式存储结构分析3.5循环链表循环链表——是一种首尾相接的链表。循环链表最后一个结点的next指针不为0(NULL)，

而是指向表头结点。在循环链表中没有NULL

特点：循环链表中，从任一结点出发都可访问到表中所有结点；而在单链表中，必须从头指针开始，否则无法访问到该结点之前的其他结点。1.线性表3、线性表的链式存储结构循环链表与单链表不同的是链表中表尾结点的指针域不是NULL，而是链表头结点的指针Head循环链表的示例带表头结点的循环链表3.5循环链表1.线性表3.6双向链表(DoublyLinkedList)双向链表是指在前驱和后继方向都能游历(遍历)的线性链表双向链表的结点结构：前驱方向(a)结点结构后继方向双向链表通常采用带表头结点的循环链表形式。1.线性表3、线性表的链式存储结构非空双向循环链表空表99关于顺序表和链表的小结：（1）顺序表是用数组实现的，而链表是用指针来实现的。（2）当线性表的长度变化较大，难以估计其存储规模时，宜采用动态链表作为存储结构为佳；当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。（基于空间的考虑）1.线性表100（3）顺序表是一种随机存取结构，访问速度快。若线性表的操作主要是查找，很少涉及到插入、删除操作时，可采用顺序表结构。若要频繁地进行插入和删除操作，宜采用链表作为存储结构。关于顺序表和链表的小结：第二节线性结构线性表的应用学生信息管理系统Page

101利用顺序表存储学生基本信息，此时该表中的数据元素是一个结构体类型，包括学号、姓名、性别、年龄、专业等。对学生信息的建立、查询、插入、删除操作均可利用顺序表基本操作的框架来实现。structStudent{ stringno; stringname; stringsex; intage; stringmajor;};typedefStudentElemType;Page

102voidSqList::Creat(intn) //创建学生信息{ intk; length=n; if(length>0) { cout<<"请输入学生信息（以空格隔开）:"<<endl; cout<<"学号

姓名

性别

年龄

专业"<<endl; for(k=1;k<=length;k++) { cin>>elem[k].no; cin>>elem[k].name; cin>>elem[k].sex; cin>>elem[k].age; cin>>elem[k].major; } } else cout<<"输入人数有误！"<<endl;}Page

103voidSqList::Insert(inti,ElemType&e) //插入学生信息{ intj; if(i<1||i>length+1) //判断插入位置 cout<<"InsertLocationiError!"<<endl; else { for(j=length+1;j>i;j--) { elem[j].no=elem[j-1].no; //移动元素

elem[j].name=elem[j-1].name; elem[j].sex=elem[j-1].sex; elem[j].age=elem[j-1].age; elem[j].major=elem[j-1].major; } elem[i].no=e.no; //插入元素 elem[i].name=; elem[i].sex=e.sex; elem[i].age=e.age; elem[i].major=e.major; length++; //线性表长度加1 cout<<"InsertSucess!"<<endl; }}本次课程结束Page

1052.1栈的定义栈（Stack）是一种限定性线性表，限定线性表的插入和删除运算在表的一端进行。将表中允许进行插入、删除操作的一端称为栈顶（Top），栈顶的位置是动态变化的，由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底（Bottom）。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。2.栈2.1栈的定义Page

106右图中表示了栈S=（a1，a2，a3，…，an）的示意图。a1为栈底元素，an为栈顶元素。栈中元素是以a1，a2，a3，…，an的顺序进栈的，而出栈的次序却是an，…，a3，a2，a1，是一种后进先出的结构。因此，栈又称为后进先出（LastInFirstOut，LIFO）的线性表。

特点：后进先出

(LIFO)2.栈1思考设一个栈的输入序列为1,2,3,4,5，进栈过程中容许出栈，则下列序列中不可能是栈的输出序列的是（）A1,2,3,4,5B2,3,4,5,1C5,4,3,2,1D4,1,2,3,5Page

10732415122312.栈Page

1082.2栈的抽象数据类型栈的抽象数据类型定义为：ADTStack{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0;}

数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}

约定an

端为栈顶，a1

端为栈底。基本操作：初始化一个空栈；判栈空，空栈返回True,否则返回False；进栈，在栈顶插入一个元素；出栈，在栈顶删除一个元素；取栈顶元素值；置栈为空状态；求栈中数据元素的个数；销毁栈；

……}ADTStack；

Page

109栈也有顺序存储和链式存储两种结构。注意对栈的操作只能在栈顶进行。

2.1栈的定义2.栈Page

1102.3栈的顺序存储结构（1）栈的顺序存储结构（2）顺序栈类定义（3）顺序栈的算法实现2.栈Page

1112.栈2.3栈的顺序存储结构（1）栈的顺序存储结构采用顺序存储的方式存储的栈称之为顺序栈。通常用一维数组来实现栈的顺序存储，设指针top指向栈顶元素的位置。将下标0设为栈底，这样空栈时栈顶指针top=-1；进栈时，栈顶指针top加１，当top达到数组的最大下标值时为栈满；出栈时，栈顶指针top减１。Page

112假设数组长度为10，栈操作的示意图如图所示。其中，图(a)是空栈，图(c)是A、B、C、D、E5个元素依次进栈之后，图(d)是在图(c)之后E、D相继出栈，此时栈中还有3个元素，或许最近出栈的元素D、E仍然在原先的单元存储，但top指针已经指向了新的栈顶，表示元素D、E已不在栈中了2.栈2.3栈的顺序存储结构2.栈2.3栈的顺序存储结构Page

113（2）顺序栈类定义栈采用顺序存储结构，其数组和栈顶指针作为类的数据成员,栈的各种操作可作为类的公用成员函数。顺序栈类定义如下constintMAXSIZE=100;typedefintElemType;//假设栈元素为整型classSqStack{private:ElemTypeelem[MAXSIZE]; //一维数组

inttop;//栈顶指针public:SqStack(){top=-1;}//构造函数，初始化一个空栈

~SqStack(){}; //析构函数

voidSetEmpty(){top=-1;}//置已有的栈为空栈

intIsEmpty(); //判断栈是否为空

voidPush(ElemTypee); //进栈

ElemTypePop(); //出栈

voidPrintOut(); //输出栈中数据元素

ElemTypeGetPop();//取栈顶元素数据}；2.栈（3）顺序栈的算法实现①输出栈中所有数据元素voidSqStack::PrintOut()//输出函数,不改变top{cout<<"\nPrintOutData:\n";if(top==-1)cout<<"\n空栈！"else{for(intk=top;k>=1;k--)

cout<<setw(6)<<elem[k];

cout<<endl;}}②判断栈是否为空int

SqStack::IsEmpty()//判断栈是否为空

{if(top==-1)return1;elsereturn0;}2.栈2.3栈的顺序存储结构Page

115③进栈操作假设要在栈顶插入数据元素e。首先判断栈是否为满，栈不满才能执行进栈操作。在进栈时，先使栈顶指针top自加1，然后使数据元素e进栈。算法实现如下：voidSqStack::Push(ElemTypee

）{if(top==MAXSIZE-1)cout<<“\n栈满溢出”<<endl; //判断栈是否为满

else{top++;elem[top]=e;//数据元素e进栈

}}

2.栈2.3栈的顺序存储结构Page

116④出栈操作假设要在栈顶删除数据元素e。首先判别栈是否为空，栈不空时才能出栈。出栈时先把栈顶元素值保存，然后栈顶指针top自减，最后返回删除的数据元素值。算法实现如下：

ElemTypeSqStack::Pop(){ElemTypex;if(top==-1){cout<<"\n栈为空，不能进行出栈操作"<<endl;x=0;}//表示未出栈else{x=elem[top];//出栈top--;}returnx;}Page

1172.栈2.4栈的链式存储结构用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，其结点结构与单链表的结构相同，链栈中数据元素结点描述如下：typedefcharElemType;//数据元素为字符型structLsnode

{ElemTypedata;Lsnode*next;};栈中的插入、删除运算是在栈顶进行的，显然使用链表的表头指针表示栈顶是最方便的。

Page

118链栈表示成图所示的形式。其中图（a）所示为3个数据元素A，B，C的栈，A是栈底元素（链表的尾结点），指针变量top指向栈顶元素C；图（b）所示为在图（a）的基础上出栈一个元素后的状态；图（c）所示为在图（b）的基础上进栈一个元素D后的状态。(a)(b)(c)2.栈2.4栈的链式存储结构Page

119（2）链栈类定义classLinkStack{private:

LSNodeType*top; //链表栈头指针public:

LinkStack(); //构造函数，初始化空链栈 ~LinkStack(){} //析构函数 voidDisplay(); //输出链栈的数据元素

voidPush(ElemTypee);

ElemTypePop(); };//类定义结束2.栈2.4栈的链式存储结构算法实现：进栈在链表首结点前插入数据出栈删除链表首结点算法与链表的插入与删除相同Page

1202.栈Page

121voidLinkStack::Push(ElemTypee){LSNodeType*p;p=newLSNodeType;p->data=e;p->next=top;top=p;}2.栈链栈的进栈算法：

p

topePage

122ElemTypeLinkStack::Pop(){ LSNodeType*p; ElemTypex; if(top==NULL)//判断是否为空栈 { cout<<"StackIsEmpty,CannotPop!\n"; x=-1;} else {

x=top->data; p=top; top=top->next; deletep;

} returnx;}链栈的出栈算法：

toppdata

topdataPage

1232.栈的应用例：数制转换将十进制数N转换为r进制，转换方法是除基逆序取余法。以N=3467，r=8为例转换方法如下所示：

NN/8（整除）N%8（求余）

34674333低

4335415466606