0

Image Description

荆文征

Zhidu Inc.


你好,再见

树的定义

之前我么你只在谈的是一对一的线性结构,可现实中,还有很多一对多的情况徐耀处理,所以我们需要研究这种一对多的数据结构—–“树”,考虑他的各种特性,来解决我们在编程中遇到的相关问题。

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,….Tm,其中每个节点本身又是一棵树,并且成为根的子树(SubTree)

栈的定义

早先的计算机在被发明是,只要作用是做一些科学和工程的计算工作,也就是现在我们理解的计算器,只不过它比小小计算器功能更强大,速度更快一些。后来发现,在计算机上做的非数值处理的工作越来越多,使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。
比如我们现在常用的搜索引擎,当我们在文本框中输入“数据”时,他已经把我们想要的“数据结构”列在下面了。显然网站这里做了一个字符串查找匹配的工作。

栈与队列

栈的定义

栈(Stack)是限定尽在表为进行插头和删除操作的线性表

我们把允许插入和删除的一段称为栈顶(top),另一端称为栈底(bottom),不含有任何元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,建成LIFO结构。
理解栈的定义需要注意:
首先它是一个线性表,也就是说,栈元素具有线性关系,继前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表为进行插入和删除操作,这里表为是指栈顶,而不是栈底。
栈的插入操作,叫做进栈,也称压栈,入栈。类似子弹入弹夹。
栈的删除操作,也叫出栈,也有的叫做弹栈。如同弹夹中的子弹出夹。

线性表的定义

线性表,从名字你就能感觉到,是具有像线一样的性质的表。在广场上,有很多人分散在各处,当中有些是小朋友,可能有很多大人甚至有不少宠物,这些小朋友的数据对于整个广场来说不是线性表的结构。但像刚才提到的那样,一个班级的小朋友,一个牵着一个排着队,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面的一个是谁,他后面一个是谁,这样如同有一根线把他们串联起来。就称之为线性表。

线性表(List):零个或者多个数据元素的有限序列

算法

算法: 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

数据结构与算法关系

我们这门课程叫做数据结构,但很多时候我们会讲到算法,以及它们之间的关系,市场上也有不少书叫“数据结构与算法分析”这样的名字。
有人可能就要问了,那你到底直降数据结构,还是算法一起讲?它们之间是什么关系呢?干嘛要放在一起?
这个问题怎么回答。打个比方,今天是你女友生日,你打算请女友去看爱情音乐剧,到了戏院,抬头一看—《梁山伯》18:00开眼。嗯?怎么会这样?一问才知道,今天饰演祝英台的演员生病,所以梁山伯唱独角戏。真是搞笑了,这还有什么看头?
事实上,数据结构和算法也是类似的关系。只谈数据结构,当然也可以,我们可以在很短的时间就把几种重要的数据结构介绍完。听完后,很可能你没什么感觉,不知道这些数据结构有啥用处,但如果我们再把响应的算法拿出来讲一讲,你就会发现,深刻开始感慨:哦计算机界的前辈们,的确是一些很牛很牛的人,他们是很多看似难以解决或者没法解决的问题,变得如此的美妙和神奇。

数据结构绪论

数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构起源

早起人们都把计算机理解为数值计算工具,就是感觉计算机当然是用来计算的,所以计算机额解决问题,应该先从具体问题抽象成一个适当的数据模型,设计出一个借此数据模型的算法,然后在编写程序,得到一个实际的软件。