Skip to main content

数据结构-线性结构

{e∈L:∣L∣≥0}\{e \in L: |L| \ge 0\}

特性​

  • † ∃i<1, e∗i∉L† ∃j>∣L∣, ej∉L† ∃k>1,e∗k−1∈L† ∃m<∣L∣,a_m+1∈L\dag \space \exists i<1, \space e*i \notin L \\ \dag \space \exists j>|L|, \space e_j \notin L \\ \dag \space \exists k>1, e*{k-1} \in L \\ \dag \space \exists m<|L|, a\_{m+1} \in L

存储结构​

  • 🧵∀ei∈L, loc(ei)=loc(e1)+(i−1)⋅∣L∣\forall e_i \in L, \space loc(e_i)=loc(e_1)+(i-1)\cdot |L|
  • ⛓class Node {data:any;next:Node*}

推广​

串/字符串​

  • Properties
    • † ∀L,Φ⊆L† ∃L′,L′⊆L\dag \space \forall L, \Phi \sube L \\ \dag \space \exists L', L' \sube L

栈​

  • Specific
    • ⇌outintop∣⋯∣bottom\xrightleftharpoons[out]{in}\boxed{top|\cdots|bottom}

队列​

  • Specific
    • ←outfront∣⋯∣rear←in\xleftarrow{out}\boxed{front|\cdots|rear}\xleftarrow{in}

数组​

  • Specific
    • lower bound:1upper bound:∣L∣lower \space bound: 1 \\ upper \space bound: |L|
    • 🧵∀ei∈L, loc(eij)=loc(e11)+((i−1)⋅∣L∣+(j−1))⋅∣e∣\forall e_i \in L, \space loc(e_{ij})=loc(e_{11})+((i-1) \cdot |L| + (j-1)) \cdot |e|

矩阵​

  • Specific
    • 特殊矩阵
      • 可压缩为一维数组
    • 稀疏矩阵
      • Element(i,j,Aij)Element(i,j,A_{ij})
      • 🧵 三元组顺序表
      • ⛓ 十字链表

广义表​

  • Specific
    • ⛓SL1∣hp∣tp E0∣data∀∣L∣>0, type(tail(L))=SLSL\boxed{1|hp|tp} \space E\boxed{0|data} \\ \forall |L|>0, \space type(tail(L))=SL