数据结构--链表

 　　网上关于链表的文章很多，比我写的好的前辈也多不胜数。工作一年总是感觉前面学的后面忘，于是就诞生了写博客的想法，把自己的工作学习历程记下来互勉。思来想去还是把链表作为我的处女博吧，毕竟这是我踏入程序员路上写的第一个数据结构，以下内容在忐忑、羞射的心情下编写。如果有什么不能忍的地方欢迎大家指正!

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--与链表无关纯属矫情

　　谈到链表之前，就想先说一下线性表。线性表是最基本、也是最常用的一种数据结构。一个线性表是多个数据的集合，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。

　　我们常用的数组就是一种典型的顺序存储结构。链表就是下面要详细说的链式存储结构。

　　顺序存储结构就是两个相邻的元素在内存中也是相邻的，这种存储方式的优点是查询比较方便，通过首地址和偏移量就可以访问到某个元素，匹配的查找算法也有好多，最快的可以达到O(logn)。缺点是插入删除很不方便，复杂度最坏能达到O(n)，例如你想在某个位置插入/删除元素，你需要将这个位置之后的所有元素都后移/前移一位。另外一个不方便的地方是元素数量的确定，必须在使用前创建一个足够大的数组放置所有的元素，但是开辟的数组空间往往不能够充分的利用造成资源浪费。

               

　　链式存储结构就是相邻的两个元素在内存中不一定相邻，这种存储方式的优点是只需要操作指针就可以添加删除元素，比较方便，时间复杂度为O(1)；另外一个优点就是节省内存，元素在需要添加的时候才开辟内存，不需要的时候就释放，也不需要事先预估元素的数量，相对于顺序存储结构要灵活许多。缺点就是查找的算法比较少，一般只能通过遍历查找，时间复杂度为O(n)，还有一个缺点就是申请或者释放内存会消耗时间，如果频繁的对内存申请释放，消耗的时间是很可观的。

　　链表中的元素称为结点，一般由两部分组成：指针域和值域，值域可以是基本数据类型也可以是结构体等复杂数据类型，存放需要的具体数据；指针域为指向下一个节点的指针。根据指针域的不同链表可以分为单向链表，双向链表，循环链表等等。

                                                                

　　如上图所示就是一个由四个节点组成的单向链表，其中每个Data和Next为一个节点，第一个节点称为头节点，最后一个节点称为尾节点，Head为一个指向头节点的指针。Data为节点的值域，用来存放数据；Next为节点的指针域，指向下一个节点。尾节点的指针域为空。

　　链表的操作主要是围绕着指针域和对内存的申请释放进行，一般的操作就是增、删、改、查。头节点可以与其他的节点数据类型不同，头节点的值域中可以存放一些链表的信息，比如说链表的长度，创建时间，创建人等等。

 　　下面还是以一个简单的C程序来具体操作一下。

　　整个程序由三个文件组成Chain——chain.h　　存放一些类型、函数等的声明

　　　　　　　　　　　　　　　 |——chain.c　　存放函数的具体实现

　　　　　　　　　　　　　　　 |——main.c　　调用、测试实现的函数

　　　　　　　　　　　　　　　 |____Makefile　　MakeFile文件，编译的时候使用，如果是初次接触的话请忽略，后续的博客中会更新。

　　以下为chain.h文件

#ifndef _CHAIN_H_
#define _CHAIN_H_

/*声明一些数据类型*/
typedef int datatype;//声明链表存储的数据类型
typedef unsigned short uint16;
typedef unsigned char bool;
/*返回结果*/
typedef enum
{
    TRUE,
    FALSE
}bool_val;

/*声明链表节点*/
typedef struct node
{
    datatype data;
    struct node* next;
}ListNode;

/*声明链表头*/
typedef struct head
{
    char info[20];
    unsigned short length;
    ListNode* next;
}ListHead;

/*一下为一些链表操作函数的声明*/
ListHead* CreateList();//创建链表
bool ViewList(ListHead* head);//遍历链表
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data);//在指定位置添加节点
bool DelNodeByLoc(ListHead* head, uint16 loc);//删除指定位置的节点
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data);//修改指定位置的节点数据
datatype FindDataByLoc(ListHead* head, uint16 loc);//返回指定位置的节点数据
bool DestoryList(ListHead* head);//销毁链表



#endif

chain.h

　　以下为chain.c文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "chain.h"

/*创建链表*/
ListHead* CreateList()
{
    ListHead* head =  NULL;
    head = (ListHead*)malloc(sizeof(ListHead));    //申请内存
    memset(head, 0, sizeof(head));
    
    /*初始化链表信息*/
    head -> length = 0;
    strcpy(head -> info, "CangLing's List");
    head -> next = NULL;
    return head;
}

/*遍历链表*/
bool ViewList(ListHead* head)
{
    /*合法性判断*/
    if(head == NULL)
    {
        return FALSE;
    }
    ListNode* p = NULL;
    
    /*打印链表信息*/
    printf("The List Info is %s\n",head -> info);
    printf("The List Length is %d\n",head -> length);

    /*输出节点内容*/
    p = head -> next;
    while(p != NULL)
    {
        printf("%d\n",p -> data);
        p = p -> next;
    }

    return TRUE;
}

/*根据位置添加节点，大于链表长度的位置添加在链表末尾*/
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data)
{
    /*合法性判断*/
    if((head == NULL) || (loc == 0))
    {
        return FALSE;
    }

    bool_val ret = FALSE;
    ListNode* node = head -> next;
    ListNode* tmp = NULL;
    /*初始化要创建的节点*/
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p -> data = data;
    p -> next = NULL;

    if(head -> length == 0)//对只有头节点的链表进行处理
    {
        head -> next = p;
        p -> next = NULL;
    }
    else if(loc <= head -> length)//对1<loc<length的情况进行处理
    {
        /*添加在头节点之后*/
        if(loc == 1)
        {
            head -> next = p;
            p -> next = node;
        }
        else
        {
            /*寻找对应位置的前一个节点*/
            while(loc > 2)
            {
                loc--;
                node = node -> next;
            }
            tmp = node -> next;//保存loc位置的节点地址
            node -> next = p;//将要添加的节点放在loc位置
            p -> next = tmp;
        }

    }
    else//对loc>length的情况进行处理
    {
        while(node -> next != NULL)
        {
            node = node -> next;
        }

        node -> next = p;
    }

    head -> length++;//修改链表信息
    ret = TRUE;

    return ret;

}

/*删除loc位置的节点*/
bool DelNodeByLoc(ListHead* head, uint16 loc)
{
    /*进行合法性判断*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }

    bool_val ret = FALSE;
    ListNode* tmp = head -> next;
    ListNode* freenode = NULL;

    if(loc == 1)//针对第一个节点的处理
    {
        freenode = tmp;
        head -> next = tmp -> next;
    }
    else//对1<loc<length的情况进行处理
    {
        while(loc > 2)//找到loc的前一个节点
        {
            loc--;
            tmp = tmp -> next;
        }

        freenode = tmp -> next;//保存要释放的节点地址
        tmp -> next = freenode -> next;
    }

    /*释放节点并修改链表信息*/
    free(freenode);
    head -> length --;

    return ret;
}

/*修改loc位置的节点信息*/
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data)
{
    /*合法性判断*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }
    bool_val ret = FALSE;
    ListNode* tmp = head -> next;

    while(loc > 1)//找到loc节点
    {
        tmp = tmp -> next;
        loc --;
    }

    tmp -> data = data;//修改节点数据
    return ret;
}

/*返回loc节点的数据*/
datatype FindDataByLoc(ListHead* head, uint16 loc)
{
    /*合法性判断*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }
    datatype ret = 0;
    ListNode* tmp = head -> next;

    while(loc > 1)//找到loc节点
    {
        tmp = tmp -> next;
        loc --;
    }

    ret = tmp -> data;

    return ret;
}

bool DestoryList(ListHead* head)
{
    ListNode* p = NULL;
    ListNode* node = NULL;
    if(head == NULL)
    {
        return TRUE;
    }

    /*释放除头节点之外的节点*/
    p = head -> next;

    while(p != NULL)
    {
        node = p;
        p = p -> next;
        free(node);
    }

    /*释放头节点*/
    free(head);

    return TRUE;
}

chain.c

　　以下为main.c文件

#include <stdio.h>
#include "chain.h"

int main()
{
    int i = 0;
    ListHead* head =  NULL;
    head = CreateList();//创建链表

    printf("Now we will Add four Nodes\n");
    for(i = 1; i < 5; i++)
    {
        AddNodeByLoc(head, i, i);//添加链表节点
    }
    ViewList(head);//遍历链表

    printf("Now we will Delete the third Node\n");
    DelNodeByLoc(head, 3);//删除链表的第三个节点
    ViewList(head);

    printf("Now we will modify the third Node to 5\n");
    ModNodeByLoc(head, 3, 5);//将第三个节点的信息修改为5
    ViewList(head);

    printf("Now we will view the second Node\n");
    printf("%d\n",FindDataByLoc(head, 2));//查看第二个节点的数据
    DestoryList(head);//销毁链表
}

main.c

　　以下为MakeFile文件

main: chain.o main.o    #生成main依赖的文件
#执行命令cc chain.o main.o -o main生成最终的可执行文件main
    cc chain.o main.o -o main
main.o: main.c chain.h    #生成main.o依赖的文件

chain.o: chain.c chain.h    #生成chain.o依赖的文件

#删除生成的中间文件
clean:    
    rm *.o main

MakeFile

　　上面的四个文件我在Linux的环境下使用，将上面的文件放在同一个文件夹下，输入make运行，完成后生成chain.o main.o以及可执行文件main，运行make clean清除三个编译生成的文件。

　　这里我简单说一下什么是Makefile。在Windows下编译工作都由IDE来完成，例如VC6.0编译工程，你不需要管文件之间的依赖关系。但是在Linux环境下这部分工作由MakeFile完成。MakeFile关系到整个工程的编译规则，一个工程下文件不计其数，按模块、类型、功能分放在不同的目录下，MakeFile指定了一系列规则来指定哪些文件先编译，哪些文件需要后编译，哪些文件需要重新编译，甚至还有一些更复杂的功能操作。它带来的好处就是“自动化编译”，一旦写好MakeFile文件，工程的编译只需要一个make命令，整个工程就会全自动编译。上面就是我为链表写的一个很简单的MakeFile文件，后续的博客中会更新MakeFile的相关用法。

       

　　如果很不习惯也可以直接运行编译命令gcc main.c chain.c -o main当然也可以直接复制三个文件的内容直接在VC6.0下运行，效果是一样的。

　　

　　下面是链表运行的结果