软件 designer 的 data structure 和 algorithm design

数组与矩阵

• 数组的存储地址计算
  对于一维数组a[n]，其元素a[i]的存储位置可通过公式a[i]=a+ilen进行计算。
  针对二维数组a[m][n]，其存储方式存在两种形式：
  按行排列时，元素a[i][j]的地址可表示为a+(in+j)len；
  按列排列时，对应的地址则为a+(jm+i)*len。
  其中，参数a代表数组中首个元素a[0]的起始内存位置，而len则表示每个元素在内存中所占据的空间大小。

• 矩阵计算
  矩阵中位于i行j列的元素，在转换为一维数组索引时可采用代入排除法进行计算。
  具体而言，上三角矩阵对应的索引公式为(2n-i+1)*i/2+j；而下三角矩阵的索引公式则为(i+1)*i/2+j。

线性表结构与特性分析

• 线性表结构

  • 链式存储结构

  • 队列：遵循先进先出原则（两端均可进行操作）
    循环队列结构
    判断队列为空的条件为：头指针等于尾指针
    判断队列满的条件为：（尾指针+1）模总容量等于头指针

  • 栈：遵循先进后出原则（仅一端可进行操作）

广义表的结构与应用

• 长度：最外层所包含的元素数量
  • 深度：括号嵌套的层级数目
  • 表头head：序列中的首个元素
  • 表尾tail：除去首个元素后的其余部分
    **若存在：LS=(a,