C语言数据结构之单链表与双链表的增删改查操作实现

目录

• 前言
• 单链表的增删改查
• 定义结构体以及初始化
• 增加结点
• 删除结点
• 查找修改结点
• 移除结点
• 最终效果
• 双链表的基本操作
• 初始化建表
• 遍历双链表
• 指定位置插入结点
• 指定位置删除结点
• 查找结点位置
• 最终效果
• 结语

前言

上篇博客分享了创建链表传入二级指针的细节，那么今天就分享几个c语言课程实践设计吧。这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了，那么再应对复杂的链表类的题也就能慢慢钻研了。学习是一个积累的过程，想要游刃有余就得勤学苦练！

单链表的增删改查

(1)项目需求

构造带有头结点的单链表数据结构，实现初始化、清空和销毁操作，在两端插入元素和删除元素操作并在链表中查找操作，在指定位置插入和删除元素操作，移除元素操作

(2)解决思路
①  定义节点类型，定义单链表类型，构造创建新节点的函数。

②  初始化、清空和销毁操作：初始化操作负责将参数指向的单链表类型变量初始 化为空链表。清空操作的作用是将一个链表清空。销毁操作负责销毁一个链表。

③  在两端插入元素和删除元素操作：包括从链表头部插入和删除元素，从链表尾 部插入和删除元素。

④  在链表中查找操作 : 查找操作用于在参数指向的链表中，查找首个值等于待插入 参数的元素。并返回结点的首地址，返回的地址可供使用者修改结点信息。

⑤  在指定位置插入和删除元素操作：插入和删除元素都涉及到前后位置指针的指 向问题，有多种解决方案。以插入元素为例，将元素插入指定位置、指定位置 之 4前和指定位置之后等。

⑥  移除元素：用于删除链表中所有满足某个条件的元素。删除单向链表中的结点 需要修改前驱结点的指针域，链表的首元结点没有前驱结点，需要考虑如何处理。

定义结构体以及初始化

typedef struct LinkList //typedef是重命名的含义，此时LinkList * 和 List 含义一致，都是指向结点的指针
{
    int data;//数据域
    LinkList* next;//指针域
}*List; //指向结点的指针
//初始化链表
void init_List(List &L)
{
    //初始化后链表第一个结点就是头结点
    L = (List)malloc(sizeof(LinkList));//为链表分配空间
    L->data = 0;//数据域为零
    L->next = NULL;//指针指向空
}

//清空链表
void clear_List(List &L)
{
    if (L->next != NULL)//如果头结点连着的第一个结点不为NULL
    {
        L->next = NULL;//置为NULL，此时链表只有头结点，相当于清空链表
    }
    printf("清空链表成功");
}
//销毁链表
void destory_List(List &L)
{
    if (L != NULL)//当头结点不为空时
    {
        free(L);//删除头结点地址
        L = NULL;//将指针指向NULL，彻底销毁链表
    }
    printf("销毁链表成功");
}

增加结点

1、头插

//头插法
void headAdd_List(List &L)
{
    List ptr = L->next;//ptr指针初始化指向首元结点，也就是除了头结点的第一个结点
    int value = 0;//用来赋值为插入结点的data属性
    printf("输入头插的结点值：");
    scanf("%d", &value);
    List s = (List)malloc(sizeof(LinkList));//s 为待插入结点
    s->data = value;//将value赋值给s data属性
    s->next = ptr;//s 指向 ptr，即指向头结点的下一个结点
    L->next = s;//L头结点指向s,那么现在s结点就插入
}

2、 尾插

//尾插法
void tailAdd_List(List &L)
{
    int value = 0;//用来赋值为插入结点的data属性
    printf("输入尾插的结点值：");
    scanf("%d", &value);
    List s = (List)malloc(sizeof(LinkList));//s 为待插入结点
    s->data = value;//将value赋值给s data属性
    List ptr = L->next;//ptr指针初始化指向首元结点，也就是除了头结点的第一个结点
    if (ptr == NULL)//此时链表为空
    {
        s->next = L->next;
        L->next = s;
    }
    else {
        List pre = NULL;//创建pre指针
        while (ptr)//当ptr不为NULL时
        {
            pre = ptr;//将pre指向ptr
            ptr = ptr->next;//ptr指向他的下一个结点
        }//循环结束时，pre指向链表最后一个结点,ptr指向最后一个结点的下一个结点
        s->next = ptr;//待插入s结点指向ptr
        pre->next = s;//将s结点插入到链表最后，尾插完成
    }
}

3、指定位置插入

//插入操作
void insert_List(List &L,int n,int data)
{
    List ptr = L->next;
    List pre = NULL;
    List s = (List)malloc(sizeof(LinkList));//s 为待插入结点
    s->data = data;//将形参列表的data数据赋值给s的data属性
    s->next = NULL;
    if (n<1)
    {
        printf("插入位置错误!");
    }
    else if (n == 1)
    {
        printf("调用头插法，请重写输入元素值：");
        headAdd_List(L);//如果插入第一个位置，调用头插法
    }
    else
    {
        for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循环结束后，ptr指向待插入的位置,pre指向待插入位置的前一个位置
        s->next = ptr;//插入s结点
        pre->next = s;
    }
}

删除结点

1、头删

void headDelete_List(List &L)
{
    printf("执行头删：\n");
    List ptr = L->next;//ptr指针初始化指向首元结点，也就是除了头结点的第一个结点
    L->next = ptr->next;//直接让头结点指向首元结点的下一个结点，跳过首元结点就是删除
    delete ptr;//将首元结点地址删除
    ptr = NULL;//指针指向空，防止空指针异常
}

2、尾删

//尾删
void tailDelete_List(List& L)
{
    printf("执行尾删：\n");
    List ptr = L;//ptr指针指向头结点
    List pre = NULL;//创建结点pre
    while (ptr->next)//当ptr的下一个结点不为NULL时
    {
        pre = ptr;//将pre指向ptr
        ptr = ptr->next;//ptr指向他的下一个结点
    }//循环结束时，pre指向链表最后一个结点的前一个结点,ptr指向链表最后一个结点
    pre->next = NULL;//将pre的next指针置为空，删除掉
    free(ptr);//释放删除掉的ptr指针
}

3、指定位置删除 

void delete_List(List & L, int n)
{
    List ptr = L->next;
    List pre = NULL;
    if (n<1)
    {
        printf("删除位置有误!");
    }
    else if (n == 1)
    {
        headDelete_List(L);//调用头删
    }
    else
    {
        for (int i = 1; i < n ;i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }//循环结束后，ptr指向待插入的位置,pre指向待插入位置的前一个位置
        pre->next = ptr->next;//删除该位置的结点
        delete ptr;//删除ptr地址
        ptr = NULL;//防止空指针异常
    }

}

查找修改结点

List find_List(int data,List &L)
{
    int i = 1;
    List ptr = L->next;
    while (ptr)//当结点不为空时
    {
        if (ptr->data == data)
        {
            printf("该元素在链表的位置为第 %d个\n",i);
            return ptr;//找到就返回地址
        }
        i++;
        ptr = ptr->next;//继续遍历
    }
    printf("链表中没有该元素\n");
    return NULL;
}

移除结点

//移除元素
void cancel_List(List &L,int n)
{
    List ptr = L->next;
    List pre = L;
    while (ptr)//ptr不空时
    {
        if (ptr->data == n)//如果和传进来的n相等
        {
            pre->next = ptr->next;//删除改结点
            delete ptr;//删除地址
            ptr = pre;//重新指向前一个结点
        }
        else {
            pre = ptr;//如果ptr不和n相等，让pre往后走
            ptr = ptr->next;//ptr向后遍历
        }
    }
}

最终效果

双链表的基本操作

初始化建表

typedef int ElemType;//将整型数据重命名为int
typedef int Status;//整型重命名为Status

//双链表的数据结构定义
typedef struct DouNode {
    ElemType data;               //数据域
    struct DouNode* head;        //前驱指针
    struct DouNode* next;        //后继指针
}DousList, * LinkList;// 结点指针
//双链表的创建
void CreateDouList(LinkList &L, int n)
{
    LinkList  ptr;
    int i;
    L = (LinkList)malloc(sizeof(DousList));    //为头结点申请空间
    L->next = NULL;
    L->head = NULL;
    L->data = n;//L->data记录结点的个数
    ptr = L;
    for (i = 0; i < n; i++)
    {
        int value = 0;
        scanf("%d",&value);
        LinkList me = (LinkList)malloc(sizeof(DouNode));
        me->data = value;    //节点数据域
        me->next = NULL;
        me->head = NULL;
        ptr->next = me;
        me->head = ptr;
        ptr = ptr->next;     //尾插法建表
    }
}

遍历双链表

//双链表的遍历
void DisPlayList(LinkList L)
{
    printf("当前链表数据为：\n");
    LinkList ptr= L->next;
    while (ptr)
    {
        printf("%d ",ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

指定位置插入结点

void InsertNode(LinkList &L, int n, ElemType data)
{
    LinkList pre=NULL;
    LinkList ptr = L->next;
    LinkList me = (LinkList)malloc(sizeof(DouNode));
    me->head = NULL;
    me->next = NULL;
    me->data = data;
    if (n<1 || n>L->data)
    {
        printf("插入位置有误!");
        return ;
    }
    else if (n == 1)
    {
        ptr->head = me;
        me->next = ptr;
        L->next = me;
        me->head = L;
        L->data++;
    }
    else
    {
        for (int i = 1; i < n; i++)
        {
            pre = ptr;
            ptr = ptr->next;
        }
        ptr->head = me;
        me->next = ptr;
        pre->next = me;
        me->head = pre;
        L->data++;
    }

}

指定位置删除结点

Status DeleteNode(LinkList& L, int n, ElemType* v)
{
    LinkList ptr = L->next;
    if (n<1 || n>L->data)
    {
        printf("删除位置有误!");
        return -1;
    }
    else
    {
        for (int i = 1; i < n; i++)
        {
            ptr = ptr->next;
        }
        v= &ptr->data;
        ptr->head->next = ptr->next;
        ptr->next->head = ptr->head;

    }
    L->data--;
    return *v;
}

查找结点位置

void FindNode(LinkList L, ElemType data)
{
    int i = 0;
    LinkList ptr = L;
    while (ptr) {
        i++;
        ptr=ptr->next;
        if (ptr->data == data) {
            printf("该元素在链表中的位置为：%d\n",i);
        }
    }
}

最终效果

结语

链表的操作看着复杂其实也不复杂，和数组的区别就是需要动态分配内存空间，然后遍历有点小复杂罢了，多加练习就好了。

以上就是C语言数据结构之单链表与双链表的增删改查操作实现的详细内容，更多关于C语言 单链表 双链表的资料请关注我们其它相关文章！