数据结构（概念及链表）-EW帮帮网

1.数据结构的概念

程序由数据结构和算法构成，它是描述数据存储和操作的结构，是操作数据对象的方法。

1.1.衡量代码的质量和效率

1）时间复杂度:数据量的增长与程序运行时间的增长所呈现的比例函数关系，称为时间复杂度。以下是常见的时间复杂度：

O(1) - 常数时间复杂度：

def constant_time(n):
    return n * n  # 无论n多大，操作次数固定

O(n) - 线性时间复杂度：

def linear_time(n):
    total = 0
    for i in range(n):  # 循环次数与n成正比
        total += i
    return total

O(log n) - 对数时间复杂度：

def logarithmic_time(n):
    i = 1
    while i < n:
        i *= 2  # 每次循环i翻倍
    return i

O(n log n) - 线性对数时间复杂度

def linearithmic_time(n):
    result = 0
    for i in range(n):  # 外层循环O(n)
        j = 1
        while j < n:    # 内层循环O(log n)
            j *= 2
            result += 1
    return result

O(n²) - 平方时间复杂度

def quadratic_time(n):
    count = 0
    for i in range(n):      # 外层循环O(n)
        for j in range(n):  # 内层循环O(n)
            count += 1
    return count

O(n³) - 立方时间复杂度

def cubic_time(n):
    count = 0
    for i in range(n):          # 三层嵌套循环
        for j in range(n):
            for k in range(n):
                count += 1
    return count

O(2ⁿ) - 指数时间复杂度

def exponential_time(n):
    if n <= 1:
        return n
    return exponential_time(n-1) + exponential_time(n-2)  # 斐波那契数列的递归实现

O(n!) - 阶乘时间复杂度

def factorial_time(n):
    if n == 0:
        return 1
    count = 0
    for i in range(n):  # 每次递归调用n次
        count += factorial_time(n-1)
    return count

（各个复杂度的运行时间与数据量的变换）

2）空间复杂度:数据的增长与程序占据空间的增长所呈现的比例函数关系，称为空间复杂度。

1.2.数据结构

1.2.1逻辑结构

包括：线性结构（表，一对一），非线性结构（树，一对多），（图，多对多）

1.2.2存储结构

包括：顺序存储，链式存储，散列存储，索引存储

1.2.3数据结构

包括：顺序表，链式表，顺序栈，链式栈，顺序队列，链式队列，二叉树，邻接表，邻接矩阵

2.链表

2.1链表的概念

顺序表（数组）特点：存储空间连续，访问元素方便，无法利用小的空间，必须连续的大空间，顺序表元素必须为有限的（不存在无限连续的空间）插入和删除效率低。

链表特点：存储空间不需要连续，可以利用一些小的存储空间，但访问元素不方便，链表元素可以没有上限，插入和删除效率高。

2.2链表的分类

单向链表：只能通过链表节点找到后一个节点，访问链表元素的方向是单向的

双向链表：能够通过链表节点找到前一个节点和后一个节点

循环链表：能够通过第一节点快速找到最后一个节点，能够通过最后一个节点快速找到第一个节点

内核链表：Linux内核所采用的一种通用的链表结构

3.单向链表

无头链表：频繁传递二级指针，容易出错。

有头链表：只需传递一级指针即可完成各种操作。

3.1定义链表节点类型

//链表存放数据的类型：
typedef int datatype;
//链表节点的类型：
typedef struct node{
    datatype data;
    struct node *pnext;
}linknode;

3.2创立空白节点（头节点）

创建一个空的链表节点，data不需要赋值（最好赋值)，空白节点不存放数据，主要为了保证链表操作的便利性,pnext必须赋值为NULL，表示该节点为最后一个节点,将节点地址返回。

#include"linklist.h"
#include<stdio.h>
#include<stdlib.h>
//创建一个空链表
linknode *create_empty_linklist(void)
{
    linknode *ptmpnode = NULL;
    ptmpnode = malloc(sizeof(linknode));
    if(NULL == ptmpnode)
    {
        perror("file to malloc");
        return NULL;
    }
    ptmpnode->pnext = NULL;
    return ptmpnode;
}

3.3链表的头插法

申请新的节点空间，将存放的数据放入新申请的数据空间中，将新申请节点的pnext赋值为空白节点的pnext，将空白节点pnext赋值为新申请节点

//插入一个节点
int insert_head_linklist(linknode*phead,datatype tmpdata)
{
    linknode*ptmpnode = NULL;
    ptmpnode = malloc(sizeof(linknode));
    if (NULL == ptmpnode)
    {
        perror("fail to malloc");
        return -1;
    }
    //存放数据
    ptmpnode->data = tmpdata;
    //存放下一个节点的地址
    ptmpnode->pnext = phead->pnext;
    //更新空白节点的下一个地址
    phead->pnext = ptmpnode;
    return 0;
}

3.4链表的遍历

方法一：适用于遍历所有链表节点

void show_linklist(linknode *phead)
 {
    linknode *ptmpnode = NULL;
    ptmpnode = phead->pnext;
    while (ptmpnode != NULL)//判断下一个节点是不是空
    {
        printf("%d ", ptmpnode->data);
        ptmpnode = ptmpnode->pnext;
    }
    printf("\n");
    return;
 }

方法二：适用于寻找最后一个链表节点

linknode* find_last_node(linknode *phead) 
{
    if (phead == NULL)  // 如果链表为空，直接返回NULL
        return NULL;

    linknode *ptmpnode = phead;  // 从头节点开始（如果phead是哨兵节点，则用 phead->pnext）
    
    while (ptmpnode->pnext != NULL)  // 如果下一个节点不是NULL，就继续向后移动
    {
        ptmpnode = ptmpnode->pnext;
    }
    
    return ptmpnode;  // 此时 ptmpnode 就是最后一个节点
}

3.5从链表中删除所有某元素

定义两个指针ptmpnode用来遍历链表查找要删除的节点元素，pprenode永远只想 ptmpnode的前一个节点，当ptmpnode找到要删除的节点元素，让pprenode->pnext赋值为ptmpnode->pnext 并且把将要删除的节点元素释放，让ptmpnode判断下一个节点元素是否要删除，直到该指针指向NULL为止

//删除链表中所有的某一指定元素
int delete_linklist(linknode *phead, datatype tmpdata)
{
    linknode *pprenode = NULL;
    linknode *ptmpnode = NULL;

    pprenode = phead;
    ptmpnode = phead->pnext;
    while (ptmpnode != NULL)
    {
        if (ptmpnode->data == tmpdata)
        {
            pprenode->pnext = ptmpnode->pnext;
            free(ptmpnode);
            ptmpnode = pprenode->pnext;
        }
        else 
        {
            ptmpnode = ptmpnode->pnext;
            pprenode = pprenode->pnext;
        }
    }
    return 0;
}

3.6返回链表中第一个指定元素节点的地址

//数返回链表中第一个指定元素节点的地址
 void find_linklist(linknode *phead, datatype tmpdata)
 {
    linknode *ptmpnode = NULL;
    linknode *pprenode = NULL;
    pprenode = phead;
    ptmpnode = pprenode->pnext;
    while (ptmpnode != NULL)
    {
        if (ptmpnode->data == tmpdata)
        {
            printf("%p\n",&pprenode->pnext);
            break;
        }
        else
        {
            ptmpnode = ptmpnode->pnext;
            pprenode = pprenode->pnext;
        }
    }
    return;
 }

3.7将链表中指定元素的值更新为新值

//将链表中指定元素的值更新为新值
 void update_linklist(linknode *phead, datatype olddata, datatype newdata)
 {
    linknode *ptmpnode = NULL;
    ptmpnode = phead;
    while (ptmpnode != NULL)
    {
        if (ptmpnode->data == olddata)
        {
            ptmpnode->data = newdata;
        }
        ptmpnode = ptmpnode->pnext;
    }
    return;
 }

3.8链表的尾插法

 //尾插（顺序）
 void insert_tail_linklist(linknode *phead, datatype tmpdata)
 {
    linknode *ptmpnode = NULL;
    linknode *tail = phead;//从第一个节点寻找，不能从第一个节点的下一个节点找，因为可能为空。
    ptmpnode = malloc(sizeof(linknode));
    ptmpnode->data = tmpdata;
    ptmpnode->pnext = NULL;
    while(tail ->pnext != NULL)
    {
        tail = tail->pnext;
    }
    tail->pnext = ptmpnode;//将尾节点的pnext指向新建立的节点ptmpnode
    return;
 }

3.9链表的销毁

void destroy_linklist(linknode **pphead)//销毁需要传递二级指针，因为要将外部指针指向空
{
    linknode *pfreenode = NULL;
    linknode *ptmpnode = NULL;
    ptmpnode = *pphead;
    pfreenode = *pphead;
    while(ptmpnode != NULL)
    {
        ptmpnode = ptmpnode->pnext;
        free(pfreenode);
        pfreenode = ptmpnode;
    }
    *pphead = NULL;
}

3.10查找链表的中间节点

定义两个指针，分别为快慢指针，快指针一次走两步，慢指针一次走一步，当快指针走向末尾时，慢指针刚好走到中间节点。

//寻找中间节点的元素
linknode * find_midnode(linknode *phead)
{
    linknode *pfast = NULL;
    linknode *pslow = NULL;
    pfast = phead->pnext;
    pslow = phead->pnext;
    while(pfast->pnext != NULL)
    {
        pfast = pfast->pnext;
        if (pfast == NULL)
        {
            break;
        }
        pfast = pfast->pnext;
        if (pfast == NULL)
        {
            break;
        }
        pslow = pslow->pnext;
    }
    return pslow;
}

3.11查找倒数第k个节点元素

同样的，定义一对快慢指针，快指针先走k步，再让快慢指针同时向后走，当快指针走向最后一个节点，慢指针刚好走到倒数第k个节点。

linknode *find_last_kth_node(linknode *phead,int k)
{
    linknode *pfast = NULL;
    linknode *pslow = NULL;
    pfast = phead ->pnext;
    pslow = phead ->pnext;
    for (int i = 0;i < k && pfast != NULL;i++)
    {
        pfast = pfast->pnext;
    }
    if (pfast == NULL)
    {
        return NULL;
    }
    while(pfast != NULL)
    {
        pfast = pfast->pnext;
        pslow = pslow->pnext;
    }
    return pslow;
}

3.12单向链表的倒置

3.13单向链表的排序

3.14判断是否有环

4.Makefile

3.1 Makefile

工程管理工具，主要用来管理代码的编译，Makefile可以根据文件中的规则来选择符合条件的代码完成编译，其能够根据依赖关系和文件修改的时间戳来决定哪些代码需要编译，哪些代码不需要重新编译。

3.2 Makefile使用规则

1）在工程目录下，新建一个Makefile或者makefile的文件

2）在Makefile中编写对应的文件编译规则

3）在工程目录下使用make来调用Makefile中的规则完成代码编译

3. 3Makefile语法规则

要生成的文件:依赖的所有文件
    生成命令方式

3.4Makefile语法的扩展

phony后的目标只能通过命令生成，phony之前的为make默认生成。

如上图为查看内存是否泄露。

结果为所有内存均被释放。

数据结构（概念及链表）