第四章: C数据结构
+++++++++++++++
根据底层的抽象数据类型理解显式的数据结构操作.
C语言中, 一般使用内建的数组类型实现向量, 不再对底层实现进行抽象.
N个元素的数组可以被序列for (i=0; i<N; i++)完全处理; 所有其他变体都应该引起警惕.
表达式sizeof(x)总会得到用memset或memcpy处理数组x(不是指针)所需的正确字节数.
区间一般用区间内的第一个元素和区间后的第一个元素来表示.
不对称区间中元素的数目等于高位边界与低位边界的差.
当不对称区间的高位边界等于低位边界时, 区间为空.
不对称区间中的低位边界代表区间的第一个元素; 高位边界代表区间外的第一个元素.
结构的数组常常表示由记录和字段组成的表.
指向结构的指针常常表示访问底层记录和字段的游标.
动态分配的矩阵一般存储为指向数组列的指针或指向元素指针的指针; 这两种类型都可以按照二维数组进行访问.
以数组形式存储的动态分配矩阵, 用自定义访问函数定位它们的元素.
抽象数据类型为底层实现元素的使用(或误用)方式提供一种信心的量度.
数组用从0开始的顺序整数为键, 组织查找表.
数组经常用来对控制结构进行高效编码, 简化程序的逻辑.
通过在数组中每个位置存储一个数据元素和一个函数指针(指向处理数据元素的函数), 可以将代码与数据关联起来.
数组可以通过存储供程序内的抽象机(abstract machine)或虚拟机(virtual machine)使用的数据或代码, 控制程序的运作.
可以将表达式sizeof(x) / sizeof(x[0])理解为数组x中元素的个数.
如果结构中含有指向结构自身|名为next的元素, 一般说来, 该结构定义的是单向链表的结点.
指向链表结点的持久性(如全局|静态或在堆上分配)指针常常表示链表的头部.
包含指向自身的next和prev指针的结构可能是双向链表的结点.
理解复杂数据结构的指针操作可以将数据元素画为方框|指针画为箭头.
递归数据结构经常用递归算法来处理.
重要的数据结构操作算法一般用函数参数或模板参数来参数化.
图的结点常常顺序地存储在数组中, 链接到链表中, 或通过图的边链接起来.
图中的边一般不是隐式地通过指针, 就是显式地作为独立的结构来表示.
图的边经常存储为动态分配的数组或链表, 在这两种情况下, 边都锚定在图的结点上.
在无向图中, 表达数据时应该将所有的结点看作是等同的, 类似地, 进行处理任务的代码也不应该基于它们的方向来区分边.
在非连通图中, 执行遍历代码应该能够接通孤立的子图.
处理包含回路的图时, 遍历代码应该避免在处理图的回路进入循环.
复杂的图结构中, 可能隐藏着其他类型的独立结构.
+++++++++++++++++ |
