数据结构（二）单链表

发布于：2024-05-24 ⋅ 阅读:(152) ⋅ 点赞:(0)

一、链表

（一）概念

逻辑结构：线性
存储结构：链式存储，在内存中不连续

分为有头链表和无头链表
同时又细分为单向、循环、双向链表

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

以下数据及地址只是为了方便理解设置
在这里插入图片描述

（三）操作

1. 节点的结构体定义：

① 定义：

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

② 注意点：

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

2. 创建链表

（1） 函数声明

create_list(nd_t **phead,int num);

该函数需要在内存中申请一块nd_t类型大小的空间，并将其地址返回给main函数中用户定义的指针中；
num是用来初始化这块空间中数据域的值。

（2）注意点：
  1. 必须传入二级指针
  2. phead不能为空，即不能传一个NULL作为形参，后面需要对phead取值
  3. 需要检查是否申请内存成功
（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）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（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)；

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（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);

② 注意点：
  1. 传入一级指针即可
  2. 需要判断传入的列表指针是否是空指针
③ 示意图

在这里插入图片描述

③ 代码实现
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);

② 注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
③ 代码实现
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<pos;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 insert_list_by_tail(nd_t *phead,int num);

② 注意点：
③ 代码实现
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 *ptemp=phead->next;
    phead->next=ptemp->next;
    free(ptemp);
    ptemp=NULL;
    return 0;
}
（2）尾删
① 函数声明

int insert_list_by_tail(nd_t *phead,int num);

② 注意点：
③ 代码实现
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);

② 注意点：
③ 代码实现
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<pos;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);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（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);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（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);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（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 create_node(node_t **list,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现

11. 链表翻转

（1） 函数声明

int create_node(node_t **list,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现

12. 链表剔重

（1） 函数声明

int create_node(node_t **list,int *num);

（2）注意点：
  1. 必须传入二级指针
  2. 需要判断传入的列表指针是否是空指针
（3）代码实现

13. 打印链表

（1） 函数声明

int print_list(nd_t *phead);

（2）注意点：
  1. 注意对于边界点的判定
（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;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布