526互联

数据结构复习——王道考研

发布时间 2023-09-05 13:49:41作者: Beasts777

数据结构

一. 绪论

1.1 基本概念

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据类型：是相互之间存在一种或多种特定关系的数据元素的集合。

1.2 数据结构三要素

  1. 逻辑结构：指数据元素之间的逻辑结构，也就是从逻辑上去对数据元素进行处理。
    • 集合结构：集合之中的数据元素除了“同属一个集合之外”再无别的关系。
    • 线性结构：结构中的数据元素只存在一对一的关系。除了第一个元素，所有元素都有唯一的前驱。除了最后一个元素，所有元素都有唯一后驱。
    • 树形结构：结构中的数据元素存在一对多的关系。
    • 图形结构：数据元素之间是多对多的关系。
  2. 存储结构：指数据结构在计算机上的表示。
    • 顺序结构：将逻辑上相邻的元素存储到物理位置上也相邻的存储单元之中，元素之间的关系由存储单元之间的邻近关系进行表示。
    • 链式结构：逻辑上相邻的元素在物理位置上可以不相邻，但可以借助指向元素位置的指针来表示元素之间的逻辑关系。
    • 索引结构：在存储元素信息时，还建立附加的索引表，索引表中的每项被称为索引项，索引项的一般形式是（关键字，地址）。
    • 散列结构：根据元素的关键字直接计算出该元素的存储地址，又称为哈希（Hash）存储。
  3. 运算：施加在数据上的运算包括运算的定义和实现，其中：
    • 运算的定义针对逻辑结构，指出运算的功能。
    • 运算的实现针对存储结构，指出运算的具体操作步骤。

1.3 算法的基本概念

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

算法的特性：

  • 有穷性：一个算法必须在有穷步之后结束，且每一步都在有穷时间内完成。
  • 确定性：算法中的每条指令必须有确定的含义，对于相同的输入只能有相同的输出。
  • 可行性：算法中描述的操作都可以通过已经实现的基本元素按执行有限次来实现。
  • 输入：一个算法有零个或多个输入，这些输入都取自某个特定对象的集合。
  • 输出：一个算法有一个或多个输出，这些输出都是与输入有某种特定关系的量。

好的算法应当具有：

  • 正确性：算法应当能够正确的求解问题。
  • 可读性：算法应当具有良好的可读性，便于人们理解。
  • 健壮性：输入非法数据时，算法能够适当的作出反应和进行处理，而不会产生莫名其妙的结果或者不产生结果。
  • 高效率：算法执行的时间较短，与问题规模有关。
  • 低存储效率：算法执行过程中需要的存储空间，与问题规模有关。

1.4 算法的时间复杂度

一般情况下，算法中的基本重复执行的次数时问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O(n)，它表示时间复杂度随着问题规模n的增大而增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，也就是时间复杂度。

1.5 算法的空间复杂度

算法的空间复杂度S(n)被定义为该算法所消耗的存储空间，是关于问题规模n的函数。记作S(n)=O(g(n))。

二. 线性表

2.1 线性表的定义

定义：线性表是具有相同数据类型的n(n>0)个数据的有限序列，当n=0时，线性表是一个空表。其中，数据元素可以由若干个数据项组成。此外，线性表属于逻辑上的线性结构，除了第一个元素，所有元素都有唯一的前驱。除了最后一个元素，所有元素都有唯一后驱。

2.2 线性表的顺序表示

2.2.1 概述

定义：就是使用一组地址连续的存储单元依次存储线性表的数据元素。显然，此时的线性表存储结构为顺序结构，用物理意义上的相邻来表示逻辑意义上的相邻。

特性：

  • 随机存取。即：只要确认了线性表的起始位置，就能够对其中的任一元素进行随机存取。这一点和数组很像，因此也常用数组来表示数据结构中的顺序存储结构。
  • 存储密度高，每个节点只存储数据元素。
  • 拓展容量不方便。
  • 插入，删除操作不方便，需要移动大量元素。

2.2.2 顺序表的初始化

这里使用可扩容版本，默认初始最大长度为100，扩容时以10为单位。

// 顺序表
#include <stdio.h>
#include <stdlib.h> // 内存分配与释放

#define LIST_INIT_SIZE 100 // 线性表初始化长度
#define LIST_INCREMENT 10   // 线性表每次扩容长度

typedef enum{    //状态码。这里需要注意的是枚举不能直接作为函数返回类型，必须用typedef将其标记为一种数据类型
    ERROR, OK
}Status;

typedef struct      // 封装的数据类型
{
    char sex;
    int age;
} ElemType;

typedef struct          // 顺序表
{
    ElemType *data;
    int length; //顺序表当前长度
    int list_size;  // 当前分配的存储单位，也就是最大长度
} Sqlist;

//顺序表初始化
Status InitList(Sqlist *L){  
    if(L==NULL){    // 当L是空指针时，需要为其分配空间
        L = (Sqlist *) malloc (sizeof(Sqlist));
    }
    // 随后为data分配空间
    L->data = (ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);  // 注意对动态分配的内存进行类型转换
    if (L->data==NULL)
    {
        printf("Memoty allocation failed");
        return ERROR;
    }
    L->length = 0;
    L->list_size = LIST_INIT_SIZE;
    
    return OK;
}

2.2.3 顺序表的基本操作

顺序表的基本操作包括增删改查，依次列写如下：

查：十分简单的操作。如果根据下标查，时间复杂度为O(1；如果根据数据查，平均复杂度为\(\frac{n}{2}\)时间复杂度为O(n)。

// 查找元素,返回它是第几个
int ListFind_Sq(Sqlist *L, ElemType e){
   for (int i = 0; i < L->length; i++)
   {
    if ((L->data+i)->age == e.age && (L->data+i)->sex == e.sex)
        return i+1;
   }
}

增：在指定位置插入一个数据，要求将该位置原有的元素以及后面的元素依次向后移动一位，时间复杂度为O(n)

// 顺序表插入元素：在第i个元素之前
Status ListInsert_Sq(Sqlist *L, int index, ElemType e){
    if (index<1 || index>L->length+1)
    {
        printf("The subscript is illegal");
        return ERROR;
    }
    if (index>=L->list_size) // 此时需要扩容 
    {
        L->data = realloc(L->data, sizeof(ElemType)*(L->list_size+LIST_INCREMENT));
        if (L->data==NULL)
        {
            printf("Memoty reallocation failed");
            return ERROR;
        }
    }
    for (int i = L->length; i > index-1; i--)   //首先从最后一个的后一位开始，依次向前复制
    {
        *(L->data + i) = *(L->data + (i - 1)); 
    }
    *(L->data+index-1) = e;
    L->length++;

    return OK;
}

删：删除指定位置的数据，要求将后面的数据全都向前移动一位，时间复杂度为O(n)

//删除指定位置的数据，并将其用e返回
Status ListDelete_Sq(Sqlist *L, int index, int *e){
    if (index < 1 || index > L->length )
    {
        printf("The subscript is illegal");
        return ERROR;
    }
    *e = L->data+index-1;
    for (int i = index - 1 ; i < L->length-1 ; i++)
    {
        *(L->data+i) = *(L->data+i+1);
    }
    L->length--;
    
    return OK;
}

改：步骤基本一致，这里省略。

2.3 线性表的链式表示

2.3.1 概述

定义：用一组任意的存储单元来存储线性表的数据元素，这些存储单元可以连续，也可以不连续。每个元素为了记录与其相邻的元素的位置，需要添加指针域，用于将数据串起来，就像珠子一样。

特性：

  • 删除与插入方便。
  • 容量无限。
  • 无法随机存取。（也就是按位置存取）

2.3.2 线性链表（单链表）

1. 单链表的定义

定义：每个节点只包含一个指针域的表叫做线性链表或单链表。

头结点：是在单链表的第一个节点之前设置的一个结点，数据域一般并不适用，而是用来存放其他信息，如第一个第一个节点的位置，线性表的长度等。

带头节点与不带头节点：

  • 不带：不利于代码的书写，对第一个数据节点和后续数据节点需要有不同的处理方式，对空表和非空表的处理也使用不同的代码。此时头指针指向的结点用于存放数据。
  • 带：代码书写较为简单，对不同节点的处理逻辑基本一致，头指针指向的头节点不存放数据，头节点指向的下一个结点才存放数据。

单链表的初始化

// 链表
#include <stdio.h>
#include <stdlib.h>

typedef enum {
    ERROR, OK
} Status;

typedef struct {
    short age;
    int id;
} ElemType;

typedef struct LNode 
{
    ElemType data;
    struct LNode *next; 
        // C中的指针都是long类型，大小固定，它指向的是变量占据的空间，而不是数据类型。因此可以实现嵌套
        // 结构体类型在使用时必须加上struct前缀，如果想不加前缀直接使用，则使用typedef将其定义为数据类型
}LNode, *LinkList;  // 这里的LinkList是一个指向LNode类型的一维指针

// ---------不带头结点的单链表初始化,此时第一个节点就承载了数据---------
Status InitList_NoHead(LinkList *L){     // 头指针的值、也就是指向发生了变化，为了实现内外同步，需要使用二重指针 
    *L = NULL; // 此时为空
    return OK;
}

Status IsEmpty_NoHead( LinkList L ){
    if (L==NULL)
        return OK;
    return ERROR;  
}

// --------------带头结点的单链表，第一个结点不承载数据，仅用于记录其他信息----------------------
// 初始化
Status InitList(LinkList *L){   // 这里要同步变更传入的头指针的指向，所以使用二重指针    
    *L = (LinkList) malloc (sizeof(LNode));
    if (*L==NULL)
    {
        printf("Memory allocation failed");
        return ERROR;
    }
    (*L)->next = NULL;
    return OK;
}

Status IsEmpty(LinkList L){
    if (L->next == NULL)
        return ERROR;
    return OK;  
}

int main(){
    return 0;
}
2. 单链表的基本操作的实现

按位插入：带头节点

因为有头节点，所有第0个结点为头节点，第一个实际存储数据的结点就是第一个结点。

// 按位插入（带头节点）
Status ListInsert(LinkList L, int index, ElemType e){
    if ( index < 1) // 合法性检验
        return ERROR;
    LNode *p;   // 用于遍历链表的指针。
    int j = 0;  // 记录当前遍历到第几个了
    p = L;      // 先指向头节点
    while (p!=NULL && j<index-1)    // 需要遍历到index前面的一个，
    {
        p = p->next;
        j++;
    }
    if (p==NULL)    // 说明链表没有那么长
    {
        printf("The subscript is illegal");
        return ERROR;
    }
    LNode * node = (LNode *)malloc(sizeof(LNode));  //由于新插入了一个结点，因此需要分配内存
    if (node == NULL){
        printf("Memory allocation failed");
        return ERROR;
    }
    node->data = e; 
    node->next = p->next;   // 注意这里替换的顺序
    p->next = node;

    return OK;   
}

按位插入：不带头节点

这里的关键在于index=1时的插入，由于在插入时函数内头节点的指向变化了，我们需要main函数内头结点的指针也发生变化，因此使用二级指针，即“指向指针的指针”。

// 按位插入，不带头结点。需要注意：此时如果在第一个位置插入，逻辑与在后面的元素插入不同
Status ListInsert_NoHead(LinkList *L, int index, ElemType e){
    if (index < 1)
        return ERROR;
    if (index == 1) // 此时头指针L需要变更指向
    {
        LNode *temp = (LNode *)malloc(sizeof(LNode));
        if (temp == NULL)
            return ERROR;
        temp->data = e;
        temp->next = *L;
        *L=temp;
        return OK;
    }
    // 剩下的操作和带头结点的按位插入一致，不过j的起始值不一样
    LNode *p = *L;
    int j = 0;
    while (p!=NULL && j<index-2)    
    {
        p=p->next;
        j++;
    }
    LNode *temp = (LNode *)malloc(sizeof(LNode));
    if (temp==NULL)
        return ERROR;
    temp->data = e;
    temp->next = p->next;
    p->next = temp;

    return OK;  
}

指定结点后插入

带不带头节点方法都一样。

// 指定节点的后插操作（带不带头节点都一样）
Status InsertNextNode(LNode *p,  ElemType e){
    if (p == NULL)  // 传入的节点为空，无法插入
        return ERROR;
    LNode *node = (LNode *)malloc(sizeof(LNode));
    if (node == NULL)   // 内存分配失败
        return ERROR;
    node->data = e;     // 后插
    node->next = p->next;
    p->next = node;
    
    return OK;    
}

有了这个方法，按位插入可以进行化简，以带头指针的按位插入为例：

// 按位插入（带头节点）
Status ListInsert(LinkList L, int index, ElemType e){
    if ( index < 1) // 合法性检验
        return ERROR;
    LNode *p;   // 用于遍历链表的指针。
    int j = 0;  // 记录当前遍历到第几个了
    p = L;      // 先指向头节点
    while (p!=NULL && j<index-1)    // 需要遍历到index前面的一个，
    {
        p = p->next;
        j++;
    }
    if (p==NULL)    // 说明链表没有那么长
    {
        printf("The subscript is illegal");
        return ERROR;
    }
    InsertNextNode(p, e);

    return OK;   
}

指定结点前插入

由于单链表只能向后看，因此我们无法直接前插。假设要在p的其前面插入s，可以先将s插入p的后面，再将s和p的数据互换即可。如此即满足了逻辑关系，又能实现时间复杂度O(1)。

// 指定节点的前插操作（带不带头节点都一样）
Status InsertPriorNode(LNode *p,  ElemType e){
    if (p==NULL)
        return  ERROR;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL)
        return ERROR;
    // 先进行后插
    s->next = p->next;
    p->next = s;
    // 随后交换值
    s->data = p->data;
    p->data = e;

    return OK;
}

按位序删除节点：带头节点

分析：带头节点的情况下，第0个结点为头节点，从1开始的结点承载数据。要删除第i个结点，则将(i-1)->next = i->next，随后释放第i个结点即可。

// 按位序删除结点：带头结点
Status ListDelete(LinkList L, int index, ElemType *e){  // e用来返回被删除的节点的值
    if (index < 1)  // 下标不合法
        return ERROR;
    LNode *p;
    int j = 0;
    p = L;
    while (p!=NULL && j<index-1)    // 找到第i-1个结点
    {
        p = p->next;
        j++;
    }
    if (p==NULL)    // 链表长度不够
        return ERROR;
    
    LNode *s;
    s = p->next;
    *e = s->data;     // 返回被删除的结点
    p->next = s->next;    // 将i-1个结点的下一个结点设置为i+1
    free(s);  // 释放空间

    return OK;
}

时间复杂度分析：

  • 最坏、平均时间复杂度：O(n)
  • 最好时间复杂度：O(1)

指定结点的删除(带不带头结点都一样)

分析：单链表无法根据当前节点获取上一个节点（除非遍历，比较地址，但这会导致时间复杂度上升为O(n)），因此这里采用另一种思路：想要释放一个结点，必须知道该节点的前驱和后继，所以我们将当前结点变成后一个节点，我们又知道后一个节点的前驱和后继，因此删除后一个节点，如此实现曲线救国。

  1. 假设想要删除的节点为N1，后面的结点依次为N2、N3。
  2. 先记录结点N2。
  3. 将N2的数据复制到N1。
  4. 将N1的next设置为N3。
  5. 释放N2。完成，时间复杂度为O(1)。
// 指定节点的删除（带不带头节点都一样）
Status DeleteNode(LNode *p){
    if (p==NULL)
        return ERROR;
    // 将后一个节点的数据复制到当前节点，将当前节点的next指向下下个结点，随后释放下一个节点，如此等价于删除当前节点。
    LNode *q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q);
}
3. 单链表的查找

按位查找：带头结点

// 按位查找，获取第I个元素
LNode * GetELem(LinkList L, int index){
    if (index < 1)
        return NULL;
    LNode *p;
    int j = 0;
    p = L;
    while (p!=NULL && j<index)
    {
        p = p->next;
        j++;
    }
    return p;
}

平均时间复杂度：O(n)

按值查找：带头结点

LNode * LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    //p指向第一个结点
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           //找到后返回该结点指针，否则返回NULL
}

求单链表的长度：带头结点

需要注意的是，在计算带头结点的单链表的长度时，并不对头节点计数。

// 计算长度（带头结点，但不对头结点进行计数）
int Length(LinkList L){
    int len = 0;
    LNode *p = L;
    while (p->next!=NULL)
    {
        p = p->next;
        len++;
    }
    return len; 
}
4. 单链表的建立

以带头结点的单链表为例：

头插法建立单链表

每一个新的结点都插到头结点后面。时间复杂度为O(n)。

// 头插法建立单链表(带头结点)
LinkList List_HeadInsert(LinkList L){
    LNode *p;
    ElemType e = {1, 1000};
    // 建立头结点
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    // 从头部依次插入
    for (int i = 0; i < 10; i++)
    {
        p = (LNode *)malloc(sizeof(LNode));
        p->data = e;
        p->next = L->next;
        L->next = p;
    }

    return L;
}

尾插法建立单链表

每个新节点都查到链表的尾部，因此需要一个指针始终指向链表的尾部，好处在于表内的数据顺序和插入的顺序一致。时间复杂度为O(n)。

// 尾插法建立单链表(带头结点)
LinkList List_TailInsert(LinkList L){
    L = (LNode *)malloc(sizeof(LNode));
    if (L==NULL)
        return ERROR;
    L->next = NULL;

    LNode *r = L; // 指向尾部的指针
    LNode *node=NULL; //用来分配空间的指针
    ElemType e = {0, 1000};
    
    for (int i = 0; i < 10; i++)
    {
        node = (LNode *)malloc(sizeof(LNode));
        node->data = e;
        r->next = node;
        r = node;
    }
    r->next = NULL; // 尾结点置空

    return L;
}

链表的逆置

将原链表中的结点依次删除，再逐个插入逆置链表的表头（也就是头插法），直到结尾。

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;     //p指针指向第一个结点
	L->next = NULL;  //头结点指向NULL

	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;  
		L->next = q;
	}
	return L;
}
5. 双链表