数据结构1
数据结构三要素
数据的逻辑结构
逻辑结构是指元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机id。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合，树，图是典型的非线性结构
- 集合：结构中的数据元素之间除同属一个集合外，别无其他关系
- 线性结构：结构中固定数据元素之间存在一对一的关系
- 树形结构：结构中的数据元素存在一对多的关系
- 图状结构或者网状结构。结构中的数据元素之间存在多对多的关系
数据的存储结构
存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素怒表示和关系的表示。数据存储是用计算机语言实现的逻辑结构，它依赖于计算机语言。数据存储的结构主要有顺序存储，链式存储和散列存储
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片
- 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的空间，且只能实现顺序存取
- 索引存储：在存储元素信息的同时，还简历附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字+地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外增加元素的关键字时也要修改索引表，因而会花费较多的时间
- 散列存储：根据元素的关键字直接计算出该元素怒的存储地址，又称hash存储，其优点是检索，增加和删除节点的操作都很快；缺点是函数如果散列不好，则可能出现元素的冲突，而散列冲突会增加时间和空间的开销
算法的概念
算法是对特定问题求解步骤的一种描述，它还是指令的有限序列，其中每条指令表示一个或多个操作。
特性
1)有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2）确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。3）可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4）输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
5）输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。通常，设计一个“好”的算法应考虑达到以下目标:
好的算法必须满足
1)正确性。算法应能够正确地解决求解问题。
2）可读性。算法应具有良好的可读性，以帮助人们理解。
3）健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4）效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。
时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频率和频度之和记为T（b），它是该算法问题规模n的函数，时间复杂度主要分析T(N)的数量级。算法中的基本运算，（最深层循环内的语句）的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f（n）来分析算法的时间复杂度，因此算法的时间复杂度记为
T(n)=O(f(n))
渐进时间复杂度
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^3)<O(2^n)<O(n!)<O(n^n)空间复杂度
空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数记为
S(n)=O(g(n))
一个程序执行时除需要存储空间来存放本身所用的指令，常数，变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，秩序分析除输入和程序之外的额外空间
算法原地工作是指算法所需的辅助空间为常量O(1)
线性表
定义
线性表是相同数据类型 n（n>=0）个数的有限序列，其中n为表长，当n=0时，线性表是一个空表.
a1是唯一的第一个元素,又称表头元素,an是唯一的最后一个元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。这种线性有序的存储结构正是线性表名字的由来
特点如下
- 表中元素个数有限
- 表中元素㕛逻辑上的顺序性，表中元素有先后次序
- 表中元素怒都数据元素，每个元素都是单个元素
- 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
- 表中元素具有抽象性，即仅讨论元素之间的逻辑关系，不考虑元素究竟表示什么内容
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系，顺序表和链表是存储结构，俩这属于不同层面的概念，请不要将其混淆
线性表的顺序表示
线性表的顺序存储又称顺序表，它是用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑上相邻的俩个元素在地址上也相邻。第一个元素存储在线性表的起始位置，第i个元素存储位置后面进阶这存储的是i+1个元素。因此顺序表的特点是，逻辑顺序与其物理顺序相同。
每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序正比常数，因此，线性表中的任一数据元素可以随机存取，所以线性表的存储结构是一种随机存取的存储结构。通常用高级程序语言的数组来描述线性表的顺序存储结构
注意：线性表中元素位的顺序是从1开始的，而数组中元素的下标是从0开始的
线性表的链式表示
顺序表可以随时存取表中任意一个元素，它的存储位置可以用一个简单只管的公式表示
但是插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过链建起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，只需要修改指针，但也会失去顺序表可随机存取的优点
单链表
线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，存放元素自身的信息外，还需要存放一个后继指针。
typeof struct LNode{ //定义单链表节点类型
ElemType data; //数据域
struct LNode *next; //指针域
}LNode，*LinkList;利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存储结构，即不能找到表中某个特定的节点。查找某个特定节点时，需要从表头开始遍历。
通常用头指针来标识一个单链表，如单链表L，头指针为Null时标识一个空表。此外为了操作上的方便，在单链表第一个节点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头节点的指针域指向线性表的第一个元素节点。
引入头结点后有俩个优点
- 由于第一个数据节点的位置被存放在头结点的指针域中，因此在链表上第一个位置上的操作和在表的其他位置上操作一致，无序特殊处理
- 无论链表是否为空，其头指针都指向头结点的非空指针(空表头节点的指针域为空)，因此空表的处理也就得到了统一
双链表
单链表节点只有一个指向其后继姐弟啊你的指针，使得单链表只能从头结点一次顺序地向后遍历。要访问某个前驱节点时，只能从头开始遍历，访问后继节点的时间复杂度为o(1)，访问前驱节点的复杂度为O(n)
为了客服单链表困难，引入了双链表，有俩个指针，prior和next，分别指向前驱节点和后继节点
循环链表
循环单链表和单链表的区别在于，表中最后一个指针不是null，而改为指向头结点，从而形成一个环
因此，循环单链表的判空调机不是头结点的指针是否为空，而是它是否等于头指针
循环双链表
由循环单链表的定义不难推出循环双链表，不同的是头结点的prior指针还要指向表尾节点
静态链表
静态链表借助数组来描述线性表的链式存储结构，节点也有数据域data和指针域next，与前面讲的链表指针不同的是，这里的指针是节点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要先分配一块连续的内存空间
栈队列和数组
栈
栈stack是只允许在一段进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入删除操作
- 栈顶：线性表允许插入和删除的一段
- 栈底：固定的，不允许插入和删除的另一端
- 空栈：不含任何元素的空表
栈的操作特性可以明显地概括为先进后出（Last In First Out LIFO）
顺序栈
栈是一种操作受限的顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针指示当前栈顶元素的位置
由于顺序栈的入栈操作，受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错
共享栈
利用栈底位置相对不变的特性，可以让俩个顺序栈共享一个一维数组空间，将俩个栈的栈底分别设置在共享空间的俩端，俩个栈顶向共享空间的中间延伸
俩个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空，仅当俩个栈顶指针相邻时，判断栈为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时则正好相反
共享栈是为了更有效地利用存储空间，俩个栈的空间相互调节，只有在整个存储空间被沾满时才会发生上溢。其存取的时间复杂度为O(1)，所以对存取效率没什么影响
栈的链式存储结构
采用链式存储的栈为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素
采用链式存储，便于节点的插入与删除。链栈的操作与链表类似，入栈和出站的操作都在链表的表头进行。带头结点和不带头结点的链栈，具体的实现会有所不同
队列
队列简称队，也是一种操作受限的线性表，只允许表的一端进行插入，而在表的一段进行删除。想队列中插入元素称为入队或者进队；删除元素称为出队或离队。这和我们日常生活中的排队是一直的，最早排队的也是最早离队的（First In First OutFIFO）
- 对头（front）允许删除的一端，又称队首
- 队尾（rear）允许插入的一端
- 空队列：不含任何元素的空表
队列顺序存储
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素， 并附设俩个指针，队头指针front指向队头元素，队尾指针rear指向队尾元素下一个位置。
初始状态队空调机Q.front==Q.rear==0
进队操作：队不满时，先送值到队尾元素，再将队尾指针+1
出队操作：队不空时，先取队头元素值，再将对头指针+1
循环队列
前面已经指出了顺序队列的缺点，这里引入循环队列的概念。将顺序队列臆造为一个环形的空间，即把存储队列元素的表从逻辑上视为一个环，称为环形队列
当队首指针Q.firnt=maxSize-1后，再前进一个位置就自动到0，这可以利用触发求余运算（%）来实现
那么循环队列队空和队满的判断条件是什么呢？显然，队空的条件是Q.front==Q.rear若此时入队元素的速度快于出队的元素的速度，则队尾指针就会很快赶上队首指针，此时可以看出队满也有Q.front=Q.rear
- 牺牲一个单元来区分空和对满，入队时少用一个队列单元，这是一种较为普遍的做法
- 队列增加表示元素个数的数据成员，这样判断Q.size==0；Q.size==maxSize
- 类型中增设tag数据成员，以区分队满还是队空，若因删除导致Q.front==Qrear，则为队空；tag等于1时，若因插入Q.front==Q.rear则为队满
链式存储队列
队列的链式存储称为链队列，它实际上是一个同时带有头尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点，
出队时先判断队是否为空，若不为空，则去除队头元素，将其从链表中摘除，并让Q.front指向下一个节点（若该节点为最后一个节点，则Q.front和Q.rear都为null）。入队时新建一个节点，将新节点插入到链表的尾部，并让Q.rear指向这个新插入的节点（若原队列为空，令Q.front也指向该节点）
不难看出不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。
但链表表示的链式队列特别合适与数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。另外加入程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理溢出的问题
双端队列
双端队列是只俩端都可以进行入栈和出站操作的队列。其他逻辑结构仍然是线性结构。队列俩端分别是前端和后端，俩端可以入队和出队
在双端队列进队时，前端的元素排列在队列中后端进的元素的前面，后端进的元素的前面，后端进的元素排列在队列中前端进的元素后面。在双端队列出队时，无论是前端还是后端出队，先出的元素排列在后出的元素前面。
输出受限的双端队列：允许在一段进行插入和删除，但在另一端只允许插入的双端队列称为输出首先的双端队列
输入受限的双端队列：允许在一段进行插入和删除，但在另一端只允许删除的双端队列称为输入寿险的双端队列，若限定双端队列从某个端点插入的元素只能从端点删除，则该双端队列就蜕变为俩个栈底的相邻接的栈
数组和特殊矩阵
数组
数组是由n个相同类型元素构成的有限序列，每个元素称为一个数组的元素，每个元素在n个线性关系中序号称为该严肃的下标，下标的取值范围称为数组的维界。
数组和线性表的关系：数组是线性表的推广。一维数组可以视为一个线性表，二位数组科士威其元素也是定长线性表的线性表。以此类推，数组一旦被定义，其维数和维界就不再被改变。因此，除结构的初始化和销毁外，数组只有存取元素和修改元素的操作
特殊矩阵压缩存储
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间
特殊矩阵：指具有许多相同举证元素或零元素，并且这些相同举证元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有堆成矩阵，对角矩阵等
特殊矩阵的压缩存储方法：找出特殊举证中值相同的矩阵元素的分布规律，把那些呈现规律性分布的，值相同的多个举证元素压缩存储到一个存储空间中
对称矩阵
若对一个n阶方阵，A[1...n][1...n]中任意一个元素都有a[i][j]=a[j][i]则成为对称矩阵。
对于n阶对称举证，上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费一半的空间，为此将对称矩阵A[1...n][1...n]存放在一维数组B[n(n+1)/2]中，即元素a[i][j]存放在bk中，只存放下三角部分（含主对角的元素）
第一行：第一个元素a[1][1]
第二行：第一个元素a[2][1]
第三行：第一个元素a[2][1]
三角矩阵
下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角去和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵A[1...n][1..n]压缩存储在B[n(n+1)/2+1]中
上三角矩阵中，下三角区的所有元素均为同一常量
(i-1)(2n-i+2)/2+(j-i) i<=上三角区和对角线元素 （默认为0开始的情况下）
n(n+1)/2 i>j(下三角区元素)三对角矩阵
对角矩阵也称带状矩阵。对于n阶方阵A中华任一元素a[i][j]当|i-j|>1时，有a[i][j]=0则为三对角矩阵
在三对角矩阵中，所有非0元素都几种在以主对角线为中心的3条对角线的区域，其他区域的元素都为0
三对角矩阵A也可以采用压缩存储，将3条对角线上的元素按优先方式存放在一维数组B中，且a[1][1]存放于B[0]中
k=2i+j-2 从1开始，0开始就是k=2i+j-3
稀疏矩阵
矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵，列如一个矩阵的阶为100*100，该矩阵中只有少于100个非零元素
若采用常规的方式存储稀疏矩阵非常浪费空间，因此仅存储非零元素。但通常非零元素的分布没有规律，所以还要存储它所在的行和列。
稀疏矩阵存取后便失去了随机存取的特性
稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储
串
字符串简称串，计算机上非数值处理的对象基本都是字符串数据。我们插件的信息检索系统（如搜索引擎），文本编辑程序，问答系统，自然语言翻译系统等，都是以字符串数据作为处理对象的
串的定义
串（string）是由零个或多个字符组成的有限序列，一般记为S='a1a2a3a4'
其中s是串名，单引号括起来的字符串序列是串的值，ai可以是字幕，数字或其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串
串中任意多个连续的字符自称的子序列称为该串的子串，包含子串的串称为主串。某个 字符在串中的序号称为该字符在串中的位置。子串在主串中的位置，以子串的第一个字符在主串中的位置来表示。当俩个传的长度相等且每个对应位置的字符都相等时，称这俩个串是相等的
需要主义，一个或多个空格（空格是特殊字符）组成的串称为空格串（空格串不是空串）其长度为串中空格字符的个数
串的逻辑结构和线性表极为相似，区别仅在于串的数据结构限定为字符集。在基本操作上，串和线性表有很大的差别。线性表的基本操作主要以单个元素作为操作对象，如查找，插入，删除某个元素等；而串的基本操作通常以子串作为操作对象，如查找，插入删除一个子串等
串的存储结构
定长顺序结构表示
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串定长顺序存储结构中，为每个变量分配一个固定长度的存储区，即定长数组
#define MAXLEN 255 //预定义最长串为255
typedef struct{
char ch [MAXLEN]; //每个分量存储一个字符
int length; //串的实际长度
}SString串的实际长度只能小于等于MAXLEN，超过预期定长的从串值会被舍去，称之为截断。串长有俩种表示方法：一是如上述定义描述的那样，用一个额外的变量len来存放串的长度；二是在串的值后面加一个不计入串场的结束标记字符“0”此时串长为隐含值
在一些串的操作（如插入，联接）中，若串值序列的长度超过MAXLEN，约定用截断法处理，要克服这种弊端，只能不限定串的最长长度，即采用动态分配的方式
堆分配存储表示
堆分配存储表示仍然以一组地址连续的存储大院存放串值的字符序列，但它们的底层空间是在程序执行过程中动态分配得到的
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length; //
}HString在c语言中，存在一个称之为堆的自由存储区，并用malloc()和free()函数来完成动态存储管理。利用malloc()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基地址，这个串由ch指针来指示；若分配失败，则返回null。已分配的空间可用free()释放掉
上俩种存储表示通常为高级程序语言设计所用，块链存储表示仅做简单介绍
块链存储表示
类似于线性表的链式存储结构，也可采用链表方式存储串值。有意义串的特殊性（每个元素只有一个字符），在具体实现时，每个节点既可以存放一个字符，也可以存放多个字符。每个节点称之为块，整个链表称为快链结构
