《大话数据结构》（一）

一、数据结构绪论

A.数据结构起源

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

2.程序设计=数据结构+算法

B.基本概念和术语

1.数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合

2.数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。

3.数据项：一个数据元素可以上若干个数据项组成。数据项是数据不可分割的最小单位

4.数据对象：是性质相同的数据元素的集合，是数据的子集

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

C.逻辑结构与物理结构

1.逻辑结构：数据对象中数据元素之间的相互关系

• 集合结构：数据元素除了同属于一个集合外，它们之间没有其他关系。
• 线性结构：数据元素之间是一对一的关系
• 树形结构：数据元素之间存在一种一对多的层次关系
• 图形结构：数据元素之间是多对多的关系

2.物理结构：指数据的逻辑结构在计算机中的存储形式

• 顺序存储结构：把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的（数组）
• 链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的

D.抽象数据类型

1.数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

C语言中数据类型：

• 原子类型，不可以再分解 的基本类型；
• 结构类型，由若干个类型组合而成，是可以再分解的；

2.抽象是指抽取出事物具有的普遍性的本质。

3.抽象数据类型（Abstract Data Type,ADT）：是指一个数学模型及定义在该模型上的一组操作。

• 抽象的意义在于数据类型的数学抽象特性。
• 一个抽象数据类型定义了：一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。
• 抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。

二、算法

A.算法

1.算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

B.算法的特性

1.输入输出：算法有零个或多个输入，算法至少有一个或多个输出

2.有穷性：指算法在执行有限的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成

3.确定性：算法的每一步骤都具有确定的含义，不会出现二义性

4.可执行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成

C.算法设计的要求

1.正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案

• 算法程序没有语法错误
• 算法程序对于合法的输入数据能够产生满足要求的输出结果
• 算法程序对于非法的输入数据能够得出满足规格说明的结果
• 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果

2.可读性：算法设计的另一目的是为了便于阅读、理解和交流

3.健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果

4.时间效率高和存储量低：时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间

D.算法效率的度量方法

1.事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。缺点：

• 必须依据算法事先编制好程序
• 时间的比较依赖计算机硬件和软件等环境因素
• 算法的测试数据设计困难

2.事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算

• 一个程序的运行时间，依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。
• 在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

E.函数的渐近增长

1.函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有n>N，f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)

2.最高次项相乘的常数并不重要

3.最高次项的指数大的，函数随着n的增长，结果也变得增长特别快

4.判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

5.某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法

F.算法时间复杂度

1.算法时间复杂度：在进行算法分析时，语句总执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作T(n)=O(f(n))。它表示问题规模的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

2.推导大O阶方法

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不是1，则去除与这个项相乘的常数

3.常数阶：与问题的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又称为常数阶

4.线性阶：分析算法的复杂度，关键就是要分析循环结构的运行情况，如一个为n的循环就是O(n)

5.对数阶：在循环中i*2之后，有多少个i*2就会大于n，由2x=n，x=log2n，时间复杂度为O(log2n)

6.平方阶：嵌套循环，例如两层循环，基本上心O(n2)为主

G.常见的时间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

H.最坏情况与平均情况

1.最坏情况是一种保证，除特殊情况，我们提到的运行时间都是最坏情况运行时间（最坏时间复杂度）

2.平均运行时间是最有意义的，因为它是期望的运行时间（平均时间复杂度）

I.算法空间复杂度

1.算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中n为问题的规模，f(n)为语句关于n所占存储空间的函数

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/1.c

三、线性表

A.线性表的定义

1.线性表（List）：零个或多个数据元素的有限序列。

2.线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

3.在较复杂的线性表中，一个数据元素可以由若干个数据项组成

B.线性表的顺序存储结构

1.线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

2.一维数组实现顺序存储结构，三个属性：存储空间的起始位置、线性表的最大存储容量、线性表当前的长度

3.数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的；线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作操作的进行，这个量是变化的。

4.存储器中每个存储单元都有自己的编号，这个编号称为地址

C.线性存储结构的插入与删除

1.插入算法思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入元素填入位置i处；
• 表长加1；

2.删除算法思路：

• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
• 表长减1；

3.线性表的顺序存储结构，在存、读数据时，时间复杂度为O(1)；在插入、删除时，时间复杂度为O(n)；

4.优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

5.缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 千万存储空间的碎片

D.线性表链式存储结构定义

1.为了表示每个数据元素ai与其直接后继元素ai-1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素ai的存储映像，称为节点（Node）。

2.n个结点（ai的存储映像）链结成一个链表，即为线性表的链式存储结构，因此，链表的每个节点中只包含一个指针域，所以叫做单链表。

3.链表中第一个节点的存储位置叫做头指针，通常会在单链表的第一个结点前附设一个结点，称为头结点。

E.线性表链式存储结构代码描述

1.结点由存放数据元素的数据域存放后继节点地址的指针域组成。

F.单链表的读取

1.获得链表第i个数据的算法思路：

• 声明一个结点p指向链表第一个结点，初始化j从1开始
• 当j<1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
• 若到链表末尾p为空，则说明第i个元素不存在
• 否则查找成功，返回结点p的数据

G.单链表的插入与删除

1.单链表第i个数据插入结点的算法思路：

• 声明一结点p指向链表第一个结点，初始化j从1开始
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
• 若到链表末尾p为空，则说明第i个元素不存在
• 否则查找成功，在系统中生成一个空结点s
• 将数据元素e赋值给s->data
• 单链表的插入标准语句s->next=p->next;p->next=s;
• 返回成功

H.单链表的删除

1.单链表第i个数据删除结点的算法思路：

• 声明一个结点p指向链表第一个节点，初始化j从1开始
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
• 若到链表末尾p为空，则说明第i个元素不存在
• 否则查找成功，将欲删除的结点p->next赋值给q
• 单链表的删除标准语句p->next=q->next
• 将q结点中的数据复制给e，作为返回
• 释放q结点
• 返回成功

2.对于插入或删除数据越频繁的操作，单链表的效率优势就越明显

I.单链表的整表创建

1.单链表整表创建的算法思路：

• 声明一结点p和计数器变量
• 初始化一空链表L
• 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
• 循环：生成一个新结点赋值给p；随机生成一数字赋值给p的数据域p->data；将p插入到头结点与前一新结点之间

J.单链表的整表删除

1.单链表删除的算法思路：

• 声明一个结点p和q
• 将第一个结点赋值给q
• 循环：将下一节点赋值给q；释放p；将q赋值给p

K.单链表结构与顺序存储结构优缺点

1.若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若要频繁插入和删除时，宜采用单链表结构。

2.当线性表中的元素个数变化较大或者根本不知道有多大时，使用单链表。

L.静态链表

1.用数组来代替指针，来描述单链表。

2.我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。

M.循环链表

1.将单链表中终端节点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的就是循环链表（circular linked list）

N.双向链表

1.双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/2.c

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/2-1.c

四、栈与队列

A.栈的定义

1.栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

2.允许插入和删除的一端称为栈顶（Top），另一端称为栈底（bottom），不含任何元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

3.栈是线性表。栈的插入操作，叫做进栈，也称压栈、入栈；栈的删除操作，叫做出栈，也称弹栈。

B.两栈共享空间

1.数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处，向中间靠拢。

C.栈的链式存储结构

1.简称链栈。不存在栈满的情况，除非内存用完。

2.如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些

D.栈的应用—递归

1.递归：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数称为递归函数。

2.每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

E.队列的定义

1.队列：队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

2.队列是一种先进先出（）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

3.循环队列：头尾相接的顺序存储结构称为循环队列；队列满的条件：（rear+1）%QueueSize==front；计算队列长度公式：(rear-front+QueueSize)%QueueSize

F.队列的链式存储结构

1.队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/4-1.c

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/4-2.c

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/4-3.c

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/4-4.c

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/4-5.c

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/4.c

五、串

A.串的定义

1.串（string）：是由零个或多个字符组成的有限序列，又名字符串

2.一般记为s=“a1a2a3……an”(n>=0)，串中的字符数目n称为串的长度，零个字符串被称为空串（null string）

B.串的比较

1.串的比较是通过组成串的字符之间的编码来进行的，而字符编码指的是字符在对应字符集中的序号

2.给定两个串，s(a1a2……an),t=(b1b2……bm)：

• 当n<m时，且a1==b1()
• 存在某个k<=min(m,n)，使得ai=bi(I=1,2……,k-1)

T=a b a c a a b a c a b a c a b a a b b（主串）

W=a b a c a b（模式串）

C.朴素的模式匹配算法

1.简单来说就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串作大循环，每个字符开头做T的长度小循环，直到匹配成功或全部遍历完成为止。T[0]==W[0]，如果T[1]!=W[1]，则再进行T[1]==W[0]

2.比较低效，时间复杂度O((n-m+1)*m)

D.KMP算法

1.时间复杂度：O(n+m)，仅当模式与主串之间存在许多“部分匹配”的情况下才体现出优势，否则差异不明显

2.基本思想（百度）：

• 在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
• 在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，现在T[0]~T[4]就是已经匹配的模式串子串，现在移动找出最长的相同的前缀和后缀并使他们重叠
• 例如：T[5]!=W[5]，下次从T[5]==W[0]开始

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/5.c