常用的数据结构.pdfVIP

常用的数据结构

1、线性数据结构：典型的有：数组、栈、队列和线性表

（1）数组和链表

a、数组：存放着一组相同类型的数据，需要预先指定数组的长度，有一维数组、

二维数组、多维数组等

b、链表：链表是C语言中一种应用广泛的结构，它采用动态分配内存的形式实

现，用一组任意的存储单元存放数据元素链表的，一般为每个元素增设指针域，用

来指向后继元素

c、数组和链表的区别：

从逻辑结构来看：数组必须事先定义固定的长度，不能适应数据动态地增减的情

况；链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插

入、删除数据项（数组中插入、删除数据项时，需要移动其它数据项）

从内存存储来看：（静态)数组从栈中分配空间（用NEW创建的在堆中）,对于程

序员方便快速,但是自由度小；链表从堆中分配空间,自由度大但是申请管理比较麻

烦

从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机

访问；链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序

访问，所以访问效率比数组要低

（2）栈、队列和线性表：可采用顺序存储和链式存储的方法进行存储

顺序存储：借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系

链式存储：借助表示数据元素存储地址的指针表示元素之间的逻辑关系

a、栈：只允许在序列末端进行操作，栈的操作只能在栈顶进行，一般栈又被称为

后进先出或先进后出的线性结构

顺序栈：采用顺序存储结构的栈称为顺序栈，即需要用一片地址连续的空间来

存储栈的元素，顺序栈的类型定义如下：

b、队列：只允许在序列两端进行操作，一般队列也被称为先进先出的线性结构

循环队列：采用顺序存储结构的队列，需要按队列可能的最大长度分配存储空

空，其类型定义如下：

链队列：采用链式存储结构的队列称为链队列，一般需要设置头尾指针只是链

表的头尾结点：

c、线性表：允许在序列任意位置进行操作，线性表的操作位置不受限制，线性表

的操作十分灵活，常用操作包括在任意位置插入和删除，以及查询和修改任意位置

的元素

顺序表：采用顺序存储结构表示的线性表称为顺序表，用一组地址连续的存储

单元一次存放线性表的数据元素，即以存储位置相邻表示位序相继的两个元素之间

的前驱和后继关系，为了避免移动元素，一般在顺序表的接口定义中只考虑在表尾

插入和删除元素，如此实现的顺序表也可称为栈表：

线性表：一般包括单链表、双向链表、循环链表和双向循环链表

单链表：

双向链表：

线性表两种存储结构的比较：

顺序表：

优点：在顺序表中，逻辑中相邻的两个元素在物理位置上也相邻，查找比较方

便，存取任一元素的时间复杂度都为O(1)

缺点：不适合在任意位置插入、删除元素，因为需要移动元素，平均时间复杂度

为O(n)

链表：

优点：在链接的任意位置插入或删除元素只需修改相应指针，不需要移动元素；

按需动态分配，不需要按最大需求预先分配一块连续空空

缺点：查找不方便，查找某一元素需要从头指针出发沿指针域查找，因此平均时

间复杂度为O(n)

2、树形结构：结点间具有层次关系，每一层的一个结点能且只能和上一层的一个

结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系，常见类型

有：树、堆

（1）二叉树：二叉树是一种递归数据结构，是含有n(n=0)个结点的有限集合，

二叉树具有以下特点：

二叉树可以是空树；二叉树的每个结点都恰好有两棵子树，其中一个或两个可能为

空；二叉树中每个结点的左、右子树的位置不能颠倒，若改变两者的位置，就成为

另一棵二叉树

（2）完全二叉树：从根起，自上而下，自左而右，给满二叉树的每个结点从1到

n连续编号，如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一

对应，则称为完全二叉树

a、采用顺序存储结构：用一维数组存储完全二叉树，结点的编号对于与结点的下

标（如根为1，则根的左孩子为2*i=2*1=2，右孩子为2*i+1=2*1+1=2）

b、采用链式存储结构：

二叉链表：

三叉链表：它的结点比二叉链表多一个指针域parent，用于执行结点的双亲，便

于查找双亲结点

两种存储结构比较：对于完全二叉树，采用顺序存储结构既能节省空间，又可利用

数组元素的下标值确定