(转载)(c#)数据结构与算法分析 --数组、向量和表
时间：2010-11-04 来源：higirle
内存
地址
intArray[0]
intArray[1]
intArray[2]
intArray[3]
|
int[2][2] |
内存 |
地址 |
|
intArray[0][0] |
|
bffff4f0 |
|
|
|
bffff4f1 |
| bffff4f2 | ||
| bffff4f3 | ||
|
intArray[0][1] |
|
bffff4f4 |
|
|
|
bffff4f5 |
| bffff4f6 | ||
| bffff4f7 | ||
|
intArray[1][0] |
|
bffff4f8 |
|
|
|
bffff4f9 |
| bffff4fa | ||
| bffff4fb | ||
|
intArray[1][1] |
|
bffff4fc |
|
|
|
bffff4fd |
| bffff4fe | ||
| bffff4ff |
上面是两个一维整数数组和二维整数数组。从图中可以看出每次读取某个元素时只要加上某个偏移量就行了，偏移量就是就是这个元素类型所占的内存空间大小，上面是整形数组，一个整形占4个字节。
可以看到，无论是多少维（稚）的数组，在内存中都是线性的连续存储，它是按行优先顺序放在内存中的，即，如果有从n00开始，其次是n01...然后是n10,n11.........以此类推，三维的数组就是n000,n001.......n010,n011一直到n100.......。有些例外情况，比如fortran语言中，它是按列优先顺序存放的，顺序是n10,n20,n30.....n11,n21......n12,n22 这样的，以此类推，不管多少维，都是这样算的。
数组的优点就是访问速度快，缺点是在声明时就已经确定数组的大小，不能再扩充了。
向量（vector容器）
vector大家都经常使用，其实向量是一个动态数组，所谓动态就是数组在声明后还可以增长，也可以插入元素，动态数组在增长的时候，其实也就是先分配好内存，然后new 一个数组，一个个将原数组再拷贝进去。向量使用完后再delete分配的内存。
向量的优点和数组一样，缺点就是增长过快的时候比较耗资源。
表（list)
一个简单的单向链表：
|
→ |
|
→ |
|
→ |
|
→ |
|
→ |
|
链表的每个元素称为节点，每个结点都有两个单元，第一个就是数据项，存放数据，第二个称为链（或next链），它指向第二个元素的地址，以此类推，最后的一个元素指向NULL。
这种单项列表，如果给表头或表尾添加元素的时候会有些不便，最好的办法就是加上表头和表尾了。
一个带表头和表尾的单向链表：
|
→ |
|
→ |
|
→ |
|
→ |
|
→ |
|
→ |
|
→ |
|
表头的数据元素是这个表的名字，例如上面那个表名是head，表头的链指向第一个节点，最后一个节点则指向尾节点。
给表添加一个元素的时，以上边的head表为例，在A和B中间插入一个节点Y，则首先把A节点的链指向Y，然后将Y的链指向B。如果是删除一个结点的话，假设删除D节点，则只要将C节点链指向D节点的下一个节点，即E节点。是不是很简单，但问题又来了，每次插入或删除一个结点的时候，尤其是删除最后一个结点的时候，都得寻找它前面的节点，这就比较麻烦了，而双向链表则解决了这种问题。
双向链表：
|
|
|
|
|
|
可以看出，每个都在数据区前面都多了一个指向它前面节点的指针。我们把一个节点的后一个节点叫做直接后驱，它前面的一个结点叫做直接前驱。第一个节点没有直接前驱，所以为NULL，末尾节点没有直接后驱，也为NULL，这样在插入或删除一个节点的时候的就可以直接找到它的前后两个节点了。
有时候为了方便查询，会让最后一个节点的后驱的next链指向第一个节点，这样的链表就叫做循环链表。
当然，表不止有链表，还有别的，以后会学习到的。
链表的优点就是可以不受内存单元的线性限制（比如数组），可以充分利用空间，缺点就是链表的存储密度不如数组或向量的高，密度当然是质量除以体积了，这里质量就是实际数据的大小，体积就是链表的大小，因为每个节点要额外存储链，所以链表的存储密度就相对小了 ，另外在链表很长时，操作一个节点就比较麻烦了，因为它在内存中不是连续的，所以得从头开始一个个找，效率就低了。
大致算是解了数组、向量和链表，可以根据它们的特点再不同场合使用。
相关阅读 更多 +
