数据结构与算法（1）

1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位

2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算

3、主要的数据存储方式：顺序存储结构（逻辑和物理相邻，存储密度大）和链式存储结构

顺序存储结构：

顺序存储计算公式 Li＝L0＋(i－1)×K 顺序结构可以进行随机存取；插人、删除运算会引起相应节点的大量移动

链式存储结构：

a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小

b、逻辑上相邻的节点物理上不一定相邻。 c、插人、删除等不需要大量移动节点

4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2（插入）和（n-1）/2（删除）。

5、链表：线性链表（单链表和双向链表等等）和非线性链表

线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。（注意结点的插入和删除操作）

6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等

7、队列：“先进先出”线性表。应用：树的层次遍历

8、串：由零个或多个字符组成的有限序列。