使用C语言实现简单的通用的链表
在数据结构中,我们已经学习到了简单的静态链表以及单链表和双链表,它们各有优缺点,但是有个共同的问题是他们呢无法存储不同的数据。下面提供了一种方法,可以将不同节点的数据链接起来。
下面的代码都是基础的C语言代码,涉及到的知识点基本覆盖到C语言学习的所有知识面,尤其是使用了宏,减少了重复的代码。
无论是C语言大佬还是C语言萌新,都可以食用此链表,理解起来可能很复杂,以下是源码,建议好好理解。
Main.c
#include "stdafx.h" #include"Teacher.h" #include "Student.h" #include"MainCmd.h" int main() { CALL_PROC(Main, MainCmd) return 0; }
Stdafx.h
#pragma once #include<iostream> using namespace std;
Teacher.h
#pragma once #include"List.h" #include"CmdMap.h" DECLEAR_PROC(Teacher) struct TEACHER { LINKER linker; char szName[20]; char szAddr[20]; int nAge; }; extern LINKER* g_pTeacher; LINKER* CreateTeacher(); void InputTeacher(LINKER* pLink); void OutputTeacher(const LINKER* pLink); LINKER* FindTeacher(LINKER* pHead); void CreateTeacherList(); void AddTeacher(); void DeleteTeacher(); void FindTeacherNode(); void InsertTeacher(); void ShowTeacherList(); void ClearTeacherList();
Teacher.cpp
#include"Teacher.h" #include"Student.h" #include"stdafx.h" #include"CmdFun.h" FUN_TABLE g_TeacherTable = { CreateTeacher,&InputTeacher,&OutputTeacher,&FindTeacher }; LINKER* CreateTeacher() { char szName[12] = ""; cout << "请输入创建的结点类型:(Student Or Teacher)"; cin >> szName; if (!strcmp(szName, "Student")) { STUDENT* pNew = new STUDENT; if (NULL != pNew) { pNew->linker.pFunTab = &g_StudentTable; pNew->linker.pNext = NULL; pNew->linker.pPrev = NULL; } return (LINKER*)pNew; } if (!strcmp(szName, "Teacher")) { TEACHER* pNew = new TEACHER; if (NULL != pNew) { pNew->linker.pFunTab = &g_TeacherTable; pNew->linker.pNext = NULL; pNew->linker.pPrev = NULL; } return (LINKER*)pNew; } return NULL; } void InputTeacher(LINKER* pLink) { TEACHER* pTemp = (TEACHER*)pLink; cout << "请输入姓名:"; cin >> pTemp->szName; cout << "请输入住址:"; cin >> pTemp->szAddr; cout << "请输入年龄:"; cin >> pTemp->nAge; } void OutputTeacher(const LINKER* pLink) { TEACHER* pTemp = (TEACHER*)pLink; cout << "***********************" << endl; cout << "姓名:" << pTemp->szName << endl; cout << "住址:" << pTemp->szAddr << endl; cout << "年龄:" << pTemp->nAge << endl; } LINKER* FindTeacher(LINKER* pHead) { TEACHER* pTemp = (TEACHER*)pHead; cout << "请输入要查找的姓名:"; char szBuf[20]; cin >> szBuf; while (NULL != pTemp->linker.pNext) { if (0 == strcmp(szBuf, pTemp->szName)) { return (LINKER*)pTemp; } pTemp = (TEACHER*)pTemp->linker.pNext; } return NULL; } CMD_MAP_BEGIN(Teacher) CMD(Create, 创建, CreateTeacherList) CMD(Add, 添加, AddTeacher) CMD(Delete, 删除, DeleteTeacher) CMD(Find, 查找, FindTeacherNode) CMD(Insert, 插入, InsertTeacher) CMD(Show, 创建, ShowTeacherList) CMD(Clear, 清空, ClearTeacherList) CMD(Back, 返回, NULL) CMD_MAP_END() LINKER* g_pTeacher = NULL; CmdFun(Teacher)
Student.h
#pragma once #include"List.h" #include"CmdMap.h" DECLEAR_PROC(Student) struct STUDENT { LINKER linker; char szID[20]; char chSex; int nGrade; }; struct STAFF { LINKER linker; char szID[20]; char chSex; int nGrade; }; LINKER* CreateStudent(); void InputStudent(LINKER* pLink); void OutputStudent(const LINKER* pLink); LINKER* FindStudent(LINKER* pHead); void CreateStudentList(); void AddStudent(); void DeleteStudent(); void FindStudentNode(); void InsertStudent(); void ShowStudentList(); void ClearStudentList();
Student.cpp
#include"Student.h" #include"Teacher.h" #include"stdafx.h" #include"CmdFun.h" FUN_TABLE g_StudentTable = { &CreateStudent,&InputStudent,&OutputStudent,&FindStudent }; LINKER* CreateStudent() { char szName[12] = ""; cout << "请输入创建的结点类型:(Student Or Teacher)"; cin >> szName; if (!strcmp(szName, "Student")) { STUDENT* pNew = new STUDENT; if (NULL != pNew) { pNew->linker.pFunTab = &g_StudentTable; pNew->linker.pNext = NULL; pNew->linker.pPrev = NULL; } return (LINKER*)pNew; } if (!strcmp(szName, "Teacher")) { TEACHER* pNew = new TEACHER; if (NULL != pNew) { pNew->linker.pFunTab = &g_TeacherTable; pNew->linker.pNext = NULL; pNew->linker.pPrev = NULL; } return (LINKER*)pNew; } return NULL; } void InputStudent(LINKER* pLink) { STUDENT* pTemp = (STUDENT*)pLink; cout << "请输入ID:"; cin >> pTemp->szID; cout << "请输入性别:"; cin >> pTemp->chSex; cout << "请输入分数:"; cin >> pTemp->nGrade; } void OutputStudent(const LINKER* pLink) { STUDENT* pTemp = (STUDENT*)pLink; cout << "***********************" << endl; cout << "ID:" << pTemp->szID << endl; cout << "性别:" << pTemp->chSex << endl; cout << "分数:" << pTemp->nGrade << endl; } LINKER* FindStudent(LINKER* pHead) { if (NULL == pHead) { return NULL; } STUDENT* pTemp = (STUDENT*)pHead; cout << "请输入要查找的ID:"; char szBuf[20]; cin >> szBuf; while (NULL != pTemp) { if (0 == strcmp(szBuf, pTemp->szID)) { return (LINKER*)pTemp; } pTemp = (STUDENT*)pTemp->linker.pNext; } return NULL; } CMD_MAP_BEGIN(Student) CMD(Create, 创建, CreateStudentList) CMD(Add, 添加, AddStudent) CMD(Delete, 删除, DeleteStudent) CMD(Find, 查找, FindStudentNode) CMD(Insert, 插入, InsertStudent) CMD(Show, 创建, ShowStudentList) CMD(Clear, 清空, ClearStudentList) CMD(Back, 返回, NULL) CMD_MAP_END() LINKER* g_pStudent = NULL; //CmdFun(Student)
void CreateStudentList() { switch (CreatList(&g_pStudent, CreateStudent)) { case ELIST_MEMORY_FAIL: cout << "动态内存分配失败" << endl; break; case ELIST_OK: cout << "创建链表成功" << endl; break; case ELIST_PARAM: cout << "传参不合理" << endl; break; case ELIST_CREATE_FAIL: cout << "链表已存在,创建链表失败" << endl; break; default: break; } } void AddStudent() { switch (Add(g_pStudent)) { case ELIST_MEMORY_FAIL: cout << "动态内存分配失败" << endl; break; case ELIST_OK: cout << "增加结点成功" << endl; break; case ELIST_NOTEXIST: cout << "链表不存在" << endl; break; default: break; } } void DeleteStudent() { LINKER* pNode = FindStudent(g_pStudent); switch (DeleteNode(&g_pStudent, pNode)) { case ELIST_OK: cout << "删除结点成功" << endl; break; case ELIST_PARAM: cout << "没有找到要删除的结点" << endl; break; case ELIST_NOTEXIST: cout << "链表不存在" << endl; break; default: break; } } void FindStudentNode() { LINKER* pNode = FindStudent(g_pStudent); if (NULL != pNode) { cout << "查找成功,该结点信息如下:" << endl; OutputStudent(pNode); } else { cout << "查找失败" << endl; } } void InsertStudent() { LINKER* pNode = FindStudent(g_pStudent); if (NULL == pNode) { cout << "没有找到要插入的位置" << endl; } int mode; cout << "输入1表示前插输入0表示后插:"; cin >> mode; switch (Insert(&g_pStudent, pNode, (MODE)mode)) { case ELIST_MEMORY_FAIL: cout << "动态内存分配失败" << endl; break; case ELIST_OK: cout << "插入成功" << endl; break; case ELIST_NOTFIND: cout << "没有找到要插入的位置,插入失败" << endl; break; case ELIST_PARAM: cout << "传入的参数有误" << endl; break; case ELIST_NOTEXIST: cout << "链表不存在,插入失败!" << endl; break; default: break; } } void ShowStudentList() { switch (ShowList(g_pStudent)) { case ELIST_PARAM: cout << "链表不存在" << endl; break; case ELIST_OK: cout << "链表已全部显示" << endl; break; default: break; } } void ClearStudentList() { switch (ClearList(&g_pStudent)) { case ELIST_PARAM: cout << "链表不存在" << endl; break; case ELIST_NOTEXIST: cout << "链表清空链表失败" << endl; break; case ELIST_OK: cout << "清空链表成功" << endl; break; default: break; } }
MainCmd.h
#pragma once #include"CmdMap.h" DECLEAR_PROC(Main);
MainCmd.cpp
#include"stdafx.h" #include"MainCmd.h" #include"Student.h" #include"Teacher.h" void Teacher(); void Student(); CMD_MAP_BEGIN(Main) CMD(Teacher, 老师, &Teacher) CMD(Student, 学生, &Student) CMD(Exit, 退出, NULL) CMD_MAP_END() void Teacher() { system("cls"); CALL_PROC(Teacher, Teacher); system("cls"); } void Student() { system("cls"); CALL_PROC(Student, Student); system("cls"); }
List.h
#pragma once #define ELIST_OK 1 #define ELIST_CREATE_FAIL -1 #define ELIST_MEMORY_FAIL -2 #define ELIST_NOTEXIST -3 #define ELIST_PARAM -4 #define ELIST_NOTFIND -5 struct LINKER; struct FUN_TABLE { LINKER* (*pfnCreateNode)(); void (*pfnInput)(LINKER* pNode); void (*pfnOutput)(const LINKER* pNode); LINKER* (*pfnFind)(LINKER* pHead); }; extern FUN_TABLE g_TeacherTable; extern FUN_TABLE g_StudentTable; struct LINKER { FUN_TABLE* pFunTab; LINKER* pNext; LINKER* pPrev; }; enum MODE { before = 1, after = 0 }; int CreatList(LINKER** ppHead, LINKER* (*pfnCreateNode)()); int Add(LINKER* pHead); int DeleteNode(LINKER** ppHead, LINKER* pNode); LINKER* FindNode(LINKER* pHead); int Insert(LINKER** ppHead, LINKER* pNode, MODE mode); int ShowList(LINKER* pHead); int ClearList(LINKER** ppHead);
List.cpp
#include "List.h" #include"stdafx.h" int CreatList(LINKER** ppHead, LINKER* (*pfnCreateNode)()) { if (NULL == ppHead) { return ELIST_PARAM; } if (NULL != *ppHead) { return ELIST_CREATE_FAIL; } LINKER* pNew = pfnCreateNode(); if (NULL == pNew) { return ELIST_MEMORY_FAIL; } pNew->pFunTab->pfnInput(pNew); *ppHead = pNew; return ELIST_OK; } int Add(LINKER* pHead) { if (NULL == pHead) { return ELIST_NOTEXIST; } while (NULL != pHead->pNext) { pHead = pHead->pNext; } LINKER* pNew = pHead->pFunTab->pfnCreateNode(); if (NULL == pNew) { return ELIST_MEMORY_FAIL; } pNew->pFunTab->pfnInput(pNew); pHead->pNext = pNew; pNew->pPrev = pHead; return ELIST_OK; } int DeleteNode(LINKER** ppHead, LINKER* pNode) { if (NULL == ppHead || NULL == pNode) { return ELIST_PARAM; } if (NULL == *ppHead) { return ELIST_NOTEXIST; } if (NULL == pNode->pPrev) { *ppHead = pNode->pNext; } else { pNode->pPrev->pNext = pNode->pNext; } if (NULL != pNode->pNext) { pNode->pNext->pPrev = pNode->pPrev; } delete pNode; pNode = NULL; return ELIST_OK; } LINKER* FindNode(LINKER* pHead) { if (NULL == pHead) { return NULL; } return pHead->pFunTab->pfnFind(pHead); } int Insert(LINKER** ppHead, LINKER* pNode, MODE mode) { if (NULL == ppHead) { return ELIST_PARAM; } if (NULL == *ppHead) { return ELIST_NOTEXIST; } if (NULL == pNode) { return ELIST_NOTFIND; } LINKER* pNew = (*ppHead)->pFunTab->pfnCreateNode(); if (NULL == pNew) { return ELIST_MEMORY_FAIL; } pNew->pFunTab->pfnInput(pNew); if (1 == mode) { if (NULL == pNode->pPrev) { *ppHead = pNew; } else { pNode->pPrev->pNext = pNew; } pNew->pPrev = pNode->pPrev; pNew->pNext = pNode; pNode->pPrev = pNew; } else if (0 == mode) { if (NULL != pNode->pNext) { pNode->pNext->pPrev = pNew; } pNew->pNext = pNode->pNext; pNew->pPrev = pNode; pNode->pNext = pNew; } else { return ELIST_PARAM; } return ELIST_OK; } int ClearList(LINKER** ppHead) { if (NULL == ppHead) { return ELIST_PARAM; } if (NULL == *ppHead) { return ELIST_NOTEXIST; } LINKER* pTemp = *ppHead; while (NULL != pTemp) { *ppHead = pTemp->pNext; delete pTemp; pTemp = *ppHead; } return ELIST_OK; } int ShowList(LINKER* pHead) { if (NULL == pHead) { return ELIST_PARAM; } while (NULL != pHead) { pHead->pFunTab->pfnOutput(pHead); pHead = pHead->pNext; } cout << endl; return ELIST_OK; }
CmdFun.h
#pragma once #pragma once #include"stdafx.h" #include"List.h" #define CmdFun(name)\ void Create##name##List()\ {\ switch (CreatList(&g_p##name, Create##name))\ {\ case ELIST_MEMORY_FAIL:\ cout << "动态内存分配失败" << endl;\ break;\ case ELIST_OK:\ cout << "创建链表成功" << endl;\ break;\ case ELIST_PARAM:\ cout << "传参不合理" << endl;\ break;\ case ELIST_CREATE_FAIL:\ cout << "链表已存在,创建链表失败" << endl;\ break;\ default:\ break;\ }\ }\ void Add##name()\ {\ switch (Add(g_p##name))\ {\ case ELIST_MEMORY_FAIL:\ cout << "动态内存分配失败" << endl;\ break;\ case ELIST_OK:\ cout << "增加结点成功" << endl;\ break;\ case ELIST_NOTEXIST:\ cout << "链表不存在" << endl;\ break;\ default:\ break;\ }\ }\ \ void Delete##name()\ {\ LINKER* pNode = Find##name(g_p##name);\ \ switch (DeleteNode(&g_p##name, pNode))\ {\ case ELIST_OK:\ cout << "删除结点成功" << endl;\ break;\ case ELIST_PARAM:\ cout << "没有找到要删除的结点" << endl;\ break;\ case ELIST_NOTEXIST:\ cout << "链表不存在" << endl;\ break;\ default:\ break;\ }\ }\ \ void Find##name##Node()\ {\ LINKER* pNode = Find##name(g_p##name);\ if (NULL != pNode)\ {\ cout << "查找成功,该结点信息如下:" << endl;\ Output##name(pNode);\ }\ else\ {\ cout << "查找失败" << endl;\ }\ }\ \ void Insert##name()\ {\ LINKER* pNode = Find##name(g_p##name);\ if (NULL == pNode)\ {\ cout << "没有找到要插入的位置" << endl;\ }\ \ int mode;\ cout << "输入1表示前插输入0表示后插:";\ cin >> mode;\ \ switch (Insert(&g_p##name, pNode, (MODE)mode))\ {\ case ELIST_MEMORY_FAIL:\ cout << "动态内存分配失败" << endl;\ break;\ case ELIST_OK:\ cout << "插入成功" << endl;\ break;\ case ELIST_NOTFIND:\ cout << "没有找到要插入的位置,插入失败" << endl;\ break;\ case ELIST_PARAM:\ cout << "传入的参数有误" << endl;\ break;\ case ELIST_NOTEXIST:\ cout << "链表不存在,插入失败!" << endl;\ break;\ default:\ break;\ }\ }\ \ void Show##name##List()\ {\ switch (ShowList(g_p##name))\ {\ case ELIST_PARAM:\ cout << "链表不存在" << endl;\ break;\ case ELIST_OK:\ cout << "链表已全部显示" << endl;\ break;\ default:\ break;\ }\ }\ \ void Clear##name##List()\ {\ switch (ClearList(&g_p##name))\ {\ case ELIST_PARAM:\ cout << "链表不存在" << endl;\ break;\ case ELIST_NOTEXIST:\ cout << "链表清空链表失败" << endl;\ break;\ case ELIST_OK:\ cout << "清空链表成功" << endl;\ break;\ default:\ break;\ }\ }
CmdMap.h
#pragma once #include"stdafx.h" struct CMD_MAP { const char* pStrName; const char* pStrInfo; void (*pfn)(); }; #define CMD_MAP_BEGIN(name)\ void name##Proc(const char *pStrApp)\ {\ CMD_MAP *pCmdMap = NULL;\ char szCmd[256] = "";\ while(true)\ {\ pCmdMap = GET_CMD_MAP(name);\ cout << pStrApp << ">";\ cin >> szCmd;\ \ while(NULL != pCmdMap->pStrName)\ {\ if(0 == strcmp(pCmdMap->pStrName,szCmd))\ {\ if(NULL != pCmdMap->pfn)\ {\ pCmdMap->pfn();\ }\ break;\ }\ pCmdMap++;\ }\ if (NULL == pCmdMap->pStrName)\ {\ cout << "您输入的命令有误!" << endl;\ }\ else\ {\ if(NULL == pCmdMap->pfn)\ {\ break;\ }\ }\ }\ }\ CMD_MAP g_##name[] = { #define CMD(name,info,fn)\ {#name,#info,fn}, #define CMD_MAP_END()\ {NULL,NULL,NULL}}; #define GET_CMD_MAP(name) g_##name #define DECLEAR_PROC(name)\ void name##Proc(const char *pStrApp);\ extern CMD_MAP g_##name[]; #define CALL_PROC(name,app_name) name##Proc(#app_name);
运行结果:
创建通用型链表 增加节点:
显示增加的节点: