数据结构与算法笔记

数据结构与算法

第一周 绪论（略）

1.1什么是数据结构

1.2数据结构的基本概念（一）逻辑结构

1.2数据结构的基本概念（二）物理结构

1.3抽象数据类型

1.4什么是算法

1.5算法的分析与度量

第二周 线性表

2.1线性表的定义（一）概念和ADT

引入

线性结构

定义：结构中数据元素之间均满足线性关系

要学习的四种线性表：

• 线性表
• 栈：超栈、双栈
• 队列：超队列、双端队列
• 串

线性结构定义的解释：按照线性关系，把所有的元素排列成一个线性序列，除了第一个和最后一个元素之外的每一个元素有且只有一个直接前驱和一个直接后继（俗称的一对一关系）

image

线性表的相关概念

线性表（Linear List）：n（n>0）个数据元素组成的有限序列。

数据元素/节点：原子类型（简单）或结构类型（复杂）

• 由若干个数据项（item）组成的数据元素，也称为记录（record）
• 含有大量记录的线性表又称为文件
• 同一线性表中的元素必须属于同一数据对象

线性表的长度：线性表中元素的个数n

空表：n = 0的线性表

位序：

sdas

dasdas

在上面图示这个关系上每个元素最多有一个前驱节点和一个后继节点。

线性表的抽象数据类型定义

image

补充（PS）：

数据关系R1描述的就是一个线性关系：除了表头结点外每个元素有且只有一个后继。 DestroyList()跟ClearList()的区别：前者是将表的存储空间释放，后者只是将表恢复到空表状态，而存储空间并未释放。

基本操作：

PS：

LocateElem() 第三个参数传递的是函数指针，目的是提高该函数操作的通用性，如果表中的元素是较复杂的结构体类型，在不同的应用场景中所需要的判等操作可能不同这里只需要在调用时给出不同类型的判等函数指针就可以了。

image

PS：

ListDelet()中的visit()参数也是函数指针，用来传递访问函数，具体可以是printf()之类的输出操作，也可以是修改元素值等编辑操作，注意遍历也是后继各个数据结构必备的基本操作。 上述只是最基本的线性表的操作，对于不同的应用需求，线性表的基本操作集应进行相应调整，线性表的复制拆分合并等复杂操作可以用ADT里面的基本操作的组合来实现。

线性表符合操作举例

将复杂的操作利用组合起来的ADT基本操作来处理，详细见2.1线性表的定义（二）合并于归并中的两个案例。

2.1线性表的定义（二）合并于归并

并集算法

image

思路一：可以注意检查B中的每一个元素，如果A中没有该元素我们就将其插入到A中

image

image

PS：

怎么知道是否找到呢？可以根据LocateElem()操作的返回值，在ADT中约定如果找到就返回第一个与e满足与equal()关系元素的位序，否则就返回0

image

PS：

整个算法中时间复杂度最大的就是这个for循环，将一直执行Lb_len式，而每次for循环中又需要调用时间按复杂度为O(La_len)的LocateElem()操作，当这个表比较大时这个复杂度比较可观。

归并有序线性表算法

image

image

算法具体操作分析：

在LA跟LB两个有序的表中，先让排头两个元素进行比较，小的那个现出表，进入LC，如下先将7与3比较，3小所以先出，再将LA中的7与LB中的7比较，假设LA中的7出，再将LA中的15与LB中的7比较，LB中的7出，以此类推，直到一个表中的元素都排到新表中，另一个表中的剩余元素按照原来的顺序插入LC中即可。

image

image

PS：

与并集操作不同的是LA与LB中的元素都要插入到LC中。

2.2顺序表

2.3线性链表（一）单链表

2.3线性链表（二）静态链表

2.4循环链表和双向链表

2.5顺序表和线性链表的比较（一）顺序表与链表

2.5顺序表和线性链表的比较（二）各种链表的对比

2.6一元多项式的表示及运算