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

数据结构与算法_C语言链表案例

程序员文章站 2024-03-23 10:02:34
...
#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

//设计链表节点
typedef struct __LINKNODE
{
	void*data;
	struct __LINKNODE*next;
}LinkNode;

//设计链表管理结构体  由于多了m_Size  可以更方便管理节点
typedef struct __LINKLIST
{
	LinkNode*pHeader;
	int m_Size;
}LinkList;

//初始化链表
//为 防止随意操作,将链表结构体指针做"隐身"
typedef void* LINKPTR;
 LINKPTR init_LinkList()
{
	 LinkList*p = malloc(sizeof(LinkList));
	 //初始化LinkList属性
	 p->pHeader = malloc(sizeof(LinkNode));
	 p->pHeader->data = NULL;
	 p->pHeader->next = NULL;
	 p->m_Size = 0;
	 return p;
}
 //插入数据
 void insert_LinkList(LINKPTR handle, void*data,int pos)
{
	 LinkList*p = handle;
	 if (p == NULL || data == NULL)
	 {
		 return;
	 }
	 if (pos<0||pos>p->m_Size)
	 {
		 //如果传入位置超出数组大小,或参数无效,则尾插
		 pos = p->m_Size;
	 }
	 LinkNode*pCurrent = p->pHeader;
	 for (int i = 0; i < pos ; i++)
	 {
		 pCurrent = pCurrent->next;
	 }
	 LinkNode*newNode = malloc(sizeof(LinkNode));
	 newNode->data = data;
	 newNode->next = pCurrent->next;
	 pCurrent->next = newNode;
	 p->m_Size++;
}
 //遍历链表
 void foreach_LinkList(LINKPTR handle,void(*callback)(void*))
 {
	 LinkList*p = handle;
	 if (p == NULL)
	 {
		 return;
	 }
	 LinkNode*pCurrent = p->pHeader->next;
	 for (int i = 0; i < p->m_Size;i++)
	 {
		 callback(pCurrent->data);
		 pCurrent = pCurrent->next;
	 }
 }

 //根据位置删除数据
 void del_ByPos_LinkList(LINKPTR handle,int pos)
 {
	 LinkList*p = handle;
	 if (p == NULL )
	 {
		 return;
	 }
	 LinkNode*pPrev = NULL;
	 LinkNode*pCur = p->pHeader;
	 if (pos>=p->m_Size||pos<0)
	 {
		 //如果传入参数无效,直接return
		 return;
	 }
	 for (int i = 0; i <= pos; i++)
	 {
		 pPrev = pCur;
		 pCur = pCur->next;
	 }
	 pPrev->next = pCur->next;
	 free(pCur);
	 pCur = NULL;
	 p->m_Size--;
 }
 //根据值删除节点
 void del_ByValue_LinkList(LINKPTR handle,void*data,int(*callback)(void*,void*))
 {
	 if (handle == NULL||data == NULL)
	 {
		 return;
	 }
	 LinkList*p = handle;
	 LinkNode*pCur = p->pHeader->next;
	 for (int i = 0; i < p->m_Size;i++)
	 {
		 if (callback(pCur->data,data))
		 {
			 del_ByPos_LinkList(p, i);
			 break;
		 }
		 pCur = pCur->next;
	 }
 }

 //返回链表长度
 int len_LinkList(LINKPTR handle)
 {
	 if (handle == NULL)
	 {
		 return;
	 }
	 LinkList*p = handle;
	 return p->m_Size;
 }

 //清空链表
 void destroy_LinkList(LINKPTR * handle)
 {
	 if (*handle == NULL)
	 {
		 return;
	 }
	 LinkList*p = *handle;
	 LinkNode*pCur = p->pHeader->next;
	 for (int i = 0 ; i < p->m_Size;i++)
	 {
		 LinkNode*next = pCur->next;
		 free(pCur);
		 pCur = next;
	 }
	 free(p->pHeader);
	 p->pHeader = NULL;
	 free(p);
	 *handle = NULL;
 }

 //------------------------------用户区------------------------------------//
 typedef struct __HERO
 {
	 char name[64];
	 int attack;
 }Hero;

 void print_Hero(void*data)
 {
	 Hero*p = (Hero*)data;
	 printf("%s\t%d\n", p->name, p->attack);
 }

 int cmp_Hero(void*data1, void*data2)
 {
	 Hero*h1 = (Hero*)data1;
	 Hero*h2 = (Hero*)data2;
	 return (strcmp(h1->name, h2->name) == 0);
 }

 void test()
 {
	 LINKPTR handle = init_LinkList();
	 Hero h1 = { "张飞",85 };
	 Hero h2 = { "赵云",95 };
	 Hero h3 = { "刘备",78 };
	 Hero h4 = { "关羽",93 };
	 Hero h5 = { "曹操",81 };
	 Hero h6 = { "孙权",72 };
	 Hero h[3] =
	 {
		 { "孙尚香",77 },
		 { "大乔",65 },
		 { "黄盖",85 }
	 };
	 for (int i = 0 ; i < 3; i++)
	 {
		 insert_LinkList(handle, h+i, 1);
	 }
	 insert_LinkList(handle, &h3, -1);
	 foreach_LinkList(handle, print_Hero);
	 printf("当前链表长度:%d\n", len_LinkList(handle));
	 printf("--------------------------\n");
	 del_ByPos_LinkList(handle, 1);
	 foreach_LinkList(handle, print_Hero);
	 printf("当前链表长度:%d\n", len_LinkList(handle));
	 printf("--------------------------\n");
	 del_ByValue_LinkList(handle, &h3, cmp_Hero);
	 foreach_LinkList(handle, print_Hero);
	 printf("当前链表长度:%d\n", len_LinkList(handle));
	 printf("--------------------------\n");
	 insert_LinkList(handle, &h3, -1);
	 insert_LinkList(handle, &h1, -1);
	 insert_LinkList(handle, &h2, -1);
	 foreach_LinkList(handle, print_Hero);
	 printf("当前链表长度:%d\n", len_LinkList(handle));
	 printf("--------------------------\n");
	 destroy_LinkList(&handle);
	 printf("清空链表后handle值为:%d\n", handle);
	 printf("--------------------------\n");
 }

int main()
{
	test();
	system("pause");
	return 0;
}