算法设计与分析-5基本数据结构

《算法设计与分析-5基本数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析谭守标安徽大学电子学院2007.9第五章基本数据结构定义是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构的研究包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。5.1逻辑结构线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。非线性结构元素之间为一对多（树形结构）或多对多（图形结构）的非线性关系，每个元素有多个直接前驱或多个直接后继。5.2存贮结构顺序存贮链式存贮索引存贮散列存贮5

2、.3基本数据结构5.3.1数组顺序存储大小确定操作：存、取、增加、删除下标索引直接访问（要防止越界）；增加、删除会影响到后面所有的元素。例：inta[10];a[2]=3;5.3基本数据结构5.3.2堆栈顺序存储后进先出(LIFO)操作：存、取PUSH、POP（可能溢出）；只能操作栈顶5.3基本数据结构5.3.3队列顺序存储先进先出(FIFO)操作：存、取ENQUEUE、DEQUEUE（可能溢出）；头尾操作。5.3基本数据结构5.3.4链表链式存储（指针，头节点、前驱、后继）单链、双链、环链操作：存、取：逐项查

3、找（防止空指针错）；增加、删除：修改当前处的指针。5.3基本数据结构5.3.4链表（续）例：structchain{intk;chain*prev;chain*next;}chain*head;5.3基本数据结构5.3.5树链式存储(根节点、父、子、兄弟)二叉树（二叉查找树…）、…操作：存、取：路径上逐项查找（防止空指针错）；增加、删除：修改当前处的指针。5.3基本数据结构5.3.5树（续）5.3基本数据结构5.3.5树（续）例：structtree{intk;tree*p;tree*left;tree*rig

4、ht;}tree*root;5.3基本数据结构5.3.6哈希表散列存储5.3基本数据结构5.3.6哈希表（续）操作：存、取、增加、删除用某个哈希函数计算出地址后直接操作（可能碰撞，可采用链表方式解决）。例：乘法哈希函数：h(k)=m(kAmod1)5.3基本数据结构5.3.7图链式存储（邻接表）、顺序存储（邻接矩阵）（节点、边、权值）无向图、有向图、加权图操作：搜索（宽度优先、深度优先）。例：回路搜索最短路径搜索5.3基本数据结构5.3.7图（续）TheEndThankyou!