数据结构--基础知识

数据结构是计算机存储、组织数据的方式。常见的数据结构有：数组(Array)、栈(Stack)、队列(Queue)、顺序表(SeqList)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等。

栈(Stack)

栈是一种只能在表尾部进行添加和删除元素操作的线性表。是后进先出(First In First Out)的线性表。

特点

进行插入（入栈）和删除（出栈）的一端称为栈顶(top),另一端称为栈底(bottom) ，通常以top = -1表示空栈，栈底不允许操作;

不含任何数据元素的栈称为空栈；

使用数组结构实现的栈称为顺序栈，单链表实现的结构称为链栈。

---

多栈共享技术

一个程序可能需要使用多个栈，使用顺序栈会因为大小难以准确估计，会产生有点栈溢出，有的栈空间空闲的情况，通过多栈共享技术可以让多个栈共享一个足够大的数组空间。

最常用的是两个栈的共享技术，即双端栈。

双端栈

双端栈利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。

方法：

首先为两个栈申请一个共享的一维数组空间S[M] ；

将两个栈的栈底分别放在一维数组的两端，分别是0，M-1 ；

由于两个栈顶是动态变化的，这样可以形成互补：

---

---

队列(Queue)

队列是一种在表一端进行添加元素，另一端进行取出元素的线性表。是先进先出(First In First Out)的线性表。

特点

允许删除的一端称为队头，允许删除的一端称为队尾。

队列可用数组和链表实现，但使用链表的结构更优。如果使用数组的结构，出队列会在数组头上出数据，效率略低。采用链式存储结构的队列称为链队列。

---

链队列

链队列通常采用带头结点的链表结构，并设置一个队头指针和一个队尾指针。空的链队列的队头指针和队尾指针均指向头节点。

//链队列中数据结点
typedef struct Node
{
QueueElementType data; /*数据域*/
struct Node *next; /*指针域*/
}LinkQueueNode;

//链队头结点
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;

---

队列的顺序存储

顺序存储

与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组Queue[MAXSIZE] ；

由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front和rear，分别指示队头元素和队尾元素在数组中的位置初始化队列时，令front = rear = 0：

#define MAXSIZE 50 /*队列的最大长度*/
typedef struct
{
QueueElementType element[MAXSIZE]; /* 队列的元素空间*/
int front; /*头指针指示器*/
int rear ; /*尾指针指示器*/ }SeqQueue;

入队时，直接将新元素送入尾指针rear所指的单元，尾指针增1 ;

出队时，直接取出队头指针front所指的元素，头指针增1 。

顺序存储的缺陷：假溢出

当如图所示的情况时，由于采用rear + 1 == MAXSIZE作为队满条件，且只能在队尾入队，会导致空位置无法使用，这种现象叫做假溢出。

真正队满的条件是：rear – front == MAXSIZE

解决假溢出现象并使得队列空间得到充分利用：构造循环队列

循环队列

把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，

称为环形队列或循环队列；

将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元；

假 设 队 列 数 组 为 Queue[MAXSIZE] ，当rear+1=MAXSIZE时，令rear=0，即可求得最后一个单元Queue[MAXSIZE-1]的后继：Queue[0] ；

实际上内存地址一定是连续的，不可能是环形的。我们通过逻辑方式实现环形队列，也就是将rear++和front++改为:

进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE

出队操作时，队头指针的变化是：front=（front+1）mod MAXSIZE

但只凭rear == front 无法判断队列的状态是“空”还是“满”。

判断空满的方法：

法一：少用一个元素空间

当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队；

队尾指针永远追不上队头指针，所以队满时不会有front =rear；

队列“满”的条件为（rear+1）mod MAXSIZE == front；

判队空的条件不变，仍为rear == front。

法二：增设一个标志量，以区别队列是“空”还是“满”。

---

---

顺序表(SeqList)

特点

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组
上完成数据的增删查改。

顺序表是可动态增长的数组，要求数据是连续存储的。

静态顺序表：使用指定大小的数组存储元素

#define MAXSIZE 10
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType array[MAXSIZE];  //指定大小的数组
	size_t size;          //有效数据个数(最后一个有效数据的下标)
}SeqList;

动态顺序表：使用动态开辟的数组存储元素，当动态数组被填满时，可通过realloc()扩容

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;    //指向动态开辟的数组
	size_t size;      //有效数据个数(最后一个有效数据的下标)
	size_t capacity;  //数组容量大小
}SeqList;

---

---

树(Tree)

特点

树是由n（n≥0）个有限节点组成一个具有层次关系的集合。当n=0时称为空树。

• 没有父节点的固定节点称为根节点；

• 每个非根节点有且仅有一个父节点；

• 每个节点有零个或多个节点；

• 除了根节点外，每个子节点可以分为多个不相交的**子树(SubTree)**；

• 结点拥有的子树数目称为结点的度；

• 度为零的结点为叶子；

• 结点子树的根结点为该结点的孩子结点，相应该结点称为孩子结点的双亲结点， 同一个双亲结点的孩子结点之间互称兄弟结点；

• 树中结点的最大层次数称为树的深度或高度；

• 无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。

• 有序树：如果树中结点的各子树之间的次序是重要的, 不可以交换位置。

• 森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

---

二叉树

在日常的应用中，我们讨论和用的更多的是树的其中一种结构——二叉树。

特点

二叉树具有以下特点：

• 每个节点最多有两个子树，结点的度最大为2；
• 左右子树是有顺序的，次序不能颠倒；
• 即使某结点只有一个子树，也要区分左右子树。

性质：

• 二叉树第i层上的结点数目最多为 2的{i-1}次方 (i≥1)。
• 深度为k的二叉树至多有2的k次方-1个结点(k≥1)。
• 包含n个结点的二叉树的高度至少为**log2 (n+1)**。
• 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。此外，二叉树还有很多扩展类型的数据结构，需要深入的学习。

---

满二叉树、完全二叉树与二叉查找树

满二叉树

每一个层的结点数都达到最大值的二叉树。

• 非叶子结点的度一定是2；
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树（即最后一层从左到右按顺序排列，但未填满）。

• 叶子结点只能出现在最下层和次下层。
• 最下层的叶子结点集中在树的左部。
• 倒数第二层若存在叶子结点，一定在右部连续位置。
• 如果结点度为1，则该结点只有左孩子，即没有右子树。
• 同样结点数目的二叉树，完全二叉树深度最小。

注：满二叉树一定是完全二叉树，但反过来不一定成立。

二叉查找树

二叉查找树又称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。

即通过中序遍历后顺序为从小到大的二分树。

在二叉查找树中：
若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节结点的左、右子树也分别为二叉查找树；
没有键值相等的节结点（no duplicate nodes）。

二叉查找树的代码实现：

typedef int Type;
 
//结点定义
 typedef struct BSTreeNode{
    Type   key;//关键字（键值）
    struct BSTreeNode *left;//左孩子
    struct BSTreeNode *right;//右孩子
    struct BSTreeNode *parent;//父节点
}Node ,*BSTree;

//创建结点
struct Node* create_bstree_node(Type key,Node *parent,Node *left, Node* right)
{
    Node* p;
    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
    {return NULL;}
    p->key = key;
    p->left = left;
    p->right = right;
    p->parent = parent;
 
    return p;
}

---

存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序结构（数组存储，堆）

一般使用数组存储只适合表示完全二叉树，不是完全二叉树会有空间浪费，正常使用只有堆才会使用数组存储，请跳转到堆的部分。

二叉树顺序存储在物理上是个数组，在逻辑上是个二叉树。

链式结构

通过链表表示二叉树，用链指示元素的逻辑关系。通常方法是用三个域组成链表结点：数据域和左右指针域，通过左右指针分别指出左孩子右孩子的结点地址。

链式结构又分为二叉链和三叉链，在基础学习中一般为二叉链，高阶数据结构会用到三叉链。

---

二叉树的四种遍历方式

二叉树的遍历方式：从根节点出发，按照某种次序依次访问二叉树中的所有节点，每个结点仅被访问一次。

通过二叉树遍历，可实现查找、插入、打印、删除等多种操作。

二叉树的遍历需要使用递归。

如何学会递归：为什么你学不会递归？告别递归，谈谈我的经验_递归看不懂-CSDN博客

前序遍历

先访问根节点，然后前序遍历左子树，再前序遍历右子树（根结点 -> 左子树 -> 右子树）。

图示遍历的顺序为：ABDGHCEIF

代码实现：

void preorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        printf("%d ", tree->key);
        preorder_bstree(tree->left);
        preorder_bstree(tree->right);
    }
}

中序遍历

从根结点开始（不是先访问根结点），中序遍历根结点的左子树，再访问根结点，最后中序遍历右子树（左子树 -> 根结点 -> 右子树）。

图示遍历的顺序为：GDHBAEICF

注意：I为E的右孩子，E为I的父结点，所以先E再I。

代码实现：

void inorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        inorder_bstree(tree->left);
        printf("%d ", tree->key);
        inorder_bstree(tree->right);
    }
}

后序遍历

从左到右先叶子后结点的方式访问左右子树，最后访问根结点（从左到右访问叶子结点 -> 根结点）。

图示遍历的顺序为：GHDBIEFCA

代码实现：

void postorder_bstree(BSTree tree)
{
    if(tree != NULL)
    {
        postorder_bstree(tree->left);
        postorder_bstree(tree->right);
        printf("%d ", tree->key);
    }
}

层序遍历

从树的第一层，即根结点开始访问，从上而下逐层遍历，在同一层中按从左到右的顺序对结点逐个访问（第一层 -> 第二层（从左到右访问结点）-> ··· -> 最后一层（从左到右访问结点））。

图示遍历的顺序为：ABCDEFGH

实例

前序遍历输出为：ABDHIEJCFG

中序遍历输出为：HDIBJEAFCG

后序遍历输出为：HIDJEBFGCA

层次遍历输出为：ABCDEFGHIJ

---

二叉树操作

查找：

Node* bstree_search(BSTree x, Type key)
{
    if (x==NULL || x->key==key)
        return x;

    if (key < x->key)
        return bstree_search(x->left, key);
    else
        return bstree_search(x->right, key);
}

查找最大值：

Node* bstree_maximum(BSTree tree)
{
    if (tree == NULL)
        return NULL;

    while(tree->right != NULL)
        tree = tree->right;
    return tree;
}

插入：

//bstree_insert(tree, z)是内部函数，作用是：将结点(z)插入到二叉树(tree)中，并返回插入节点后的根节点
static Node* bstree_insert(BSTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;

    // 查找z的插入位置
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->parent = y;
    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    return tree;
}

//insert_bstree(tree, key)是对外接口，作用是：在树中新增节点，key是节点的值；并返回插入节点后的根节点
Node* insert_bstree(BSTree tree, Type key)
{
    Node *z;    // 新建结点

    // 如果新建结点失败，则返回。
    if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
        return tree;

    return bstree_insert(tree, z);
}

删除：

删除没有左右子树的结点，直接删除即可；

删除只有右子树的结点，用右子树直接代替此结点的位置，整个二分搜索树的性质不变；

删除只有左子树的结点，用左子树直接代替此结点的位置，整个二分搜索树的性质不变；

删除左右都有子树的结点，用右子树中的最小值代替此结点的位置。

示例：

删除左右都有孩子的节点，如下图节点 58：

找到右子树中的最小值，为节点 59：

节点 59 代替待删除节点 58：

//bstree_delete(tree, z)是内部函数，作用是：删除二叉树(tree)中的节点(z)，并返回删除节点后的根节点。
static Node* bstree_delete(BSTree tree, Node *z)
{
    Node *x=NULL;
    Node *y=NULL;

    if ((z->left == NULL) || (z->right == NULL) )
        y = z;
    else
        y = bstree_successor(z);

    if (y->left != NULL)
        x = y->left;
    else
        x = y->right;

    if (x != NULL)
        x->parent = y->parent;

    if (y->parent == NULL)
        tree = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else
        y->parent->right = x;

    if (y != z) 
        z->key = y->key;

    if (y!=NULL)
        free(y);

    return tree;
}

//delete_bstree(tree, key)是对外接口，作用是：在树中查找键值为key的节点，找到的话就删除该节点；并返回删除节点后的根节点。
Node* delete_bstree(BSTree tree, Type key)
{
    Node *z, *node; 

    if ((z = bstree_search(tree, key)) != NULL)
        tree = bstree_delete(tree, z);

    return tree;
}

---

---

堆(Heap)

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。我们通常通过堆使用顺序结构的数组来存储。即堆通常是一个可以被看做一棵完全二叉树的数组对象。

特点

堆是一颗完全二叉树，为非线性数据结构，相当于一维数组；

堆中的某个结点总是不大于或不小于其父节点的值；

根结点最大的堆叫做大根堆，树中的父亲都大于等于孩子；

根结点最小的堆叫做小根堆，树中的父亲都小于等于孩子；

---

堆的实现

向下调整算法

给出一个数组，在逻辑上看作一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小(大)堆。

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = { 27,15,19,18,28,34,65,49,25,37 };

根结点的左右子树均为小堆，我们从根节点开始，将其调整为小堆。

思路

从根节点开始不断向下调；

选出根节点左右孩子中最小的孩子，与父亲进行比较；

若父亲小于孩子，则已经是小堆了，无需处理；

若父亲大于孩子，就将其与父亲交换位置，并以新的孩子(原来的父亲)为根结点继续向下调整，直到叶子结点为止。

代码实现

// 向下调整算法，建小堆，把大的节点往下调整
// 前提是：左右子树都是小堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默认左孩子最小
	int child = parent * 2 + 1;

	while (child < size)
	{
		// 1. 选出左右孩子最小的那个，先判断右孩子是否存在
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++; // 指向右孩子
		}

		// 2. 最小的孩子与父亲比较
		if (a[parent] > a[child]) // 如果父亲大于孩子
		{
			// 父亲与孩子交换位置
			Swap(&a[parent], &a[child]);

			// 更新父子下标，原先最小的孩子作为父亲，继续往下调
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父亲小于孩子，说明已经为小堆了，停止调整
		{
			break;
		}
	}
}

此算法的时间复杂度为 **O(log2n)**。

堆的创建：利用向下调整

下面给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但不是一个堆。我们可以从下到上，从倒数第一个非叶子节点的子树开始，依次对每一个非叶子结点通过向下调整变成大（小）堆，一直到根节点，就能建成一个大（小）堆。

int a[] = { 1,5,3,8,7,6 };

---

从下到上，依次遍历完所有非叶子节点，分别对每个子树进行向下调整。

---

// 向下调整算法建大堆，把小的节点往下调
// 前提是：左右子树都是大堆
void AdjustDown(int* a, int size, int parent)
{
	// 指向左孩子，默认左孩子最大
	int child = parent * 2 + 1;

	while (child < size)
	{
		// 1. 选出左右孩子最大的那个，先判断右孩子是否存在
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++; // 指向右孩子
		}

		// 2. 最大的孩子与父亲比较
		if (a[parent] < a[child]) // 如果父亲小于孩子
		{
			// 父亲与孩子交换位置
			Swap(&a[parent], &a[child]);

			// 更新父子下标，原先最大的孩子作为父亲，继续往下调
			parent = child;
			child = parent * 2 + 1;
		}
		else // 如果父亲大于孩子，说明已经为大堆了，停止调整
		{
			break;
		}
	}
}

void HeapSort(int* a, int size)
{
    /* 建堆（大堆）
    * 倒着调整，从倒数第一个非叶子节点的子树进行向下调整，直到调整到根节点的树
    */
	int parent = ((size - 1) - 1) / 2; // 最后一个叶子节点的父亲的下标
	for (int i = parent; i >= 0; i--)  // 从下到上，依次遍历完所有子树，分别对其进行调整
	{
		AdjustDown(a, size, i);
	}
    /* 堆排序
    * 排升序 --> 建大堆，每次选出一个最大的数放到最后
    * 排降序 --> 建小堆，每次选出一个最小的数放到最后
    */
    // 下面是排升序：
	int end = size - 1; // 记录堆中最后一个元素的下标
	while (end > 0)
	{
		Swap(&a[0], &a[end]);  // 将堆顶元素和堆中最后一个元素交换，把最大的数(堆顶)放到最后
		AdjustDown(a, end, 0); // 不看最后一个数，从根节点开始，对前面的数进行向下调整成大堆
		end--;
	}
}

时间复杂度为O(N)。

堆排序

数据结构–排序算法笔记 | Luvmand

堆的操作

参考：【数据结构入门】堆（Heap）_堆数据结构-CSDN博客

---

---

本文资料均来源于互联网，如有侵权请联系删除