欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  网络运营

荐 04、STL中循环链表代码实现(用企业链表实现)

程序员文章站 2022-03-07 19:38:37
常用的容器包括vector, list, deque, queue, stack, map等,这些容器都是用基本的数据结构实现的。vector是用动态数组实现的;list是用双向循环链表实现的;deque有些特别,他是用一个个缓冲器组成的,把这些缓冲区的头指针放在数组中,使得使用者用迭代器+1就可以不停地遍历下一个元素,给使用者造成queue是顺序存储的假象,而这正是stl想要的,因为使用者不必去关心它复杂的实现过程;deque头尾都可插入弹出, queue, stack的实现是直接调用部分dequ......

    常用的容器包括vector, list, deque, queue, stack, map等,这些容器都是用基本的数据结构实现的。vector是用动态数组实现的;list是用双向循环链表实现的;deque有些特别,他是用一个个缓冲器组成的,把这些缓冲区的头指针放在数组中,使得使用者用迭代器+1就可以不停地遍历下一个元素,给使用者造成queue是顺序存储的假象,而这正是stl想要的,因为使用者不必去关心它复杂的实现过程;deque头尾都可插入弹出, queue, stack的实现是直接调用部分deque的接口,来完成各自的特性;map则是用红黑树来去实现的,是一种associate容器,它的查找速度相对于以上的sequence容器要快很多。

    数据结构和算法无疑是大学最枯燥的课程之一,相比于其他的不同,其他的枯燥可以不必认真学,因为这门课的重要性,使得它是一门味同嚼蜡且还要去嚼的课程。话说到这了,不好意思的是对于半路出家的我来说,大学并没学过,哈哈哈。。。。。可是我要自学啊,这。。。。。

    没的办法,想要练成《辟邪剑谱》,又不愿意自宫,哪有的事,男人要对自己狠一点(手动狗头)。。。。。。凡是要成为武学宗师必身怀些个威震江湖的神功,东邪的桃花影落飞神剑,碧海潮生按玉箫;西毒的蛤蟆功与逆行九阴真经 ;南帝的一阳指;北丐那至阳至刚的降龙十八掌与打狗棒法;中神通的先天功。如果已经学完了C,C++的基本语法(或看过《C++ Primer》),想要再精进一步,那就要该接触数组结构了。此外,若一门语言是一套剑的招式,数据结构更像是内功。不管学什么语言都用得到数组结构的基础。

    看到这,要点赞,你不点他不点,鄙人怎么找友仔玩,吃火锅KTV;你光说你不点,你不点,鄙人在深圳怎么找女朋友;你光说你不点,你不点,鄙人怎么搞定一套房,再见丈母娘。你光说你不点,今儿说破大天儿,也没这个理!

   看到这,我认为你已经看过鄙人的03、企业链表的代码实现,那么我们知道无论是单向链表还是企业链表(单向链表的另一种实现形式),每个节点不仅要存储用户放入的元素,还要放入下一个节点的地址,这样才能连接在一起,形成Sequence.这是单向链表,双向链表,顾名思义,就是每个节点存储下一个结点地址的同时,还存储上一个结点的地址。因此在插入结点做地址交接时也比单向链表多了两个步骤,具体见.c文件里插入接口的实现。其他无异。

    上代码,鄙人亲测有效!
CircleLinkList.h

#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//链表小结点
typedef struct LINKNODE
{
	struct LINKNODE* next;
}LinkNode;

//链表结点
typedef struct LINKLIST
{
	LinkNode head;
	int size;
}LinkList;
//遍历函数指针
typedef void(*PRINTNODE)(LinkNode*);
//比较的函数指针
typedef int(*COMPARENODE)(LinkNode*, LinkNode*);
//1.初始化链表
LinkList* Init_LinkList();

//2.插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data);

//3.删除,根据位置
void Remove_LinkList(LinkList* list, int pos);

//4.查找
int Find_LinkList(LinkList* list, LinkNode* data, COMPARENODE compare);

//5.返回链表大小
int Size_LinkList(LinkList* list);

//6.打印
void Print_LinkList(LinkList* list, PRINTNODE print);

//7.释放链表内存
void FreeSpace_LinkList(LinkList* list);

//8.获得第一个元素
LinkNode* Front_LinkList(LinkList* list);

//9.根据值删除
void RemoveByValue_LinkList(LinkList* list, LinkList* data, COMPARENODE compare);

//10.判断是否为空
int IsEmpty_LinkList(LinkList* list);


#endif

 

CircleLinkList.c

#include "CircleLinkList.h"



//1.初始化链表
LinkList* Init_LinkList()
{
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	//指向自身
	//头结点的空间在定义list时分配
	list->head.next = &(list->head);
	list->size = 0;
	return list;
}

//2.插入
void Insert_LinkList(LinkList* list, int pos, LinkNode* data)
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	if (pos < 0 || pos > list->size)
	{
		//友好判断   
		pos = list->size;
	}
	//相比链表,不用定义辅助结点接受参数值
	//直接将参数放入链表中
	//查找插入位置
	LinkNode* pCurrent = &(list->head);
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//插入新结点
	data->next = pCurrent->next;
	pCurrent->next = data;
	list->size++;
}


//3.删除
void Remove_LinkList(LinkList* list, int pos)
{
	if (list == NULL)
	{
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
		return;
	}
	//赋值指针变量
	LinkNode* pCurrent = &(list->head);
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}
	//删除结点
	pCurrent->next = pCurrent->next->next;
	list->size--;
}


//4.查找
int Find_LinkList(LinkList* list, LinkNode* data, COMPARENODE compare)
{
	if (list == NULL)
	{
		return -1;
	}
	if (data == NULL)
	{
		return -1;
	}
	//赋值指针变量
	LinkNode* pCurrent = list->head.next;
	int flag = -1;
	for (int i = 0; i < list->size; i++)
	{
		//比较函数返回0代表成功,-1代表失败
		if (compare(pCurrent, data) == 0)
		{
			flag = i;
			break;
		}
		pCurrent = pCurrent->next;
	}
	return flag;
}


//5.返回链表大小
int Size_LinkList(LinkList* list)
{
	return list->size;
}

//6.打印
void Print_LinkList(LinkList* list, PRINTNODE print)
{
	if (list == NULL)
	{
		return;
	}
	//辅助指针
	LinkNode* pCurrent = list->head.next;
	//打印2遍
	for (int i = 0; i < list->size * 2; i++)
	{
		//头结点不是用户malloc的空间
		//头结点的地址指向的空间不存在用户需要的数据
		//打印第一次遍历完需要跳过头结点
		if (pCurrent == &(list->head))
		{
			pCurrent = pCurrent->next;
			printf("------------打印完一遍-------------\n");
		}
		print(pCurrent);
		pCurrent = pCurrent->next;
	}
	return;
}

//7.释放链表内存
void FreeSpace_LinkList(LinkList* list)
{
	if (list == NULL)
	{
		return;
	}
	free(list);
}

//8.获得第一个元素
LinkNode* Front_LinkList(LinkList* list)
{
	if (list == NULL)
	{
		return NULL;
	}
	return list->head.next;
}

//9.根据值删除
void RemoveByValue_LinkList(LinkList* list, LinkList* data, COMPARENODE compare)
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	LinkNode* pPrev = &(list->head);
	LinkNode* pCurret = pPrev->next;
	int i = 0;
	//找到要删除结点的上一个结点
	for (i = 0; i < list->size; i++)
	{
		//判断A结点是否是要找的结点
		if (compare(pCurret, data) == 0)
		{
			//删除A几点,将A结点的上一个结点的next
			//指向A结点的下一个结点
			pPrev->next = pCurret->next;
			break;
		}
		//找到A结点前,先备份A结点的上一个结点
		pPrev = pCurret;
		pCurret = pPrev->next;
	}
}

//10.判断是否为空
int IsEmpty_LinkList(LinkList* list)
{
	if (list->size == 0)
	{
		return 1;
	}
	return 0;
}

 

循环链表.c(循环链表的使用)

#define _CRT_SECURE_NO_WARNINGS
#include "CircleLinkList.h"

typedef struct PERSON
{
	
	LinkNode node;
	char name[64];
	int age;
}Person;

void MyPrint(LinkNode* data)
{
	Person* p = (Person*)data;
	printf("Name: %s Age: %d\n", p->name, p->age);
}

int MyComPare(LinkNode* nodel, LinkNode* node2)
{
	Person* p1 = (Person*)nodel;
	Person* p2 = (Person*)node2;
	if (strcmp(p1->name, p2->name) == 0 && p1->age == p2->age)
	{
		return 0;
	}
	return -1;

}
int main(void)
{
	//创建链表
	LinkList* list = Init_LinkList();
	//创建数据
	Person p1, p2, p3, p4, p5;
	strcpy(p1.name, "aaa");
	strcpy(p2.name, "bbb");
	strcpy(p3.name, "ccc");
	strcpy(p4.name, "ddd");
	strcpy(p5.name, "eee");
	p1.age = 10;
	p2.age = 20;
	p3.age = 30;
	p4.age = 40;
	p5.age = 50;
	//将节点插入到链表
	//需要把p1,p2,p3等强转为LinkNode*后
	//才能在插入函数中,调用LinkNode的next成员
	Insert_LinkList(list, 0, (LinkNode*)&p1);
	Insert_LinkList(list, 0, (LinkNode*)&p2);
	Insert_LinkList(list, 0, (LinkNode*)&p3);
	Insert_LinkList(list, 0, (LinkNode*)&p4);
	Insert_LinkList(list, 0, (LinkNode*)&p5);
	//打印
	Print_LinkList(list, MyPrint);
	Person pDel;
	strcpy(pDel.name, "ccc");
	pDel.age = 30;
	//删除结点,根据值
	RemoveByValue_LinkList(list, (LinkList*)&pDel, MyComPare);
	printf("------------删除后-----------\n");
	//打印
	Print_LinkList(list, MyPrint);
	//删除结点,根据位置
	//Remove_LinkList(list, 2);
	//打印
	printf("------------\n");
	//Print_LinkList(list, MyPrint);
	////查找
	//Person findP;
	//strcpy(findP.name, "ccc");
	//findP.age = 30;
	//int pos = Find_LinkList(list, (LinkNode*)&findP, MyComPare);
	//printf("位置:%d\n", pos);
	//释放链表内存
	FreeSpace_LinkList(list);
	system("pause");
	return 0;
}

 

本文地址:https://blog.csdn.net/weixin_43466192/article/details/107251999