使用C语言实现简单的通用的链表

177 0 0

作者:maiyat

在数据结构中，我们已经学习到了简单的静态链表以及单链表和双链表，它们各有优缺点，但是有个共同的问题是他们呢无法存储不同的数据。下面提供了一种方法，可以将不同节点的数据链接起来。

下面的代码都是基础的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);