算法与数据结构day2 笔记

程序=数据结构+算法

ADT abstract data type 抽象数据结构

#内存

连续的存储空间

0x01********1byte字节

0x02********

0x03********

0x04********

forexample

inta =1

0x0200000000

*****************************************

li = [200,390,78,1211] li (0x23)

0x23200

int4byte=32bit

li[1]0x(23+4)390按字节

li[2]0x（23+4*2）78

li[3]0x（23+4*3）1211

标号以0开始是为了偏移的方便

li=[23,"ghk"] int和字符串数据类型不同

这时候偏移像之前的方法就不可行了

这时候内存中应该放地址的方法来解决

地址的大小是统一的 可以通过用偏移的方法来做

forexample

元素外置的列表

li=[12,"ab",1.111,1000,"jhbjhb"] 类型不一样了哦

li[]--->0x11--->0x23--->12

li[1]--->0x15--->0x34--->"ab"

li[2]--->0x19--->0x45--->1.111

li[3]--->0x23--->0x55--->1000

li[4]--->0x27--->0x34--->"jhbjhb"

顺序表的结构与实现

forexample

li[8]

表头 max最大数目 num单位偏移

数据区

0x12********

0x16******** 已保存的数据

0x20空的位置

0x24

顺序表的两种基本实现方式

表头+数据 放在同一位置

表头

数据区

真实的情况

(1) 连续式

0x146max

0x183num

0x22********

0x26********

0x30********

0x34

0x38

0x42

(2) 分离式

0x1114

0x1153

0x1190x23

0x23********

0x27********

0x31********

0x35********

怎样扩充

对于第一种

重新申请

注意要考虑表头的空间

对于第二种

分离式（常用）

表头不用改

指向数据区的内容指向新的空间就ok

扩充的方式 （对于分离式）

固定式加倍 每次扩充固定 空间换时间

每次扩充加倍 每次加倍 时间换空间

建议这部分区看看计算机操作系统作为参考。