数据结构与算法：单链表（超详细实现）

阳光穿透心脏的1/2处 2022-05-31 03:23 166阅读 0赞

# 实现算法预览 #

**这次博主写的单链表主要实现了以下算法。所有功能可进行循环运行测试**。**欢迎各位指正**。

LinkList.h

#pragma once
    #ifndef __LINKLIST_H__
    #define __LINKLIST_H__
    #define _CRT_SECURE_NO_WARNINGS
    typedef struct LinkNode LinkNode;
    typedef struct LinkNode
    {
    	int data;
    	LinkNode* next;
    }LinkNode;
    
    //初始化链表数据
    LinkNode* initLinkList();
    
    //插入结点 根据查询的值的在其前面插入新的值
    int insertLinkList(LinkNode* pHeader, int oldVal, int newVal);
    
    //获取链表结点个数
    int getLengthLinkList(LinkNode* pHeader);
    
    //遍历链表进行打印结点
    int printLinkList(LinkNode* pHeader);
    
    //删除结点 根据查询的值删除相应的结点
    int deleteLinkList(LinkNode* pHeader, int val);
    
    //清空链表 保留头结点，仍然可以进行单链表相关操作
    int clearLinkList(LinkNode* pHeader);
    
    //销毁链表 连头结点都释放
    int destroyLinkList(LinkNode* pHeader);
    
    //loc 插入到链表的第几个位置，从1开始 loc <=1 放在第一个位置 ，超过结点最后一个位置放在尾结点
    int insertPositionLinkList(LinkNode* pHeader, int loc, int val);
    
    //删除第loc位置的元素，loc 如果不合法（<1或>结点个数不删除元素），通过指针将结点数据返回
    int delPositionLinkList(LinkNode* pHeader, int loc, int* val);
    
    //链表反转
    int reverseLinkList(LinkNode* pHeader);
    
    //利用递归进行逆序遍历
    void printRerverseLinkList(LinkNode* pHeader);
    
    #endif // !__LINKLIST_H__

![SouthEast][]

# 单链表简要介绍 #

**单链表是一种**链式存取的数据结构**，用一组**地址任意的存储单元**存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。**

# 单链表代码展示 #

LinkList.c

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "LinkList.h"
    
    LinkNode* list = NULL;
    //初始化链表数据
    LinkNode* initLinkList()
    {
    	LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode));
    	LinkNode* cur = head;
    	while (1)
    	{
    		printf("请输入结点数据（-1退出）：");
    		int val = 0;
    		scanf("%d", &val);
    		if (val == -1)
    		{
    			break;
    		}
    		LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
    		node->next = NULL;
    		node->data = val;
    		cur->next = node;
    		cur = node;
    	}
    	return head;
    }
    
    //插入结点 往查询的值的前面插入新的值
    int insertLinkList(LinkNode* pHeader, int oldVal, int newVal)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	LinkNode* pre = pHeader;
    	LinkNode* cur = pHeader->next;
    	while (cur!=NULL)
    	{
    		if (cur->data == oldVal)
    		{
    			break;
    		}
    		pre = pre->next;
    		cur = cur->next;
    	}
    	//创建新结点
    	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    	newNode->data = newVal;
    	newNode->next = NULL;
    	pre->next = newNode;
    	newNode->next = cur;
    	return 1;
    }
    //获取链表结点个数
    int getLengthLinkList(LinkNode* pHeader)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	LinkNode* cur = pHeader;
    	int length = 0;
    	while (cur->next != NULL)
    	{
    		cur = cur->next;
    		length++;
    	}
    	return length;
    }
    
    //打印结点
    int printLinkList(LinkNode* pHeader)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	if (pHeader->next == NULL)
    	{
    		printf("当前链表为空！\n");
    	}
    	LinkNode* cur = pHeader->next;
    	int num = 1;
    	while (cur!=NULL)
    	{
    		printf("第%d个结点data: %d\n", num, cur->data);
    		cur = cur->next;
    		num++;
    	}
    	return 0;
    }
    //删除结点
    int deleteLinkList(LinkNode* pHeader,int val)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	LinkNode* pre = pHeader;
    	LinkNode* cur = pHeader->next;
    	while (cur != NULL)
    	{
    		if (cur->data == val)
    		{
    			break;
    		}
    		pre = pre->next;
    		cur = cur->next;
    	}
    	if (cur != NULL)
    	{
    		pre->next = cur->next;
    		free(cur);
    		cur = NULL;
    	}
    	return 1;
    }
    //清空链表 保留头结点
    int clearLinkList(LinkNode* pHeader)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	LinkNode* cur = pHeader->next;
    	while (cur != NULL)
    	{
    		LinkNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	pHeader->next = NULL;
    	return 1;
    }
    //销毁链表
    int destroyLinkList(LinkNode* pHeader)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	clearLinkList(pHeader);
    	free(pHeader);
    	return 1;
    }
    //loc 插入到链表的第几个位置，从1开始 loc <=1 放在第一个位置 ，超过结点最后一个位置放在尾结点
    int insertPositionLinkList(LinkNode* pHeader,int loc, int val)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	LinkNode* cur = pHeader;
    	int i = 1;
    	while (cur->next!=NULL && i<loc)
    	{
    		i++;
    		cur = cur->next;
    	}
    	//cur 为插入元素的前驱结点
    	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
    	newNode->data = val;
    	newNode->next = cur->next;
    	cur->next = newNode;
    
    	return 1;
    }
    //删除第loc位置的元素，loc 如果不合法（<1或>结点个数不删除元素），通过指针将结点数据返回
    int delPositionLinkList(LinkNode* pHeader, int loc, int* val)
    {
    	if (pHeader == NULL || loc < 1)
    	{
    		return 0;
    	}
    	LinkNode* cur = pHeader;
    	int i = 1;
    	while (cur->next != NULL&&i<loc)
    	{
    		i++;
    		cur = cur->next;
    	}
    	//cur 为删除元素的前驱结点
    	if (i == loc && cur->next!=NULL)
    	{
    		LinkNode* del = cur->next;
    		*val = del->data;
    		cur->next = del->next;
    		free(del);
    		del = NULL;
    		return 1;
    	}
    	return 0;
    }
    //链表反转
    int reverseLinkList(LinkNode* pHeader)
    {
    	if (pHeader == NULL)
    	{
    		return 0;
    	}
    	LinkNode* pre = NULL;
    	LinkNode* cur = pHeader->next;
    	LinkNode* next = NULL;
    	while (cur !=NULL)
    	{
    		//保存当前节点的下一个结点
    		next = cur->next;
    		//将当前节点的next域指向前一个结点
    		cur->next = pre;
    
    		//pre、cur 往后移动
    		pre = cur;
    		cur = next;
    	}
    	//循环结束 pre 指向最后一个结点，将头结点指向 它
    	pHeader->next = pre;
    	return 1;
    }
    
    void printRerverseLinkList(LinkNode * pHeader)
    {
    	LinkNode* cur = pHeader->next;
    	if (cur == NULL)
    	{
    		return;
    	}
    	printRerverseLinkList(cur);
    	printf("%d ", cur->data);
    }
    
    void fun01_init()
    {
    	list = initLinkList();
    	printLinkList(list);
    	return;
    }
    void fun02_valueInsert()
    {
    	int oldVal = 0, newVal = 0;
    	printf("请输入查询的值：");
    	scanf("%d", &oldVal);
    	printf("请输入要插入值：");
    	scanf("%d", &newVal);
    	int ret = insertLinkList(list, oldVal, newVal);
    	if (ret)
    	{
    		printf("插入成功\n");
    	}
    	else
    	{
    		printf("插入失败\n");
    	}
    	printLinkList(list);
    	return;
    }
    void fun03_valueInsertPosition()
    {
    	int loc = 0, newVal = 0;
    	printf("请输入插入的位置：");
    	scanf("%d", &loc);
    	printf("请输入要插入值：");
    	scanf("%d", &newVal);
    	int ret = insertPositionLinkList(list, loc, newVal);
    	if (ret)
    	{
    		printf("插入成功\n");
    	}
    	else
    	{
    		printf("插入失败\n");
    	}
    	printLinkList(list);
    	return;
    }
    void fun04_valueDel()
    {
    	int val = 0;
    	printf("请输入要删除的值：");
    	scanf("%d", &val);
    	int ret = deleteLinkList(list,val);
    	if (ret)
    	{
    		printf("删除成功\n");
    	}
    	else
    	{
    		printf("删除失败\n");
    	}
    	printLinkList(list);
    	return;
    }
    void fun05_valueDelPosition()
    {
    	int loc = 0,val = 0;
    	printf("请输入删除元素的位置：");
    	scanf("%d", &loc);
    	int ret = delPositionLinkList(list, loc,&val);
    	if (ret)
    	{
    		printf("删除成功,删除元素的值：%d\n",val);
    	}
    	else
    	{
    		printf("删除失败\n");
    	}
    	printLinkList(list);
    	return;
    }
    void fun06_reverseLinkList()
    {
    	reverseLinkList(list);
    	printLinkList(list);
    	return;
    }
    void fun07_clearLinkList()
    {
    	clearLinkList(list);
    	return;
    }
    void fun08_destroyLinkList()
    {
    	destroyLinkList(list);
    	return;
    }
    
    
    
    
    
    
    int main(int argc, char *argv[])
    {
    	int menu = 0;
    	while (1)
    	{
    		printf("---菜单-----------------------\n");
    		printf("---1、初始化链表--------------\n");
    		printf("---2、通过结点值插入结点------\n");
    		printf("---3、通过位置插入结点--------\n");
    		printf("---4、通过结点值删除结点------\n");
    		printf("---5、通过位置删除结点--------\n");
    		printf("---6、反转链表----------------\n");
    		printf("---7、清空链表----------------\n");
    		printf("---8、销毁链表----------------\n");
    		printf("---9、遍历链表----------------\n");
    		printf("--10、链表长度----------------\n");
    		printf("--11、逆序遍历----------------\n");
    		printf("---0、退出--------------------\n请输入:");
    		scanf("%d",&menu);
    		if (menu == 0)
    		{
    			break;
    		}
    		switch (menu)
    		{
    		case 1:
    			fun01_init();
    			break;
    		case 2:
    			fun02_valueInsert();
    			break;
    		case 3:
    			fun03_valueInsertPosition();
    			break;
    		case 4:
    			fun04_valueDel();
    			break;
    		case 5:
    			fun05_valueDelPosition();
    			break;
    		case 6:
    			fun06_reverseLinkList();
    			break;
    		case 7:
    			fun07_clearLinkList();
    			break;
    		case 8:
    			fun08_destroyLinkList();
    			break;
    		case 9:
    			printLinkList(list);
    			break;
    		case 10:
    			printf("链表元素个数：%d\n",getLengthLinkList(list));
    			break;
    		case 11:
    			printRerverseLinkList(list);
    			printf("\n");
    			break;
    		default:
    			break;
    		}
    
    	}
    	return 0;
    }

# 运行结果测试 #

![SouthEast 1][]  ![SouthEast 2][]

![SouthEast 3][]  ![SouthEast 4][]

[SouthEast]: /images/20220531/1f6a9512929a4e31bb5d57f2daa5ca9e.png
[SouthEast 1]: https://img-blog.csdn.net/20180205232840297?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk1NDI2MTE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220531/55c83269c0cb433e96b06493f98ebe7b.png
[SouthEast 3]: https://img-blog.csdn.net/20180205232849744?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjk1NDI2MTE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: /images/20220531/bd65586dd3694794a13bfe32c796b882.png