数据结构

1.线性表:

储存结构:

1.顺序储存结构

顺序表(顺序储存结构)

所有元素按照逻辑顺序,即原本顺序,依次储存到从指定位置开始的一块连续的储存空间当中,第一个元素的储存位置就是指定的储存位置,可以直接根据地址进行连续性访问,或者跳跃访问.

2.链式储存结构

链表(链式储存结构):

2.1单链表:

2.1.1 节点{数据域,指针域(指向后继节点)}

2.2.2 带头结点的单链表:

头指针指向头结点,(头结点为空)值域不含任何信息,从头结点的后继节点开始储存数据,头指针head始终不等于null,当head->next为null的时候,链表为空.

2.2.3 不带头结点的单链表:

2.2.3.1头指针head直接指向开始结点,头结点不为空,head=null的时候,链表即空(因为带头结点的链表有头结点,所以需要next到开始结点判断开始结点是否为空才能确定单链表是否为空,而不带头结点的单链表只需要我们直接从head也就是开始结点判断是否为空即可判断单链表是否为空.)

2.2 信息:

链表中,每个结点不止包含所存元素的信息,还包括元素之间逻辑关系的信息,单链表的前驱结点中包含后继节点的地址信息,可以通过前驱结点的地址信息找到后继节点的位置.

链表储存空间利用率较低,因为他还需要储存一个前驱节点或者后继节点的位置信息,但是它支持存储空间的动态分配.

3.双链表:

3.1 除了增加了一个前驱结点,指向了前部,使其可以从尾部走向前端的链表结构, 其余与单链表一致.

4.循环链表:

4.1循环单链表:带头结点或不带头结点

4.1.1 带头结点,尾部节点指向头结点

4.1.2 不带头结点,尾部节点指向开始节点

4.2 循环双链表:带头结点的循环双链表是没有空指针的,其head->next一定还是等于head

5.顺序表做插入操作需要移动多个元素

6.链表插入操作无需移动元素(高效)

7.静态链表,空间来自数组结构体,而非整个内存