文档介绍：数据结构与算法
数据结构(Data Structure)
是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型
集合:结构中的数据元素除了“同属于一个集合”外,没有其它关系。
线性结构:结构中的数据元素之间存在一对一的关系。
树型结构:结构中的数据元素之间存在一对多的关系。
图状结构或网状结构:结构中的数据元素之间存在多对多的关系。
数据结构的存储方式
数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
元素之间的关系在计算机中有两种不同的表示方法:顺序表示和非顺序表示。由此得出两种不同的存储结构:顺序存储结构和链式存储结构。
顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
链式存储结构:在每一个数据元素中增加一个存放另一个元素地址的指针(pointer ),用该指针来表示数据元素之间的逻辑结构(关系)。
逻辑结构和物理结构
数据的逻辑结构
非线性结构
集合
图状结构
有向图
无向图
树形结构
一般树
二叉树
线性结构
一般线性表
线性表推广
广义表
数组
串
受限线性表
栈和队列
数据逻辑结构层次关系图
图1-4 逻辑结构与所采用的存储结构
线性表
树
图
顺序存储结构
链式存储结构
复合存储结构
逻辑结构
物理结构
数据结构的运算
数据结构的主要运算包括:
⑴建立(Create)一个数据结构;
⑵消除(Destroy)一个数据结构;
⑶从一个数据结构中删除(Delete)一个数据元素;
⑷把一个数据元素插入(Insert)到一个数据结构中;
⑸对一个数据结构进行访问(Access);
⑹对一个数据结构(中的数据元素)进行修改(Modify);
⑺对一个数据结构进行排序(Sort);
⑻对一个数据结构进行查找(Search)。
线性表
线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中:
①存在一个唯一的被称为“第一个”的数据元素;
②存在一个唯一的被称为“最后一个”的数据元素;
③除第一个元素外,每个元素均有唯一一个直接前驱;
④除最后一个元素外,每个元素均有唯一一个直接后继。
线性表的顺序存储
在高级语言(如C语言)环境下,数组具有随机存取的特性,因此,借助数组来描述顺序表。
顺序存储结构中,很容易实现线性表的一些操作:初始化、赋值、查找、修改、插入、删除、求长度等
线性表的链式存储
用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
存储链表中结点的一组任意的存储单元以是连续的或不连续的,甚至是零散分布在内存中的任意位置。
为了正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其直接后继结点的地址(或位置),称为指针(pointer)或链(link),这两部分组成了链表中的结点结构
链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。
每一个结只包含一个指针域的链表,称为单链表。
为操作方便,总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。
双向链表
双向链表(Double Linked List) 指的是构成链表的每个结点中设立两个指针域,一个指向其直接前趋的指针域prior,一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链,故称为双向链表。
和单链表类似,双向链表一般增加头指针也能使双链表的某些运算变得方便。
将头结点和尾结点链接起来也能构成循环链表,并称之为双向循环链表。
双向链表是为了克服单链表的单向性的缺陷而引入的。
双向链表的结点及其类型定义
data
next
prior
双向链表结点形式
……
非空双向链表
head
⋀
a2
a1
an
⋀
空双向链表
head
⋀
⋀
带头结点的双向链表形式