单链表的基本操作大全之C语言达成

发布时间：2021-12-05 17:40:24 所属栏目：教程来源：互联网

导读：单链表的基本操作大全之C语言实现 1. 单链表的定义链表是通过一组任意的存储单元来存储线性表中的数据元素，这些存储单元可以是连续的也可以是不连续的。为了建立起数据元素之间的关系，对于每个数据元素除了存放数据元素自身的信息外，还必须有包含的指示

单链表的基本操作大全之C语言实现

1. 单链表的定义
链表是通过一组任意的存储单元来存储线性表中的数据元素，这些存储单元可以是连续的也可以是不连续的。为了建立起数据元素之间的关系，对于每个数据元素除了存放数据元素自身的信息外，还必须有包含的指示该元素直接后继元素存储位置的信息，这两部分信息组成一个结点，即每个结点都有至少包括两个域，一个域存储数据元素信息，称为数据域，另一个域存储直接后继的地址,称为指针域。

    typedef struct node{
        int data;    //数据域
        struct node *next;    //指针域
    }NODE;
当n个元素的线性表通过每个结点的指针域连接成了一条“链子”，我们形象的称之为链表。

2. 建立单链表
建立单链表有两种方法，一种是头插法，一种是尾插法。
在主函数中调用函数时，使用一个NODE *类型的指针接收函数的返回值。

2.1初始化一个链表结点
每次malloc的结点都要初始化，因此写成一个函数。

    //初始化一个节点
    NODE *initnode(NODE *pnode, int data)
    {
            pnode = (NODE *)malloc(sizeof(NODE));
            pnode->data = data;//初始化数据域
            pnode->next = NULL;//初始化指针域为NULL

            return pnode;
    }
2.2头插法建立链表
在链表的头部插入结点建立单链表，称为“头插法”。

    //创建一个新节点(头插法)
    NODE *createlink_byhead(NODE *phead, int data)
    {
            NODE *pnode = initnode(pnode, data);//初始化一个结点
            NODE *ptmp = phead;

        if(NULL == phead){    //链表为空，直接返回初始化的结点
                return pnode;
        }else{
                phead = pnode;    //将新申请的结点插在phead后面，也就是整个链表的最前面
                pnode->next = ptmp;
        }

        return phead;
}
因为每次新结点都会插在链表的头部，则数据读入的顺序和线性表中的逻辑顺序正好相反。

2.3尾插法建立链表
在链表的尾部插入结点建立单链表，简称”尾插法“。

    //创建一个链表节点(尾插法)
    NODE *createlink_bytail(NODE *phead, int data)
    {
            NODE *pnode = initnode(pnode, data);//初始化结点
            NODE *ptmp = phead;

        if(NULL == phead){//当链表为空，直接返回初始化的结点
                return pnode;
        }else{
                while(ptmp->next != NULL){//找到最后一个结点，插在尾部
                        ptmp = ptmp->next;
                }
                ptmp->next = pnode;
        }

        return phead;
    }
尾插法读入的数据与线性表中的逻辑顺序相同

3. 链表的长度
    //求链表长度
    int linklen(NODE *phead)
    {
            int len = 0;//计数器
            NODE *ptmp = phead;

            while(ptmp != NULL){//遍历链表，计数器加1
                    len++;
                    ptmp = ptmp->next;
            }

            return len;
    }
这个算法的时间复杂度为O(n)

4. 按值查找操作
   //按值查找
    NODE *searchnode(NODE *phead, int key)
    {
        NODE *ptmp = phead;

        if(NULL == phead){    //链表为空，直接返回
                return NULL;
        }
        while(ptmp->data != key && ptmp->next != NULL){//没找到key && 链表没找完
                ptmp = ptmp->next; //指针移动
        }
        if(ptmp->data == key) //找到key，返回该结点地址
                return ptmp;
        if(ptmp->next == NULL)//没找到，返回空
                return NULL;
    }
这个算法的时间复杂度为O(n)

5.插入操作
插入操作也分为两种，一种是插在目标值得前面，简称“前插法”，另一种是插在目标值的后面，简称“后插法”。

5.1前插法
//向前插入
    NODE *insertnode_bypre(NODE *phead, int data, int key)
    {
        NODE *pnode = initnode(pnode, data);//初始化插入的结点
        NODE *ptmp = phead;

        if(NULL == phead){//链表为空，直接返回初始化的结点
                return pnode;
        }else if(phead->data == key){//处理第一个结点是否为目标结点
                phead = pnode;
                pnode->next = ptmp;
        }else{
                while(ptmp->next != NULL && ptmp->next->data != key){//循环遍历，没找完 && 没找到
                        ptmp = ptmp->next;
                }
                if(NULL == ptmp->next){//没找到的情况
                        printf("insert key NOT FOUNDn");
                }else{//把新节点插入目标结点的前面
                        ptmp->next->data == key;
                        pnode->next = ptmp->next;
                        ptmp->next = pnode;
                }
        }
        return phead;
    }
前插法单独处理了第一个结点，是因为前插法会改变phead的值，而且前插法查找目标结点必须知道目标节点的前驱结点的next值，所以从第二个结点开始处理。

5.2后插法
   //向后插入
    NODE *insertnode_byback(NODE *phead, int data, int key)
    {
        NODE *pnode = initnode(pnode, data);//初始化插入的结点
        NODE *ptmp = searchnode(phead, key);//查找到目标结点

        if(NULL == ptmp){//处理链表为空，或没找到
                printf("link is empty or not found keyn");
                return phead;
        }
        if(NULL == ptmp->next){//如果key为最后一个结点
                ptmp->next = pnode;
        }else{ //将新节点插入在目标结点的后面
                pnode->next = ptmp->next;
                ptmp->next = pnode;
        }

        return phead;
}
后插法要单独处理尾结点的情况，因为插入操作不相同。
前插法和后插法的时间复杂度都为O(n)

6.删除操作
  //删除节点
    NODE *delnode(NODE *phead, int key)
    {
        NODE *ptmp = phead;
        NODE *tmp = NULL;

        if(NULL == phead){//处理链表为空的情况
                printf("link is empty, del failn");
                return NULL;
        }else if(phead->data == key){//单独处理第一个结点
                phead = phead->next;
                free(ptmp);
                ptmp = NULL;
        }else{
                while(ptmp->next != NULL && ptmp->next->data != key){ //没找完 && 没找到
                        ptmp = ptmp->next;
                }
                if(NULL == ptmp->next){ //没找到
                        printf("del key NOT FOUNDn");
                        return phead;
                }
                if(ptmp->next->data == key){ //找到目标结点删除之
                        tmp = ptmp->next;
                        ptmp->next = tmp->next;
                        free(tmp);
                        tmp = NULL;
                }
        }
        return phead;
}
单独处理第一个结点还是因为要知道要删除目标结点的前驱结点
删除操作算法时间复杂度为O(n)

7.链表的倒置
链表的倒置算法思路：一次取出原链表中的每一个结点，将其作为第一个结点插入新链表中。

  //链表的倒置
    NODE *reverselink(NODE *phead)
    {
        NODE *ptmp = NULL;//创建一个新链
        NODE *tmp = NULL;

        if(NULL == phead){//处理链表为空
                printf("link is emptyn");
                return NULL;
        }else{
                while(phead != NULL){//将旧链上的结点链到新链上
                        tmp = phead;
                        phead = phead->next;
                        tmp->next = ptmp;
                        ptmp = tmp;
                }
        }
        return ptmp;
}
8.链表的排序（冒泡排序）
    //链表排序(冒泡)
    NODE *linksort(NODE *phead)
    {
        NODE *p = NULL; //i
        NODE *q = NULL; //j
        NODE *r = NULL;
        NODE tmp;

        for(p = phead; p; p = p->next){
                for(q = p->next; q; q = q->next){
                        if(p->data > q->data){
                                tmp = *p;//整个结点交换
                                *p = *q;
                                *q = tmp;
                                r = p->next;//将指针换回去
                                p->next = q->next;
                                q->next = r;
                        }
                }
        }

        return phead;
    }
冒泡排序的时间复杂度为O(n²)

下面是补充：

1. 递归打印链表
void show_linklist(PNODE *phead)
{
        if(phead == NULL){
                return;
        }else{
                printf("%dt", phead->data);
                show_linklist(phead->pnext);
                //将此行放在printf的前面则递归打印倒置链表
        }
}
2.链表快速排序
PNODE *divide_two_Qsort(PNODE *phead, PNODE *ptail)
{
        int key = phead->data;
        PNODE *p = phead;
        PNODE *q = phead->pnext;

        while(q != ptail){
                if(q->data < key){
                        p = p->pnext;
                        int tmp;
                        tmp = p->data;
                        p->data = q->data;
                        q->data = tmp;
                }
                q = q->pnext;
        }
        int tmp = p->data;
        p->data = phead->data;
        phead->data = tmp;

        return p;
}

void quicksort_linklist(PNODE *phead, PNODE *ptail)
{
        if(phead != ptail){
                PNODE *pmid = divide_two_Qsort(phead, ptail);
                quicksort_linklist(phead, pmid);
                quicksort_linklist(pmid->pnext, ptail);
        }
}
3. 递归计算链表长度
int getlistlen_recursion(PNODE *phead)
{
        if(phead == NULL)
                return 0;
        else
                return 1+getlistlen_recursion(phead->pnext);
}
4.反转链表（非递归）
PNODE *invert_linklist(PNODE *phead)
{
        if(phead == NULL || phead->pnext == NULL){
                return phead;
        }else{
                PNODE *p = phead;
                PNODE *q = NULL;
                PNODE *r = NULL;
                while(p != NULL){
                        q = p->pnext;//保存下一个节点
                        p->pnext = r;//让该节点指向上一个节点
                        r = p;//上一个节点走到当前节点
                        p = q;//当前节点走到下一个节点
                }
                return r;
        }
}
5.反转链表（递归）
PNODE *invert_linklist_recursion(PNODE *phead)
{
        if(phead == NULL || phead->pnext == NULL){
                return phead;
        }else{
                PNODE *p = phead;//保存头节点
                PNODE *q = p->pnext;//保存下一个节点
                phead = invert_linklist_recursion(q);//递归到最后一个几点,返回转置后链表的地址
                q->pnext = p;//让后面的节点指向前一个节点
                p->pnext = NULL;//每次递归返回都赋值为空，最后一次返回将转置后的节点的pnext赋值为空
                return phead;
        }
}
6.合并两个有序链表（非递归）
PNODE *merge_linklist(PNODE *phead1, PNODE *phead2)
{
        if(phead1 == NULL){
                return phead2;
        }else if(phead2 == NULL){
                return phead1;
        }

        PNODE *phead = NULL;

        if(phead1->data < phead2->data){
                phead = phead1;
                phead1 = phead1->pnext;
        }else{
                phead = phead2;
                phead2 = phead2->pnext;
        }//让phead找到最小的头节点

        PNODE *pcur = phead;//要比较节点(phead1 或 phead2)的上一个节点
        while(phead1 != NULL && phead2 != NULL){
                if(phead1->data < phead2->data){
                        pcur->pnext = phead1;
                        pcur = phead1;
                        phead1 = phead1->pnext;
                }else{
                        pcur->pnext = phead2;
                        pcur = phead2;
                        phead2 = phead2->pnext;
                }
        }

        pcur->pnext = ((phead1 == NULL) ? phead2 : phead1);

        return phead;
}
7.合并两个有序链表（递归）
PNODE *merge_linklist_recursion(PNODE *phead1, PNODE *phead2)
{
        if(phead1 == NULL){
                return phead2;
        }else if(phead2 == NULL){
                return phead1;
        }
        PNODE *phead = NULL;
        if(phead1->data < phead2->data){
                phead = phead1;
                phead->pnext = merge_linklist_recursion(phead1->pnext, phead2);
        }else{
                phead = phead2;
                phead->pnext = merge_linklist_recursion(phead1, phead2->pnext);
        }
        return phead;
}
8.找到链表中间节点
PNODE *find_midnode(PNODE *phead)
{
        if(phead == NULL || phead->pnext == NULL){
                return phead;
        }

        PNODE *p1 = phead;
        PNODE *p2 = phead;
        while(p2->pnext != NULL){
                p1 = p1->pnext;//p1走一步
                p2 = p2->pnext;
                if(p2->pnext != NULL){
                        p2 = p2->pnext;//p2走两步
                }
        }
        return p1;
}
9.判断链表是否有环
int is_circularlinklist(PNODE *phead)
{
        if(phead == NULL || phead->pnext == NULL){
                return 0;
        }
        PNODE *p1 = phead;
        PNODE *p2 = phead;
        while(p1 != NULL && p2 != NULL){
                p2 = p2->pnext;
                if(p1 == p2)
                        return 1;
                p2 = p2->pnext;
                p1 = p1->pnext;
        }
        return 0;
}
10.释放链表
void destory_linklist(PNODE *phead)
{
        PNODE *ptmp;
        while(phead != NULL){
                ptmp = phead;
                phead = phead->pnext;
                free(ptmp);
                ptmp = NULL;
        }
}

（编辑：开发网_开封站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

台式电脑怎样恢复系统	iso其是什么格式怎么打
电脑上对话框太大如何	小白重装系统Bootfix.