欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

数据结构--单链表的基本功能实现

程序员文章站 2024-01-15 16:47:40
...

链表实现下面功能

//初始化链表
void InitLinkList(pList* pplist);
//销毁链表
void DestroyLinkList(pList* pplist);
//销毁节点
void Destroy(pList* pplist);
//打印
void PrintList(pList plist);
//尾插
void PushBack(pList* pplist, DataType d);
//尾删
void PopBack(pList* pplist);
//头插
void PushFront(pList* pplist, DataType d);
//头删
void PopFront(pList* pplist);
//查找
pNode Find(pList plist, DataType d);
//指定位置插入
void Insert(pList* pplist, pNode pos, DataType d);
//指定位置删除
void Erase(pList* pplist, pNode pos);
//删除指定元素
void Remove(pList* pplist, DataType d);
//删除所有指定元素
void RemoveAll(pList* pplist, DataType d);
//删除无头单链表的非尾节点（不能遍历链表）
void EraseNotTailNode(pNode pos);
//链表长度
int GetListLength(pList plist);
//递归方法从尾到头打印
void PrintTailToHeadRec(pList plist);
//非递归从尾到头打印
void PrintTailToHead(pList plist);
//在无头单链表的一个节点前插入一个节点（不能遍历链表）
void InsertNotTailNode(pNode pos, int num);
//单链表实现约瑟夫环
pNode JosephCircle(pList* pplist, int num);
//逆置反转单链表
void TailToHeadListWayOne(pList* pplist);
void TailToHeadListWayTwo(pList* pplist);

 

Linklist.h  头文件

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <windows.h>

//定义元素类型
typedef int DataType;	

//链表的定义
typedef struct Node
{
	DataType data;			//存放数据
	struct Node* next;		//定义一个struct Node类型的指针记录下一个节点的地址
}Node,*pNode,List,*pList;

//初始化链表
void InitLinkList(pList* pplist);
//销毁链表
void DestroyLinkList(pList* pplist);
//销毁节点
void Destroy(pList* pplist);
//打印
void PrintList(pList plist);
//尾插
void PushBack(pList* pplist, DataType d);
//尾删
void PopBack(pList* pplist);
//头插
void PushFront(pList* pplist, DataType d);
//头删
void PopFront(pList* pplist);
//查找
pNode Find(pList plist, DataType d);
//指定位置插入
void Insert(pList* pplist, pNode pos, DataType d);
//指定位置删除
void Erase(pList* pplist, pNode pos);
//删除指定元素
void Remove(pList* pplist, DataType d);
//删除所有指定元素
void RemoveAll(pList* pplist, DataType d);
//删除无头单链表的非尾节点（不能遍历链表）
void EraseNotTailNode(pNode pos);
//链表长度
int GetListLength(pList plist);
//递归方法从尾到头打印
void PrintTailToHeadRec(pList plist);
//非递归从尾到头打印
void PrintTailToHead(pList plist);
//在无头单链表的一个节点前插入一个节点（不能遍历链表）
void InsertNotTailNode(pNode pos, int num);
//单链表实现约瑟夫环
pNode JosephCircle(pList* pplist, int num);
//逆置反转单链表
void TailToHeadListWayOne(pList* pplist);
void TailToHeadListWayTwo(pList* pplist);

#endif __LINKLIST_H__

Linllist.c 文件

#include "Linklist.h"

//链表的初始化
void InitLinkList(pList* pplist)
{
	*pplist = NULL;
}
//申请节点
pNode BuyNode(DataType d)
{
	pNode L = (Node *)malloc(sizeof(Node));
	if (L == NULL)
	{
		perror("Buy Node");
		exit(FILENAME_MAX);
	}
	L->data = d;
	L->next = NULL;
	return L;
}
//销毁节点
void Destroy(pList* pplist)
{
	pNode del = NULL;
	assert(pplist);
	del = *pplist;
	*pplist = (*pplist)->next;
	free(del);
	del = NULL;
}
//销毁链表
void DestroyLinkList(pList*  pplist)
{
	pNode del = NULL;
	assert(pplist);
	while (*pplist)
	{
		del = *pplist;
		*pplist = (*pplist)->next;
		free(del);
		del = NULL;
	}
}
//尾插
void PushBack(pList* pplist, DataType d)
{
	pNode p;
	assert(pplist);
	p = *pplist;
	//当链表为空，不需要遍历链表，需特殊处理
	if (p == NULL)
	{
		*(pplist) = BuyNode(d);
	}
	else
	{
		//遍历链表，找到尾节点
		while (p->next != NULL)
		{
			p = p->next;
		}
		p->next = BuyNode(d);
	}
}
//尾删
void PopBack(pList* pplist)
{
	pNode ret = NULL;
	pNode del = *pplist;
	assert(pplist);
	assert(*pplist);
	//当链表只有一个非空节点时，直接删除
	if (del->next == NULL)
	{
		Destroy(&del);
		*pplist = NULL;
		return;
	}
	//遍历链表，找到尾节点
	while (del->next != NULL)
	{
		ret = del;
		del = del->next;
	}
	ret->next = NULL;
	Destroy(&del);
}
//头插
void PushFront(pList* pplist, DataType d)
{
	pNode newNode;
	assert(pplist);
	newNode = BuyNode(d);
	newNode->next = *pplist;
	*pplist = newNode;
}
//头删
void PopFront(pList* pplist)
{
	pNode del = NULL;
	assert(pplist);
	assert(*pplist);  //链表非空
	del = *pplist;
	*pplist = del->next;
	Destroy(&del);
}
//查找
pNode Find(pList plist, DataType d)
{
	assert(plist);
	while (plist)
	{
		if (plist->data == d)
		{
			return plist;
		}
		plist = plist->next;
	}
	return NULL;
}
//指定位置插入
void Insert(pList* pplist, pNode pos, DataType d)
{
	pNode newNode = NULL;
	pNode ret = NULL;
	assert(pplist);
	ret = *pplist;
	newNode = BuyNode(d);
	//当插入位置为头结点时，则头插
	if (pos == *pplist)
	{
		newNode->next = *pplist;
		*pplist = newNode;
		return;
	}
	//查找pos的上一个节点
	while (ret && (ret->next != pos))
	{
		ret = ret->next;
	}
	//找不到直接返回
	if (ret == NULL)
	{
		return;
	}
	//插入
	else
	{
		newNode->next = pos;
		ret->next = newNode;
	}
}
//指定位置删除
void Erase(pList* pplist, pNode pos)
{
	pNode ret = *pplist;
	pNode del = *pplist;
	assert(pplist);
	assert(pos);
	assert(*pplist);
	if (pos == *pplist)
	{
		*pplist = (*pplist)->next;
		Destroy(&del);
		return;
	}
	//ret记录被删除节点的上一个节点位置
	while (del != pos)
	{
		ret = del;
		del = del->next;
	}
	ret->next = del->next;
	Destroy(&del);
}
//删除指定元素
void Remove(pList* pplist, DataType d)
{
	pNode ret = NULL;
	pNode del = NULL;
	pNode newNode = NULL;
	assert(pplist);
	assert(*pplist);
	ret = *pplist;
	del = *pplist;
	//调用查找函数，查找要删除元素的节点地址
	newNode = Find(*pplist, d);
	if (newNode == NULL)
	{
		printf("删除元素不存在！\n");
		return;
	}
	else
	{
		//头删
		if (ret == newNode)
		{
			del = *pplist;
			*pplist = (*pplist)->next;
			Destroy(&del);
			return;
		}
		while (ret->next != newNode)
		{
			ret = ret->next;
		}
		    del = ret->next;
			ret->next = del->next;
			Destroy(&del);
	}
}
//删除所有指定元素
void RemoveAll(pList* pplist, DataType d)
{
	pNode ret = NULL;
	pNode del = NULL;
	pNode newNode = NULL;
	assert(pplist);
	assert(*pplist);
	ret = *pplist;
	del = *pplist;
	while (ret)
	{
		newNode = Find(*pplist, d);
		if (newNode == NULL)
		{
			return;
		}
		else
		{
			if (ret == newNode)
			{
				del = *pplist;
				*pplist = (*pplist)->next;
				Destroy(&del);
				ret = *pplist;  //更新ret
			}
			else
			{
				while (ret->next != newNode)
				{
					ret = ret->next;
				}
				del = ret->next;
				ret->next = del->next;
				Destroy(&del);
			}
		}
	}
}
//删除无头单链表的非尾节点（不能遍历链表
//思想：相当与将被删节点的下一个节点的数据存放在被删节点中，然后删除被删节点的下一个节点即可
void EraseNotTailNode(pNode pos)
{
	pNode del = NULL;
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}	
	del = pos->next;
	pos->data = del->data;
	pos->next = del->next;
	Destroy(&del);
}
//链表长度
int GetListLength(pList plist)
{
	int count = 0;
	if (plist == NULL)
	{
		return 0;
	}
	else
	{
		while (plist)
		{
			count++;
			plist = plist->next;
		}
		return count;
	}
}
//递归方法从尾到头打印
void PrintTailToHeadRec(pList plist)
{
	if (plist == NULL)
	{
		return;
	}
	else
	{
		PrintTailToHead(plist->next);
	}
	printf("%d->", plist->data);
}
//非递归方法从尾到头打印
void PrintTailToHead(pList plist)
{
	pNode tail = NULL;
	pNode cur = NULL;
	if (plist == NULL)
        {
            return NULL;
        }
	while (plist != tail)
	{
		cur = plist;
		while (cur->next != tail)
		{
			cur = cur->next;
		}
		//不断更新tail，直到tail == plist
		tail = cur;
		printf("%d->", tail->data);
	}
}
//在无头单链表的一个节点前插入一个节点（不能遍历链表）
//思想：将要插入节点的数据和pos进行交换，然后插入pos后面即可
void InsertNotTailNode(pNode pos, DataType d)
{
	pNode newNode = BuyNode(pos->data);
	assert(pos);
	pos->data = d;
	newNode->next = pos->next;
	pos->next = newNode;
}

约瑟夫环：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

举例：约瑟夫环（约瑟夫问题）是一个非常经典的数学的应用问题：简化来说就是已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。开始从编号为k的人报数，数到数字为m的那个人出列；继续，他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列！

关于约瑟夫： Josephus有过的故事：39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

数据结构--单链表的基本功能实现

 

//单链表实现约瑟夫环
pNode JosephCircle(pList* pplist, int count)
{
	//pre记录被删节点的上一个节点
	pNode pre = NULL;
	//cur记录被删节点
	pNode cur = NULL;
	int ret = 0;
	assert(pplist);
    cur = *pplist;
	while ((*pplist)->next != *pplist)
	{	
		ret = count;
		while (--ret)
		{
			pre = cur;
			cur = cur->next;
		}
		pre->next = cur->next;
		Destroy(&cur);
		cur = pre->next;
	}
	return cur;
}

逆置翻转单链表：

方法一：用三个指针分别为first，second，third分别记录要插入的位置，要插入的节点，要插入节点的下一个节点，用头插将2插在1的前面，然改变first，second，third，继续重复上述操作，直到second指向NULL时结束，再将*pplist = first，逆置结束。

图解：

 

 

 

代码：数据结构--单链表的基本功能实现

//逆置反转单链表
void TailToHeadListWayOne(pList* pplist)
{
	pNode first = NULL;
	pNode second = NULL;
	pNode third = NULL;
	assert(pplist);
	assert(*pplist);
	if ((*pplist)->next == NULL)
	{
		return;
	}
	first = *pplist;
	second = first->next;
	third = second->next;
	while (second)
	{
		if (first == *pplist)
		{
			first->next = NULL;
		}
		second->next = first;
		first = second;
		second = third;
		if (third != NULL)
		{
			third = third->next;
		}
	}
	*pplist = first;
}

方法二：相当于创建一个新的链表, 创建一个空指针head，head=NULL, 再用一个cur指针指向*pplist，tmp指针指向cur->next；先将cur->next = head，然后更新head = cur，cur = tmp，当tmp不为空时 tmp = tmp->next，直到cur为空时循环结束后再更新*pplist,  即 : *pplist = head；

代码：

void TailToHeadListWayTwo(pList* pplist)
{
	pNode head = NULL;
	pNode cur = NULL;
	pNode tmp = NULL;
	assert(pplist);
	assert(*pplist);
	if ((*pplist)->next == NULL)
	{
		return;
	}
	cur = *pplist;
	tmp = cur->next;
	while (cur)
	{
		cur->next = head;
		head = cur;
		cur = tmp;
		if (tmp != NULL)
		{
			tmp = tmp->next;
		}
	}
	*pplist = head;
}

test.c 测试文件
 

#include "Linklist.h"

void testPushBack()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);
	PopBack(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testPushfront()
{
	pList plist;
	InitLinkList(&plist);
	PushFront(&plist, 1);
	PushFront(&plist, 2);
	PushFront(&plist, 3);
	PushFront(&plist, 4);
	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);
	PopFront(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testInsert()
{
	pNode pos = NULL;
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	pos = Find(plist, 4);
	if (pos != NULL)
	{
		Insert(&plist, pos, 5);
	}
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testErase()
{
	pNode pos = NULL;
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	pos = Find(plist, 2);
	if (pos != NULL)
	{
		Erase(&plist, pos);
	}
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testRemove()
{
	int length = 0;
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 2);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 2);
	RemoveAll(&plist, 2);
	length = GetListLength(plist);
	printf("单链表长度为：%d\n", length);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testEraseNotTailNode()
{
	pList plist;
	pNode newNode = NULL;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	newNode = Find(plist, 3);
	EraseNotTailNode(newNode);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testPrintTailToHeadRec()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	PrintTailToHeadRec(plist);
}
void testPrintTailToHead()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	PrintTailToHead(plist);
}
void testInsertNotTailNode()
{
	pList plist;
	pNode newNode = NULL;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	newNode = Find(plist, 3);
	InsertNotTailNode(newNode, 6);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testJosephCircle()
{
	pList plist;
	pNode head = NULL;
	pNode tail = NULL;
	pNode newNode = NULL;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	head = plist;
	tail = plist;
	while (tail->next && tail)
	{
		tail = tail->next;
	}
	//head = pHead(plist);
	//tail = pTail(plist);
	tail->next = head;
	newNode = JosephCircle(&plist, 3);
	printf("剩余的数字为：%d\n", newNode->data);
	free(plist);
	plist = NULL;
}
void testTailToHeadListWayOne()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	TailToHeadListWayOne(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
void testTailToHeadListWayTwo()
{
	pList plist;
	InitLinkList(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	TailToHeadListWayTwo(&plist);
	PrintList(plist);
	DestroyLinkList(&plist);
}
int main()
{
//     testPushBack();
//     testPushfront();
//     testInsert();
//     testErase();
//     testRemove();
//     testEraseNotTailNode();
//     testPrintTailToHead();
//     testPrintTailToHead();
//     testInsertNotTailNode();
//     testJosephCircle();
//     testTailToHeadListWayOne();
//     testTailToHeadListWayTwo();
       system("pause");
    return 0;
}

 





 

 

 

相关标签： 单链表 约瑟夫环 逆置反转

上一篇： Smarty 封装 YII2 Form表单API - 开关 Switch

下一篇：

推荐阅读