C语言 单链表 双链表
叶落秋白 人气:0前言
上篇博客分享了创建链表传入二级指针的细节，那么今天就分享几个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);
}
}
}
最终效果
结语
链表的操作看着复杂其实也不复杂，和数组的区别就是需要动态分配内存空间，然后遍历有点小复杂罢了，多加练习就好了。
加载全部内容