DSA-01 note


Posted by clins210 on 2020-11-27

Array as Memory Block in C/C++

(1)acess:
data getByIndex(index)
insertByIndex(index, data)

(2)maintenance:

  • construct(length)
  • updateByIndex(Index, data)
    removeByIndex(index)

desired property : fast computation of address from index
=> fast random access

implicit assumption:
index to address done by formula

C++ STL Vector : a Growing array

get, update
STL vector : a more "structured" way of using arrays

!!STL

2-D array

access:
index = (row, col)
data getByIndex(Index)
address = arr + sizeof(data)x(row x nCol + cool)

maintenance:
length = (nRow, nCol)
construction(length)
arr=new data [nRow x nCol]

implementation
(1)one-block:tradeoff & succinct
(2)array of array: easier for programmers

Ordered array

想像有連續放東西:排好的值(ordered Value)
insert
update

Asymptotic Notation

goal : tough rather than steps
f(n)
g(n)


#DSA #CS #note







Related Posts

JS 字串拼接 Template Literals

JS 字串拼接 Template Literals

Git & GitHub 快速入門

Git & GitHub 快速入門

npm ERR! enoent ENOENT: no such file or directory, open ... package.json

npm ERR! enoent ENOENT: no such file or directory, open ... package.json


Comments