数据结构与算法

基本概念和术语

数据(Data)是描述客观事物的数的符号的集合，是所有能输入到计算机中并被计算机程序处理的符号的总称（集合)。

数据项(Data Item)是组成数据元素的、有独立含义的、不可分割的最小单位。

数据对象(Data Object)是性质相同的数据元素的集合，是数据的一个子集。

数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构和存储结构

逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。

物理结构/存储结构：数据的逻辑结构在计算机中(内存)的存储形式。分为顺序存储结构、链式存储结构、索引存储结构、散列存储结构。

数据类型和抽象数据类型

数据类型：C语言中提供int,char,float,double等基本数据类型；数组、结构、共用体、枚举等构造数据类型；还有指针、空(void)类型，用户也可用typedef自己定义数据类型。而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。

在C语言中，数据类型可以分为两类：

原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等。 结构类型：由若干个类型组合而成，是可以再分解的。包括数组、结构体等。

抽象数据类型：(Abstract Data Type, ADT​)一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

抽象数据类型可用(D,S,P)三元组表示（离散数学上的概念）其中： D是数据对象； S是D上的关系集； P是对D的基本操作集。

算法

算法：对特定问题求解步骤的一种描述。它是为指令的有限序列。其中每条指令表示计算机的一个或多个操作。

算法的特性

  • 有穷性：指算法必须能在执行有限个步骤之后终止。
  • 确定性：算法的每一步骤必须有确切的定义。
  • 可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
  • 有输入：一个算法有零个或多个输入。
  • 有输出 ：一个算法有一个或多个输出。

算法的设计要求

  • 正确性：正确执行预定的功能和性能要求。也是最重要最基本的标准。
  • 可使用性：算法能够很方便地使用。
  • 可读性：便于阅读、理解和交流。
  • 健壮性：指软件对于规范要求以外的输入情况的处理能力。具有很好的容错性。
  • 时间效率高与存储量低：即时间复杂度和空间复杂度低，算法程序耗费的时间短和占用的空间少。
算法分析

(时间效率)运行时间的长短和(空间效率)占用内存空间的大小是衡量算法好坏的重要因素。

衡量算法时间效率的方法主要有两类：事后统计法和事前分析估算法。 通常采用的是事前分析估算法。

算法的时间复杂度

重点

  1. 理解T(n)的大O表示法
  2. 计算简化的算法时间复杂度
  3. 几种常见的时间复杂度分析 https://zhuanlan.zhihu.com/p/50479555
  4. 常用的几种时间复杂度，以及它们之间的大小关系：O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)​平方阶 < O(n3)(立方阶) < O(2n) (指数阶)​
算法的空间复杂度

算法的空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的度量。一般也作为问题规模n的函数，以数量级形式给出，记作 S(n) = O(g(n))。

程序=数据结构+算法

线性表

基础知识
  • 顺序表的基本运算
  • 单链表的插入删除结点操作、建立单链表（头插法）
  • 线性表基本运算在单链表中的实现
两种存储结构对应的运算的时间复杂度
查找序号为i的元素查找第一个值为x的元素插入元素作为第一个元素插入元素作为最后一个元素插入第i个元素删除第一个元素删除最后一个元素删除第i个元素
顺序表O(1)O(n)O(n)O(1)O(n)O(n)O(1)O(n)
带头结点的单链表O(n)O(n)O(1)O(n)O(n)O(1)O(n)O(n)

注：在长度为n的线性表中插入一个元素时所需移动的元素的平均次数为：n/2

在长度为n的线性表中删除一个元素时所需移动的元素的平均次数为：(n-1)/2

两种存储结构的对比
顺序存储结构链式存储结构
有无指针域无有
存储密度较大较小
存储空间开辟一整块空间 利用率较低单独分配空间 利用率较高
是否有随机存储性有无
优点方便查找指定序号的元素插入和删除时不必移动结点

随机存储性：是指查找序号为i的元素与顺序表中元素个数n无关。

(顺序表例题)在线性表中删除x元素 
#define MAXSIZE 100  
typedef int ElemType;  //将ElemType与int类型等同起来
typedef struct         //定义顺序表结构体SeqList
{
    ElemType data[MAXSIZE]; //顺序表中的元素
    int length; //当前顺序表的长度
} SeqList;
//传入顺序表L和要删除的元素x，定义一个函数实现删除操作
void del(SeqList * &L, ElemType x)
{
    int i, k = 0;
    while (i < L->length)
    {
        if (L->data[i] != x) //如果dat[i]不等于x，则i++，k++并把data[i]赋值给data[k]
        {
            i++;
            k++;
            L->data[k] = L->data[i];
        }
        else   //如果dat[i]等于x则只让i++
        {
            i++;
        }
    }
    L->length = k;  //最后把L的长度设置为k，此时的L就是删除掉所有x的顺序表
}
(顺序表例题)快速排序算法 
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE]; //顺序表中的元素
    int length;             //当前顺序表的长度
} SeqList;
​
void soup(SeqList *L, int m, int n) //对L[m]到L[n]快速排序
{
    int i = m, j = n;
    ElemType point = L->data[0]; //定义一个point，把data[0]的值赋值给point作为基准
    if (m >= n)
        return;   //定义了一个出口
    while (i < j) //从顺序表两端交替扫描，直到i等于j为止
    {
        while ((i < j) && (point < L->data[j])) //从右向左扫描找到一个小于等于point的data[j]
            j--;
        L->data[i] = L->data[j];                 //找到这样的data[j]放到data[i]处
        while ((i < j) && (L->data[i] <= point)) //从左向右扫描找到一个大于point的data[i]
            i++;
        L->data[j] = L->data[i]; //找到这样的data[i]放到data[j]处
    }
    L->data[i] = point; //while循环结束后i等于j，把point赋给data[i]
    soup(L, m, i - 1);  //data[i]左边递归
    soup(L, i + 1, n);  //data[i]右边递归
}
(链表例题)删除链表中最大元素 
typedef int ElemType;
typedef struct LNode
{
    ElemType data; //存放元素值
    struct LNode *next; //指向后继节点
}LinkNode;  //单链表结点类型
void del(LinkNode *&L) 
{
    LinkNode *p, *pre, *max, *premax;
    p = L->next;  
    pre = L; //pre始终指向p的前驱结点
    max = p; //初始化max结点
    premax=pre; //初始化max结点的前驱结点
    while (p != NULL) //扫描单链表L
    {
        if (max->data < p->data) //如果发现了比max更大的结点
        {
            max = p;    //更新max
            premax = pre;  //更新premax
        }
        pre = p;   //若没有进入if语句，则让pre和p一起向后移动一个结点
        p = p->next;
    }
    premax->next = max->next; //让premax指向max的next结点，删除max结点
    free(max); //释放max结点
}
创建单链表-头插法

从一个空链表开始依次读取数组a（长度为n）的元素，并生成一个新结点，将元素储存在结点的数据域中，插入到链表的表头上，直至数组a的元素被读完。注意头插法得到的链表元素的顺序和数组a的元素的顺序是相反的。

代码实现

void CreateListF(LinkNode *&L, ElemType a[], int n)
{
    LinkNode *s;
    L = (LinkNode *)malloc(sizeof(LinkNode)); //创建一个头结点
    L->next = NULL; //其next域置为NULL
    for (int i = 0; i < n; i++) //循环创建s结点
    {
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = a[i];  //将s结点的data域置为a[i]
        s->next = L->next; //s的next指向头结点L的next
        L->next = s; //头结点L的next指向s
    }
}