链表(数据结构)

本篇文章主要针对《数据结构》中的单链表，循环链表，循环双链表的增删查改以及一些常用算法进行详尽的代码描述。本代码使用c语言书写，并且通过测试。可以直接拷贝编译，在你的main函数中进行测试。

链表结点结构定义

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

头插法建立带头结点单链表

/**
 * [CreatListHeadInsert 采用头插法建立带头结点的单链表]
 * @return [构造成功返回头结点的指针]
 */
LinkList CreatListHeadInsert()
{
    LNode *s;
    LinkList L;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while(x != 999)
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

尾插法建立带头结点的单链表

/**
 * [CreatListTailInsert 采用尾插法建立带头结点的单链表]
 * @return [构造成功后返回头结点的指针]
 */
LinkList CreatListTailInsert()
{
    LinkList L;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r = L;
    int x;
    scanf("%d",&x);
    while(x != 999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

依照单链表结点的储存顺序依次输出单链表的值

/**
 * [PrintList 依照顺序依次打印单链表储存的值]
 * @param  L [单链表的头结点指针]
 * @return   [成功打印返回 1]
 */
int PrintList(LinkList L)
{
    L = L->next;
    while (L != NULL) {
        printf("%d,",L->data);
        L = L->next;
    }
    printf("\n");
    return 1;
}

逆向打印单链表中的值

/**
 * [ReversePrint 逆向输出所有单链表中的值]
 * @param L [传入单链表所指向的下一个结点指针]
 */
void ReversePrint(LinkList L)
{
    if(L->next != NULL)
    {
        ReversePrint(L->next);
    }
    printf("%d,",L->data);
}

将单链表中的结点依照结点值大小顺序依次从大到小输出并且依次释放所有结点

/**
 * [PrintIncrease 将单链表中的结点按顺序依次从大到小输出并且释放该结点]
 * @param L [单链表头结点]
 */
void PrintIncrease(LinkList L)
{
    LinkList preMin,p,u;
    while (L->next != NULL) {
        preMin = L;
        p = L->next;
        while (p->next != NULL) {
            if(preMin->next->data  > p->next->data)
            {
                preMin = p;
            }
            p = p->next;
        }
        printf("%d ",preMin->next->data);
        u = preMin->next;
        preMin->next = u->next;
        free(u);
    }
    free(L);
}

查找第i个位置上单链表存储的值

/**
 * [GetElem 依照顺序查找单链表储存的值]
 * @param  L [单链表的头指针]
 * @param  i [要查找的位置]
 * @return   [成功返回该位置的指针 L,失败返回 NULL]
 */
LinkList GetElem(LinkList L,int i)
{
    int j = 2;
    LinkList p = L->next;
    if(i == 1)
    {
        return p;
    }
    if(i < 0)
    {
        return NULL;
    }
    while (p && j <= i) {
        p = p->next;
        j++;
    }
    return p;
}

查找目标值e 所对应的结点

/**
 * [LocateElem 依照目标数据查找单链表储存该值得结点]
 * @param  L [单链表的头指针]
 * @param  e [查找的目标值]
 * @return   [成功返回该位置的指针 L，失败返回 NULL]
 */

LinkList LocateElem(LinkList L, int e)
{
    L = L->next;
    while(L && L->data != e)
    {
        L = L->next;
    }
    return L;
}

单链表结点的插入与删除

/*------------------------------------------------------------------*/
/* 针对单链表的插入删除过程中，如果我们需要插入或者删除单链表的某一指针上的数值，除了寻找 */
/* 单链表的前驱结点，我们还可以通过将该结点的值与后继结点值的位置进行互换，然后删除后继结点 */
/* 以使插入和删除操作 在 O(1)时间内 完成，减少了寻找前驱结点消耗的时间 */

/**
 * [LinkListInsert 向单链表目标位置之前插入目标数据]
 * @param  L [单链表的头指针]
 * @param  i [待插入的目标位置 i]
 * @param  e [待插入的目标值 e]
 * @return   [插入成功返回 1，失败返回 -1]
 */
int LinkListInsert(LinkList L, int i, int e)
{
    LinkList p,s;
    p = GetElem(L,i-1);
    if(p == NULL)
    {
        return -1;
    }
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}
/**
 * [LinkListDelete 删除目标位置的结点]
 * @param  L [单链表的头指针]
 * @param  i [待删除位置 i]
 * @return   [成功返回 1,失败返回 -1]
 */
int LinkListDelete(LinkList L, int i)
{
    LinkList p,q;
    p = GetElem(L,i-1);
    if(p == NULL)
    {
        return -1;
    }
    q = p->next;
    p->next = q->next;
    free(q);
    return 1;
}
/*------------------------------------------------------------------*/

/**
 * ？  wrong program
 * [RecursiveDelElem 递归删除不带头结点的单链表中为x的结点]
 * @param L [单链表的首个结点]
 * @param x [需要删除的元素 x]
 */
void RecursiveDelElem(LinkList L, int x){
    LinkList p;
    if(L == NULL)
    {
        return ;
    }
    if(L->data == x)
    {
        p = L;
        L = L->next;
        free(p);
        RecursiveDelElem(L,x);
    } else {
        RecursiveDelElem(L->next,x);
    }
}

删除所有值为x的结点

/**
 * [DelElem 删除单链表中所有值为x的结点]
 * @param L [单链表的头结点]
 * @param x [待删除值为 x 的结点]
 */
void DelElem(LinkList L,int x) {
    LinkList p;
    L = L->next;
    if(L == NULL)
    {
        return;
    }
    while(L != NULL)
    {
        if(L->data == x)
        {
            p = L->next;
            L->data = p->data;
            L->next = p->next;
            free(p);
            continue;
        }
        L = L->next;
    }
    return;
}

删除值在某个范围内的所有结点

/**
 * [DelRangeElem 删除单链表中结点值在某个范围的所有结点]
 * @param L   [单链表头结点]
 * @param min [删除范围的最小值]
 * @param max [删除范围的最大值]
 */
void DelRangeElem(LinkList L,int min, int max) {
    LinkList p;
    L = L->next;
    if(L == NULL || (min > max))
    {
        return ;
    }
    while(L != NULL)
    {
        if(L->data >=min && L->data <= max)
        {
            p = L->next;
            L->data = p->data;
            L->next = p->next;
            free(p);
            continue;
        }
        L = L->next;
    }
}

删除单链表中的首个最小值结点

/**
 * [DeleteFirstMin 删除单链表中的首个最小值]
 * @param  L [单链表的头结点]
 * @return   [成功返回单链表的删除的最小值]
 */
int DeleteFirstMin(LinkList L)
{
    int tmpMin;
    LinkList p,q;
    L = L->next;
    tmpMin = L->data;
    p = L;
    while(L != NULL)
    {
        if(L->data < tmpMin)
        {
            tmpMin = L->data;
            p = L;
        }
        L = L->next;
    }
    q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return tmpMin;
}

将单链表逆置

/**
 * [LinkListReverse 将单链表原地逆置]
 * @param L [单链表的表头结点]
 */
void LinkListReverse(LinkList L)
{
    LinkList p,q;
    p = L->next;
    L->next = NULL;
    while (p != NULL)
    {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
    return ;
}

单链表插入排序，返回有序单链表

/**
 * [LinkListInsertSort 对链表中的元素进行排序，返回递增有序的单链表]
 * @param L [单链表的表头结点]
 */
void LinkListInsertSort(LinkList L)
{
    int tmp;
    LinkList p,pre,insert;
    pre = L->next;
    p = pre->next;
    insert = L->next;
    while (p != NULL)
    {
        if(p->data < pre->data)
        {
            insert = L->next;
            while(insert->data < p->data)
            {
                insert = insert->next;
            }
            pre->next = p->next;
            tmp = insert->data;
            insert->data = p->data;
            p->data = tmp;
            p->next = insert->next;
            insert->next = p;
        }else{
            pre = pre->next;
        }
        p = pre->next;
    }
}

将单链表拆分返回两个单链表A，B，其中A,B分别存储源表中奇数与偶数位置元素

/**
 * [SepLinkList 将单链表A分解成两个单链表A,B,其中A中储存源单链表A中奇数位置元素，
 * B保存偶数位置元素]
 * @param A [单链表A的头结点]
 * @param B [单链表B的头结点]
 */
void SepLinkList(LinkList A,LinkList B)
{
    LinkList p,insert,pre;
    pre = A;
    p = pre->next;
    int i = 0;
    while (p != NULL) {
        i++;
        if(i % 2 == 0)
        {
            insert = p;
            pre->next = p->next;
            insert->next = B->next;
            B->next = insert;
            B = B->next;
        }else{
            pre = pre->next;
        }
        p = pre->next;
    }
}

删除单链表中所有重复元素

/**
 * [DelDumpElem 删除单链表中所有的重复数据]
 * @param L [单链表的头结点]
 */
void DelDumpElem(LinkList L)
{
    LinkList p,pre,q;
    q = L->next;
    while (q->next != NULL) {
        pre = q;
        p = pre->next;
        while(p != NULL)
        {
            if(p->data == q->data)
            {
                pre->next = p->next;
                free(p);
            }else{
                pre = pre->next;
            }
            p = pre->next;
        }
        q = q->next;
    }
}

在有序的单链表中删除所有重复元素

/**
 * [DelSortDumpElem 单链表有序排列，删除单链表中所有相同的元素]
 * @param L [单链表的头结点L]
 */
void DelSortDumpElem(LinkList L)
{
    LinkList p,pre;
    pre = L->next;
    p = pre->next;
    while (p != NULL) {
        if(p->data == pre->data)
        {
            pre->next = p->next;
            free(p);
        }else{
            pre = pre->next;
        }
        p = pre->next;
    }
}

最后编辑于：2017.12.10 02:47:54

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

链表(数据结构)

推荐阅读更多精彩内容