数据结构（计算机存储、组织数据方式）
数据结构是存储、组织的方式。数据结构是指相互之间存在一种或多种特定关系的的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储。数据结构往往同高效的检索和技术有关。
数据结构是指相互之间存在着一种或多种关系的元素的集合和该集合中数据之间的关系组成。记为：
Data_Structure=(D,R)
其中D是数据元素的，R是该集合中所有元素之间的关系的。[1]
Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是，以及存在于该对象的和组成实
例的数据元素之间的各种联系。这些联系可以通过定义相关的来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。
Clifford A.Shaffer在《》一书中的是：“数据结构是ADT（Abstract
Data Type） 的物理实现。”
Robert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的及其，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。
数据结构具体指同一类数据元素中，各元素之间的相互，包括三个组成，数据的，的存储结构和数据运算结构。
一、数据的逻辑结构：指反映数据之间的逻辑关系的，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：
二、数据的物理结构：指数据的在计算机存储空间的存放形式。
三、数据结构的运算。[1]
一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种，且各种影响数据处理的效率。
在许多类型的的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。
选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种方法和的出现，语言就是其中之一。
在计算机科学中，数据结构是一门研究非的程序设计问题中的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的。
“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年（Donald Ervin Knuth）教授开创了数据结构的最初体系，他所著的《》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课，数据结构是介于、计算机硬件和三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现、、及其他系统程序的重要基础。
科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：的表示，信息的处理 。
而信息的表示和组织又直接关系到处理信息的程序的。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。
计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的，然后设计一个解此数学模型的（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法
。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。
是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由处理的符号的总称。
数据元素是数据的，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个组成。数据项是数据的不可分割的最小单位。有两类数据元素：一类是不可分割的原子型数据元素，如：整数&5&，字符
&N& 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出生日期又可以由三个数据项：&年&、&月&和&日&组成，则称&出生日期&为组合项，而其它不可分割的数据项为原子项。
关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 &主& 关键字，否则称之为 &次& 关键字。
数据对象是性质相同的数据元素的集合，是数据的一个。数据对象可以是有限的，也可以是无限的。
是指对数据进行、、删除、合并、、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和的进一步普及，计算机用于数据处理的时间比例必将进一步增大。
数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为、（）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
根据数据元素间关系的不同特性，通常有下列四类基本的结构： ⑴集合结构。该结构的数据元素间的关系是“属于同一个集合”。 ⑵线性结构。该结构的数据元素之间存在着一对一的关系。 ⑶树型结构。该结构的数据元素之间存在着一对多的关系。 ⑷图形结构。该结构的数据元素之间存在着多对多的关系，也称网状结构。 从上面所介绍的数据结构的概念中可以知道，一个数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。
数据结构的形式定义为：数据结构是一个二元组 ：Data_Structure=（D，R），其中，D是数据元素的有限集，R是D上关系的有限集。的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个中的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型;
一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。
是最简单、最基本、也是最常用的一种线性结构。 线性表是具有相同数据类型的n(n&=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) ，其中n为表长， n=0 时称为空表。 它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。
数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和。
顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的。
：就是根据结点的关键字直接计算出该结点的存储地址。
数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种顺序存取的存储结构，的链式存储结构是一种的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机中的实现，为了全面的反映一个数据的逻辑结构，它在中的映象包括两方面内容，即数据元素之间的信息和数据元素之间的关系。不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。
数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的及其实现算法的讨论。
数据结构不同于，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助所提供的数据类型来描述数据的存储结构。
计算机中表示数据的最小单位是二进制数的一位，叫做位。我们用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。元素或结点可看成是数据元素在计算机中的映象。
一个系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。
对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。
不同的数据结构其操作集不同，但下列操作必不可缺：
1,结构的生成；
2.结构的销毁；
3,在结构中查找满足规定条件的数据元素；
4,在结构中插入新的数据元素；
5,删除结构中已经存在的数据元素；
抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。的定义为：
ADT 抽象数据类型名：{数据对象：（数据元素集合），数据关系：（数据关系二元组结合），基本操作：（操作函数的罗列）}； 抽象数据类型名;抽象数据类型有两个重要特性：
用ADT描述程序处理的时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的（即外界使用它的方法）。
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于、科学计算和商务处理等；非数值数据包括字符、文字、、图像、语音等。数据元素（Data
Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生中学生信息表中的一个记录等，都被称为一个数据元素。
有时，一个数据元素可由若干个数据项（Data Item）组成，例如，中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时是把每个学生记录当作一个基本单位进行访问和处理的。
数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。
在程序设计中，为了处理方便， 把具有相同类型的若干按有序的形式组织起来。这些按序排列的同类数据元素的集合称为。在中，
数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、、结构数组等各种类别。
是只能在某一端插入和删除的特殊。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
一种特殊的，它只允许在表的（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。
是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
是包含n（n&0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件：
（1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（）。　 （2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。
（3）K中各结点，对关系N来说可以有m个后继（m&=0）。
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。
若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为。
[2]　（bubble sort）
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序)
插入排序 （insertion sort）
桶排序 （bucket sort）
计数排序 (counting sort)
合并排序 （merge sort）
原地合并排序
二叉排序树排序 （Binary tree sort）
鸽巢排序 (Pigeonhole sort)
基数排序 （radix sort）
Gnome 排序
图书馆排序
（selection sort）
（shell sort）
堆排序 （heapsort）
（quicksort）
内省排序 （Introsort）
Patience sorting
Stupid sort
珠排序（Bead sort）
Pancake sorting
Uninterpreted
数值
Data_structures
1．钟志永 姚珺
．大学计算机应用基础 ．重庆 ：重庆大学出版社，2012
2．．中国Linux联盟
[引用日期] ．
数据类型和数据结构的区别
在逻辑结构上，数据类型就是一块内存块，而数据结构则是由多块内存块构成，且多块内存块间存在一定关系而连接起来的。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：479987次
积分：8984
积分：8984
排名：第704名
原创：304篇
转载：891篇
评论：12条
(4)(19)(41)(63)(76)(32)(33)(88)(41)(16)(25)(37)(73)(63)(92)(75)(120)(159)(55)(67)(13)(1)bbs的数据结构和存储过程（一）bbs的数据结构和存储过程（一）if exists(select * from sysobjects where id = object_id('BBSUser'))drop table BBSUser gocreate table BBSUser(id int identity primary key ,UserName varchar(20) default ' not null ,Password varchar(10) default ' not null ,Email varchar(100) default ' not null ,Homepage varchar(150) default ' not null ,Signature varchar(255) default ' not null ,SignDate datetime default getdate() not null ,Point int default 0 not null)gocreate index ix_bbsuser on bbsuser (id , username , password)if exists(select * from sysobjects where id = object_id('Face'))drop table Facegocreate table Face(id tinyint identity primary key ,Face varchar(30) default ' not null)goif exists(select * from sysobjects where id = object_id('BBS'))drop table BBSgocreate table BBS(id int identity primary key ,RootID int default 0 not null , --根IDFatherID int default 0 not null , --父IDLayer tinyint default 0 not null , --层OrderNum float(53) default 0 not null , --排序基数UserID int default 0 not null , --发言人IDForumID tinyint default 1 not null , --版面IDSubject varchar(255) default ' not null , --主题Content text default ' not null , --内容FaceID tinyint default 1 not null , --表情Hits int default 0 not null , --点击数IP varchar(20) default ' not null , --发贴IPTime datetime default getdate() not null , --发表时间Posted bit default 0 not null --是否精华贴子)go create index ix_bbs on bbs(id , rootid ,layer , fatherid , subject,posted) with DROP_EXISTING create index ix_bbs1 on bbs(fatherid , forumid) with DROP_EXISTINGcreate index ix_bbs2 on bbs(forumid , rootid , ordernum) with drop_existingif exists(select * from sysobjects where id = object_id('PostedTopic'))drop table PostedTopicgocreate table PostedTopic(id int identity primary key ,UserID int default 0 not null , --发言人IDForumID tinyint default 1 not null , --版面IDSubject varchar(255) default ' not null , --主题Content text default ' not null , --内容FaceID tinyint default 1 not null , --表情Hits int default 0 not null , --点击数IP varchar(20) default ' not null , --发贴IPTime datetime default getdate() not null --发表时间)go if exists(select * from sysobjects where id = object_id('forum'))drop table forumgocreate table Forum(ID tinyint identity primary key ,RootID tinyint default 0 not null , --根IDFatherID tinyint default 0 not null , --父IDLayer tinyint default 0 not null , --层Title varchar(50) default ' not null , --版面名称Description varchar(255) default ' not null , --版面描述MasterID int default 1 not null , --版主IDTopicCount int default 0 not null , --贴子总数Time datetime default getdate() not null , --创建时间IsOpen bit default 0 not null --是否开放)goinsert into forum(rootid , fatherid , layer , title , description , masterid) values(1 , 0 , 0 , &谈天说地& , &在不违犯国家法律的情况下，你可以发表你自己的言论。& , 1)insert into forum(rootid , fatherid , layer , title , description , masterid) values(2 , 0 , 0 , &体育& , &在不违犯国家法律的情况下，你可以对体育发表你自己的评论。& , 1)insert into forum(rootid , fatherid , layer , title , description , masterid) values(1 , 1 , 1 , &笑话站& , &笑话，让你在工作间隙轻松一下。& , 1)insert into forum(rootid , fatherid , layer , title , description , masterid) values(2,2 , 1 , &体育沙龙& , &体育总和评论。& , 1)insert into forum(rootid , fatherid , layer , title , description , masterid) values(2,2 , 1 , &足球& , &足球评论。& , 1)insert into forum(rootid , fatherid , layer , title , description , masterid) values(2,2 , 1 , &海牛俱乐部& , &海牛球迷的讨论园地。& , 1)select * from forumif exists(select * from sysobjects where id = object_id('Notify'))drop table Notifygocreate table Notify(ID int identity primary key ,TopicID int default 0 not null ,Closed bit default 0 not null ,)goselect * from notifydelete from notify where id=5if exists(select * from sysobjects where id = object_id('up_GetBBSInfo'))drop proc up_GetBBSInfogocreate proc up_GetBBSInfoasdeclare @ForumCount intdeclare @TopicCount intdeclare @UserCount intset nocount onselect @ForumCount = count(*) from Forum where layer && 0select @TopicCount = count(*) from BBSselect @UserCount = count(*) from BBSUserselect 'ForumCount' = @ForumCount , 'TopicCount' = @TopicCount , 'UserCount' = @UserCountgoup_getbbsinfoif exists(select * from sysobjects where id = object_id('up_GetForumInfo'))drop proc up_GetForumInfogocreate proc up_GetForumInfo @a_intForumID intasdeclare @intTopicCount intdeclare @intRootTopicCount intset nocount onif not exists(select * from Forum where id=@a_intForumID) return 0select @intTopicCount = count(*) from bbs where forumid = @a_intForumIDselect @intRootTopicCount = count(*) from bbs where forumID=@a_intForumID and fatherid=0 select * , 'TopicCount'=@intTopicCount , 'RootTopicCount' = @intRootTopicCountfrom Forum where id = @a_intForumIDset nocount offgo select id , rootid , title , fatherid from forumif exists(select * from sysobjects where id = object_id('up_GetPostedForumInfo'))drop proc up_GetPostedForumInfogocreate proc up_GetPostedForumInfo @a_intForumID intasdeclare @intTopicCount intdeclare @intRootTopicCount intset nocount onif not exists(select * from Forum where id=@a_intForumID) return 0select @intTopicCount = count(*) from bbs where forumid = @a_intForumID and posted=1select * , 'TopicCount'=@intTopicCount , 'RootTopicCount' = @intTopicCountfrom Forum where id = @a_intForumIDset nocount offgo &数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
顺序存储结构的线性表、链式存储结构的线性表（即链表）、栈、队列、串都属于线性表的范畴。
顺序存储结构的线性表
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。
优点：查找快（因为地址连续，所以只要找到一个，其他的很快就找到）
缺点：插入和删除操作需要移动元素，速度慢
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
优点：插入和删除操作快
缺点：查找慢
先进后出的数据结构，只能在栈顶进行插入和删除。
栈的一个重要的作用就是记忆功能。栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：
函数的返回地址和参数&临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量
先进先出的数据结构，只能在队列的后端进行插入操作，只能在队列的前端进行删除操作。
我们把字典定义为“键-值对”（Key-Value Pair）的集合。
从字典中查找“键- 值对”的最简单方法就是使用数组存储，然后在查找的时候遍历此数组，当遍历到和被查找的“键 - 值对”的名字相同项的时候，这个“键 - 值对”就被找到了。这种最朴实的方式肯定是不能满足实际要求的，因此人们发明了一种检索效率非常高的组织字典数据的方法 ，即哈希表结构。
哈希方法将 “键-值对”的存储位置 和 “键-值对”的键 建立起一种对应的函数关系hash()，同过哈希函数，能够为每一个键找到一个存储位置。即
存储位置=hash(键)
哈希表也被称作散列表。
当查找一个键所对应的值的时候，首先通过哈希函数取得此“键-值对”的存储位置，然后直接在此存储位置查找，如果键相等，则查找成功。
举个例子，有一组键-值对如下：
&5, &Tom&&、&8, &Jane&&、&12, &Bit&&、&17, &Lily&&、&20, &sunny&&
我们按照如下哈希函数对键进行计算：
得出如下结果：
因此，我们把&5, &Tom&&、&8, &Jane&&、&12, &Bit&&、&17, &Lily&&、&20, &sunny&&分别放在地址为8、11、15、3、6的位置上。当要检索17对应的值的时候，首先计算17的hash值为3，然后到地址为3的存储位置取得17对应的值为Lily，可见检索速度很快
但是有一个问题，不同的键有时候算出来的hash值是同一个，即不同的键-值对放到了同一个存储位置。这个不要紧，检索的时候把对应存储位置的所有键-值对拿出来比较，找到键相等的那个
二叉树是每个节点最多有两个子树的有序树（有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树）。
尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。树和二叉树的2个主要差别：
树中结点的最大度数没有限制，而二叉树结点的最大度数为2树的结点无左、右之分，而二叉树的结点有左、右之分
完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
&&&&&&&&&&&&&&&&&&&&&&& 图1&&&&&&&&&&&&&&&&&&&&&&&&&& 图2&&&&&&&&&&&&&&&&&&&&& 图3
图2是完全二叉树，图3不是完全二叉树
图1是完全二叉树，也是满二叉树
二叉排序树（二叉查找树）
二叉排序树又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值若右子树不空，则右子树上所有结点的值均大于它的根结点的值左、右子树也分别为二叉排序树
如下图，就是一个二叉排序树。
二叉排序树查找节点
若根结点的关键字值等于查找的关键字，成功
否则，若小于根结点的关键字值，递归查左子树
若大于根结点的关键字值，递归查右子树
若子树为空，查找不成功
二叉排序树插入节点
若当前的二叉查找树为空，则插入的元素为根节点
若插入的元素值小于根节点值，则将元素插入到左子树中；若插入的元素值不小于根节点值，则将元素插入到右子树中
按以上方法递归
注意：新插入的结点总是叶子节点
二叉排序树删除节点（3种情况）
要删除的节点是叶子节点。直接删除要删除的节点只有左（右）子树。直接删除并把它的左（右）子树当成它的父节点的左（右）子树要删除的节点的左子树和右子树均不空。可以有两种做法：其一是把要删除节点的左子树的最右下节点代替要删除节点；其二是把要删除节点的直接前驱（或直接后继）代替要删除的节点
二叉平衡树
二叉平衡树是在二叉排序树的基础上得来的。对于一颗二叉排序树，插入、删除、查找所花的时间和树的高度h有关，那么如果能够让树维持矮矮胖胖的身材，那么可以提高效率。所以二叉平衡树就诞生了。
平衡二叉树定义：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树
B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：162005次
积分：2319
积分：2319
排名：第6978名
原创：67篇
转载：20篇
评论：29条
(1)(2)(8)(1)(2)(1)(15)(1)(2)(10)(4)(6)(16)(18)