2019-08-24 09:41 已编辑西北工业大学 Java

关注

数据结构总结及实现（详细）

首先声明本篇文章参考链接

文章目录

一、数据结构的一些常见概念
二、数据的物理结构
三、数组的逻辑结构

一、数据结构的一些常见概念

数据元素：数据的基本单位（又称为记录）
数据项：不可分割的最小标识单位
数据对象：相同类型的数据元素的集合
数据结构：相互之间存在一种或多种特定关系的元素的集合
数据类型：是在程序设计语言中已经实现了的数据结构

C语言中常见的基本数据类型:

那什么是数据结构，它包括：

我们常说的：程序 = 数据结构 + 算法，这里的数据结构指的是：数据的逻辑结构 + 存储结构

二、数据的物理结构

常见的物理结构为

a、顺序存储结构（数组实现）：在底层是一组地址连续的存储单元来存储数据

b、链式存储结构（链表实现）：采用动态分配内存的形式实现，用一组任意的存储单元存放数据元素，并为每个元素增设指针域，用来指向后继元素

*数组和链表的区别：

从逻辑结构来看：数组必须事先定义固定的长度，不能适应数据动态地增减的情况；链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项
从内存存储来看：（静态)数组从栈中分配空间（用NEW创建的在堆中）, 对于程序员方便快速，但是自由度小；链表从堆中分配空间, 自由度大但是申请管理比较麻烦
从访问方式来看：数组在内存中是连续存储的，因此，可以利用下标索引进行随机访问；链表是链式存储结构，在访问元素的时候只能通过线性的方式由前到后顺序访问，所以访问效率比数组要低

三、数组的逻辑结构

逻辑结构主要分为以下四类：

集合	线性结构	树形结构	图形结构
结构中的数据元素之间除了“同属于一个集合”的关系之外，别无其他关系	数据元素之间属于“一对一”的关系常见类型：线性表、栈、队列	结点间具有层次关系，每一层的一个结点能且只能和上一层的一个结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系常见类型有：树、堆	在图形结构中，允许多个结点之间相关，称为“多对多”关系

下面分别对这4种数据结构做个介绍：

1、线性数据结构：线性表、栈、队列

1.1 线性表

线性表按底层结构的不同分为：顺序表和链表，这两种存储结构的比较：

线性表的分类：

1.1.1 顺序表：采用顺序存储结构表示的线性表

顺序表实现方式不同又分为静态顺序表（静态数组实现）和动态顺序表（动态数组实现）。

静态顺序表的代码实现
动态顺序表的代码实现

1.1.2 链表：采用链式存储结构表示的线性表

分类方式	类别1	类别1
按照指针数量分	单链表：只有一个指向下一个节点的指针。	双链表：有一个指向下一个节点的指针，还有有一个指向上一个节点的指针。
链表是否循环分	循环链表：即链表的尾指针指向头结点	不循环链表
链表按照头结点分	带头结点的链表：链表中的第一个结点中不存放有效的数据（相当于哨兵）	不带头结点的链表：链表中的第一个节点为有效结点

其中以（不带头节点，不循环的单链表）和（带头节点，循环的双链表）最为重要。

不带头节点，不循环的单链表的代码实现
带头节点，循环的双链表的代码实现

1.2 栈、队列

栈与队列是两种重要的线性数据结构，也是两种特殊的线性数据结构。从数据的逻辑结构角度看，栈和队列是线性表；从运算看，栈和队列的基本运算是线性表运算的子集，是操作受限的线性表。

1.2.1 栈

栈：一种特殊的线性表，它的插入和删除元素操作其只允许在线性表固定的一端进行。
允许进行数据操作的一端称为栈顶，另一端称为栈底。
处于栈顶位置的数据元素成为栈顶元素
不含任何元素的栈称为空栈
栈又称为后进先出的线性表

和线性表类似，栈也有两种存储结构：顺序存储结构和链式存储结构。

a. 顺序栈

通常由一个一维静态数组和一个记录栈顶元素位置的变量组成。习惯上将栈底放在数组下标小的那端。

顺序栈所有的操作时间复杂度为O(1)

顺序栈的代码实现

b. 链栈

采用链式存储结构的栈简称为链栈，其组织形式与单链表类似。其中，单链表的第一个结点就是链栈栈顶结点，栈由栈顶指针唯一确定，栈底结点的next指向NULL，因为链栈本身没有容量限制，故不存在栈满的情况。

链栈的代码实现

c. 栈的应用

括号匹配问题
逆波兰表达式（后缀表达式）
迷宫

1.2.2 队列

队列也是一种运算受限的线性表，在队列上，插入限定在某一端进行，删除限定在另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。新插入的结点只能添加到队尾，被删除的只能是排在队头的结点。

进行插入操作的一端称为队尾（入队列）
进行删除操作的一端称为队头（出队列）
队列具有先进先出的特性

队列的分类：

a. 顺序队列

由一个一维数组及两个分别指向队头front和队尾rear的变量组成。

它的操作有两种方式：

队头指针不动，队头元素出队后后面的所有元素向队头移动。缺陷：操作时如果出队列比较多，要搬移大量元素。
队头移动，出队时队头向后移动一个位置。如下图，此时如果再有F、G进栈，就会出现假溢出的情况。

b. 循环队列（环形队列）

为了能够充分利用数组的存储空间，可以把数组的前端和后端连接起来，形成一个环形的表，这个环形的表称为循环队列。

那循环队列如何判断队列空和满呢？

少用一个存储单元
设置一个标记位
设置一个计数器

顺序队列进行入队列和出队列时时间性能不是很好，循环队列虽然能够解决假溢出的问题，但循环队列又面临着真溢出的问题。

循环队列的代码实现

c. 链式队列

链式队列实际上是一个同时带有一个首指针和尾指针的单链表，首指针指向头结点，尾指针指向队尾节点。

链式队列的代码实现

d. 优先级队列

带有优先级的队列称为优先级队列

队列具有先进先出的特性，即最先进入队列的元素将被最先出队列，有时也需要把进入队列中的元素分优先级(比如线程调度)，出队列时首先选择优先级最高的元素出队列，对于优先级相同的元素则按照先进先出的原则出队列

e. 队列的应用

生产者消费者模型
消息队列
排队现象
网络数据传输

1.3 广义表

广义表是线性表的推广。广义表GL = (a1,a2,a3…,an)，如果ai是单个数据元素，则称ai是广义表的原子；如果ai也是一个广义表，则称ai是广义表的子表。在广义表中要求各原子具有相同的类型，但允许各子表具有不同的结构。

举一个广义表的例子：D=((a,b), ( c), d, ((e,f),g))，这个广义表D有4个元素，其中4表示广义表的长度。D中所包含括号的最大层数称为广义表的`深度``，D的深度 = 3。广义表的第一个元素称为广义表的表头（head(D) = (a,b)），除表头外，其余部分称之为表尾（tail(D)=(( c), d, ((e,f),g)）。原子和空表没有表头和表尾。

广义表通常使用链式存储结构（带头节点），链表中的每一个结点对应广义表中的一个元素。其中节点有不同的类型：

前面广义表D的存储结构如下图所示：

广义表的实现

2、树形结构：树、堆

树形结构：结点间具有层次关系，每一层的一个结点能且只能和上一层的一个结点相关，但同时可以和下一层的多个结点相关，称为“一对多”关系。

2.1 树

树是递归定义的：由N(n>=0)个结点构成的集合。当n=0时，称为空树；当n>1时，树有：

有一个特殊的结点，称为根结点，根节点没有前驱结点
除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

关于树的相关概念：

结点：结点包括一个数据元素及若干指向其他子树的分支(指针(索引))
结点的度：结点所拥有子树的个数称为该结点的度
树的度：树中所有结点的度的最大值称为该树的度
叶子结点（终端节点）：度为0的结点称为叶子结点
分支结点（非终端节点）：度不为0的结点称为分支结点，一棵树中除叶节点外的所有节点都是分支结点
祖先结点：从根节点到该结点所经分支上的所有节点
子孙结点：以某节点为根节点的子树中所有节点
双亲结点（前驱结点）：一个结点称之为其后继结点的双亲节点。
孩子结点（后继结点）：树中一个节点的子树的根节点称为该结点的孩子结点
兄弟结点：具有同一双亲的结点之间互称为为兄弟结点
结点层次：从根节点到树中某节点所经路径上的分支数称为该结点的层次，根结点为第一层，其孩子节点为第二层，以此类推。
树的深度（高度）：树中所有节点层次的最大值称为该树的深度
有序树和无序树：树中各结点从左到右是有次序的，即若交换了某结点各子树的相对位置则构成了不同的树，那么称之为有序树，反之则为无序树。
森林：m棵树的集合(m大于等于0)。在自然界中树和森林是两个不同的概念，但在数据结构中，它们之间的差别很小。删去一棵非空树的根节点，树就变成森林；反之若增加一个节点，让森林中每一棵树的根节点都变成他的子女，森林就变成一棵树

树的存储结构

计算机中存储树的信息，要求既要存储结点的数据元素信息，又要存储结点之间的逻辑关系信息

下面介绍常用的存储结构：

1. 双亲表示法

双亲表示法：

优点：寻找一个节点的双亲结点操作实现很方便
缺点：寻找一个节点的孩子结点很不方便

对于下图的树的存储，双亲表示法有两种实现方式：

1. 一维数组实现	2. 用指针表示出每个结点的双亲节点
用一维数组存储树中的各个结点，其中数组元素是个记录，包含data和parent两个字段，分别表示结点的数据值和其双亲在数组中的下标。

2. 孩子表示法

孩子表示法：

优点：寻找一个节点的孩子结点比较方便
缺点：寻找一个节点的双亲结点很不方便

孩子表示法的实现方式：用指针表示出每个结点的孩子结点，但是有个问题：结点的数据结构中应该给几个孩子结点指针呢？，看树的度。

数据结构：

typedef int DataType;
struct Node
{
	struct Node* _pChild1;  
	struct Node* _pChild2;  
	struct Node* _pChild3;  
	DataType _data;  //数据域
};

3. 双亲孩子表示法

双亲孩子表示法：用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点，即：双亲表示法+孩子表示法

typedef int DataType;
struct Node
{
	struct Node* _pParent;  //指向双亲节点
	struct Node* _pChild1;  
	struct Node* _pChild2;  
	struct Node* _pChild3;  
	DataType _data;  //数据域
};

4. 孩子兄弟表示法

孩子兄弟表示法：即表示出每个结点的第一个孩子结点，也表示出每个结点的下一个兄弟结点。孩子兄弟链表存储结构是一种二叉链表，链表中的每一个结点包含两个指针，分别指向对应结点的第一个孩子结点和下一个孩子结点。

typedef int DataType;
struct Node
{
	struct Node* _pChild1;  
	struct Node* _pNextBrother;  
	DataType _data;  //数据域
};

2.1.1 二叉树

二叉树是一种特殊的树。二叉树的特点：

每个结点最多有两棵子树，即二叉树不存在度大于2的结点
二叉树的子树有左右之分，其子树的次序不能颠倒
二叉树即使只有一颗子树也要明确指出该子树是左子树还是右子树。

满二叉树&完全二叉树

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子节点都在同一层上
完全二叉树：从根起，自上而下，自左而右，给满二叉树的每个结点从1到n连续编号，如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称为完全二叉树

二叉树性质

二叉树上叶子结点数等于度为2的节点数加1.

证明：
设在一棵二叉树中，n为所有节点总数，n0为叶子结点个数，n1为度为1的节点个数，n2为度为2的结点个数。

则 n = n0 + n1 + n2 （1）
再看二叉树中的分支数：除根节点外，所有结点都有一个分支进入，设b为分支数，
则 n = b + 1
又因为分支是由度为1或2的结点分出的，因此：
b = n1 + 2 x n2
于是： n = n1 + 2 x n2 + 1 （2）
由（1）（2）得： n0 = n2 +1

二叉树上第i层上至少有2^(i-1)个结点。（i>=1，根结点的层数为1）

证明：数学归纳法

若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k - 1 (k>=0)
对于完全二叉树（n≥1，n为节点数），如果按照从上至下从左至右的顺序对所有节点从1开始编号，则对于序号为i的结点有：
4.1 除树的根节点外，若一个结点的编号为i，则双亲编号为：i/2。也就是说，当i为偶数的时候，其双亲结点编号为i/2，他是双亲节点的左孩子；当i为奇数的时候，其双亲结点编号为(i-1)/2，他是双亲节点的右孩子
4.2 如果 2 * i ≤ n，则编号为i的结点为分支结点；否则为叶子结点。
4.3 若n为奇数，则每个分支结点都既有左孩子又有右孩子；若n为偶数，则编号最大的分支结点只有左孩子，没有右孩子。
4.4 若编号为i的结点有左孩子，则左孩子结点编号为2i；若编号为i的结点有右孩子，则右孩子结点编号为2i+1

二叉树的存储结构

与线性表一样，二叉树也有顺序存储结构和链式存储结构。

顺序存储结构

typedef DataType SqBinTree[MaxSize];   //其中DataType为二叉树结点的数据类型；MAxSize为顺序表的最大长度。

顺序存储一个完全二叉树，首先对该树的节点进行编号，然后以各结点的编号为下标，把各结点的值对应存储到一维数组中。完全二叉树的编号过程为：首先，把树的编号定为1，然后按照层次上从上到下、每层从左到右的顺序对每一结点进行编号。

对于一般二叉树，也可以用这种方法进行存储。首先，在二叉树上补上若干虚拟结点使其成为完全二叉树。然后按照上面的方法进行编号。

下图是个示例：

顺序存储结构的优点：存储完全二叉树，简单省空间；缺点：存储一般二叉树尤其单支树，存储空间利用不高。

二叉链存储结构

链表中每个结点包含两个指针，分别对应结点的左孩子和右孩子。

struct BinTreeNode
{
	struct BinTreeNode* _pLeft;
	struct BinTreeNode* _pRight;
	DataType _data;   
};

这种存储结构的优点是访问结点的孩子很方便，有时为了方便访问结点的双亲可在每个节点中再增加一个指向双亲的指针域。

三叉链存储结构

struct BinTreeNode
{
	struct BinTreeNode* _pParent;
	struct BinTreeNode* _pLeft;
	struct BinTreeNode* _pRight;
	DataType _data;   
};

二叉树的基本操作

假设二叉树采用二叉链存储结构。

建立二叉链

用ch扫描采用括号表示法表示二叉树的字符串str。分为以下几种情况：
1）若 ch == ‘(’ ，则将前面刚创建的结点作为双亲节点进栈，并置k=1，表示其后创建的节点将作为这个节点的左孩子节点。
2）若 ch == ‘(’，表示栈中结点的左右孩子结点处理完毕，退栈。
3）若 ch == ‘,’，k=2，表示其后创建的节点为右孩子结点
4）若 ch 为一个字母，创建一个节点，并根据k值建立它与栈中结点之间的联系，当k=1表示这个节点作为栈中栈顶结点的左孩子结点；当k=2表示这个节点作为栈中栈顶结点的右孩子结点；如此循环直至str处理完毕。算法中使用一个栈st保存双亲节点，top为其栈顶指针；k指定其后处理的结点是双亲节点的左孩子结点还是右孩子。

#define MaxSize 20
typedef char DataType;

typedef struct tnode
{
	DataType data;
	struct tnode* pchild1;
	struct tnode* pchild2;
}BTNode;

//建立二叉链
void CreateBTree(BTNode *&bt, char *str)
{
	BTNode *st[MaxSize], *p = NULL;
	int top = -1, k, j = 0;
	char ch;
	bt = NULL;//建立二叉树初始化为空
	ch = str[j];
	while ('\0' != ch)   //str未扫描完时循环
	{
		switch (ch)
		{
		case '(':top++; st[top] = p; k = 1; break;//左孩子节点
		case ')':top--; break;
		case ',':k = 2; break;  //右孩子结点
		default:
			p = (BTNode*)malloc(sizeof(BTNode));
			p->data = ch;
			p->pchild1 = p->pchild2 = NULL;
			if (bt == NULL)
				bt = p;
			else
			{
				switch (k)
				{
				case 1:st[top]->pchild1 = p; break;
				case 2:st[top]->pchild2 = p; break;
				
				}
			}
		}
		j++;
		ch = str[j];
	}
}

求二叉树高度（递归求法）

int BTHeight(BTNode *bt)
{
	int left, right;
	if (NULL == bt)
	{
		return 0;
	}
	else
	{
		left = BTHeight(bt->pchild1);
		right = BTHeight(bt->pchild2);
		return (left > right) ? (left + 1) : (right + 1);
	}
}

求二叉树结点个数（递归算法）

int NodeCount(BTNode *bt)
{
	int left, right;
	if (NULL == bt)
	{
		return 0;
	}
	else
	{
		left = NodeCount(bt->pchild1);
		right = NodeCount(bt->pchild2);
		return left + right + 1;
	}
}

求二叉树叶子结点个数

int LeafCount(BTNode *bt)
{
	int left, right;
	if (NULL == bt)
		return 0;
	else if (NULL == bt->pchild1 && NULL == bt->pchild2)
		return 1;
	else
	{
		left = LeafCount(bt->pchild1);
		right = LeafCount(bt->pchild2);
		return left + right;
	}
}

以括号表示法输出二叉树

void DisBTree(BTNode *bt)
{
	if (NULL != bt)
	{
		cout << bt->data;
		if (NULL != bt->pchild1 || NULL != bt->pchild2)
		{
			cout << '(';
			DisBTree(bt->pchild1);
			if (NULL != bt->pchild2) cout << ",";
			DisBTree(bt->pchild2);
			cout << ")";
		}
	}
	
}

二叉树的遍历（重要）

所谓二叉树的遍历，是指按照一定次序访问书中的所有节点，使得每个结点恰好被访问一次。

二叉树常用的遍历有：先序遍历（先根遍历）、中序遍历、后序遍历和层次遍历。不同遍历方式区别在于访问根节点的顺序。

对于下面这个二叉树，它对应的遍历方式序列为：

先序遍历：ABDEGHCF

若二叉树为空，则：1）访问根结点；2）先序遍历左子树；3）先序遍历右子树。

void PreOrder(BTNode *bt)
{
	if (NULL != bt)
	{
		cout << bt->data;
		PreOrder(bt->childleft);
		PreOrder(bt->childright);
	}
}

中序遍历：DBGEHAFC

若二叉树为空，则：1）中序遍历左子树；2）访问根节点；3）中序遍历右子树。

void InOrder(BTNode *bt)
{
	if (NULL != bt)
	{
		InOrder(bt->childleft);
		cout << bt->data;
		InOrder(bt->childright);
	}
}

后序遍历：DGHEBFCA

若二叉树为空，则：1）后序遍历左子树；2）后序遍历右子树；3）访问根节点。

void PostOrder(BTNode *bt)
{
	if (NULL != bt)
	{
		PostOrder(bt->childleft);
		PostOrder(bt->childright);
		cout << bt->data;
	}
}

层次遍历：ABCDEFGH

在进行层次访问的时候，对某一层的结点访问完，再按照他们的访问次序对各个结点的左孩子、右孩子顺序访问。

层次访问需要一个环形队列qu来实现：先将根结点进队，在队不空时循环；从队列中出列一个节点*p，访问它；若它有左孩子节点，将左孩子节点进队；若它有右孩子结点，将右孩子结点进队。如此操作直到队空为止。

void LevelOrder(BTNode *bt)
{
	BTNode *p;
	BTNode *qu[MaxSize];//定义环形队列
	int front, rear;//对头与队尾指针
	front = rear = -1;//队列为空
	rear++;
	qu[rear] = bt;   //根节点进入队列
	while (front != rear){         //队列不为空 
		front = (front + 1) % MaxSize;
		p = qu[front];//队头出队列
		printf("%c ", p->data);//访问结点
		if (NULL != p->leftchild)//有左孩子时将其入队
		{
			rear = (rear + 1) % MaxSize;
			qu[rear] = p->leftchild;
		}
		if (NULL != p->rightchild)//有右孩子时将其入队
		{
			rear = (rear + 1) % MaxSize;
			qu[rear] = p->rightchild;
		}
	}
}