数据结构中链表的实现以及排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构中链表的实现以及排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

本期和大家主要分享的是关于数据结构中双向链表的实现过程，那么话不多说，来具体看看吧！

一、链表结构体定义

来分析一下，这里呢定义了一个int的数据类型，表明整个链表存放的是整形的数据；其次定义了链表节点的数据类型，其中包括了此节点存放的数据以及链接向下一个节点的地址；最主要的呢我们的链表是有头的（且链表类型结构体中存放了当前链表中的元素），并且链表头（链表类型，并不是一个节点）后的第一个节点是空节点，我们的有效节点是从这个空节点后面的这个节点开始存放数据的；

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 存储数据的类型 */
typedef int DataType;

/* 链表节点类型 */
typedef struct node
{
	DataType Data;			//数据域
	struct node *pNext;		//指向下一个节点的指针
}LinkNode;

/* 链表表头类型 */
typedef struct list
{
	LinkNode *pHead;
	int clen;
}LinkList;

extern LinkList *CreateLinkList(void);
extern LinkList *InsertHeadLinkList(LinkList *pTmpList, DataType TmpData);
extern int ShowLinkList(LinkList *pTmpList);
extern LinkNode *SearchLinkList(LinkList *pTmpList, DataType TmpData);
extern int UpdateLinkList(LinkList *pTmpList, DataType OldData, DataType NewData);
extern int InsertTailLinkList(LinkList *pTmpList, DataType TmpData);
extern int DeleteLinkList(LinkList *pTmpList, DataType TmpData);
extern int DestroyLinkList(LinkList **ppTmpList);
extern LinkNode *FindMidLinkNode(LinkList *pTmpList);
extern int ReverseLinkList(LinkList *pTmpList);
extern int BubbleSort(LinkList *pTmpList);
extern int ChoiceSortLinkList(LinkList *pTmpList);
#endif

二、具体实现过程

下面呢具体来看一下数据结构中链表的主要实现过程，其中包括了链表的创建，插入，删除，修改以及销毁，每个模块的代码如下：

#include "linklist.h"
/* 创建链表 */
LinkList *CreateLinkList(void)
{
	LinkList *pTmpList = NULL

	pTmpList = malloc(sizeof(LinkList));
	if (NULL == pTmpList)
	{
		perror("fail to malloc");
		return NULL;
	}

	pTmpList->clen = 0;
	pTmpList->pHead = malloc(sizeof(LinkNode));
	if (pTmpList->pHead == NULL)
	{
		perror("fail to malloc");
		return NULL;
	}

	pTmpList->pHead->pNext = NULL;

	return pTmpList;
}

/* 头插法插入数据 */
LinkList *InsertHeadLinkList(LinkList *pTmpList, DataType TmpData)
{
	LinkNode *pTmpNode = NULL;

	pTmpNode = malloc(sizeof(LinkNode));
	if (NULL == pTmpNode)
	{
		perror("fail to malloc");
		return NULL;
	}

	pTmpNode->Data = TmpData;
	pTmpNode->pNext = pTmpList->pHead->pNext;
	pTmpList->pHead->pNext = pTmpNode;
	pTmpList->clen++;

	return pTmpList;
}

/* 链表遍历 */
int ShowLinkList(LinkList *pTmpList)
{
	LinkNode *pTmpNode = NULL;

	pTmpNode = pTmpList->pHead->pNext;
	while (pTmpNode != NULL)
	{
		printf("%d ", pTmpNode->Data);
		pTmpNode = pTmpNode->pNext;
	}
	putchar('\n');

	return 0;
}

/* 查找元素 */
LinkNode *SearchLinkList(LinkList *pTmpList, DataType TmpData)
{
	LinkNode *pTmpNode = NULL;
	pTmpNode = pTmpList->pHead->pNext;

	while (pTmpNode != NULL)
	{
		if (pTmpNode->Data == TmpData)
		{
			return pTmpNode;
		}
		pTmpNode = pTmpNode->pNext;
	}
	
	return NULL;
}

/* 修改元素 */
int UpdateLinkList(LinkList *pTmpList, DataType OldData, DataType NewData)
{
	LinkNode *pTmpNode = NULL;
	pTmpNode = pTmpList->pHead->pNext;
	
	while (pTmpNode != NULL)
	{
		if (pTmpNode->Data == OldData)
		{
			pTmpNode->Data = NewData;
		}
		pTmpNode = pTmpNode->pNext;
	}

	return 0;
}

/* 尾插法插入元素 */
int InsertTailLinkList(LinkList *pTmpList, DataType TmpData)
{
	LinkNode *pTmpNode = NULL;
	LinkNode *pptmNode = NULL;
	pTmpNode = pTmpList->pHead;

	pptmNode = malloc(sizeof(LinkNode));
	if (pptmNode == NULL)
	{
		perror("fail to malloc");
		return -1;
	}

	while (pTmpNode->pNext != NULL)	//访问NULL的空间会段错误，这个就是第一个节点存在的好处
	{
		pTmpNode = pTmpNode->pNext;			//跳出后为最后一个节点
	}

	pptmNode->Data = TmpData;
	pTmpNode->pNext = pptmNode;
	pptmNode->pNext = NULL;
	pTmpList->clen++;

	return 0;
}

/* 删除一个链表节点(所有相同的元素都删除) */
int DeleteLinkList(LinkList *pTmpList, DataType TmpData)
{
	LinkNode *preLinkNode = NULL;
	LinkNode *desLinkNode = NULL;
	
	preLinkNode = pTmpList->pHead;
	desLinkNode = pTmpList->pHead->pNext;

	while (desLinkNode != NULL)
	{
		if (desLinkNode->Data == TmpData)
		{
			preLinkNode->pNext = desLinkNode->pNext;
			free(desLinkNode);
			desLinkNode = preLinkNode->pNext;
			pTmpList->clen--;
		}
		else
		{
			preLinkNode = preLinkNode->pNext;
			desLinkNode = desLinkNode->pNext;
		}	
	}

	return 0;
}

/* 销毁链表 */
int DestroyLinkList(LinkList **ppTmpList)
{
	LinkNode *pFreeNode = NULL;
	LinkNode *pTmpNode = NULL;

	pFreeNode = (*ppTmpList)->pHead;
	pTmpNode = (*ppTmpList)->pHead;

	while (pTmpNode != NULL)
	{
		pTmpNode = pTmpNode->pNext;
		free(pFreeNode);
		pFreeNode = pTmpNode;
	} 

	free(*ppTmpList);
	*ppTmpList = NULL;

	return 0;
}

/* 以下为链表的高级操作 */
/* 查找中间节点 */
LinkNode *FindMidLinkNode(LinkList *pTmpList)
{
	LinkNode *pFast = NULL;
	LinkNode *pSlow = NULL;

	pFast = pTmpList->pHead->pNext;
	pSlow = pTmpList->pHead->pNext;

	while (pFast != NULL)
	{
		pFast = pFast->pNext;
		if (NULL == pFast)
		{
			break;
		}
		pFast = pFast->pNext;			//快指针走两步(分两步,防止出现非法访问地址)
		if (NULL == pFast)
		{
			break;
		}
		pSlow = pSlow->pNext;			//慢指针走一步
	}
	
	return pSlow;
}

/* 链表倒置(头插法) */
/* 将链表断开，再次用头插法插入即可实现链表倒置 */
int ReverseLinkList(LinkList *pTmpList)
{
	LinkNode *pTmpNode = NULL;
	LinkNode *pInsertNode = NULL;

	pTmpNode = pTmpList->pHead->pNext;
	pTmpList->pHead->pNext = NULL;
	
	while (pTmpNode != NULL)
	{
		pInsertNode = pTmpNode;
		pTmpNode = pTmpNode->pNext;
		pInsertNode->pNext = pTmpList->pHead->pNext;
		pTmpList->pHead->pNext = pInsertNode;
	}
	return 0;
}

三、排序方法

这里给出两种排序方法，可能大家用c语言实现排序的时候比较简单，但是过渡到数据结构会有一点难度，这是没有关系的，主要是多画图多理解多思考；几遍下来比较难的问题就会变得容易许多；数据结构中前面会学习到顺序表和链式表，后面会紧接着学习顺序栈和链式栈，因此每到一个地方，都可以自己手动的去练习一下，这些都是一些最基本的模块化的程序，在程序设计上可以根据自己的需要在定义数据类型时适当进行增加都是可以的；

1. 冒泡排序

/* 冒泡排序(最后一次不需要进行比较) */
int BubbleSort(LinkList *pTmpList)
{
	LinkNode *preTmpNode = NULL;
	LinkNode *deTmpNode = NULL;
	LinkNode *pEndTmpNode = NULL;
	DataType TmpData = 0;

	preTmpNode = pTmpList->pHead->pNext;				 //前一个指向第一个节点
	if (preTmpNode == NULL || preTmpNode->pNext == NULL) //第一个节点没存数据或者只有第一个节点存储了数据不用排序
	{
		return 0;
	}

	deTmpNode = preTmpNode->pNext;						//后一个指针指向第一个指针的下一个节点

	while (deTmpNode != pEndTmpNode)					//前一个指针和后一个指针不是同一个节点，pEndTmpNode为每次比较后的最后一个节点
	{
		while (deTmpNode != pEndTmpNode)
		{
			if (preTmpNode->Data > deTmpNode->Data)
			{
				TmpData = preTmpNode->Data;
				preTmpNode->Data = deTmpNode->Data;
				deTmpNode->Data = TmpData;
			}
			preTmpNode = preTmpNode->pNext;
			deTmpNode = deTmpNode->pNext;
		}
		pEndTmpNode = preTmpNode;
		preTmpNode = pTmpList->pHead->pNext;
		deTmpNode = preTmpNode->pNext;
	}
	return 0;
}

2. 选择排序

/* 选择排序 */
int ChoiceSortLinkList(LinkList *pTmpList)
{
	LinkNode *pMinNode = NULL;		//每轮找出最小的一个，与pSwapNode交换值
	LinkNode *pTmpNode = NULL;		//每次从 pSwapNode的后一个开始往后寻找最小的数（与pMinNode比较）
	LinkNode *pSwapNode = NULL;		//每次寻找的开头（前面已经找好最小的数排列完毕）
	DataType TmpData;

	if (pTmpList->pHead->pNext == NULL || pTmpList->pHead->pNext->pNext == NULL)	//如果空节点后面的第一个节点无元素或者之后的第二个节点无元素(全部链表只有一个元素)则不用排序
	{
		return 0;
	}

	pSwapNode = pTmpList->pHead->pNext;

	while (pSwapNode->pNext != NULL)
	{
		pMinNode = pSwapNode;			//每轮开始从 pSwapNode开始
		pTmpNode = pSwapNode->pNext;	//从后一个往后开始比较寻找比最小的还小的
		while (pTmpNode != NULL)
		{
			if (pTmpNode->Data < pMinNode->Data)
			{
				pMinNode = pTmpNode;		//找到后将最小的地址赋值给 pMinNode
			}
			pTmpNode = pTmpNode->pNext;		//接着往后找
		}

		if (pMinNode != pSwapNode)			//如果最小的不是第一个就交换，若是第一个则不用进行操作
		{
			TmpData = pMinNode->Data;
			pMinNode->Data = pSwapNode->Data;
			pSwapNode->Data = TmpData;
		}
		pSwapNode = pSwapNode->pNext;		//此位置已经排列完毕，开始从下一个位置开始
	}

	return 0;
}

3. 判断一个链表是否有环

/* 如何判断一个链表是否有环（用快慢指针的方法） */
int IsCircleLinkList(LinkList *pTmpList, int *pn, LinkNode *ppNode)		//未理解
{
	LinkNode *pFast = NULL;
	LinkNode *pSlow = NULL;
	LinkNode *pTmpNode = NULL;
	int cnt = 1;

	pFast = pTmpList->pHead->pNext;
	pSlow = pTmpList->pHead->pNext;

	while (pFast != NULL)
	{
		pFast = pFast->pNext;
		if (NULL == pFast)
		{
			return 0;
		}
		pFast = pFast->pNext;
		if (NULL == pFast)
		{
			return 0;
		}

		pSlow = pSlow->pNext;
		if (pFast == pSlow)
		{

			pTmpNode = pSlow->pNext;
			while (pTmpNode != pSlow)
			{
				cnt++;
				pTmpNode = pTmpNode->pNext;
			}

			*pn = cnt;

			pFast = pTmpList->pHead->pNext;
			while (1)
			{
				pSlow = pSlow->pNext;
				pFast = pFast->pNext;

				if (pSlow == pFast)
				{
					*ppNode = pSlow;
					break;
				}
			}

			return 1;
		}
	}

	return 0;
}

总结

链表的优点：原则上只要系统的内存足够大，那么链表能够进行无限存储；而且存一个申请一个，不会提前占用空间，它是一种空间上不连续的存储方式；

本期的分享就到这里结束啦，总结一下，链表是必须掌握的一种数据结构，是闭着眼睛都要能写出来的一种数据结构，所以必须多练习，多思考；
最后，各位小伙伴们如果喜欢我的分享可以点赞收藏哦，你们的认可是我创作的动力，一起加油！文章来源地址https://www.toymoban.com/news/detail-787946.html

到了这里，关于数据结构中链表的实现以及排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！