数据结构

一、数据结构绪论

一）基本概念和术语

（1）数据结构

• 数据(data)是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

• 数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由多个数据项组成，例如一本书可以由书名、作者等等组成。

• 数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。

• 数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。通常有以下四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。数据结构的形式定义为：数据结构是一个二元组Date_Structure = (D, S)，其中， D是数据元素的有限集，S是D上关系的有限集。

• 数据结构：

  • 逻辑结构

  • 存储结构（物理结构）：是数据结构在计算机中的表示（又称映像）。

• 数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，对应两种不同的存储结构：顺序存储结构和链式存储结构。

• 数据类型(data type)是数据对象集和在该集上的操作的总称。

• 抽象数据类型(AbstractData Type)是指一个数学模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。

（2）算法

• 算法是对特定问题求解步骤的一种描述，算法特性：有穷性、确定性、可行性、输入、输出。

  

• 算法的度量（算法分析的两个主要方面）：

  • 时间复杂度
  • 空间复杂度

  一般更偏向于计算最坏情况复杂度。

  • 语句的频度：每条语句的执行次数。

  • 我们把算法所耗费的时间定义为该算法中每条语句的频度之和。例：该算法的时间消耗T(n) =

  • 时间复杂度的渐进表示法：（为了便于比不同算法的时间效率，我们仅比较它们的数量级）
    则有：

    

    简而言之，算法的时间复杂度就是所有语句频度之和的数量级。在实际求的过程中直接看算法中嵌套层数最深的语句（也就是基本语句）执行次数的数量级（即f(n)）即可。

    

  • 分析时间复杂度的ji小技巧：（当一个算法直接求时间复杂度数量级难以确定时，可以考虑拆分为几个算法，若这些子算法为先后顺序，则原算法时间复杂度为子算法时间复杂度中的数量级最高阶的时间复杂度，若为嵌套关系，则原算法的时间复杂度为子算法时间复杂度的数量级的乘积）
    例1：

    例2：

    例3：

    

    注意：有时候算法中基本操作重复的次数还因为问题输入的数据集不同而不同。例如：

    

  • 时间复杂度O(1), O(n), O(logn), O(nlogn) 的区别：

  • 渐进空间复杂度
    
    例：
    

• 衡量一个算法是否优秀，则主要从以下几点考虑：正确性，可读性，健壮性，时间复杂度，空间复杂度。

二、线性表

【总纲】

一）线性表的定义和特点

同一个线性表中的元素必定具有相同特性，数据元素之间的关系是线性关系。

线性表的逻辑特征

二）案例引入

若多项式为一元稀疏多项式，例如：

用上面的方法可能会导致大量空间的浪费，因此可以采用如下方法来实现：

当两个稀疏多项式相加时：

以上为用数组这种顺序结构来实现的方式，下面再看链式存储结构的方法：

三）线性表的类型定义

定义：

基本操作：

四）线性表的顺序表示和实现

（一）基本知识

线性表示的优点：任一元素均可随机存取。

可以用一维数组表示线性顺序表，但是顺序表的长度可变，而数组的长度一般不可变。因此采用结构体的方式来表示顺序表，结构体有一个数据元素的数组和一个整数组成，整数记录顺序表的长度。

顺序表的定义模板：

例：

【补充】

typedef int ElemType;   //起别名，此时ElemType就是int，两者相等。即int a等效于 ElemType a。

区别：数组是基于指针实现的，数组名表示的其实就是数组第一个元素的地址也就是数组的基地址。第一种方法相当于同时设置了数组的基地址和数组的大小，而第二种方法只设置了数组的基地址而没有设置数组的大小，这更加符合顺序表长度可变的特点。

在使用第二种方法时，按C语言语法用如下方法给数组分配空间：

注：需要头文件：<stdlib.h>。前面的括号里的ElemType*存在的意义是将这些得到的空间按哪种变量的方式来分。例如若为(char *)malloc(800)就表示将800字节的空间按一个字节一个空间分配为800个，若为(int *)malloc(800)则表示将800个字节按4个字节一个空间，分成200个空间。

除了使用c语言语法的动态存储分配之外，有时候还会使用c++的语法来实现，可以使得算法看起来更加简短，

使用引用类型做参数传值比传指针和传数组更加方便，而且时间和空间效率都好

（二）顺序表简单操作算法实现：

【预定义常量和类型】

（1）初始化线性表

（2）销毁、清空线性表

（3）求线性表的长度、判断是否为空

（4）在顺序表中取值

（5）查找算法

方法一：

方法二：

【算法分析】

（6）插入算法

【算法分析】

（7）删除算法

【算法分析】

（三）总结

【顺序表优缺点】

五）线性表的链式表示和实现

链表中的每一个结点由数据域（存储元素数值数据）和指针域（存储直接后继结点的位置 ）组成。另外，第一个结点的位置由头节点来确定。最后一个结点的指针域为NULL

单链表是由头指针唯一确定，因此单链表可以由头指针的名字来命名。

单链表（线性链表）：结点只有一个指针域的链表。

双链表：结点有两个指针域的链表。（一个存储直接前驱元素的地址，一个存储直接后继元素的地址）

循环链表：首尾相接的链表。（最后一个结点存储的是头节点或者首元节点的位置）循环链表又可以分为单循环链表和双循环链表。

头指针：指向链表中第一个元素的指针。

首元节点：链表中存储第一个元素的结点。

头节点：在链表的首元结点之前附设的一个结点。

如何表示空表？

• 无头结点时，头指针为空时表示空表。
• 有头结点时，头节点指针为空时表示空表。、

设置头节点有什么好处？

• 便于首元结点的处理：首元节点的位置保存在头结点的指针域中，所以链表第一个位置上的操作与其他位置一致，不须要进行特殊处理。
• 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头节点的非空指针，因此空表和非空表的处理也就一致了。

头结点的数据域：可以为空，也可以存放线性表长度等附加信息，但是该结点不能计入链表的长度值。

链表（链式存储结构的特点）：

（一）单链表

1、命名

单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名。若头指针名是L，则把链表称为表L。

2、定义

例：

3、单链表基本操作的实现

1）初始化操作

2）判断链表是否为空

3）销毁单链表

步骤为一个一个销毁每一个结点。先新初始化一个该链表结点类型的指针，当L不为空时，先让p = L，即p和L指向同一个结点，再通过L ->next使L指向下一结点，再删除p对应的结点。当L为空时，说明p指向了最后一个结点，再删除p指向的结点后，删除操作完成。

补充：若p是指向线性表中的第i个元素（ai）的指针，则p->next则是指向第i+1个元素的指针。换句话说，若p->data = ai, 则p->next->data = ai+1

4）清空链表

说明：链表仍存在，单链表中无元素，成为空链表（头指针和头结点仍存在）具体操作与删除类似。

5）求链表的表长

6）在单链表中取值

7）查找

（返回地址）

（返回位置序号）

8）插入

9）删除

【查找、插入、删除的时间复杂度】

10）单链表的建立

（1）头插法

（2）尾插法

（二）循环链表

1）带尾指针的循环链表的合并

将表Tb的所有结点接在表Ta的后面，操作完成后的结点用Tb表示（因为使用的是尾指针操作的）

（三）双向链表

1）双向链表的插入

2）双向链表的删除

根据具体问题选择最合适的结构，需要注意，虽然双向循环链表的时间复杂度都是O（1），但是占用的空间较大。

六）顺序表和链表的比较

七）线性表的应用

（一）线性表的合并

（二）有序表的合并

算法的时间复杂度是O(ListLength(La) + ListLength(Lb))

算法的空间复杂度是O(1)

八）案例分析与实现

（一）两个多项式的相加（顺序表）

（二）稀疏多项式相加

使用顺序表时：

使用顺序表时间和空间复杂度较高，故采用链表来进行求解。

（三）图书信息管理

三、栈和队列

一）栈（stack）的介绍

定义：栈是仅在表尾进行插入、删除操作的线性表。表尾（即an端）称为栈顶Top；表头（即a1端）称为栈底Base。a1称为栈底元素，an称为栈顶元素。插入元素到栈顶的操作成为入栈，从栈顶删除最后一个元素的操作，称为出栈。

特点：后进先出（Last In First Out，简称LIFO结构）。例如：洗好的盘子叠成一摞，我们在使用的时候最先取得是最后一个洗好放上去的盘子。

栈的示意图：

逻辑结构：与线性表相同，都是一对一关系。

存储结构：用顺序栈或者链栈存储皆可，但顺序栈更加常见。

运算规则：只能在栈顶运算，访问结点时按照后进先出的原则。（与线性表的唯一不同的点）

实现方式：主要在实现入栈和出栈的函数，具体实现方式依顺序栈和链栈的不同而不同。

栈的应用：

二）队列（queue）的介绍

定义：在表的一端（表尾/队尾）插入，在表的另一端（表头/队头）删除的线性表。（头删尾插）插入元素称为入队，删除元素称为出队。

特点：队列（queue）是一种先进先出（First In First Out，简称FIFO）的线性表。例如：排队做核酸，先来的人先做完走，后来的人在队尾排队。

逻辑结构：与线性表相同，都是一对一关系。

存储结构：用顺序队或者链队存储皆可，以循环顺序队列更常见。

运算规则：只能在队首和队尾运算，访问结点时按照先进先出的原则。（与线性表的唯一不同的点）

实现方式：主要在实现入队和出队的函数，具体实现方式依顺序队和链队的不同而不同。

队列的应用：（处理类似排队的问题）

三）两者的区别

栈和队列都只能在表尾进行插入操作，不同的是在栈中只能删除表尾元素，而在队列中只能删除表头元素。

四）案例引入

（一）进制转换

通过入栈和出栈实现

（二）括号匹配

（三）表达式求值

（四）舞伴问题

五）栈的表示和操作的实现

栈的抽象数据类型的类型定义

（一）栈的顺序表示和实现

1）基本概念

栈中元素个数 = top – base

2）操作实现

（1）初始化

（2）判断栈是否为空

（3）求栈的长度

（4）清空顺序栈

（5）删除顺序栈

delete用于回收new分配的空间，上面操作中先用delete回收数组内存，再将两个指针都设置为空。

（6）顺序栈的入栈

*运算是对 指针所指的空间进行运算。

（7）顺序栈的出栈

（二）栈的链式表示和实现

1）基本概念

注意：

• 一般来说链栈的指针方向和链表中的相反，这样操作比较方便。其实所有的结构都是灵活的，都可以可灵活调整。
• 链栈的头指针指向栈顶。
• 链栈没有头结点。（因为栈都是在头部进行操作的，如果加了头结点等于要对头结点之后的结点进行操作，反而使算法更复杂）
• 基本不存在栈满的情况。（除非内存被用光）
• 空栈相当于头指针指向空。
• 插入和删除仅在栈顶处执行。

2）操作实现

（1）初始化

（2）判断链栈是否为空

（3）链栈的入栈

（4）链栈的出栈

（5）取栈顶元素

六）栈和递归

（一）递归

1）递归的定义：

2）用到递归方法的情况：

• 递归定义的数学函数
  

• 具有递归特性的数据结构
  

• 可递归求解的问题：迷宫、汉诺塔。

3）必备条件：

4）递归问题算法的一般条件：

5）递归算法与栈的关系

递归算法要靠栈来实现

6）递归的优缺点

7）将递归转化为非递归的方法

（1）尾递归、单项递归——>循环结构

尾递归（尾部有递归）

缺点：改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性较差，有的还需要经过一系列优化。

（2）自用栈模拟系统的运行时栈

（二）函数调用

1）函数调用过程：

2）当多个函数构成嵌套调用时：也要用栈来实现

遵循后调用的先返回的规律（与栈的先进先出原则相同），所以要实现函数的嵌套调用，就是通过栈来实现。

七）队列的表示和操作的实现

队列的抽象数据类型定义

（一）队列的顺序表示和实现

1）队列的顺序表示

队列为空的条件：front = rear。

可能存在的问题：

1. 真溢出
   
2. 假溢出
   

解决假溢出的方法：

但这样的话会导致无法判断队满还是队空，因为标志都是rear = front。

解决方法：
（1）少用一个元素空间。

（2）设一个标志来区别队列是否为空。
（3）另设一个变量，记录元素个数。

2）操作实现（采用少用一个元素空间的方法）

（1）初始化

（2）求循环顺序队列的长度

（3）循环顺序队列的入队

（4）取队头元素

（二）队列的链式表示和实现

1）队列的链式表示

若用户无法估计所用队列的长度，则宜采用链队列。

2）操作实现

（1）链队列的初始化

（2）链队列的销毁

算法思想：从头结点开始依次释放所有节点。

（3）链队列的入队

（4）链队列的出队

四、串、数组和广义表

一）串

（一）串的定义

原文地址：http://www.cnblogs.com/athonal0/p/16913205.html