信息学奥赛辅导数据结构基础知识.pdfVIP

信息学奥赛辅导数据结构基础知识.pdf

  1. 1、本文档共5页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多

数据结构基础知识

1.根据数据元素间关系的基本特征,有四种基本数据结构:

集合:数据元素间除“同属于一个集合”外,无其它关系。

线性结构:一个对一个,如线性表、栈、队列。

树形结构:一个对多个,如树。

图状结构:多个对多个,如图。

2.数据的存储结构一般有两种,用一组物理地址相邻的存储单元来存储数据元素的存储方式称之为顺

序存储结构;借助于动态数据结构来存储数据元素的存储方式称之为链式存储结构。

3.数组的存储一般采用的是顺序存储结构,如一维数组和多维数组。按照顺序往下存储数据。如图1

4.栈结构的特点是“先进后出”,如图2举例说明。

5.队列结构的特点是“先进先出”,比如排队买票等,如图3举例说明。

Vars:array[1..4,1..10]ofinteger;栈结构就像一个底部封闭的队列结构就像底部不封闭的线

则说明数组s是二维的整型数组,线性表,比如进栈元素的顺性表,比如进队列元素的顺序是

每个元素占2字节,假设存储第序分别为1、2、3,则出栈元1、2、3,则出队列元素的顺序

一个元素的起始地址为100,则它素的顺序分别是3、2、1,满也是1、2、3,满足“先进先出”

的存储结构如下:足“先进后出”原则。的原则。

地址存储方式

100S[1,1]进栈出栈进队列

102S[1,2]

……

118S[1,10]

120S[2,1]

……

178S[4,10]出队列

(图1)(图2)(图3)

6.树结构:树是n(n=0)个结点的有限集。

(1)任意一棵树,只有一个特定的称为根的结点(如图4中的A);当n1时,其余结点可分

为m(m0)个互不相交的有限集,其中每一个集合本身又是一棵树,并且称为根的子树。

(2)结点拥有的子树数称为结点的度。(如图4中的B所拥有的度为2)

(3)度为0的结点称为叶子或终端节点。(如图4中的H、I、J、K等都是叶子结点)

(4)度不为0的结点称为非终端结点或分支结点。

(5)结点的层次从根开始定义起,根为第一层,根的分支为第二层,依此类推(如图4的树结

构最大层次为4层)。树中结点的最大层次称为树的深度或高度。(如图4的树结构的深度

或高度为4)

(6)二叉树是一种特殊的树形结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存

在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒,所以二叉树

是由根节点、左子树、右子树三个基本单元构成。

k

(7)一棵深度为k的二叉树至多只有2-1个结点,此二叉树称为满二叉树(如图4为深度为

精选

4的满二叉树),最少也有K个结点(如图5为深度为4的最小二叉树)。可以验证具有n

个叶子结点的满二叉树共有2n-1个结点(如图5的满二叉树)。

(8)在二叉树的第i层上至多有2i-1个结点。

(9)树的遍历:按照根节点在访问中的先后位置,我们有三种树的遍历方式。(当然每次访问

都是左子树在右子树的前面。)

先序遍历(先访问根节点,再访问左子树,最后访问右子树):

如图4的先序遍历为:A、B、D、H、I、E、J、K、C、F、L、M、G

文档评论(0)

184****8906 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档