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

《算法设计与分析-5基本数据结构.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-5基本数据结构.ppt（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。余元素都有一个直接前驱和直接后继。n非线性结构非线性结构n元素之间为一对多（树形结构）或多对多元素之间为一对多（树形结构）或多对多（图形结构）的非线性关系，每个元素有多（图形结构）的非线性关系，每个元素有多个直接前驱或多个直接后继。个直接前驱或多个直接后继。5.2 5.2 存贮结构存贮结构n顺序存贮顺序存贮n链式存贮链式存贮n索引存贮索引存贮n散列存贮散列存贮5.3 5.3 基本数据结构基本数据结构5.3.1 5.3.1 数组数组n顺序存储顺序存储n大小确定大小确定n操作：存、取、增加、删除操作：存、取、增加、删除n下标索

3、引直接访问（要防止越界）；下标索引直接访问（要防止越界）；n增加、删除会影响到后面所有的元素。增加、删除会影响到后面所有的元素。n例：例：nintint a10;a10;na2=3;a2=3;5.3 5.3 基本数据结构基本数据结构5.3.2 5.3.2 堆栈堆栈n顺序存储顺序存储n后进先出后进先出(LIFO)(LIFO)n操作：存、取操作：存、取nPUSHPUSH、POPPOP（可能溢出）；（可能溢出）；n只能操作栈顶只能操作栈顶5.3 5.3 基本数据结构基本数据结构5.3.3 5.3.3 队列队列n顺序存储顺序存储n先进先出先进先出(FIFO)(FIFO)n操作：存、取操作：存、取nEN

4、QUEUEENQUEUE、DEQUEUEDEQUEUE（可能溢出）；（可能溢出）；n头尾操作。头尾操作。5.3 5.3 基本数据结构基本数据结构5.3.4 5.3.4 链表链表n链式存储（指针，头节点、前驱、后链式存储（指针，头节点、前驱、后继）继）n单链、双链、环链单链、双链、环链n操作：操作：n存、取：逐项查找（防止空指针错）存、取：逐项查找（防止空指针错）；n增加、删除：修改当前处的指针。增加、删除：修改当前处的指针。5.3 5.3 基本数据结构基本数据结构5.3.4 5.3.4 链表（续）链表（续）n例：例：nstructstruct chain chain n intint k;k;

5、n chain*chain*prevprev;n chain*next;chain*next;n nchain*head;chain*head;5.3 5.3 基本数据结构基本数据结构5.3.5 5.3.5 树树n链式存储链式存储(根节点、父、子、兄弟根节点、父、子、兄弟)n二叉树（二叉查找树二叉树（二叉查找树）、）、n操作：操作：n存、取：路径上逐项查找（防止空指针错）存、取：路径上逐项查找（防止空指针错）；n增加、删除：修改当前处的指针。增加、删除：修改当前处的指针。5.3 5.3 基本数据结构基本数据结构5.3.5 5.3.5 树（续）树（续）5.3 5.3 基本数据结构基本数据结构5.

6、3.5 5.3.5 树（续）树（续）n例：例：nstructstruct tree tree n intint k;k;n tree*p;tree*p;n tree*left;tree*left;n tree*right;tree*right;n ntree*root;tree*root;5.3 5.3 基本数据结构基本数据结构5.3.6 5.3.6 哈希表哈希表n散列存储散列存储5.3 5.3 基本数据结构基本数据结构5.3.6 5.3.6 哈希表（续）哈希表（续）n操作：存、取、增加、删除操作：存、取、增加、删除n用某个哈希函数计算出地址后直接操作用某个哈希函数计算出地址后直接操作（可能碰

7、撞，可采用链表方式解决）。（可能碰撞，可采用链表方式解决）。n例：例：n乘法哈希函数：乘法哈希函数：h(kh(k)=)=m(kAm(kA mod 1)mod 1)5.3 5.3 基本数据结构基本数据结构5.3.7 5.3.7 图图n链式存储（邻接表）、顺序存储（邻接矩阵）链式存储（邻接表）、顺序存储（邻接矩阵）（节点、边、权值）（节点、边、权值）n无向图、有向图、加权图无向图、有向图、加权图n操作：操作：n搜索（宽度优先、深度优先）。搜索（宽度优先、深度优先）。n例：例：n回路搜索回路搜索n最短路径搜索最短路径搜索5.3 5.3 基本数据结构基本数据结构5.3.7 5.3.7 图（续）图（续）The EndThe EndnThank you!Thank you!