数据结构（二）单链表

文章目录

一、链表

（一）概念
（二）有头单向链表示意图
（三）操作

1. 节点的结构体定义：
2. 创建链表

（1）函数声明
（2）注意点：
（3）示意图
（4）代码实现
3. 清空

（1）函数声明
（2）注意点：
（3）代码实现
4. 销毁

（1）函数声明
（2）注意点：
（3）代码实现
5. 插入（头插、尾插、任意位置插）

（1）头插

① 函数声明
② 注意点：
③ 示意图
③ 代码实现
（2）尾插

① 函数声明
② 注意点：
③ 代码实现
（3）任意位置插入

① 函数声明
② 注意点：
③ 代码实现
6. 删除（头删、尾删、任意位置删）

（1）头删

① 函数声明
② 注意点：
③ 代码实现
（2）尾删

① 函数声明
② 注意点：
③ 代码实现
（3）任意位置删除

① 函数声明
② 注意点：
③ 代码实现
7. 修改

（1）函数声明
（2）注意点：
（3）代码实现
8. 查询

（1）函数声明
（2）注意点：
（3）代码实现
9. 链表合并

（1）函数声明
（2）注意点：
（3）代码实现
10. 链表排序

（1）函数声明
（2）注意点：
（3）代码实现
11. 链表翻转

（1）函数声明
（2）注意点：
（3）代码实现
12. 链表剔重

（1）函数声明
（2）注意点：
（3）代码实现
13. 打印链表

（1）函数声明
（2）注意点：

（3）代码实现

一、链表

（一）概念

逻辑结构：线性

存储结构：链式存储，在内存中不连续

分为有头链表和无头链表

同时又细分为单向、循环、双向链表

（二）有头单向链表示意图

以下数据及地址只是为了方便理解设置

（三）操作

1. 节点的结构体定义：

① 定义：

typedef struct node
{ int data; //保存数据
    struct node* next;  //记录下一节点的地址，注意此时指针类型不能定义为nd_t*
}nd_t;

② 注意点：

定义结构体成员时，指针的类型此时不能使用nd_t定义。

2. 创建链表

（1）函数声明

create_list(nd_t **phead,int num);

该函数需要在内存中申请一块nd_t类型大小的空间，并将其地址返回给main函数中用户定义的指针中；

num是用来初始化这块空间中数据域的值。

（2）注意点：

必须传入二级指针
phead不能为空，即不能传一个NULL作为形参，后面需要对phead取值
需要检查是否申请内存成功

（3）示意图

（4）代码实现

//创建节点
create_list(nd_t **phead,int num){ if(NULL==phead){ printf("传入指针为NULL");
    }
    //*phead可以为空，即main函数中的phead可以是一个空指针
    //但是phead不能为空，即不能传一个NULL作为形参
    *phead=(nd_t *)malloc(sizeof(nd_t));
    if(NULL==*phead){ printf("申请空间失败！\n");
        return -1;
    }
    //初始化
    (*phead)->data=num;
    (*phead)->next=NULL;
    return 0;
}

3. 清空

（1）函数声明

int clean_list(nd_t *phead);

该函数通过头删的方式依次释放所有数据节点，但是保留头节点。

（2）注意点：

入参合理性检查，传入的参数不能为NULL
表不能为空，即phead->next不能为空，因为后面会用到phead->next->next，如果phead->next为空，会出现段错误

（3）代码实现

int clean_list(nd_t *phead){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(NULL==phead->next){ printf("表为空\n");
        return -1;
    }
    nd_t *ptemp=NULL;
    //使用头删清空
    while(NULL!=phead->next)
    { ptemp=phead->next;
        phead->next=ptemp->next;
        free(ptemp);
    }
    ptemp=NULL;
    return 0;
}

4. 销毁

（1）函数声明

int destory_list(nd_t **phead)；

依次删除所有数据节点后，释放头节点，并且将主函数中定义的phead置NULL。

（2）注意点：

必须传入二级指针
需要判断传入的列表指针是否是空指针
还需要判断*phead是否是NULL，因为free不能对NULL操作

（3）代码实现

int destory_list(nd_t **phead){ if(NULL==phead || NULL==*phead){ printf("传入指针为NULL");
        return -1;
    }
    clean_list(*phead);
    free(*phead);//free参数不能是一个空指针
    *phead=NULL;
    return 0;
}

5. 插入（头插、尾插、任意位置插）

（1）头插

① 函数声明

int insert_list_by_head(nd_t *phead,int num);

② 注意点：

传入一级指针即可
需要判断传入的列表指针是否是空指针

③ 示意图

③ 代码实现

int insert_list_by_head(nd_t *phead,int num){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    //创建新节点
    nd_t *ptemp = NULL;
    if(create_node(&ptemp,num)<0)
    { printf("内存分配失败\n");
        return -1;
    }
    ptemp->next=phead->next;
    phead->next=ptemp;
    return 0;
}

（2）尾插

① 函数声明

int insert_list_by_tail(nd_t *phead,int num);

先遍历函数找到尾节点，再插入

② 注意点：

入参合理性检查
判断创建新节点是否成功

③ 代码实现

int insert_list_by_tail(nd_t *phead,int num){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到尾节点
    while(NULL!=ptemp->next){ ptemp=ptemp->next;
    }
    //创建新节点
    nd_t *pnew = NULL;
    if(create_node(&pnew,num)<0)
    { printf("内存分配失败\n");
        return -1;
    }
    ptemp->next=pnew;
    return 0;
}

（3）任意位置插入

① 函数声明

int insert_list_by_pos(nd_t *phead,int pos,int num);

找到要插入的位置的前一个节点，创建新节点，插入新节点

② 注意点：

传参合理性检查
位置不能小于0，最后一个数据的后面可以插入，最后一个数据的后面的后面就不能再插入了，需要额外进行判定

③ 代码实现

int insert_list_by_pos(nd_t *phead,int pos,int num){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){ printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要插入的位置的前一个节点
    for(int i=0;i //当ptemp->next为0时，说明不能继续向下遍历了
        if(NULL==ptemp->next){ printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    
    //创建新节点
    nd_t *pnew = NULL;
    if(create_node(&pnew,num)<0)
    { printf("内存分配失败\n");
        return -1;
    }
    pnew->next=ptemp->next;
    ptemp->next=pnew;
    return 0;
}

6. 删除（头删、尾删、任意位置删）

（1）头删

① 函数声明

int delete_list_by_tail(nd_t *phead);

将phead->next=pdel->next，然后释放pdel

② 注意点：

参数合理性检查
表不能为空，即phead->next不能为空，因为后面会用到phead->next->next，如果表为空，在对NULL->next会报段错误。

③ 代码实现

int delete_list_by_head(nd_t *phead){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(NULL==phead->next){ printf("表为空\n");
        return -1;
    }
    nd_t *pdel=phead->next;
    phead->next=pdel->next;
    free(pdel);
    pdel=NULL;
    return 0;
}

（2）尾删

① 函数声明

int delete_list_by_tail(nd_t *phead,int num);

先找到尾节点的前一个节点

释放尾节点，

将新的尾节点的成员next置NULL

② 注意点：

参数合理性检查
表不能为空，即phead->next不能为空，因为后面会用到phead->next->next，如果表为空，在对NULL->next会报段错误。

③ 代码实现

int delete_list_by_tail(nd_t *phead){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(NULL==phead->next){ printf("表为空\n");
        return -1;
    }
    //找到尾节点的前一个节点
    nd_t *ptemp=phead;
    while(NULL!=ptemp->next->next){ ptemp=ptemp->next;
    }
    free(ptemp->next);
    ptemp->next=NULL;
    return 0;
}

（3）任意位置删除

① 函数声明

int delete_list_by_pos(nd_t *phead,int pos);

找到要删除的节点的前一个节点，

定义一个变量保存要删除的节点的指针

将要删除的节点的前一个节点指向要删除的节点的后一个节点

释放要删除的节点

② 注意点：

传参合理性检查
要删除的位置不能小于0，与任意位置插入不同，最后一个数据的后面就不能再删除了

③ 代码实现

int delete_list_by_pos(nd_t *phead,int pos){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){ printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要删除的位置的前一个节点
    for(int i=0;i //当ptemp->next为0时，说明此时ptemp位于链表的最后一个节点，但是此时ptemp后的节点是空，不能进行删除操作
        //所以如果ptemp->next->next为空时，就不能继续往后移动了
        if(NULL==ptemp->next->next){ printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    nd_t *pdel=ptemp->next;
    ptemp->next=pdel->next;
    free(pdel);
    pdel=NULL;
    return 0;
}

7. 修改

（1）函数声明

int modify_list_by_pos(nd_t *phead,int pos,int num);

找到要修改的位置，修改其成员data

（2）注意点：

传参合理性检查
要修改的位置不能小于0，与任意位置插入不同，最后一个数据的后面就不能再修改了

（3）代码实现

int modify_list_by_pos(nd_t *phead,int pos,int num){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){ printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要修改的位置的节点
    for(int i=0;i<=pos;i++){ //当ptemp->next为0时，说明此时ptemp位于链表的最后一个节点，不能继续后移了
        if(NULL==ptemp->next){ printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    ptemp->data=num;
    return 0;
}

8. 查询

（1）函数声明

int search_list_by_pos(nd_t *phead,int pos,int *num);

找到要查询的位置，将该位置的数据传给num

（2）注意点：

传参合理性检查
要查询的位置不能小于0，与任意位置插入不同，最后一个数据的后面就不能再进行查询了

（3）代码实现

int search_list_by_pos(nd_t *phead,int pos,int *num){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    if(0>pos){ printf("位置不合理\n");
        return -1;
    }
    nd_t *ptemp=phead;
    //找到要查找的位置的节点
    for(int i=0;i<=pos;i++){ //当ptemp->next为0时，说明此时ptemp位于链表的最后一个节点，不能继续后移了
        if(NULL==ptemp->next){ printf("位置不合理\n");
            return -1;
        }
        ptemp=ptemp->next;
    }
    *num=ptemp->data;
    return 0;
}

9. 链表合并

（1）函数声明

int merge_list(nd_t *phead1,nd_t **phead2);

找到第一个链表的尾节点

将链表1的尾节点的next赋值为phead2-next

释放phead2

（2）注意点：

链表2必须传入二级指针
需要判断传入phead1,phead2,*phead2是否为空

（3）代码实现

int merge_list(nd_t *phead1,nd_t **phead2){ if(NULL==phead1||NULL==phead2||NULL==*phead2){ printf("传参为空\n");
        return -1;
    }
    //先找到表1的尾部
    nd_t *ptemp=phead1;
    while(NULL!=ptemp->next)
    { ptemp=ptemp->next;
    }
    ptemp->next=(*phead2)->next;
    free(*phead2);
    *phead2=NULL;
    return 0;
}

10. 链表排序

（1）函数声明

int sort_list(node_t *phead);

一个定点指针，一个动点指针配合

选择排序的思路

只需要交换两个节点的数据即可

（2）注意点：

入参合理性判断
表为空，表中只有一个节点都不需要进行排序

（3）代码实现

int sort_list(node_t *phead)
{ if(NULL==phead){ printf("传参为空\n");
        return -1;
    }
    if(NULL==phead->next)
    { printf("表为空，无需排序\n");
        return -1;
    }
    if(NULL==phead->next->next)
    { printf("只有一个节点，无需排序\n");
        return -1;
    }
    nd_t *p=phead;
    nd_t *q=NULL;
    int temp=0;
    while(NULL!=p->next){ p=p->next;
        q=p->next;
        while(NULL!=q){ if(p->data > q->data){ temp=p->data;
                p->data=q->data;
                q->data=temp;
            }
            q=q->next;
        }
    }
    return 0;
}

11. 链表翻转

（1）函数声明

int overturn_list(node_t *phead);

将第一个数据节点的指针域置NULL，使用头插将第二个节点以及其后的所有节点以头插的方式插入链表

（2）注意点：

传参合理性判断
表为空，表中只有一个节点都不需要进行排序

（3）代码实现

int overturn_list(node_t *phead){ if(NULL == phead){ printf("入参为NULL\n");
        return -1;
    }
    if(NULL==phead->next)
    { printf("表为空\n");
        return -1;
    }
    if(NULL==phead->next->next)
    { printf("只有一个节点，无效翻转");
        return -1;
    }
    node_t *p=phead->next;
    node_t *q=p->next;
    p->next=NULL;
    while (q!=NULL)
    { //记录q后面的节点
        p=q->next;
        //头插
        q->next=phead->next;
        phead->next=q;
        q=p;
    }
    return 0;
}

12. 链表剔重

（1）函数声明

int dedup_list(node_t *phead);

动静指针配合，找到需要剔重的节点以及其前一个节点，然后删除该节点

（2）注意点：

传参合理性判断
判断表是否为空
判断表是不是只有一个节点
删除过节点后，动指针无需再后移

（3）代码实现

int dedup_list(nd_t *phead){ if(NULL==phead){ printf("传参为空\n");
        return -1;
    }
    if(NULL==phead->next)
    { printf("表为空，无需翻转\n");
        return -1;
    }
    if(NULL==phead->next->next)
    { printf("只有一个节点，无需翻转\n");
        return -1;
    }
    nd_t *p=phead->next;
    nd_t *m=NULL;
    nd_t *q=NULL;
    while(NULL!=p){ //*注意此处绝对不可以写作NULL!=p->next
        m=p;
        q=p->next;
        while(q!=NULL){ if(p->data==q->data){ m->next=q->next;
                free(q);
                q=m->next;
            }else{ m=q;
                q=q->next;
            }
        }
        p=p->next;
    }
}

13. 打印链表

（1）函数声明

int print_list(nd_t *phead);

（2）注意点：

传参不能为NULL

（3）代码实现

//打印
int print_list(nd_t *phead){ if(NULL==phead){ printf("传入指针为NULL");
        return -1;
    }
    nd_t *ptemp=phead->next;
    while(NULL!=ptemp){ printf("%d ",ptemp->data);
        ptemp=ptemp->next;
    }
    putchar(10);
    return 0;
}

分类:热门推荐日期:2024-05-30浏览:1评论:0

文章目录

一、链表

（一）概念

（二）有头单向链表示意图

（三）操作

1. 节点的结构体定义：

2. 创建链表

（1） 函数声明

（2）注意点：

（3）示意图

（4）代码实现

3. 清空

（1） 函数声明

（2）注意点：

（3）代码实现

4. 销毁

（1） 函数声明

（2）注意点：

（3）代码实现

5. 插入（头插、尾插、任意位置插）

（1）头插

① 函数声明

② 注意点：

③ 示意图

③ 代码实现

（2）尾插

① 函数声明

② 注意点：

③ 代码实现

（3）任意位置插入

① 函数声明

② 注意点：

③ 代码实现

6. 删除（头删、尾删、任意位置删）

（1）头删

① 函数声明

② 注意点：

③ 代码实现

（2）尾删

① 函数声明

② 注意点：

③ 代码实现

（3）任意位置删除

① 函数声明

② 注意点：

③ 代码实现

7. 修改

（1） 函数声明

（2）注意点：

（3）代码实现

8. 查询

（1） 函数声明

（2）注意点：

（3）代码实现

9. 链表合并

（1） 函数声明

（2）注意点：

（3）代码实现

10. 链表排序

（1） 函数声明

（2）注意点：

（3）代码实现

11. 链表翻转

（1） 函数声明

（2）注意点：

（3）代码实现

12. 链表剔重

（1） 函数声明

（2）注意点：

（3）代码实现

13. 打印链表

（1） 函数声明

（2）注意点：

（3）代码实现

节点函数

相关推荐

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明

（1）函数声明