链表(数据结构)

作者: jockerMe | 来源:发表于2017-08-20 16:41 被阅读61次

本篇文章主要针对《数据结构》中的单链表，循环链表，循环双链表的增删查改以及一些常用算法进行详尽的代码描述。本代码使用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;
    }
}

链表(数据结构)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

C语言

程序员