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);
       }
   }
}

最终效果

来源：https://blog.csdn.net/m0_58618795/article/details/125652787