技术教程 编程教程 数据结构 传统链表实现与Linux内核链表 正文

数据结构 传统链表实现与Linux内核链表

2023-02-13,,,,

头文件：

#pragma once

#include<stdlib.h>

//链表结点

struct LinkNode{

    void *data;

    struct LinkNode *next;

};

//链表

struct _Linklist{

    struct LinkNode header;

    int size; //链表结点的数目

};

typedef void *LinkList;

#ifdef __cplusplus

extern "C" {

#endif

    //初始化链表

    LinkList Init_LinkList();

    //指定位置插入

    int InsertByPos_LinkList(LinkList list, int pos, void *data);

    //头插

    int PushFront_LinkList(LinkList list, void *data);

    //尾插

    int PushBack_LinkList(LinkList list, void *data);

    //在指定值的前面插入

    int InsertByVal_LinkList(LinkList list, void *oldval, void *newval, int(*isequal)(void*,void*));

    //指定位置删除

    int RemoveByPos_LinkList(LinkList list, int pos);

    //根据值删除

    int RemoveByVal_LinkList(LinkList list, void *data, int(*compare)(void *, void *));

    //头删

    void PopFront_LinkList(LinkList list);

    //尾删

    void PopBack_LinkList(LinkList list);

    //遍历

    void Foreach_LinkList(LinkList list, void(*foreach)(void *));

    //销毁

    void Destroy_LinkList(LinkList list);

#ifdef __cplusplus

}

#endif

头文件实现：

#include"LinkList.h"

//初始化链表

LinkList Init_LinkList(){

    struct _Linklist *list = malloc(sizeof(struct _Linklist));

    if (NULL == list){

        return NULL;

    }

    list->header.data = NULL;

    list->header.next = NULL;

    list->size = 0;

    return list;

}

//指定位置插入 0代表插入到第一个位置

int InsertByPos_LinkList(LinkList list, int pos, void *data){

    if (NULL == list){

        return -1;

    }

    if (NULL == data){

        return -2;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    if (pos < 0 || pos > llist->size){

        pos = llist->size;

    }

    //辅助指针变量

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos;i ++){

        pCurrent = pCurrent->next;

    }

    //创建新结点

    struct LinkNode *newnode = malloc(sizeof(struct LinkNode));

    newnode->data = data;

    newnode->next = NULL;

    //新结点入链表

    newnode->next = pCurrent->next;

    pCurrent->next = newnode;

    //size

    llist->size++;

    return 0;

}

//头插

int PushFront_LinkList(LinkList list, void *data){

    return InsertByPos_LinkList(list, 0, data);

}

//尾插

int PushBack_LinkList(LinkList list, void *data){

    if (NULL == list){

        return -1;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    return InsertByPos_LinkList(list,llist->size - 1,data);

}

//在指定值的前面插入

int InsertByVal_LinkList(LinkList list, void *oldval, void *newval, int(*isequal)(void*, void*)){

    if(NULL ==list){

        return -1;

    }

    if (NULL == oldval){

        return -2;

    }

    if (NULL == newval){

        return -3;

    }

    if (NULL == isequal){

        return -4;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    //辅助指针变量

    struct LinkNode *pPrev = &(llist->header);

    struct LinkNode *pCurrent = pPrev->next;

    while (pCurrent != NULL){

        if (isequal(pCurrent->data, oldval)){

            //创建新结点

            struct LinkNode *newnode = malloc(sizeof(struct LinkNode));

            newnode->data = newval;

            newnode->next = NULL;

            //新结点入链表

            pPrev->next = newnode;

            newnode->next = pCurrent;

            llist->size++;

            break;

        }

        pPrev = pCurrent;

        pCurrent = pCurrent->next;

    }

    return 0;

}

//指定位置删除

int RemoveByPos_LinkList(LinkList list, int pos){

    if (NULL == list){

        return -1;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    if (llist->size == 0){

        return 0;

    }

    if (pos < 0 || pos > llist->size - 1){

        return 0;

    }

    //辅助指针变量

    //找到待删除结点的前一个结点

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos;i ++){

        pCurrent = pCurrent->next;

    }

    //缓存下待删除结点

    struct LinkNode *pDel = pCurrent->next;

    //重新建立待删除结点的前驱后继结点关系

    pCurrent->next = pDel->next;

    //删除结点内存

    free(pDel);

    pDel = NULL;

    llist->size--;

    return 0;

}

//根据值删除

int RemoveByVal_LinkList(LinkList list, void *data, int(*compare)(void *, void *)){

    if (NULL == list){

        return -1;

    }

    if (NULL == data){

        return -2;

    }

    if (NULL == compare){

        return -3;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    //辅助指针变量

    struct LinkNode *pPrev = &(llist->header);

    struct LinkNode *pCurrent = pPrev->next;

    while (pCurrent != NULL){

        if (compare(pCurrent->data, data)){

            pPrev->next = pCurrent->next;

            free(pCurrent);

            llist->size--;

            break;

        }

        pPrev = pCurrent;

        pCurrent = pPrev->next;

    }

    return 0;

}

//头删

void PopFront_LinkList(LinkList list){

    RemoveByPos_LinkList(list, 0);

}

//尾删

void PopBack_LinkList(LinkList list){

    if (NULL == list){

        return;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    RemoveByPos_LinkList(list, llist->size - 1);

}

//遍历

void Foreach_LinkList(LinkList list, void(*foreach)(void *)){

    if (NULL == list){

        return;

    }

    if (NULL ==    foreach){

        return;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    //辅助指针变量

    struct LinkNode *pCurrent = llist->header.next;

    while (pCurrent != NULL){

        foreach(pCurrent->data);

        pCurrent = pCurrent->next;

    }

}

//销毁

void Destroy_LinkList(LinkList list){

    if (NULL == list){

        return;

    }

    struct _Linklist *llist = (struct _Linklist *)list;

    //辅助指针变量

    struct LinkNode *pCurrent = llist->header.next;

    while (pCurrent != NULL){

        //缓存下一个结点

        struct LinkNode *pNext = pCurrent->next;

        //释放当前结点内存

        free(pCurrent);

        //指针移动到下一个结点的位置

        pCurrent = pNext;

    }

    free(llist);

    llist = NULL;

}

测试代码：

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include"LinkList.h"

struct Person{

    char name[64];

    int age;

};

void MyPrint(void *data){

    struct Person *person = (struct Person *)data;

    printf("Name:%s Age:%d\n", person->name,person->age);

}

int MyCompare(void *d1,void *d2){

    struct Person *p1 = (struct Person *)d1;

    struct Person *p2 = (struct Person *)d2;

    return strcmp(p1->name, p2->name) == 0 && p1->age == p2->age;

}

void test(){

    //创建测试数据

    struct Person p1 = { "aaa", 10 };

    struct Person p2 = { "bbb", 20 };

    struct Person p3 = { "ccc", 30 };

    struct Person p4 = { "ddd", 40 };

    struct Person p5 = { "eee", 50 };

    struct Person p6 = { "fff", 60 };

    struct Person p7 = { "ggg", 70 };

    //初始化链表

    LinkList list = Init_LinkList();

    //将数据插入链表

    InsertByPos_LinkList(list, 0, &p1);

    InsertByPos_LinkList(list, 0, &p2);

    InsertByPos_LinkList(list, 0, &p3);

    InsertByPos_LinkList(list, 1, &p4);

    InsertByPos_LinkList(list, 0, &p5);

    InsertByPos_LinkList(list, 0, &p6);

    //遍历 6 5 3 4 2 1

    Foreach_LinkList(list, MyPrint);

    printf("-------------------\n");

    printf("在name为ccc,age为30的数据前面插入:\n");

    InsertByVal_LinkList(list, &p3, &p7, MyCompare);

    Foreach_LinkList(list, MyPrint);

    printf("删除位置4的数据:\n");

    RemoveByPos_LinkList(list,4);

    Foreach_LinkList(list, MyPrint);

    printf("删除name为ggg age为70的数据:\n");

    RemoveByVal_LinkList(list, &p7, MyCompare);

    Foreach_LinkList(list, MyPrint);

    //销毁链表

    Destroy_LinkList(list);

}

int main(){

    test();

    system("pause");

    return EXIT_SUCCESS;

}

链表版本二：通过修改指针的指向的区域的大小，实现数据链接，给用户使用

头文件：

#pragma once

#include<stdlib.h>

//链表小节点

//目的 ： 第一，让用户数据包含 第二，我需要把用户指针类型转换成struct LinkNode*类型

struct LinkNode{

    struct LinkNode *next;

};

//链表结构体

struct LList{

    struct LinkNode header;

    int size;

};

typedef void *LinkList;

//初始化

LinkList Init_LinkList();

//指定位置插入

void Insert_LinkList(LinkList list, int pos, struct LinkNode *data);

//位置删除

void RemoveByPos_LinkList(LinkList list, int pos);

//遍历

void Foreach_LinkList(LinkList list, void(*foreach)(void *));

//销毁

void Destroy_LinkList(LinkList list);

头文件实现：

#include"LinkList.h"

//初始化

LinkList Init_LinkList(){

    struct LList *list = malloc(sizeof(struct LList));

    if (NULL == list){

        return NULL;

    }

    list->header.next = NULL;

    list->size = 0;

    return list;

}

//指定位置插入

void Insert_LinkList(LinkList list, int pos, struct LinkNode *data){

    if (NULL == list){

        return;

    }

    if (NULL == data){

        return;

    }

    struct LList *llist = (struct LList *)list;

    if (pos < 0 || pos >llist->size){

        pos = llist->size;

    }

    //查找pos位置前一个位置的节点

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos;i ++){

        pCurrent = pCurrent->next;

    }

    //将新节点插入到链表

    data->next = pCurrent->next;

    pCurrent->next = data;

    llist->size++;

}

//位置删除

void RemoveByPos_LinkList(LinkList list, int pos){

    if (NULL ==list){

        return;

    }

    struct LList *llist = (struct LList *)list;

    if (llist->size == 0){

        return;

    }

    if (pos < 0 || pos > llist->size - 1){

        return;

    }

    //找到pos位置的前一个节点

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos; i ++){

        pCurrent = pCurrent->next;

    }

    //缓存下待删除节点

    struct LinkNode *pDel = pCurrent->next;

    //重新建立待删除的节点前驱后继节点关系

    pCurrent->next = pDel->next;

    llist->size--;

}

//遍历

void Foreach_LinkList(LinkList list, void(*foreach)(void *)){

    if (NULL == list){

        return;

    }

    struct LList *llist = (struct LList *)list;

    //辅助指针变量

    struct LinkNode *pCurrent = llist->header.next;

    while (pCurrent != NULL){

        foreach(pCurrent);

        pCurrent = pCurrent->next;

    }

}

测试函数：

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include"LinkList.h"

struct Person{

    struct LinkNode node;

    char name[64];

    int age;

};

void MyPrint(void *data){

    struct Person *person = (struct Person *)data;

    printf("Name:%s Age:%d\n",person->name,person->age);

}

void ChanageValue(void *data){

    struct Person *person = (struct Person *)data;

    person->age += 100;

}

//#define ISSTACK

void test(){

    //创建测试数据

#ifdef ISSTACK

    struct Person p1 = { NULL , "aaa", 10 };

    struct Person p2 = { NULL , "bbb", 20 };

    struct Person p3 = { NULL , "ccc", 30 };

    struct Person p4 = { NULL , "ddd", 40 };

    struct Person p5 = { NULL , "eee", 50 };

#else

    struct Person *p1 = malloc(sizeof(struct Person));

    struct Person *p2 = malloc(sizeof(struct Person));

    struct Person *p3 = malloc(sizeof(struct Person));

    struct Person *p4 = malloc(sizeof(struct Person));

    struct Person *p5 = malloc(sizeof(struct Person));

    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;

#endif

    //初始化链表

    LinkList list = Init_LinkList();

#ifdef ISSTACK

    //数据插入到链表

    Insert_LinkList(list, 0, (struct LinkNode *)&p1);

    Insert_LinkList(list, 0, (struct LinkNode *)&p2);

    Insert_LinkList(list, 0, (struct LinkNode *)&p3);

    Insert_LinkList(list, 0, (struct LinkNode *)&p4);

    Insert_LinkList(list, 0, (struct LinkNode *)&p5);

#else

    Insert_LinkList(list, 0, (struct LinkNode *)p1);

    Insert_LinkList(list, 0, (struct LinkNode *)p2);

    Insert_LinkList(list, 0, (struct LinkNode *)p3);

    Insert_LinkList(list, 0, (struct LinkNode *)p4);

    Insert_LinkList(list, 0, (struct LinkNode *)p5);

#endif

    //遍历

    Foreach_LinkList(list, MyPrint);

    //删除2号位置

    printf("------------------\n");

    RemoveByPos_LinkList(list, 3);

    Foreach_LinkList(list, MyPrint);

    //遍历修改数据

    printf("---------------------\n");

    //Foreach_LinkList(list, ChanageValue);

    //Foreach_LinkList(list, MyPrint);

    //销毁链表

    Destroy_LinkList(list);

    free(p1);

    free(p2);

    free(p3);

    free(p4);

    free(p5);

}

int main(){

    test();

    system("pause");

    return EXIT_SUCCESS;

}

以链表为底层容器实现栈

头文件：

容器头文件：

#pragma once

#include<stdlib.h>

//链表小节点

//目的 ： 第一，让用户数据包含 第二，我需要把用户指针类型转换成struct LinkNode*类型
struct LinkNode{
struct LinkNode *next;
};

//链表结构体
struct LList{
struct LinkNode header;
int size;
};

typedef void *LinkList;

//初始化
LinkList Init_LinkList();

//指定位置插入
void Insert_LinkList(LinkList list, int pos, struct LinkNode *data);
//位置删除
void RemoveByPos_LinkList(LinkList list, int pos);
//遍历
void Foreach_LinkList(LinkList list, void(*foreach)(void *));
//根据位置获得值
void *Get_LinkList(LinkList list,int pos);
int Size_LinkList(LinkList list);

//销毁
void Destroy_LinkList(LinkList list);

栈头文件：

#pragma once

#include"LinkList.h"

struct StackNode{

    struct LinkNode node;

};

typedef void *LinkStack;

//初始化

LinkStack Init_LinkStack();

//入栈

void Push_LinkStack(LinkStack stack, void *data);

//出栈

void Pop_LinkStack(LinkStack stack);

//获得栈顶元素

void *Top_LinkStack(LinkStack stack);

//大小

int Size_LinkStack(LinkStack stack);

//销毁栈

void Destroy_LinkStack(LinkStack stack);

头文件实现：

容器头文件实现：

#include"LinkList.h"

//初始化

LinkList Init_LinkList(){

    struct LList *list = malloc(sizeof(struct LList));

    if (NULL == list){

        return NULL;

    }

    list->header.next = NULL;

    list->size = 0;

    return list;

}

//指定位置插入

void Insert_LinkList(LinkList list, int pos, struct LinkNode *data){

    if (NULL == list){

        return;

    }

    if (NULL == data){

        return;

    }

    struct LList *llist = (struct LList *)list;

    if (pos < 0 || pos >llist->size){

        pos = llist->size;

    }

    //查找pos位置前一个位置的节点

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos;i ++){

        pCurrent = pCurrent->next;

    }

    //将新节点插入到链表

    data->next = pCurrent->next;

    pCurrent->next = data;

    llist->size++;

}

//位置删除

void RemoveByPos_LinkList(LinkList list, int pos){

    if (NULL ==list){

        return;

    }

    struct LList *llist = (struct LList *)list;

    if (llist->size == 0){

        return;

    }

    if (pos < 0 || pos > llist->size - 1){

        return;

    }

    //找到pos位置的前一个节点

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos; i ++){

        pCurrent = pCurrent->next;

    }

    //缓存下待删除节点

    struct LinkNode *pDel = pCurrent->next;

    //重新建立待删除的节点前驱后继节点关系

    pCurrent->next = pDel->next;

    llist->size--;

}

//根据位置获得值

void *Get_LinkList(LinkList list, int pos){

    if (NULL == list){

        return NULL;

    }

    struct LList *llist = (struct LList *)list;

    if (pos < 0 || pos > llist->size - 1){

        return NULL;

    }

    //辅助指针变量

    struct LinkNode *pCurrent = &(llist->header);

    for (int i = 0; i < pos; i++){

        pCurrent = pCurrent->next;

    }

    return pCurrent->next;

}

int Size_LinkList(LinkList list){

    if (NULL == list){

        return -1;

    }

    struct LList *llist = (struct LList *)list;

    return llist->size;

}

//遍历

void Foreach_LinkList(LinkList list, void(*foreach)(void *)){

    if (NULL == list){

        return;

    }

    struct LList *llist = (struct LList *)list;

    //辅助指针变量

    struct LinkNode *pCurrent = llist->header.next;

    while (pCurrent != NULL){

        foreach(pCurrent);

        pCurrent = pCurrent->next;

    }

}

//销毁

void Destroy_LinkList(LinkList list){

    if (NULL == list){

        return;

    }

    free(list);

    list = NULL;

}

栈头文件实现：

#include"LinkStack.h"

//初始化

LinkStack Init_LinkStack(){

    return Init_LinkList();

}

//入栈

void Push_LinkStack(LinkStack stack, void *data){

    Insert_LinkList(stack, 0, data);

}

//出栈

void Pop_LinkStack(LinkStack stack){

    RemoveByPos_LinkList(stack, 0);

}

//获得栈顶元素

void *Top_LinkStack(LinkStack stack){

    return Get_LinkList(stack, 0);

}

//大小

int Size_LinkStack(LinkStack stack){

    return Size_LinkList(stack);

}

//销毁栈

void Destroy_LinkStack(LinkStack stack){

    Destroy_LinkList(stack);

}

测试文件

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include"LinkStack.h"

struct Person{

    struct StackNode node;

    char name[64];

    int age;

};

void test(){

    //创建测试数据

    struct Person p1 = { NULL, "aaa", 10 };

    struct Person p2 = { NULL, "bbb", 20 };

    struct Person p3 = { NULL, "ccc", 30 };

    struct Person p4 = { NULL, "ddd", 40 };

    struct Person p5 = { NULL, "eee", 50 };

    //初始化栈

    LinkStack stack = Init_LinkStack();

    //数据入栈

    Push_LinkStack(stack , &p1);

    Push_LinkStack(stack, &p2);

    Push_LinkStack(stack, &p3);

    Push_LinkStack(stack, &p4);

    Push_LinkStack(stack, &p5);

    //输出栈中元素

    while (Size_LinkStack(stack) > 0){

        //获得栈顶元素

        struct Person *person = (struct Person*)Top_LinkStack(stack);

        //输出元素

        printf("Name:%s Age:%d\n",person->name,person->age);

        //弹出栈顶元素

        Pop_LinkStack(stack);

    }

    printf("Size%d\n",Size_LinkStack(stack));

    //销毁栈

    Destroy_LinkStack(stack);

}

int main(){

    test();

    system("pause");

    return EXIT_SUCCESS;

}

数据结构 传统链表实现与Linux内核链表的相关教程结束。

《数据结构 传统链表实现与Linux内核链表.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!