数据结构

线性表与顺序表

线性表：有限序列，除了第一个表项和最后一个表项之外，都有一个唯一的前驱和后继，第一个表项只有后继，最后一个表项只有前驱

顺序表：把线性表中所有的表项按照其逻辑顺序一致存储到一块（物理顺序）连续的存储空间中，即各个表项的逻辑顺序与其存放的物离顺序一致，对于顺序表中的所有表项，既可以顺序访问也可以随机访问

多维数组

值与多维下表的序对组成的集合

稀疏矩阵

可用三元组[InvalidCharacterError: "ROW,COLUMN,VALUE" did not match the Name production]

广义表

广义表：递归定义的表结构，允许表中有表，称其第一个元素为表头，之后的为表尾，表长定义为最外层表的元素个数

表中只有一个元素的时候，这个元素是表头，表尾为空集

单链表

单链表的插入删除操作时间复杂度为O(n)

在进行链表的插入删除操作时，注意指针修改

单链表的建立有前插法和后插法

循环链表

循环链表是尾节点的next指向头节点的链表

循环链表可用于实现循环队列

双向链表

每个节点都带有前驱指针和后继指针的链表

栈是一种后进先出（FILO）的线性数据结构

栈有两种存储表示：基于数组的顺序栈和基于链表的链式栈

顺序栈

顺序栈的栈顶未知由数组下标指针表示，栈非空时，下标为0的是栈最底部的元素，栈顶下标非负；栈为空时，栈顶下标为-1

链式栈

链式栈的栈顶在链表的表头（表头一般不存储元素），新节点的插入和栈顶节点的删除都在链表的表头即栈顶进行

队列是一种先进先出（FIFO）的线性数据结构，只允许从队尾入队，队首出队

循环队列

循环队列采用数组下标表示队首和队尾，队首为队首元素所在位置的下标，队尾为队尾元素的下一块存储空间的下标

对于存储在数组中的队列，为了充分利用出队后的剩余的存储空间，采用循环队列

出队时：front=(front+1)%maxSize

入队时：rear=(rear+1)%maxSize

注意maxSize为数组容量，下标为0,...,m的数组，大小为m+1，这个数组作为循环队列最多能存储m个元素，剩下一个单位的存储空间用做判断队列是否已满，下标为rear

链式队列

链式队列是基于链表存储的队列

队列的队头指针指向链表的第一个节点，队尾指针指向单链表的最后一个节点

双端队列

队列两端都可以弹出或者插入元素的队列

散列

散列是一种通过hash函数将值映射到键的线性数据结构

散列函数

1）除留余数法

设地址数为m，p为不大于m的最大的质数，散列函数定义为hash(key)=key\%p

使用此散列函数计算出来的地址范围是[0,p-1]

2）数字分析法

各个位置上符号出现次数的方差，方差小的位被选取用作确定hash地址

\lambda_k=\sum_{i=1}^r(num_i^k-n/r)^2

其中k是第k位，num_i是可能出现的符号的个数，n/r是出现个数的期望

3）平方去中法

将值的内码平方，并取中间的几位作为hash地址

4）折叠法

将值（或者值的内码）按照hash地址的位数折叠相加并去掉多出的高位得到hash地址

处理冲突的闭散列方法

1）线性探查法

H_i=hash(key+i)=(key+i)\%m,i=0,1,...,m-1

插入：从i=0开始，i[InvalidCharacterError: "M-1，若发生冲突则检查下一个地址，若对于I=0,...,M-1都有冲突，则插入失败<" did not match the Name production]