数据结构与算法

数据结构（英语：data structure）是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。

为什么要学习数据结构和算法？

随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，

而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

常见的10种数据结构

1、数组

数组：数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。

定义结构体数组的方法很简单，同定义结构体变量是一样的，只不过将变量改成数组。

或者说同普通数组的定义是一模一样的，如：

structSTUDENT stu[10];

这就定义了一个结构体数组，共有 10 个元素，每个元素都是一个结构体变量，都包含所有的结构体成员。

结构体数组的引用与引用一个结构体变量在原理上是一样的。只不过结构体数组中有多个结构体变量，我们只需利用 for 循环一个一个地使用结构体数组中的元素。

下面编写一个程序，编程要求：从键盘输入 5 个学生的基本信息，如姓名、年龄、性别、学号，然后将学号最大的学生的基本信息输出到屏幕（如果相同则输出最后一个）。

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
# include <stdio.h>
# include <string.h>
/*
编程要求：
    从键盘输入 5 个学生的基本信息，如姓名、年龄、性别、学号，然后将学号最大的学生的基本信息输出到屏幕（如果相同则输出最后一个）。
*/
struct STU
{
    char name[20];
    int age;
    char sex;
    char num[20];
};
void OutputSTU(struct STU stu[5]);  //函数声明, 该函数的功能是输出学号最大的学生信息
int main(void)
{
    int i;
    struct STU stu[5];
    for (i = 0; i<5; ++i)
    {
        printf("请输入第%d个学生的信息:", i + 1);
        scanf("%s%d %c%s", stu[i].name, &stu[i].age, &stu[i].sex, stu[i].num);/*%c前面要加空格, 不然输入时会将空格赋给%c*/
    }
    OutputSTU(stu);
    system("PAUSE");//结束不退出
}
void OutputSTU(struct STU stu[5])
{
    struct STU stumax = stu[0];
    int j;
    for (j = 1; j<5; ++j)
    {
        if (strcmp(stumax.num, stu[j].num) < 0)  //strcmp函数的使用
        {
            stumax = stu[j];
        }
    }
    printf("学生姓名：%s 学生年龄：%d 学生性别：%c 学生学号：%s\n", stumax.name, stumax.age, stumax.sex, stumax.num);
}

2、链表

链表：链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。

链表，别名链式存储结构或单链表，用于存储逻辑关系为 "一对一" 的数据。链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

例如，使用链表存储 {1,2,3}，数据的物理存储状态如图 1 所示：

我们看到，图 1 根本无法体现出各数据之间的逻辑关系。

对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。如图 2 所示：

像图 2 这样，数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构。

链表有单链表、双向链表、静态链表，展开说的话比较多，这里就演示单链表，想要学习更多链表直接点击链接进入学习。

链表的节点

从图 2 可以看到，链表中每个数据的存储都由以下两部分组成：

数据元素本身，其所在的区域称为数据域；
指向直接后继元素的指针，所在的区域称为指针域；

即链表中存储各数据元素的结构如图 3 所示：

图 3 所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如图 4 所示：

因此，链表中每个节点的具体实现，需要使用 C 语言中的结构体，具体实现代码为：

typedef struct Link{
    char elem; //代表数据域
    struct Link * next; //代表指针域，指向直接后继元素
}link; //link为节点名，每个节点都是一个 link 结构体

提示，由于指针域中的指针要指向的也是一个节点，因此要声明为 Link 类型（这里要写成 struct Link* 的形式）。

头节点，头指针和首元节点

其实，图 4 所示的链表结构并不完整。一个完整的链表需要由以下几部分构成：

头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
节点：链表中的节点又细分为头节点、首元节点和其他节点：

头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
其他节点：链表中其他的节点；

因此，一个存储 {1,2,3} 的完整链表结构如图 5 所示：

注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。

明白了链表的基本结构，下面我们来学习如何创建一个链表。

链表的创建（初始化）

创建一个链表需要做如下工作：

声明一个头指针（如果有必要，可以声明一个头节点）；
创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

例如，创建一个存储 {1,2,3,4} 且无头节点的链表，C 语言实现代码如下：

link * initLink(){
    link * p=NULL;//创建头指针
    link * temp = (link*)malloc(sizeof(link));//创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp;//头指针指向首元节点
    //从第二个节点开始创建
    for (int i=2; i<5; i++) {
     //创建一个新节点并初始化
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        //将temp节点与新建立的a节点建立逻辑关系
        temp->next=a;
        //指针temp每次都指向新链表的最后一个节点，其实就是 a节点，这里写temp=a也对
        temp=temp->next;
    }
    //返回建立的节点，只返回头指针 p即可，通过头指针即可找到整个链表
    return p;
}

3、堆

堆：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。

二叉堆是完全二元树或者是近似完全二元树，它分为两种：最大堆和最小堆。

最大堆：父结点的键值总是大于或等于任何一个子节点的键值；

最小堆：父结点的键值总是小于或等于任何一个子节点的键值。示意图如下：

假设在最大堆[90,80,70,60,40,30,20,10,50]种添加85，需要执行的步骤如下：

如上图所示，当向最大堆中添加数据时：先将数据加入到最大堆的最后，然后尽可能把这个元素往上挪，直到挪不动为止！

将85添加到[90,80,70,60,40,30,20,10,50]中后，最大堆变成了[90,85,70,60,80,30,20,10,50,40]。

/*
 * 最大堆的向上调整算法(从start开始向上直到0，调整堆)
 *
 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 参数说明：
 *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
 */
static void maxheap_filterup(int start)
{
    int c = start;            // 当前节点(current)的位置
    int p = (c-1)/2;        // 父(parent)结点的位置 
    int tmp = m_heap[c];        // 当前节点(current)的大小
    while(c > 0)
    {
        if(m_heap[p] >= tmp)
            break;
        else
        {
            m_heap[c] = m_heap[p];
            c = p;
            p = (p-1)/2;   
        }       
    }
    m_heap[c] = tmp;
}
/* 
 * 将data插入到二叉堆中
 *
 * 返回值：
 *     0，表示成功
 *    -1，表示失败
 */
int maxheap_insert(int data)
{
    // 如果"堆"已满，则返回
    if(m_size == m_capacity)
        return -1;
    m_heap[m_size] = data;        // 将"数组"插在表尾
    maxheap_filterup(m_size);    // 向上调整堆
    m_size++;                    // 堆的实际容量+1
    return 0;
}

4、栈

栈：栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。

栈是限制插入和删除只能在一个位置上进行的线性表。其中，允许插入和删除的一端位于表的末端，叫做栈顶（top），不允许插入和删除的另一端叫做栈底（bottom）。

对栈的基本操作有 PUSH（压栈）和 POP （出栈），前者相当于表的插入操作（向栈顶插入一个元素），后者则是删除操作（删除一个栈顶元素）。

栈是一种后进先出（LIFO）的数据结构，最先被删除的是最近压栈的元素。

栈就像是一个箱子，往里面放入一个小盒子就相当于压栈操作，往里面取出一个小盒子就是出栈操作，取盒子的时候，最后放进去的盒子会最先被取出来，最先放进去的盒子会最后被取出来，这即是后入先出。

下面是一个栈的示意图：

如下入栈出栈示例：

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
//元素elem进栈
int push(int* a, int top, int elem){
    a[++top] = elem;
    return top;
}
//数据元素出栈
int pop(int * a, int top){
    if (top == -1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n", a[top]);
    top--;
    return top;
}
int main() {
    int a[100];
    int top = -1;
    top = push(a, top, 1);
    top = push(a, top, 2);
    top = push(a, top, 3);
    top = push(a, top, 4);
    top = pop(a, top);
    top = pop(a, top);
    top = pop(a, top);
    top = pop(a, top);
    top = pop(a, top);
    system("PAUSE");//结束不退出
}

基础夯实：基础数据结构与算法(一) （上）

数据结构与算法

为什么要学习数据结构和算法？

常见的10种数据结构

1、数组

2、链表

3、堆

4、栈

热门文章

最新文章

相关课程

相关电子书