数据结构

数据结构概述

五个特征

算法定义

五个特性：有穷性、确定性、可行性、输入、输出

效率的度量

时间复杂度

空间复杂度

三要素

逻辑结构：数据元素之间逻辑关系，独立于计算机

线性结构

线性表：具有相同数据类型的n个数据元素有限序列

一般线性表:  第二章--线性表

顺序存储

顺序表：第一个元素存储在线性表起始位置             第 i 个元素后面紧跟第 i+1个元素

选择：求移动节点平均次数 王道P14

综合应用题：实现对顺序表的增删查改 P17

链式存储

指针实现

单链表

双链表

循环链表

数组实现

静态链表

受限线性表

栈和队列

串

线性表推广

数组

循环单链表：每一个元素都有直接前驱和直接后继

非线性结构

集合

树形结构

一般树

二叉树

图状结构

有向图

无向图

存储结构（物理结构）：包括数据元素的表示和关系的表示

顺序存储：逻辑相邻、物理位置相邻

优点：1.实现随机存取 2.元素占用最少的存储空间PS：存储和存取不同，存取分为随机存取和顺序存取，王道P3记录笔记

缺点：1.只能使用相邻的一整块存储单元，可能产生较多的外部碎片

链式存储：物理位置不需相邻

优点：1.不会出现碎片现象 2.能充分利用所有存储单元

缺点：1.每个元素因存储指针还需要额外存储空间 2.只能实现顺序存储

索引存储：存储元素同事，建立附加索引表PS：索引表中每一项称作索引项，其一般形式（关键字，地址）

优点：检索速度快

缺点：1.附加的索引表占用存储空间 2.增删数据需要修改索引表

散列存储（哈希存储）：根据元素关键字直接计算出该元素存储地址

优点：增、删、查速度快

缺点：如果散列函数不好，会出现存储单元冲突，解决冲突耗时大

数据运算