Data Structures · topic
Row-major and column-major address formulas for 2-D and 3-D arrays with any lower bounds, reverse problems that recover the base or a dimension from two addresses, triangular, symmetric and tridiagonal storage formulas, sparse matrices in triplet and CSR form, and the shift cost of insertion and deletion.
Address formulas for one-, two- and three-dimensional arrays in row-major and column-major order with arbitrary lower bounds, the general n-dimensional rule, element counts, reverse problems that recover the base address or a dimension from two known addresses, and a compiled C program showing that C stores arrays row by row. All worked values are computed by a verification script.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
![Two 3 by 4 grids give the memory offset k of a[i][j]: row-major numbers the cells 0 to 11 along each row, column-major down each column. Cell a[1][2] is offset 6 in row-major and 7 in column-major.](https://bywjbbkinjqiyalvzqfd.supabase.co/storage/v1/object/public/sheet-media/DS/DS-02/diagrams/DS-02.d01.webp)
Packed storage for lower and upper triangular, symmetric, diagonal and tridiagonal matrices with the offset formulas for row-major and column-major packing, sparse matrices in triplet and compressed sparse row form with their space break-even points, and the shift cost of inserting into and deleting from an array. Every formula was checked against a brute-force enumeration for n up to 12.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
