数据结构基础知识(1)

1. 线性结构

线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。

存储结构：

顺序存储：用一组地址连续的存储单元 依次存储线性表中的数据元素，使得逻 辑上相邻的元素物理上也相邻。

链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

2. 线性表

顺序存储和链式存储对比：

在空间方面，因为链表还需要存储指针，因此有空间浪费存在。

在时间方面，由顺序表和链表的存储方式可知，当需要对元素进行破坏性操作（插入、删除）时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。

而当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

3. 单链表

单链表的插入和删除

在上图中p所指向的节点后插入s所指向的节点，操作为：

s->next=p->next;

p->next=s;

同理，在单链表中删除p所指向节点的后继节点q时，操作为：

p->next=p->next->next;

free(q);

4. 栈和队列

队列、栈也是线性结构，结构如下图，队列是先进先出，分队头和队尾；

栈是先进后出，只有栈顶能进出。

循环队列中，头指针指向第一个元素，尾指针指向最后一个元素的下一个位置，因此，当队列空时，head=tail,当队列满时，head=tail，这样就无法区分了，因此，一般将队列少存一个元素，这样，队列满时的条件就变为tail+1=head，而考虑是循环队列，必须要除以最大元素数来取余数，即（tail+1）%size=head，如上图右边所示两个公式。循环队列的长度公式为（Q.tail-Q.head)%size。

优先队列：元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。使用堆来存储，因为其不是按照元素进队列的顺序来决定的。

5. 串

字符串是一种特殊的线性表，其数据元素都为字符。

空串：长度为0的字符串，没有任何字符。

空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度。

子串：串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，

空串是任意串的子串。

串的模式匹配算法：子串的定位操作，用于查找子串在主串中第一次出现的位置的算法。

基本的模式匹配算法：也称为布鲁特一福斯算法，其基本思想是从主串的第1个字符起与模式串的第1个字符比较，若相等，则继续逐个字符进行后续的比较；否则从主串中的第2个字符起与模式串的第1个字符重新比较，直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止，此时称为匹配成功，否则称为匹配失败。

KMP算法：对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的

“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。

6. 数组

数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组 是一种“同构”的数据结构，其每个数据元素类型相同、结构一致。

其可以表示为行向量形式或者列向量形式线性表，单个关系最多只有一个前驱和 一个后继，本质还是线性的。

数组结构的特点：数据元素数目固定；数据元素类型相同；数据元素的下标关系 具有上下界的约束且下标有序。

数组数据元素固定，一般不做插入和删除运算，适合于采用顺序结构。

数组存储地址的计算，特别是二维数组，要注意理解，假设每个数组元素占用存 储长度为len,起始地址为a.存储地址计算如下：