600字范文 > 数据结构与算法：单链表（利用万能指针实现对任意类型数据进行操作）

数据结构与算法：单链表（利用万能指针实现对任意类型数据进行操作）

时间：2020-02-01 02:53:25

前言

C语言的指针真的很强大，万能指针更强大，可以指向任意类型的数据。在上篇博客数据结构与算法：单链表（超详细实现）中用C语言实现了单链表的相关算法，不过却有局限性只能针对某一种数据类型还是不够强大。C语言中没有C++中的模板那如何来实现类似模板的效果呢？可以针对任意类型数据的单链表呢？在C语言中就有这么一种类型可以指向任意数据类型的指针，它就是万能指针 void* ，就是它，可以利用它实现类似模板的效果！我们在链表中不维护数据，我们只维护数据的地址，那么我们的void* 就可保存任意类型的地址！

实现算法预览

LinkList.h

#pragma once#ifndef __LINKLIST_H__#define __LINKLIST_H__typedef struct LinkNode LinkNode;struct LinkNode{void* data;//维护用户提供的数据LinkNode* next;};typedef struct LINKLIST{LinkNode *pHeader;int m_size;}LINKLIST;typedef void* LinkList;//对外提供void*防止用户看到不该看到的东西，避免用户乱修改//初始化单链表LinkList Init_LinkList();//根据位置插入元素//pos 位置范围为1 ~ list->size 更符合人类的叫法int InsertByIndex_LinkList(void* list, int pos, void* data);//插入元素根据元素值int InsertByValue_LinkList(void* list, void* search,void* data,int(*compareFunction)(void* data1, void* data2));//删除元素根据位置int RemoveByIndex_LinkList(void* list, int pos);//删除元素根据值int RemoveByValue_LinkList(void * list, void * data, int(*compareFunction)(void* data1, void* data2));//清空链表int Clear_LinkList(void* list);//销毁链表int Destroy_LinkList(void* list);//获取链表元素个数int Length_LinkList(void* list);//遍历链表int Foreach_LinkList(void* list, void(*foreachFunction)(void* data));//翻转链表int Reverse_LinkList(void* list);#endif // !__LINKLIST_H__

实现代码展示

LinkList.c

#define _CRT_SECURE_NO_WARNINGS#include <stdlib.h>#include "LinkList.h"LinkList Init_LinkList(){LINKLIST* list = (LINKLIST*)malloc(sizeof(LINKLIST));list->pHeader = (LinkNode*)malloc(sizeof(LinkNode));list->pHeader->data = NULL;list->pHeader->next = NULL;list->m_size = 0;return list;}//根据位置插入元素//pos 位置范围为1 ~ list->size int InsertByIndex_LinkList(void* list, int pos, void* data){LINKLIST* linkList = (LINKLIST*)list;//非法情况if (NULL == list || NULL == data){return 0;}//位置非法进行尾插if (pos<1 || pos>=linkList->m_size + 1){pos = linkList->m_size + 1;}LinkNode* pre = linkList->pHeader;//找到第pos位置前面一个元素for (int i = 1; i < pos; i++){pre = pre->next;}//创建结点LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));newNode->data = data;newNode->next = pre->next;pre->next = newNode;linkList->m_size++;return 1;}int InsertByValue_LinkList(void* list, void* search,void* data, int(*compareFunction)(void* data1, void* data2)){if (NULL == list || NULL == search || data == NULL || NULL == compareFunction){return 0;}LINKLIST* linkList = (LINKLIST*)list;LinkNode* pre = linkList->pHeader;LinkNode* cur = linkList->pHeader->next;LinkNode* insertPre = NULL;for (int i = 0; i < linkList->m_size; i++){if (compareFunction(cur->data, search)){insertPre = pre;break;}pre = cur;cur = cur->next;}//如果没有找到要插入的位置将其插在尾结点LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));newNode->data = data;newNode->next = cur;pre->next = newNode;linkList->m_size++;return 1;}int RemoveByIndex_LinkList(void * list, int pos){if (NULL == list){return 0;}LINKLIST* linkList = (LINKLIST*)list;//位置非法返回if (pos > linkList->m_size || pos < 1){return 0;}LinkNode* cur = linkList->pHeader;//找到删除元素的前驱结点for (int i = 1; i < pos; i++){cur = cur->next;}//缓存待删除结点LinkNode* del = cur->next;//前驱结点指向删除结点后继结点cur->next = del->next;//删除结点free(del);linkList->m_size--;return 1;}int RemoveByValue_LinkList(void * list, void * data,int (*compareFunction)(void* data1,void* data2)){if (NULL == list || NULL == data || NULL == compareFunction){return 0;}LINKLIST* linkList = (LINKLIST*)list;LinkNode* pre = linkList->pHeader;LinkNode* cur = linkList->pHeader->next;LinkNode* delPre = NULL;for (int i = 0; i < linkList->m_size; i++){if (compareFunction(cur->data,data)){delPre = pre;break;}pre = cur;cur = cur->next;}if (NULL != delPre && NULL != cur){//删除元素前驱结点指向删除元素的后继结点delPre->next = cur->next;//删除结点free(cur);cur = NULL;}linkList->m_size--;return 1;}int Clear_LinkList(void * list){if (NULL == list){return 0;}LINKLIST *linkList = (LINKLIST*)list;LinkNode* cur = linkList->pHeader->next;for (int i = 0; i < linkList->m_size; i++){LinkNode* next = cur->next;free(cur);cur = next;}linkList->m_size = 0;return 1;}int Destroy_LinkList(void * list){if (NULL == list){return 0;}LINKLIST* linkList = (LINKLIST*)list;Clear_LinkList(linkList);free(linkList->pHeader);linkList->pHeader = NULL;return 1;}int Length_LinkList(void * list){if (NULL == list){return -1;}LINKLIST* linkList = (LINKLIST*)list;return linkList->m_size;}int Foreach_LinkList(void* list, void(*foreachFunction)(void* data)){if (NULL == list || NULL == foreachFunction){return 0;}LINKLIST* linkList = (LINKLIST*)list;LinkNode* cur = linkList->pHeader->next;for (int i = 0; i < linkList->m_size; i++){foreachFunction(cur->data);cur = cur->next;}return 1;}int Reverse_LinkList(void * list){if (NULL == list){return 0;}LINKLIST* linkList = (LINKLIST*)list;LinkNode* pre = NULL;LinkNode* cur = linkList->pHeader->next;LinkNode* next = NULL;while (cur!=NULL){//记录下一个结点next = cur->next;//当前结点指向前驱结点cur->next = pre;//cur pre 往后移动pre = cur;cur = next;}//将头结点指向最后一个结点实现翻转linkList->pHeader->next = pre;return 1;}

Main.c

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>#include <string.h>#include "LinkList.h"//使用结构体数据类型测试万能单链表typedef struct Hero{char name[64];int age;}Hero;int Compare_Hero(void* hero1, void* hero2){Hero* h1 = (Hero*)hero1;Hero* h2 = (Hero*)hero2;return h1->age == h2->age && strcmp(h1->name, h2->name) == 0;}void Print_Hero(Hero* hero){if (NULL == hero){return;}printf("name:%s,age:%d\n", hero->name, hero->age);return;}int main(int argc, char *argv[]){Hero h1 = { "关羽",38 };Hero h2 = { "张飞",39 };Hero h3 = { "赵云",29 };Hero h4 = { "许褚",19 };Hero h5 = { "鲁肃",25 };Hero h6 = { "周瑜",27 };Hero h7 = { "太史慈",40 };LinkList list = Init_LinkList();//根据位置进行插入InsertByIndex_LinkList(list, 1, &h1);InsertByIndex_LinkList(list, 100, &h2);InsertByIndex_LinkList(list, 1, &h3);InsertByIndex_LinkList(list, 2, &h4);InsertByIndex_LinkList(list, 3, &h5);InsertByIndex_LinkList(list, 1, &h6);//根据值进行插入InsertByValue_LinkList(list, &h5, &h7, Compare_Hero);//将太史慈插入到鲁肃之前printf("元素个数:%d\n", Length_LinkList(list));//正确顺序周瑜赵云许褚太史慈鲁肃关羽张飞 Foreach_LinkList(list, Print_Hero);//删除第一个元素周瑜RemoveByIndex_LinkList(list, 1);//删除位置非法RemoveByIndex_LinkList(list, 100);//根据值进行删除Hero hero = { "许褚",19 };RemoveByValue_LinkList(list, &hero,Compare_Hero);printf("元素个数:%d\n", Length_LinkList(list));//正确顺序赵云太史慈鲁肃关羽张飞 Foreach_LinkList(list, Print_Hero);printf("翻转后:\n");//翻转Reverse_LinkList(list);Foreach_LinkList(list, Print_Hero);//清空链表Clear_LinkList(list);printf("清空链表后，元素个数:%d\n", Length_LinkList(list));//销毁链表Destroy_LinkList(list);return 0;}

运行结果检测

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。