数据结构与算法（一）-软件设计（十七）

设计模式（十五）-面向对象概念

一、数组

存储地址的计算：

一维数组a[n]，当a[2]的存储地址为：a+2*len，如果每一个数组元素只占用一个字节，那么

a[2]的位置就是a+2。

二维数组a[n][m]分为两种，a[2][3]数组计算如下：

按行存：a+(2*m+3)*len

按列存：a+(3*n+2)*len

题目：已知五行五列的二维数组各占两个字节，那么a[2][3]按行优先存储的存储地址是多少？

按行所以是：a+(2*5+3)*2 = a+26

二、稀疏矩阵

上三角矩阵：在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为

(2n-i+1)*i/2+j。

下三角矩阵：在矩阵中下标分别为i和j的元素，对应的一维数组下标计算公式为

(i+1)*i/2+j

三、数据结构

数据结构就是计算机存储数据的方式。

数据逻辑结构有，线性结构 和 非线性结构。

非线性结构 又可以分为 树形结构和图。树形结构没有环路，图则由环路。

线性表的概念(a1,a2...aN)

有两种常见存储方式：1、顺序存储结构（顺序表）2、链式存储结构（链表）

顺序表就是一维数组方式存信息。

链表 又分为 单链表、循环链表、双向链表。

循环链表好处，头和尾是相联的，当在最后的时候，可以继续next找。

双向链表指针可以前后移动。

他们头节点都不存信息的，为了后续处理数据一致。

单链表的删除，a1，a2，a3，当删除a2时候，就是把a1的next指针指向a3。（aPoint的

Next指向a2。bPoint的next指向a3。所以删除a2的操作就是aPoint的next=bPoint的next）

单链表的插入，a1和a3之前插入a2，就是把a1Point的next指向a2，a2Point的next指向a3。

顺序存储与链式存储

空间性能：

顺序存储的【存储密度】=1(100%)，更优，链式存储的【存储密度】<1。

（意味着顺序存储的空间密度没有空间上的浪费）

顺序存储的【容量分配】事先确定（因为他需要连续的空间事先分配），链式存储的【容量分配】动态改变，更优。

时间性能：

【查找运算】：顺序存储的O(n/2)，链式的O(n/2)。

（当有序的话，顺序存储可以二分查找，性能就更优）

【读运算】：顺序存储O（1）更优，链式O（[n+1]/2）最好情况为1，最坏情况为n。

（指定某个信息读取出来，顺序存储只需要把a直接读出来。而链式表则需要一直通过next指针来找到a）

【插入运算】：顺序存储O(n/2)，最好情况是0，最坏情况是n。链式O（1），更优。

【删除运算】：顺序存储是O([N-1]/2)，链式O（1）更优。