数据结构（三）

这是卡尼慕的第n篇文章

小知识

OK！今天来复习一下数据结构中最最最基础的链表。

首先一定要区别一下两个概念：线性存储结构和非线性存储结构。

线性存储结构

像我们排队吃饭等叫号一样，一个接着一个，1号后面是2号，2号后面是3号，如此类推。

线性结构有唯一的首元素（第一个元素），

线性结构有唯一的尾元素（最后一个元素）。

除首元素外，所有的元素都有唯一的“前驱”，

除尾元素外，所有的元素都有唯一的“后继”。

那么线性结构有什么经典的例子呢？

队列、线性表、堆、栈。

非线性存储结构

相比于线性结构，一个元素的后面可能排着不止一个人，也就是数据元素之间是一对多，或者是多对一的关系。

例如：树（层次结构）、图（群结构）、多维数组。

一维数组与链表

OK，那开始我们的正题，假如我这里有4个数：2，3，5，8。我希望将数存储起来，那可能你的第一反应是：很简单啊，使用一个数组就行了呀，array[4]。没错的，确实可以使用一维数组直接存储，那么我现在又想在这四个数后面再加四个数呢？你可能会说：也很简单啊，重新定义数组，改成array[8]，就行了啊。

那假如我们在测试程序前并不知道我们需要多少个数怎么办呢，我们不可能说这个程序不停地根据用户的需求去更改吧，所以这里我们需要另外一个数据结构——链表来存储。

相比于普通的一维数组，链表看起来更加灵活，链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。从内存上看， 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.。

百度是这么说的：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

更好的理解，请看图：

如上图，head是头指针，指向链表的首节点（节点的地址：1200），在这个1200的地址上，我们存储了一个数据（12），同时也存储了下一个节点的地址（2000），接着在地址为2000的节点上存储着下个节点的地址和数据，如此类推，直到最后一个节点（注意：最后一个节点存储的指针必须指向NULL，否则该链表将会指向未知的随机地址上）

节点的组成

那么现在来看看我们代码是怎么实现的吧！

首先我们要考虑，链表由一个一个的节点连接起来，节点又是由一个数据域（用于存储数据）和指针域（用于指向下一个节点）组成，因此我们需要一个结构体来描述一个节点。

节点包括：

1、数据域，一种类型的数据，可以是int，可以是double等。

2、指针域，指向结构体（节点）的类型的指针。

typedef int ElemType;            //指定元素类型为整型 

//定义结点类型 
typedef struct Node {
    ElemType data;              //单链表中的数据域 
    struct Node *next;          //单链表的指针域 
}Node,*LinkedList;

单链表初始化

接下来，就是使用节点来初始化一个链表！怎么做呢？请看！

首先这个函数（方法）的返回值必须是一个节点类型的指针，因为我们需要该指针来访问链表。

然后创建一个指针参数，并且指向一个malloc / new（申请节点空间）的节点（这个节点是首节点，我们一般称为头节点）。

接着我们要判断是否申请空间成功（也就是创建头节点成功），我们使用一个if条件句来判断。并且使指针指向NULL，这样保证尾指针始终为NULL（这个很重要，不要忘了！）。

最后返回我们创建的指针参数就好了！那个指针参数就是我们需要的头指针。

LinkedList LinkedListInit() 
{
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间 
    if(L == NULL)                       //判断是否有足够的内存空间 
    {                    
        printf("申请内存空间失败\n");
    }
    L->next = NULL;                    //将next设置为NULL,初始长度为0的单链表 
     return L;                          //返回头指针以便我们使用 
}

单链表的建立

单链表的节点创建常用的方法有两种：尾插法，头插法。不同的方法的选择就取决于个人的需求，没有说哪一种方法一定比另外一个好，总体的思路是一样的，无非一个是变动尾指针，而另一个是变动头指针。

那我就讲讲尾插法。思路一样，不难。

老样子，跟初始化单链表一样。先设定一个指针指向一个新分配的内存空间，并使新的节点的指针指向NULL，并且给数据域赋值。

接着，我们怎么才能把这个已经赋值完成的节点接到链表的尾部呢？

很简单，首先遍历原来已有的链表（已知头节点，很方便），然后把尾节点的尾指针指向新节点的地址就完全OK了！很简单吧！

void InsertList(PNode List, int pos, int val) {
    int position = 0;
    PNode P = List;            //    定义节点p指向头节点
                            //    寻找pos节点的前驱结点
    while (P != NULL && position<pos - 1)
    {
        P = P->Next;
        ++position;
    }
    PNode Tmp = (PNode)malloc(sizeof(Node));     // 分配一个临时节点用来存储要插入的数据
    if (Tmp == NULL)
    {
        printf("内存分配失败！");
        exit(-1);
    }
    //    插入节点
    Tmp->Element = val;
    Tmp->Next = P->Next;
    P->Next = Tmp;
}

单链表节点的删除

那怎么移除一个节点呢？

同理啦！有指针都好办事，只要把要删除的节点的内存free掉，并且使前节点的指针指向后一个节点的地址，就完成了删除。

int Deletelist(node *head,int dn)
{
    if(dn>0&&dn<=n){
        n--;
        node *p,*pre;
        pre=head;
        p=head->next;
        int count=1;
        while(p){
            if(count==dn){
                pre->next=p->next;
                delete(p);
                p=NULL;
                return 1;
            }
            count++;
            pre=pre->next;
            p=p->next;
        }
    }
    return 0;
}

单链表的查询

单链表的不好的一点就是没有索引，没办法一下子确认某个数所在的节点的位置。

思路也很简单，先读取被查询的数据，才从头节点开始遍历，一边next一边比对数据域中的数据是否一致，如果正常循环到NULL，就说明被查询的数据不在链表中，反之就可以找到该数据。

PNode FindList(PNode List) {
    PNode P = List->Next;    //    定义临时指针P指向首节点的地址
    int num = 0;    //    用于记录链表节点位置
    int val = 0;    //    用于存放要查询的值
    printf("请输入要查询的数：");
    scanf_s("%d", &val);    //    输入要查询的数值
    while (P != NULL&&P->Element != val) {
        P = P->Next;
        ++num;
    }
    if (P != NULL)
        printf("找到的节点为：%d", num + 1);
    else
        printf("找不到该节点");
    printf("\n");
    return P;
}

删除整个单链表

删除整个链表比删除单个节点要稍微简单点，具体思路就是一遍遍历链表，一边free节点，直到遇到NULL。

void DeleteTheList(PNode List) {
    PNode P, Tmp;
    P = List->Next;    //定义指针P指向链表要删除的链表List的第一个点节点
    List->Next = NULL;
    while (P != NULL) {
        Tmp = P->Next;        //临时Tmp指向要删除的节点的下个节点
        free(P);    //释放指针P指向的节点
        P = Tmp;    //重新赋值
    }
    printf("删除链表成功！\n");
}

循环链表 与 单链表 与 双向链表

循环链表很好理解，听名字就是了，循环，把一条直线头尾相连，成了一环状，就是循环链表，也就是把尾指针从NULL变成指向头节点。

双向链表呢也很简单，就是在结构体中多添加一个指针指向前驱，方便查询，但是在添加和删除操作就需要多加一步。

一般就看需求来选择使用怎样的链表，可以巧妙地变换数据结构为自己所用。

总结

1、链表不难。

2、链表相比与一维数组更加灵活，随意添加随意删除，只要内存够，随意数量。但是失去快速定位能力（索引）。

3、基本操作：初始化，增删查改。

4、单链表与双向链表与循环链表的区别了解一下。

5、源码看我的GitHub，欢迎批评，你批评我会改。