首页 > > 程序设计 > C/C++ >

数据结构--链表

2018-06-18 03:55:15来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--与链表无关纯属矫情

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

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

　　顺序存储结构就是两个相邻的元素在内存中也是相邻的，这种存储方式的优点是查询比较方便，通过首地址和偏移量就可以访问到某个元素，匹配的查找算法也有好多，最快的可以达到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下运行，效果是一样的。

　　

　　下面是链表运行的结果

      

　　不知道为什么图片显示不出来，以下是终端打印的内容

　　Now we will Add four Nodes
　　The List Info is CangLing's List
　　The List Length is 4
　　1　　　　　　//第一个位置添加1
　　2　　　　　　//第二个位置添加2
　　3　　　　　　//第三个位置添加3
　　4　　　　　　//第四个位置添加4　　

　　Now we will Delete the third Node　　　　//删除第三个节点的内容并打印链表
　　The List Info is CangLing's List
　　The List Length is 3
　　1
　　2
　　4
　　Now we will modify the third Node to 5　　//将第三个链表的内容修改为5
　　The List Info is CangLing's List
　　The List Length is 3
　　1
　　2
　　5
　　Now we will view the second Node　　　　//查看第二个链表的内容
　　2

　　欢迎评论

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：[linux] C语言Linux系统编程-TCP通信的11种状态

下一篇：最长公共子序列（DP）

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签