数据结构--严蔚敏（C语言版）笔记_数据结构c语言版严蔚敏

目录

第一章 绪论

1.1 复习笔记

一、 什么是数据结构

二、 基本概念和术语

三、 抽象数据类型的实现

四、 算法和算法分析

第二章 线性表

一、线性表的类型定义

二、线性表的顺序表示和实现

1. 顺序表存储结构的表示

2. 顺序存储结构的特点

三、 线性表的链式表示和实现

1.定义

2.链式存储结构的特点

3.链式存储结构的分类

第三章 栈和队列

一、 栈

1. 栈的定义与基本操作

2. 栈的表示和实现

二、栈的应用举例

1. 括号匹配

2. 表达式求值

三、栈与递归的实现

1. 递归的定义

2.栈在递归中的运用

---

---

第一章 绪论

1.1 复习笔记

---

一、 什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

二、 基本概念和术语

1. 数据

数据是对客观事物的符号表示，是计算机科学中所有能输入到计算机中并能被计算机处理的符号的总称。

2.数据元素

数据元素是数据的基本单位。

3. 数据对象

数据对象是性质相同的数据元素的集合，是数据的一个子集。

4. 数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

（1） 数据结构的基本结构

根据数据元素之间的不同特性，通常有下列四类基本结构：

1. 集合。数据元素属于“同一个集合”，并无其他复杂关系；

2. 线性结构。数据元素之间存在一个对一个的关系；

3. 属性结构。数据元素之间存在一个对多个的关系；

4. 图状结构或网状结构。数据元素之间存在多个对多个的关系。

（2）数据结构的形式定义

数据结构的形式定义为Data _Structure = (D,S)

其中，D表示数据元素的有限集，S表示D上的关系集。

（3）数据结构在计算机上的表示

数据结构包括数据元素的表示和关系。在计算机中称为数据的物理结构（又称存储结构）。

其中，关系有两种表示方法：顺序映像和非顺序映像。这两种分别对应两种存储结构：顺序存储结构和链式存储结构。

• 顺序映像：用相对位置来表示数据元素之间的逻辑关系。

• 非顺序映像：用指针表示数据元素之间的逻辑关系。

5. 数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

6.抽象数据类型

抽象数据类型（ADT）由一个值域和定义在该值域上的一组操作组成。

【注意】抽象数据类型是对数据类型架构的一种全局体现，使我们能够更加清晰地看待某一数据类型。

7. 多形数据类型

成分不确定的数据类型。

8. 数据操作的类型

从操作的特性来看，所有的操作可归结为两类：

加工型操作：增、删、改、排序。

引用型操作：查。

9. 算法

算法是对特定问题求解步骤的一种描述。它是指令的有限序列。其中每一个指令代表一个或多个操作。

特性

• 有穷性

• 确定性

• 可行性

• 输入

• 输出

三、 抽象数据类型的实现

四、 算法和算法分析

1. 算法的描述

算法需要一种语言来描述，程序框图、程序设计语言等都能对算法进行描述。

2. 算法设计的要求

• 正确性

• 可读性

• 健壮性

• 效率与低存储要求

3. 算法效率的度量

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。度量一个程序的执行时间通常有两种方式：

1. 事后统计

2. 事前分析估算

   • 事先考虑消耗时间的因素

   • 时间复杂度

时间复杂度是关于问题规模的函数，通常用O表示，常见时间复杂度按照数量级递增排列为：O（1）＜O（log2n）＜O（n）＜O（nlog2n）＜O（n^2） ＜O（n^3） ＜O（n^k） ＜O（2^n）

4. 算法的存储空间需求

算法的空间复杂度是对算法运行所占空间的度量。

在度量时一般只考虑算法运行所需额外开销的多少，包括算法实现时定义的中间变量，数组等对存储空间的影响。

原地工作：算法运行所需的额外空间相对输入数据量是常量。

第二章 线性表

一、线性表的类型定义

1.线性表的定义含有n个相同数据类型的数据元素的有限序列称为线性表。

一般可表示为：L＝（a1，a2，…，ai－1，ai，ai＋1，…，an－1，an）；

【说明】ai－1是ai的直接前驱元素，ai＋1是ai的直接后继元素。

线性表中数据元素的个数n（n＞0）为线性表的长度。当n＝0时称线性表为空表。线性表是最常用且最简单的一种数据结构。

2.线性表的基本操作

（1）INITIATE(L)：初始化操作。

（2）LENGTH(L)：求线性表长度。

（3）GET(L,i)：取元素函数。

（4）PRIOR(L,elm)：求前驱函数。

（5）NEXT(L,elm)：求后继函数。

（6）LOCATE(L,X)：定位函数。

（7）INSERT(L,i,b)：前插操作。

（8）DELETE(L,i)：删除操作。

（9）EMPTY(L)：判空表函数。

（10）CLEAR(L)：表置空操作。

二、线性表的顺序表示和实现

1. 顺序表存储结构的表示

顺序存储结构（又称顺序表），是一种随机存取的结构，逻辑关系上邻近的元素在物理位置上也相邻。 数组是表示顺序结构的最简单的方式。只要确定了顺序表的起始位置，线性表中任意元素都可随机存取。

 

2. 顺序存储结构的特点

【优点】

1. 它是一个记录型的结构。数据元素的存储位置可以用数组的下标来表示。

2. 在顺序存储结构中，线性表的一些操作容易实现，如求表长。

【缺点】

1. 在进行插入或删除时，需要移动大量元素。

2. 在给长度变化较大的线性表进行空间预分配时，要按最大空间分配，这样容易造成空间浪费。

3. 表的容量难以扩增。

三、 线性表的链式表示和实现

链式存储结构，由于它不要求逻辑上相邻的元素在物理上也相邻，因此，它没有顺序表结构所存在的缺点。

1.定义

借助指针等手段表示数据元素ai和后继元素ai+1之间的关系，ai不仅存储本身的信息，还存储指向后继的指针。数据元素和后继指针合起来称为一个节点，n个节点链接成一个链表，即线性表的链式存储结构。

2.链式存储结构的特点

1. 不要求逻辑上相邻的元素在物理结构上也相邻。

2. 数据元素之间的逻辑关系是由节点中的指针指示的。

3.链式存储结构的分类

链式结构存储种类繁多，按照实现的方式不同，可分为借助指针实现的链式存储结构和借助数组实现的链式存储结构。

（1） 借助指针实现的链式存储结构

1.单链表

在单链表中，对于每个节点而言，它不仅存储本身的信息，还存储着指向后继元素的指针。

 

2.双链表

双链表的节点中除了数据域外，还有两个指针域，一个指向直接后继，一个指向直接前驱。

在双链表中，有些操作如Length(L)、Get(L,i)、Locate(L,x)等仅需要一种方向的指针；但在插入、删除时，需要修改两个方向上的指针。

 

删除操作

 

 

插入操作

 

 

 

3.循环链表

循环链表是一种首尾相连的链表，它的最后一个节点的指针指向头结点。形成一个闭环。

循环链表包括单循环链表和双循环链表。

单循环链表

双链表也可以有循环链表

 

双向循环链表

（2） 借助数组实现的链式存储结构——静态链表

预先分配较大的空间，利用数组下标将逻辑上相邻的元素链接起来的特殊链表叫做静态链表。

其中插入删除操作具有和指针实现的链表一样的优点。

下图所示线性表在插入数据元素“SHI”和删除数据元素“ZHENG”之后的状况。

 

【注意】

1. 采用指针实现的链式存储结构是非随机存取的数据结构。

2. 头节点和头指针的区别

    

   头节点是链表的第一个节点之前附加的一个节点，（该节点可以不存储任何信息，也可以存储链表长度等信息）从而使链表的第一个节点的操作和其他节点在处理问题上保持一致。

   头指针是为了表示一个链表而产生的，当链表存在头节点时，则头指针指向头节点，当链表不存在头节点时，指针指向链表的第一个元素（也可能为空）。

   如图所示，单链表的头指针指向头节点。若线性表为空，则头节点的指针域为空。

第三章 栈和队列

一、 栈

1. 栈的定义与基本操作

（1） 栈的定义

栈是被限定只能在表尾进行插入和删除的线性表。栈中数据元素同属一种数据类型，元素之间呈线性关系。

假设栈中有n个数据元素a1，a2，…，an，则对每一个数据元素ai，都存在关系<ai，ai＋1>，并且a1无前驱，an无后继。

其中，表尾端称为栈顶，表头端称为栈底。不含元素的栈称为空栈。栈的修改遵循后进先出的原则。因此，栈又称为后进先出线性表（LIFO）。就跟我们上弹夹一样，第一个上进去的子弹是最后打出来的。

 

（2） 栈的基本操作

①INISTACK(S)：初始化函数。

②EMPTY(S)：判栈空函数。

③PUSH(S,x)：入栈函数。

④POP(S)：出栈函数。

⑤GETTOP(S)：取栈顶元素函数。

⑥CLEAR(S)：栈置空操作。

⑦CURRENT-SIZE(S)：求当前栈中元素个数函数。

2. 栈的表示和实现

（1）顺序栈

顺序栈即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。同时设指针top指示栈顶元素的当前位置。

栈满：top=arrmax时表示栈满，此时不能进行入栈等操作。

栈空：top= 0时表示栈空，此时不能进行出栈和取栈顶灯操作。

【注意】共享栈表示两个栈共享一个数组空间，也是顺序栈的一种。它将两个栈的栈底设置在数组的两端（即top1=-1，top2 = maxsize为栈空），入栈则分别向数组的中间位置靠近，若两栈相遇，则栈满。

（2）链栈

采用链式存储结构的栈叫做链栈。一个链栈由其栈顶指针唯一确定，且链栈一般不存在栈满的情况。

 

二、栈的应用举例

1. 括号匹配

括号匹配算法如下：

①初始化一个空栈，从顺序表中顺序读取括号。

②当读到左括号时，进行入栈，且该左括号具有当前等待匹配的括号中的最高优先级。

③当读到右括号时，进行出栈，从栈顶取出具有最高优先级的括号，看是否与右括号相匹配，当栈空且读完表达式中所有括号，算法结束。

【注意】当表达式中出现了其他形式的括号时，步骤不变。

2. 表达式求值

算符优先发算法如下：

①定义两个栈，一个用于存放运算符（OPTR栈），另一个用来存放操作数和运算结果（OPND栈）。

②置操作栈为空（OPND），表达式#为运算符栈（OPTR）的栈底

③依次读入表达式中的字符，若该字符为操作数，则进入OPND栈；若是运算符，则与OPTR中的栈顶元素#进行优先级比较。若该字符优先级低于OPTR的栈顶元素，则需要将栈顶元素带入相关运算后进行入栈操作；反之则直接入栈，直到求得结果。

三、栈与递归的实现

1. 递归的定义

一个直接调用自身或通过一系列过程调用语句间接调用自身的过程，称为递归。

（1） 分类

①直接递归②间接递归

（2） 优缺点

优点：能将原始问题转化成属性相同但规模较小的子问题，程序更加易读，结构更加清晰。

缺点：递归程序时空复杂度一般比非递归程序高，运行效率也更低。

2.栈在递归中的运用

栈一般运用在递归程序转换为非递归程序中，将原本由系统管理的递归过程改为由程序员管理。在非递归程序中，栈主要有两个作用。

1. 将本层递归调用时的实际参数和返回地址传递给下一层递归。

2. 保存本层参数和局部变量，从下一层返回本层时继续恢复使用。