数据结构入门（Duruofu）

数据结构概述

数据结构定义

我们如何把现实中大量而反复的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应的操作，这个相应的操作也叫做算法。
数据结构=个体+个体的关系

算法

算法:对储存数据的操作，是解题步骤和方法

衡量算法的标准：

1. 时间复杂度
   大概程序要执行的次数，而并非是执行的时间（因为同一程序在不同机器上执行的时间是不一样的，有差异）
2. 空间复杂度
   算法执行过程中大概所占用的最大内存
3. 难易程度
   最关键的部分，要尽量简单
4. 健壮性
   能处理不同的异常不会导致程序崩溃

数据结构的地位：

数据结构是软件中最核心的课程
程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言

预备知识

指针

指针是C语言的灵魂，指针就是地址 地址就是指针，指针变量就是存放内存单元地址（内存单元编号）的变量。指针本质上就是一个操作受限的非负整数。

int *p;  //创建一个指针
         //p是一个变量的名字，int *表示该p变量只能储存int类型变量的地址

地址

地址是内存单元的编号，从0开始的非负整数

1、基本类型的指针

int i=10;
int *p = &i; //等价于 int *p;    p = &i;

详解：

1. p存放了i的地址，所以我们说p指向了i
2. p和i是完全不同的两个变量，修改其中的任意一个变量的值，不会影响另一变量的值
3. p指向i， p就是i变量本身。更形象的说所有出现 p的地方都可以换成i，所有出现i的地方都可以换成*p

利用指针的函数传值调用

#include<stdio.h>
//函数的传值调用
void f(int *p)//这里不是定义一个名字叫*p的形参，而是定义了一个形参，它的名字叫做p，他的类型是int*
{
    *p=100;   //相当于i=100，而不是9=100
}
int main()
{
    int i=9;
    f(&i);
    printf("i=%d\n",i);
    teturn 0;
}//输出结果：i=100
//思考:
//如何通过被调函数修改主调函数中普通变量的值            
//1.实参为相关变量的地址
//2.形参为以该变量的类型为类型的指针变量
//3.在被调函数中通过  *形参变量名 的方式就可以修改主函数相关变量的值

总结：

1. 如何一个指针变量(假定为p)存放了某个普通变量(假定为i)的地址，那我们就可以说：“p指向了i”， 但p与i是两个不同的变量，修改p的值不影响i的值，修改i的值不影响p的值. p等价于i 或者说 p可以与i在任何地方互换
2. 如果一个指针变量指向了某个普通变量，则* 指针变量 就完全等价于 该普通变量

注意：

指针变量也是变量，只不过它存放的不能是内存单元的内容，只能存放内存单元的地址
普通变量前不能加*
常量和表达式前不能加&

深入理解

# include <stdio.h>
int main(void)
{
    double * p;
    double x = 66.6;//double类型占八个字节
    p = &x;  //x占8个子节 1个字节是8位, 1个子节对应一个地址，p里存放的只是其中一个地址（通常是首地址）
    double arr[3] = {1.1, 2.2, 3.3};
    double * q;
    q = &arr[0];
    printf("%p\n", q);  //%p实际就是以十六进制输出
    q = &arr[1];
    printf("%p\n", q);  //所以两个输出语句数字大小差8，（相邻两个数地址的值大小差8）
    return 0;
}

2、指针和数组的关系

数组

int a[20];
//定义一个数组名为a，长度为20的整形数组，编号为0~19

数组名（一维）

一维数组名是个指针常量，它存放的是一维数组第一个元素的地址， 它的值不能被改变 ，一维数组名指向的是数组的第一个元素。

下标和指针的关系

*a[i] <<==>> (a+i)（两者等价）
假设指针变量的名字为p，则p+i的值是p+i(p所指向的变量所占的字节数)

如何界定一维数组

如何通过被调函数修改主调函数中一维数组的内容【如何界定一维数组】
两个参数：
存放数组首元素的指针变量
存放数组元素长度的整型变量
举例：

# include <stdio.h>
void Show_Array(int * p, int len)//打印这个数组，len为存放数组长度的变量
{
    int i = 0;
    for (i=0; i<len; ++i)
        printf("%d\n", p[i]);//p[i]就是主函数的a[i]
    //p[0] == *p   p[i] == *(p+i) == *(a+i) == a[i]
}
int main(void)
{
    int a[5] = {1,2,3,4,5};
    Show_Array(a, 5);  //a等价于&a[0], &a[0]本身就是int *类型
    return 0;
}

结构体

结构体是C特有的，对应C++中的类（属于一种复合数据类型）

为什么会出现结构体

为了表示一些复杂的数据，而普通的基本类型变量无法满足要求

什么叫结构体

结构体是用户根据实际需要自己定义的复合数据类型

结构体的使用

# include <stdio.h>
//定义一个结构体：数据类型的定义，相当于自己新创造了一种数据类型
struct Student
{    
    int sid;
    char name[200];
    int age;
}; //分号不能省
int main(void)
{
    struct Student st = {1000, "zhangsan", 20};//定义一个名为st，的struct Student类型变量
    printf("%d  %s  %d\n", st.sid, st.name, st.age);//输出结构体内容，应用内部要使用st.sid这样的形式 
    //引用结构体的两种方式：
    //第一种，使用st.sid这样的形式
    st.sid=99;
    //-----------------------分割线-------------------------//
    //第二种，使用指针指向结构体（最常用的引用方式）
    struct Student *pst;
    pst = &st;
    pst->sid=99;//pst->sid等价于（*pst）.sid，而（*pst）.sid等价于st.sid
    //pst->sid表示pst所指向的结构体变量中的sid这个成员
    return 0;
}

注意事项：

结构体变量不能加减乘除，但可以相互赋值

进阶内容

普通结构体变量和结构体指针变量作为函数参数的传递

# include <stdio.h>
# include <sting.h>
void f(struct Student *pst);
void g(struct Student st);
struct Student
{    
    int sid;
    char name[200];
    int age;
};
int main()
{
    struct Student st;
    f(&st);//第一种函数参数的传递方式
    g(st);//第二种函数参数的传递方式
    return 0;
}
void f(struct Student *pst)//为结构体赋值的函数
{
    pst->sid = 99;
    strcpy(pst->name,"zhangsan");
    pst->age = 22; 
}
void g(struct Student st)//输出结构体的函数
{
    printf("%d  %s  %d\n", st.sid, st.name, st.age);
}

上面例子里的两个函数在调用同一个结构体使用了不同的方式，在这里强烈推荐使用第一种，即使用结构体指针变量作为函数参数的传递。例子中第二种方式在创建函数时会创建一个新的结构体变量，则整个程序传值至少会多占用208个字节的储存空间，耗内存，耗时间，而第一种用结构体指针变量作为函数参数，只会占用四个字节的内存，有助于减小程序的空间复杂度。

动态内存分配

malloc (len)：

动态内存分配的核心是malloc函数。可以在程序运行中，根据用户的需求生成不同长度的数组，使用后也可及时清除其所占用的内存。

# include <stdio.h>
#include <stdlib.h>
int main()
{
    int a[5]={4,10,2,8,6};//这就是一个静态的数组，数组的长度是固定的
    int len;
    printf("请输入你需要分配的数组的长度：len=");
    scanf("%d",&len);//假设输入5
    int *p = (int *)malloc(sizeof(int)*len);
    *p = 4;   //类似于a[0] = 4;所以可以把p当做一个普通的数组来使用
    P[1] = 10;//类似于a[1] = 10;
    free(p);//把p所代表的动态分配的20个字节的内存释放
    return 0;
}

1. 第八行的sizeof(int)是返回一个整形变量的值，其值固定为4，则sizeof(int)*len的意思就是用户所需要分配的数组长度对应的字节数。
2. malloc只有一个int型的形参，表示要求系统分配的字节数。
3. malloc(len)函数的功能是请求系统len个字节的内存空间，如果请求分配成功，则返回第一个字节的地址，如果分配不成功，则返回NULL
4. malloc函数能且只能返回第一个字节的地址，所以我们需要把这个无任何实际意义的第一个字节的地址（俗称干地址）转化为一个有实际意义的地址，因此malloc前面必须加（数据类型 *）,表示把这个无实际意义的第一个字节的地址转化为相应类型的地址。例如：

   int *p = (int *)malloc(50);

   
   表示将系统分配好的50个字节的第一个字节的地址转化为int 型的 地址，更准确的说是把第一个字节的地址转化为四个字节的地址，这样p就指向了第一个的四个字节，p+1就指向了第2个的四个字节，p+i就指向了第i+1个的4个字节。p[0]就是第一个元素， p[i]就是第 i+1个元素
   表示将系统分配好的80个字节的第一个字节的地址转化为double 型的地址，更准确的说是把第一个字节的地址转化为8个字节的地址，这 样p就指向了第一个的8个字节，p+1就指向了第2个的8个字节，p+i就指向了第i+1个的8个字节。p[0]就是第一个元素， p[i]就是第i+1个元素

free（p）：

释放p所指向的内存，而不是释放p本身所占用的内存。（动态分配的内存一定要手动释放，否则造成内存泄露。）

跨函数使用内存

动态分配的内存必须调用free()函数才能释放，而自动变量一旦跳出它的代码作用范围，就会由编译器自动释放掉。配合动态内存分配就可以达到跨函数使用内存的效果。

# include <stdio.h>
# include <malloc.h>
struct Student
{
    int sid;
    int age;
};
struct Student * CreateStudent(void);
void ShowStudent(struct Student *);
int main(void)
{
    struct Student * ps;
    ps = CreateStudent();
    ShowStudent(ps);
    return 0;
}
void ShowStudent(struct Student * pst)
{
    printf("%d %d\n", pst->sid, pst->age);
}
struct Student * CreateStudent(void)
{
    struct Student * p = (struct Student *)malloc(sizeof(struct Student));
    p->sid = 99;
    p->age = 88;
    return p;
}
//输出结果：99 88

线性数据结构

线性数据结构就是把所有的结点用一根直线穿起来。

连续存储【数组】（顺序表）

什么叫数组：

元素类型相同，内存大小相等数据元素集合（数组传参，只要传进去首地址和长度就行）

数组的优缺点：

优点：

存取速度快

缺点：

事先必须知道数组的长度
插入删除元素很慢
空间通常是有限制的
需要大块连续的内存块
插入删除元素的效率很低

连续储存数组的算法

总体程序概览

# include <stdio.h>
# include <malloc.h>//包含malloc函数
# include <stdlib.h>//包含exit()函数
struct Arr//定义了一个数据类型，该数据类型的名字叫做struct Arr, 该数据类型含有三个成员，分别是pBase, len, cnt
{
    int *pBase;//储存数组第一个元素的地址
    int len; //数组所能容纳的最大元素的个数
    int cnt;//当前数组有效元素的个数
    //int increment;自动增长因子，在数组长度不断追加的情况下通过增大内存分配减小每次追加所占用的时间（进阶知识）
};
//编写一些对数组进行操作的方法
void init_arr(struct Arr *pArr ,int length);//初始化
bool append_arr(struct Arr *pArr, int val);//追加功能
bool insert_arr(struct Arr *pArr, int pos, int val);//插入功能
bool delete_arr(struct Arr *pArr, int pos, int *pVal);//删除功能
int get_arr(struct Arr *pArr,int pos);//获取下标为x的对应值
bool is_empty(struct Arr *pArr);//是否为空
bool is_full(struct Arr *pArr);//是否为满
void sort_arr(struct Arr *pArr);//排序
void show_arr(struct Arr *pArr);//显示输出
void inversion_arr(struct Arr *pArr);//倒置
int main()
{
    struct Arr arr;
    int val;
    init_arr(&arr, 6);
    show_arr(&arr);
    append_arr(&arr, 1);
    append_arr(&arr, 10);
    append_arr(&arr, -3);
    append_arr(&arr, 6);
    append_arr(&arr, 88);
    append_arr(&arr, 11);
    if ( delete_arr(&arr, 4, &val) )
    {
        printf("删除成功!\n");
        printf("您删除的元素是: %d\n", val);
    }
    else
    {
        printf("删除失败!\n");
    }
    show_arr(&arr);
    inversion_arr(&arr);
    printf("倒置之后的数组内容是:\n");
    show_arr(&arr);
    sort_arr(&arr);
    show_arr(&arr);
    //printf("%d\n", arr.len);
    return 0;
}
void init_arr(struct Arr *pArr ,int length)//初始化函数
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    //判断是否分配成功
    if (NULL == pArr->pBase)//在C语言里，malloc函数内存分配失败会返回NULL
    {
        printf("动态内存分配失败！\n");
        exit(-1);//用来终止整个程序的内置函数
    }
    else
    { 
        pArr->len = length;
        pArr->cnt = 0;
    }
     return ;
}
bool is_empty(struct Arr *pArr)//判断是否为空的函数
{
    if (0 == pArr->cnt)
        return true;
    else 
        return false;
}
int get_arr(struct Arr *pArr,int pos)//获取第x个数的对应值
{
    int val;
    val = pArr->pBase[pos-1];
    return val;
}
void show_arr(struct Arr *pArr)//输出数组的函数
{
    if(is_empty(pArr))//这里不是*pArr
    {
        printf("数组为空！\n");
    }
    else
    {
        for(int i=0; i<pArr->cnt;++i)
            printf("%d ",pArr->pBase[i]);
        printf("\n");
    }
    return ;
}
bool is_full(struct Arr *pArr)//是否为满
{
    if (pArr->cnt == pArr->len)
        return true;
    else
        return false;
}
bool append_arr(struct Arr *pArr, int val)//追加功能
{
    if (is_full(pArr))
        return false;
    //不满时追加
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true; 
}
bool insert_arr(struct Arr *pArr, int pos, int val)//插入功能，pos从1开始
{
    int i;
    if (is_full(pArr))
        return false;
    if(pos<1 || pos>pArr->cnt+1)
        return false;
    for(i=pArr->cnt-1; i>=pos-1;--i)
    {
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    pArr->pBase[pos-1] = val;
    return true;
}
bool delete_arr(struct Arr *pArr, int pos,int *pVal)//删除功能
{
    int i;
    if(is_empty(pArr) )
        return false;
    if(pos<1 || pos>pArr->cnt)
        return false;
    *pVal=pArr->pBase[pos-1];
    for(i =pos; i<pArr->cnt;++i)
    {
        pArr->pBase[i-1]=pArr->pBase[i];
    } 
    pArr->cnt--;
}
void inversion_arr(struct Arr *pArr)//倒置功能
{
    int i=0;
    int j= pArr->cnt-1;
    int t;
    while(i<j)
    {
        t = pArr->pBase[i];
        pArr->pBase[i]=pArr->pBase[j];
        pArr->pBase[j]=t;
        ++i;
        --j;
    }
    return ;
}
void sort_arr(struct Arr *pArr)//排序(这里使用简单的选择排序)
{
    int i , j, t;
    for(i=0; i<pArr->cnt;++i)
    {
        for(j=i+1;j<pArr->cnt;++j)
        {
            if(pArr->pBase[i]>pArr->pBase[j])
            {
             t = pArr->pBase[i];
             pArr->pBase[i]=pArr->pBase[j];
               pArr->pBase[j]=t;     
            }  
        }
    }
}

对主要算法的解释

初始化函数

void init_arr(struct Arr *pArr ,int length)//初始化函数
{
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    //判断是否分配成功
    if (NULL == pArr->pBase)//在C语言里，malloc函数内存分配失败会返回NULL
    {
        printf("动态内存分配失败！\n");
        exit(-1);//用来终止整个程序的内置函数
    }
    else
    { 
        pArr->len = length;
        pArr->cnt = 0;
    }
     return ;
}

这是初始化函数，主要使用了动态内存分配来实现初始化生成任意长度的连续数组，利用在C语言里，malloc函数内存分配失败会返回NULL值来判断是否分配成功。

判断是否为空的函数

bool is_empty(struct Arr *pArr)//判断是否为空的函数
{
    if (0 == pArr->cnt)
        return true;
    else 
        return false;
}

判断struct Arr类型里cnt（当前数组有效元素的个数）的值，返回对应的布尔值。

判断是否为满的函数

bool is_full(struct Arr *pArr);//是否为满
{
    if (pArr->cnt == pArr->len)
        return true;
    else
        return false;
}

判断当前数组有效元素的个数和数组所能容纳的最大元素的个数是否相等，返回对应的布尔值。

输出显示数组值的函数

void show_arr(struct Arr *pArr)//输出数组的函数
{
    if(is_empty(pArr))//这里不是*pArr
    {
        printf("数组为空！\n");
    }
    else
    {
        for(int i=0; i<pArr->cnt;++i)
            printf("%d ",pArr->pBase[i]);
        printf("\n");
    }
    return ;
}

这里有一个函数的嵌套调用，函数is_empty()的参数值是指针（地址），但这里不能写&pArr，因为pArr本身就存放的地址值，如果写&pArr就变成了存放这个地址值的地址了。

追加功能的函数

bool append_arr(struct Arr *pArr, int val)//追加功能
{
    if (is_full(pArr))
        return false;
    //不满时追加
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true; 
}

先判断数组是否满，不满才可追加数值。追加后数组当前有效值个数要加1

插入数值的函数

bool insert_arr(struct Arr *pArr, int pos, int val)//插入功能，pos从1开始
{
    int i;
    if (is_full(pArr))//判断是否已满
        return false;
    if(pos<1 || pos>pArr->cnt+1)//判断插入位置是否合法
        return false;
    for(i=pArr->cnt-1; i>=pos-1;--i)
    {
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    pArr->pBase[pos-1] = val;
    return true;
}

插入一个值，要先判断数组是否已满，未满即可插入,还要判断插入的位置是否合法是不是在数组的范围内。插入时需要将插入位置上的数以及后面的数值统一后移一位，留出空缺。

删除功能的函数

bool delete_arr(struct Arr *pArr, int pos,int *pVal)//删除功能
{
    int i;
    if(is_empty(pArr) )
        return false;
    if(pos<1 || pos>pArr->cnt)
        return false;
    *pVal=pArr->pBase[pos-1];
    for(i =pos; i<pArr->cnt;++i)
    {
        pArr->pBase[i-1]=pArr->pBase[i];
    } 
    pArr->cnt--;
}

类似于插入，先判断数组是否为空，为空不可删除,还要判断删除的位置是否合法是不是在数组的范围内。然后通过循环将下标大的赋值给下标小的，实现删除和移位。这里不对最后一位数值进行操作，只是将数组有效长度减一，将最后一个值变为垃圾值。

将数组进行倒置的函数

void inversion_arr(struct Arr *pArr)//倒置功能
{
    int i=0;
    int j= pArr->cnt-1;
    int t;
    while(i<j)
    {
        t = pArr->pBase[i];
        pArr->pbase[i]=pArr->pBase[j];
        ++i;
        --j;
    }
    return ;
}

这里尽量不要引入新的数组，使用中间变量即可，引入新的数组会增加程序的空间复杂度。

进行数组排序的函数

void sort_arr(struct Arr *pArr)//排序(这里使用简单的选择排序)
{
    int i , j, t;
    for(i=0; i<pArr->cnt;++i)
    {
        for(j=i+1;j<pArr->cnt;++j)
        {
            if(pArr->pBase[i]>pArr->pBase[j])
            {
             t = pArr->pBase[i];
             pArr->pBase[i]=pArr->pBase[j];
               pArr->pBase[j]=t;     
            }  
        }
    }
}

离散存储【链表】

链表的定义：

n个节点离散分配，彼此通过指针相连，每个结点只有一个前驱结点，每个节点只有一个后继结点， 首结点没有前驱结点，尾结点没有后后继结点。

专业术语：

首结点：第一个有效结点（开始结点）
尾结点：最后一个有效结点
头结点：头结点的数据类型和首结点的类型一样，没有存放有效数据（也可以存放一些线性表长度等附加信息），是最前面的，是在首结点之前的，主要是为了方便对链表的操作。
头指针：（指向头）指向头结点的指针变量
尾指针：指向尾结点的指针

调用一个链表需要几个参数：

或者说如果期望一个函数对链表进行操作我们至少需要接收链表的那些信息？？？
只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息。

为什么不使用头结点而用头指针？
头结点有可能很大，占的内存可能大，假设我想造一个函数输出所有链表的值，那你如果不用头指针类型做形参，那由于不同链表的头节点不一样大小，这样就没办法找出形参。

如何生成一个结点：

一个结点可以分为数据域和指针域

typedef struct Node
{
    int data;//数据域
    struct Node * pNext;//指针域，指向一个新的和它所处结构体一样的结构体数据类型（不是我指我自己）
}NODE,*PNODE;//这里的NODE等价于struct Node数据类型，*PNODE等价于struct Node *类型

注：[typedef的使用：]:https://www.runoob.com/cprogramming/c-typedef.html

链表的分类

单链表：就是正常的链表
双链表：每一个节点有两个指针域
循环链表：能通过任何一个节点找到其他所有的节点
非循环链表：

链表的算法

整体程序概览

#define _CRT_SECURE_NO_WARNINGS//用于解决vs2022scanf报错报错error C4996的宏定义
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Node
{
    int data;//数据域
    struct Node* pNext;//指针域
}NODE,*PNODE;//这里的NODE等价于struct Node数据类型，*PNODE等价于struct Node *类型
//函数声明：
PNODE create_list(void);//创建一个链表的函数
void traverse_list(PNODE pHead);//遍历函数
bool is_empty(PNODE pHead);//判断是否满
int length_list(PNODE pHead);//求链表的长度
bool insert_list(PNODE, int,int);//插入结点,在pHead所指向链表的第pos个结点的前面插入一个新的结点，该结点的值是val
bool delete_list(PNODE, int, int*);//删除结点
void sort_list(PNODE);//排序函数
int main()
{   
    PNODE pHead = NULL;//等价于struct Node * pHead;创建了头指针pHead并进行初始化，防止其指向未知的地址。
    pHead = create_list();//create_list()功能：创建一个非循环单链表，并将该链表的头结点的地址付给pHead
    //sort_list(pHead);//排序函数
    traverse_list(pHead);//
    int len = length_list( pHead);
    printf("链表的长度为%d",len);
    insert_list(pHead, 3, 5);
    traverse_list(pHead);//
    int len1 = length_list(pHead);
    printf("链表的长度为%d", len1);
    return 0;
}
PNODE create_list(void)//创建一个链表的函数
{
    int len;//用来存放有效结点的个数
    int i;
    int val;//用来临时存放用户输入的结点的值
    //分配了一个不存放有效数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    PNODE pTail = pHead;//生成一个指针pTail指向头结点
    pTail->pNext = NULL;
    printf("请输入你需要生成的链表节点个数：len = ");
    scanf("%d", &len);
    for (i = 0; i < len; ++i)
    {
        printf("请输入第%d个结点的值：", i+1);
        scanf("%d", &val);
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pHead)
        {
            printf("内存分配失败，程序终止！\n");
            exit(-1);
        }
        pNew->data = val;//将值写入结点
        pTail->pNext = pNew;//将新生成的结点挂到pTail后面
        pNew->pNext = NULL;//清空最后一个结点的指针域
        pTail = pNew;
    }
    return pHead;//返回头指针
}
void traverse_list(PNODE pHead)//遍历函数
{
    PNODE p = pHead->pNext;
    while (NULL != p)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}
bool is_empty(PNODE pHead)//判断是否为空
{
    if (NULL == pHead->pNext)//判断头结点的指向是不是空
        return true;
    else
        return false;
}
int length_list(PNODE pHead)//求链表的长度
{
    PNODE p = pHead->pNext;
    int len = 0;
    while (NULL != p)
    {
        ++len;
        p = p->pNext;
    }
    return len;
}
void sort_list(PNODE pHead)//排序函数
{
    int i, j, t;
    int len = length_list(pHead);
    PNODE p, q;
    for (i = 0,p=pHead->pNext; i< len - 1;++i, p=p->pNext)
    {
        for (j=i+1,q=p->pNext; j<len;++j,q=q->pNext)
        {
            if (p->data > q->data)
            {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
    return;
}
bool insert_list(PNODE pHead, int pos, int val)//插入结点,在pHead所指向链表的第pos个结点的前面插入一个新的结点，该结点的值是val
{
    int i = 0;
    PNODE p = pHead;
    while (NULL != p && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }
    if (i > pos - 1 || NULL == p)
        return false;
    //如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
    //分配新的结点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("动态分配内存失败!\n");
        exit(-1);
    }
    pNew->data = val;//将值放入新的结点
    //将新的结点存入p节点的后面
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;
    return true;
}
bool delete_list(PNODE pHead, int pos, int* pVal)//删除结点
{
    int i = 0;
    PNODE p = pHead;
    while (NULL != p->pNext && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }
    if (i > pos - 1 || NULL == p->pNext)
        return false;
    //如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
    PNODE q = p->pNext;  //q指向待删除的结点
    *pVal = q->data;
    //删除p节点后面的结点
    p->pNext = p->pNext->pNext;
    //释放q所指向的节点所占的内存
    free(q);
    q = NULL;
    return true;
}

具体算法讲解

创建结点

PNODE create_list(void)//创建一个链表的函数
{
    int len;//用来存放有效结点的个数
    int i;
    int val;//用来临时存放用户输入的结点的值
    //分配了一个不存放有效数据的头结点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if (NULL == pHead)
    {
        printf("内存分配失败，程序终止！\n");
        exit(-1);
    }
    PNODE pTail = pHead;//生成一个指针pTail指向头结点
    pTail->pNext = NULL;
    printf("请输入你需要生成的链表节点个数：len = ");
    scanf("%d", &len);
    for (i = 0; i < len; ++i)
    {
        printf("请输入第%d个结点的值：", i+1);
        scanf("%d", &val);
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pHead)
        {
            printf("内存分配失败，程序终止！\n");
            exit(-1);
        }
        pNew->data = val;//将值写入结点
        pTail->pNext = pNew;//将新生成的结点挂到pTail后面
        pNew->pNext = NULL;//清空最后一个结点的指针域
        pTail = pNew;
    }
    return pHead;//返回头指针
}

插入节点

bool insert_list(PNODE pHead, int pos, int val)//插入结点,在pHead所指向链表的第pos个结点的前面插入一个新的结点，该结点的值是val
{
    int i = 0;
    PNODE p = pHead;
    while (NULL != p && i < pos - 1)//排除各种特殊情况的算法（看不懂）
    {
        p = p->pNext;
        ++i;
    }
    if (i > pos - 1 || NULL == p)
        return false;
    //如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
    //分配新的结点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (NULL == pNew)
    {
        printf("动态分配内存失败!\n");
        exit(-1);
    }
    pNew->data = val;//将值放入新的结点
    //将新的结点存入p节点的后面（原理如下图）
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;
    return true;
}

插入操作图解：

以上面图片为例：实现将指针q指向的结点插入到指针p指向的结点后面的插入算法：
第一种方法：通过创建副本插入（中间变量）

r = p->pNext;//把P结点的指针域赋值给中间变量r。 （p->pNext  指  p所指向结构体变量中的pNext成员本身）
p->pNext = q;//把q的值（该结点的地址）赋给P结点的指针域
q->pNext = r;//把P结点的指针域的值（保存有下一个结点的地址，r里的值），赋值给q结点的指针域

第二种方法（直接交换指针域插入）：

q->pNext = p->pNext; //把P结点的指针域的值（保存有下一个结点的地址），直接赋值给q结点的指针域
p->pNext = q;//把q的值（该结点的地址）赋给P结点的指针域

删除节点

bool delete_list(PNODE pHead, int pos, int* pVal)//删除结点
{
    int i = 0;
    PNODE p = pHead;
    while (NULL != p->pNext && i < pos - 1)
    {
        p = p->pNext;
        ++i;
    }
    if (i > pos - 1 || NULL == p->pNext)
        return false;
    //如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
    PNODE q = p->pNext;  //q指向待删除的结点
    *pVal = q->data;
    //删除p节点后面的结点（原理如下图）
    p->pNext = p->pNext->pNext;
    //释放q所指向的节点所占的内存
    free(q);
    q = NULL;
    return true;
}

删除操作图解：

以上面图片为例：实现将指针p指向的结点后面的结点删除的算法：
伪算法：让P结点的指针域指向待删除结点后面的结点

p->pNext = p->pNext->pNext;//这样写原理上可行，但是会造成内存丢失（第二个结点的内存没有被释放，但是储存其地址值的p->pNext又被改写，所以就无法找到待删除结点的内存位置。ps：c c++里内存不会自动释放）

正确写法：

r = p->pNext;//先临时定义一个指向后面结点的指针
p->pNext = p->pNext->pNext;
free(r);//删除r指向结点的内存，不是删除r本身所占的内存，这里不能写free(p->pNext);

遍历

void traverse_list(PNODE pHead)//遍历函数
{
    PNODE p = pHead->pNext;
    while (NULL != p)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

判断是否为空

bool is_empty(PNODE pHead)//判断是否为空
{
    if (NULL == pHead->pNext)//判断头结点的指向是不是空
        return true;
    else
        return false;
}

只需判断头结点指向的指针域是不是为空即可。

求长度

int length_list(PNODE pHead)//求链表的长度
{
    PNODE p = pHead->pNext;
    int len = 0;
    while (NULL != p)
    {
        ++len;
        p = p->pNext;
    }
    return len;
}

通过和遍历相似的方法来确定链表的长度

排序

void sort_list(PNODE pHead)
{
    int i, j, t;
    int len = length_list(pHead);//调用函数确定长度
    PNODE p, q;
    for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext)
    {
        for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext)
        {
            if (p->data > q->data)  //类似于数组中的:  a[i] > a[j]
            {
                t = p->data;//类似于数组中的:  t = a[i];
                p->data = q->data; //类似于数组中的:  a[i] = a[j];
                q->data = t; //类似于数组中的:  a[j] = t;
            }
        }
    }
    return;
}

这里同样适用简单的选择排序做示范，链表的排序和数组的排序有共通之处，数组的排序可以看作是运算符重载后的链表排序。

链表的优缺点

优点：

空间没有限制
插入删除元素很快

缺点：

存取速度很慢

线性数据结构的应用

栈和队列是一种特殊的线性结构，是连续存储或离散存储的一种应用

栈

定义：

栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说，表尾端称为栈顶（top），表头端称为栈低（bottom）。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除，所以栈又被称为后进先出的线性表（简称LIFO:Last in, First out.结构）。可以理解为一种可以实现“先进后出“的存储结构，类似于箱子。成员变量在堆，临时变量在栈。

分类：

静态栈

动态栈（内核就是链表）

创建一个栈

这里演示创建一个链式栈结构

#include <stdio.h>
typedef struct Node
{
    int data;//数据域
    struct Node* pNext;//指针域
}NODE, * PNODE;//这里的NODE等价于struct Node数据类型，*PNODE等价于struct Node *类型
typedef struct Stack//创建一个栈的数据类型
{
    PNODE pTop;
    PNODE pBottom;
}STACK, * PSTACK;  //PSTACK 等价于 struct STACK *
int main()
{
    Stack S;//创建一个栈，Stack 等价于 struct Stack
    return 0;
}

算法：

整体概览

模块讲解

初始化：

void init_Stack(PSTACK pS)
{
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if (NULL == pS->pTop)
    {
        printf("动态内存分配失败!\n");
        exit(-1);
    }
    else
    {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL; //pS->Bottom->pNext = NULL;
    }
}

压栈

可以理解为加入一个新的结点，但是这个结点只能放在栈的最上面，并且pTop需要指向它。

void push_Stack(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;
    pNew->pNext = pS->pTop; //pS->Top不能改成pS->Bottom(如下图)
    pS->pTop = pNew;
    return;
}

出栈：

//把pS所指向的栈出栈一次(删除栈顶元素)，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败，返回false,否则返回true
bool pop_Stanck(PSTACK pS, int* pVal)//出栈
{
    if (empty_Stanck(pS)) //pS本身存放的就是S的地址
    {
        return false;
    }
    else
    {
        PNODE r = pS->pTop;//暂存
        *pVal = r->data;
        pS->pTop = r->pNext;
        free(r);//释放暂存的内存
        r = NULL;
        return true;
    }
}

遍历输出：

void traverse_Stack(PSTACK pS)//遍历输出一个栈
{
    PNODE p = pS->pTop;
    while (p != pS->pBottom)
    {
        printf("%d  ", p->data);
        p = p->pNext;
    }
    printf("\n");
    return;
}

清空

void clear_Stanck(PSTACK pS)//清空
{
    if (empty_Stanck(pS))
    {
        return;
    }
    else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while (p != pS->pBottom)
        {
            q = p->pNext;
            free(p);
            p = q;
        }
        pS->pTop = pS->pBottom;
    }
}

应用：

函数调用

中断

表达式求值

内存分配

缓冲处理

迷宫

队列

非线性数据结构