数据结构之链表及应用

**程序 = 数据结构 + 算法 **

数据结构的设计对于程序的结构和性能都至关重要。合理的数据结构不仅可以降低算法的复杂性，使程序更易于理解和维护，并且可以极大地提升程序的性能。

数据结构综述.png

上图已经列出了常用的数据结构和基本的操作，本文主要讲述线性结构的链表的创建和增删改查等基本操作。
首先明确几个名词和其对应的英文单词:
list（表）、queue（队列）、stack（栈）、tree（树）、graph（图）
link（链式）、sequence（顺序）、node（节点）

  1. 顺序表
    顺序表比较简单，不是本文的重点，在这里只做简单的介绍。比较着急的童鞋可直接跳到第二部分。
    顺序表和数组其实是差不多的，只不过数组是存储在栈空间，而表需要在堆空间申请内存空间(请参考这篇介绍：内存管理).
    定义顺序表的结构体：
typedef struct _seqlist_
{
        int *data;//可以理解为int data[tlen],指向内存片段的首地址
        int clen;//顺序表当前长度
        int tlen;//顺序表总长度
}seqlist_st;

顺序表基本操作：

  • 初始化函数
seqlist_st *seqlist_init(int len)//传入表的总长度，类似于数组的大小
{
        seqlist_st *list = NULL;

        list = (seqlist_st *)malloc(sizeof(seqlist_st));//向内存申请表头结构体的内存空间
        list->data = (int *)malloc(sizeof(int) * len);//申请顺序表的内存大小，类似于 int data[len]
        list->clen = 0;//表的当前长度
        list->tlen = len;//表的总长度

        return list;
}
  • 销毁函数
 int seqlist_destroy(seqlist_st *list)
{
        free(list->data);//先把结构体内部申请到的内存释放
        free(list);//再释放表头结构体的内存地址

        return 0;
}
  • 增
    顺序表的插入操作：由于顺序表的内存地址是连续的，所以插入操作比较麻烦，需要将插入位置及之后位置的数值全部后移一位。这里只简单地将元素插入尾部。
int seqlist_insert(seqlist_st *list,int value)
{
        if(list->clen >= list->tlen)//判断链表长度是否超过申请的内存大小
                return -1;
        list->data[list->clen++] = value;//clen记得要执行 +1 操作噢！

        return 0;
}
  • 删
    顺序表的删除操作同样需要将之后的元素全部前移一个位置：
int seqlist_delete(seqlist_st *list, int value)
{
        int i, j;

        for(i=0; i < list->clen; i++)
        {
                if(list->data[i] == value)//删除表中所以得value单元
                {
                        for(j=i; j+1 < list->clen; j++)//将value元素之后的所以单元前移一个位置
                                list->data[j] = list->data[j+1];    
                        list->clen--;//将当前长度 -1
                        i--;//请认真理解此处为何要 -1
                }
        }

        return 0;
}
  • 改
    将表中的第一个old替换为new,若不存在old则返回 -1
int seqlist_modify(seqlist_st *list,int old,int new)
{
        int i;
        for(i = 0;i < list->clen;i++)
        {
                if(list->data[i]== old)//找到第一个old并将其替换为new
                        break;
        }

        if(i>=list->clen)
                return -1;

        list->data[i]=new;

        return 0;
}```
 - 查
  看表中是否存在此值

int seqlist_search(seqlist_st *list,int value)
{
int i;

    for(i = 0;i<list->clen;i++)
    {
            if(list->data[i]==value)//查找第一个vlaue值
                    break;
    }

    if(i>=list->clen)
            return 0;

    return 1;

}

  这里给出一个show()函数和main()函数以方便测试顺序表的基本操作是否正确：

int seqlist_show(seqlist_st *list)
{
int i=0;
for(i=0;i<list->clen;i++)
printf("%5d ",list->data[i]);
printf("\n");

    return 0;

}```

int main(int argc, const char *argv[])
{
        seqlist_st *list = NULL;
        int value = 100;

        list = seqlist_init(10);

        while(0 == seqlist_insert(list,value))
                value += 100;
 
        seqlist_show(list);
        seqlist_delete(list,600);
        seqlist_show(list);
        printf("search(300)= %d \n",seqlist_search(list,300));
        printf("modify(200,300)= %d \n",seqlist_modify(list,200,300));
        seqlist_show(list);
        printf("search(200)= %d \n",seqlist_search(list,200));
        seqlist_delete(list,300);
        seqlist_show(list);
        seqlist_destroy(list);

        return 0;
}
  1. 链表
    链表和顺序表的本质区别在于：链式表在堆内存中不是顺序存储的，而是链式存储的，即相邻的两个单元在物理位置上并不相邻，也即地址并不连续。而是前一个节点里面存储的后一个节点的内存地址，通过此种方式实现存储和访问。
    链式表的创建和基本的操作我们直接在下面的完整的程序中进行说明：
链表的内存视图
#include <stdio.h>
#include <stdlib.h>

typedef struct _linknode_//链表的节点结构体
{
    int data;//存储节点的值
    struct _linknode_ *next;//存储后续单元的地址
}linknode_t;

typedef struct _linklist_//链表的结构体
{
    struct _linknode_ *head;//链表头的地址
    int clen;//链表当前的长度
    int tlen;//链表的总长度
}linklist_t;

int linklist_destroy(linklist_t *list);
linklist_t *linklist_init(int len);
int linklist_insert(linklist_t *list,int value);
linknode_t *creat_linknode(int value);
int linklist_show(linklist_t *list);
int linklist_delete(linklist_t *list,int value);
linknode_t * linklist_search(linklist_t *list,int value);
int linklist_modify(linklist_t *list,int old,int new);
int linklist_insertend(linklist_t *list,int value);
int linklist_insertmid(linklist_t *list,int local_value,int destin_value);

int main(int argc, const char *argv[])
{
    int value = 100;
    linknode_t *ret=NULL;
    linklist_t *list = NULL;//链表首地址

    list = linklist_init(10);//初始化链表，传入链表长度

    while(0 == linklist_insertend(list,value))//使用尾差法将值插入表中
        value +=100;

    linklist_show(list);//查看表

    linklist_delete(list,600);//删除表中值为600的节点
  
    linklist_show(list);
    ret = linklist_search(list,600);//查找链表中值为600的节点，返回其结构体地址

    if(ret == NULL)
        printf("search : NULL \n");
    else
        printf("%d \n",ret->data);

    linklist_modify(list,500,543);//修改
    ret = linklist_search(list,543);

    if(ret == NULL)
        printf("search : NULL \n");
    else
        printf("%d \n",ret->data);
    
    linklist_insertmid(list,400,678);//将678插入在400的下一节点

    linklist_show(list);
 
    linklist_destroy(list);//一定记得要销毁链表释放内存噢，不然会产生内存泄露喔。

    return 0;
}

linklist_t *linklist_init(int len)//链表的初始化
{
    linklist_t *list = NULL;

    list = (linklist_t *)malloc(sizeof(linklist_t));//链表的结构体地址
    list->head = creat_linknode(0);//链表的头结点，
    list->clen = 0;
    list->tlen = len;

    return list;
}

int linklist_destroy(linklist_t *list)//链表的销毁
{
    linknode_t *p = list->head;
    linknode_t *temp = NULL;

    while(NULL != p)
    {
        temp = p;//从头结点开始逐个释放申请到的内存空间
        p = p->next;
        free(temp);
    }
    free(list);

    return 0;
}

int linklist_insert(linklist_t *list,int value)//链表擦头插发，即将value值插入链表的第一个位置(头结点之后)
{
    linknode_t *new = NULL;

    if(list->clen>=list->tlen)
        return -1;

    new = creat_linknode(value);
    new->next=list->head->next;//新建节点的next指向原头节点的后继节点
    list->head->next=new;//头结点的next指向新建的节点，则完成了头插法

    list->clen++;

    return 0;
}

linknode_t *creat_linknode(int value)
{
    linknode_t  *node = NULL;

    node = (linknode_t *)malloc(sizeof(linknode_t));//申请内存空间，创建节点，链式表只在需要用时才去动态申请内存空间，顺序表和数组都是在一开始即初始化就申请了所需的全部内存
    node->data = value;
    node->next = NULL;

    return node;//返回申请到的节点的内存空间地址
}

int linklist_show(linklist_t *list)//辅助函数，顺序打印链表的值
{
    int i;
    linknode_t *p = list->head->next;
    for(i=0;i<list->clen;i++)   
    {
        printf("%5d ",p->data);
        p=p->next;
    }
    putchar('\n');
    return 0;
}

int linklist_delete(linklist_t *list,int value)
{
    linknode_t *p = list->head;
    linknode_t *tmp = NULL;

    while(NULL != p->next)//找到需要删除的节点的地址：注意，我们需要定位到其前一个节点，即 p->next->data == value 的p，请认真思考为什么
    {
        if(p->next->data == value)//
                break;
        p=p->next;
    }

    if(NULL == p->next)  
        return -1;
    
    tmp = p->next;//将要删除的节点的地址（p->next）先暂存
    p->next = tmp->next;//将其前一个节点p的next指向其后继节点，现在才可以释放其内存
    free(tmp);

    list->clen--;

    return 0;
}

 linknode_t * linklist_search(linklist_t *list,int value)
{
    linknode_t *p = list->head->next;
    while(NULL != p)
    {
        if(p->data == value)//搜索链表中值为value的节点，并将其地址返回，如不存在，则返回null
            return p;
        p=p->next;
    }

    return NULL;
}
int linklist_modify(linklist_t *list,int old,int new)
{
    linknode_t *p = list->head->next;
    while(NULL != p)
    {
        if(p->data == old)//找到old节点，将其data值替换为指定的new
        {
            p->data = new;
            break;
        }       
            p=p->next;
    }
    
    if(NULL == p)//若没有找到old节点， 即链表中不存在值为old的结点，则返回-1
        return -1;

    return 0;
}
int linklist_insertend(linklist_t *list,int value)
{
    linknode_t *p = list->head;
    linknode_t *new = NULL;
    
    while(NULL != p->next)//找到最后一个节点
        p = p->next;
    
    if(list->clen >= list->tlen)
        return -1;

    new = creat_linknode(value);//创建新的节点
    p->next = new;//将找到的最后一个节点的next指向新创建的节点，这样新创建的节点就添加在整个链表的最后了
    list->clen++;

    return 0;
}

int linklist_insertmid(linklist_t *list,int local_value,int destin_value)
{
    linknode_t *p = list->head->next;
    linknode_t *new = NULL;
    linknode_t *tmp = NULL;

    if(list->clen >= list->tlen)
        return -1;

    while(NULL != p)
    {
        if(p->data == local_value)//找到值为local_value的节点的地址
        {
            tmp = p->next;//先将其后继节点的地址存储起来
            new = creat_linknode(destin_value);//创建新的节点
            p->next = new;//使local节点的next指向新插入的节点
            new->next = tmp;//新创建的节点的next指向原local的后继节点，完成了插入操作
            list->clen++;
            break;
        }
        p = p->next;
    }

    return 0;
}

上述实现的链表是单向链表，即只能从前一个节点找到后一节点，此外还有双向链表(即能从前一个节点找到后一个节点，也能从后一个节点找到前一个节点，即一个节点结构体不仅存了前一个节点的地址还存了后继节点的地址)、循环链表(即尾节点的next不为null,而是存了第一个节点的地址)等。只需在此基础上稍加修改即可实现。我们可以根据具体的需求来选择相应的数据结构。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 196,099评论 5赞 462
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 82,473评论 2赞 373
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 143,229评论 0赞 325
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,570评论 1赞 267
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,427评论 5赞 358
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,335评论 1赞 273
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,737评论 3赞 386
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,392评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,693评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,730评论 2赞 312
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,512评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,349评论 3赞 314
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,750评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,017评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,290评论 1赞 251
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,706评论 2赞 342
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,904评论 2赞 335

推荐阅读更多精彩内容

  • iOS 数据结构之链表
    链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链...
    盖世英雄_ix4n04阅读 591评论 0赞 0
  • 数据结构之链表
    /*Linklist h; 定义头指针*/ /*ListNode *p; 定义指向某结点的指针,两者类型相同*/ ...
    钟美怡阅读 278评论 0赞 1
  • 数据结构之链表
    链表是线性表的一种。线性表是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关系是一对一的关系，...
    骑摩托马斯阅读 645评论 0赞 3
  • 此刻
    大二了，大二了，一切都是原来的样子，一切又都变了样。 还没准备好就被时间扔回了学校，迷茫，无助...
    啦里哗稀阅读 174评论 0赞 0
  • docker基础 --- 安装篇
    说明 Docker必须安装在64位平台上，且内核版本必须高于3.10，一般装于CentOS 7上 安装 使用脚本自...
    梦想做小猿阅读 183评论 0赞 0