C语言实现通用数据结构之通用链表

2024-12-24 09:32:58

本文实例为大家分享了c语言实现通用数据结构之通用链表的具体代码，供大家参考，具体内容如下

忽然想起来，大概在两年之前学习C语言的时候，曾经用C语言写过一些通用的数据结构。主要也就实现了链表、队列、椎、HashSet，还有HashMap。当时只是知道标准的C语言中没有这方面的类库，后来才知道有很多第三方的类似这样的类库。废话不多说，先把代码粘过来。

下面实现的是通用链表，注意链表中只存储了指针，没有储存实际的数据。

头文件

/*************************
*** File myList.h
**************************/

#ifndef MYLIST_H_INCLUDED
#define MYLIST_H_INCLUDED
#include <stdio.h>

typedef struct myNode
{
    void * data;
    struct myNode *next;
} MyNode;

typedef struct myList
{
    MyNode * first;
    MyNode * last;
    int count;
    int (*equal)(void * a, void * b);
} MyList;

typedef struct myListIterator
{
    MyNode * p;
    int count;
    int allSize;
} MyListIterator;

//创建链表
MyList * createMyList();

//创建链表，带有相等参数，用于查找
MyList * createMySearchList(int(*equal)(void * a, void * b));

//释放链表
void freeMyList(MyList * list);

//插入在尾部
void myListInsertDataAtLast(MyList* const list, void* const data);

//插入在首部
void myListInsertDataAtFirst(MyList * const list, void* const data);

//插入
void myListInsertDataAt(MyList * const list, void* const data, int index);

//删除在尾部
void* myListRemoveDataAtLast(MyList* const list);

//删除在首部
void* myListRemoveDataAtFirst(MyList * const list);

//删除
void* myListRemoveDataAt(MyList* const list, int index);

//删除对象,返回是否删除成功
int myListRemoveDataObject(MyList* const list, void * data);

//长度
int myListGetSize(const MyList * const list);

//打印
void myListOutput(const MyList * const list, void(*pt)(const void * const));

//取得数据
void* myListGetDataAt(const MyList * const list, int index);

//取得第一个数据
void* myListGetDataAtFirst(const MyList * const list);

//取得最后一个数据
void* myListGetDataAtLast(const MyList * const list);

//查找某个数据的位置,如果equal方法为空，比较地址，否则调用equal方法
//如果不存在返回-1，如果存在，返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, void * data);

//创建遍历器
MyListIterator* createMyListIterator(const MyList * const list);

//释放遍历器
void freeMyListIterator(MyListIterator* iterator);

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator);

//返回遍历器的下一个元素
void * myListIteratorNext(MyListIterator* const iterator);

#endif // MYLIST_H_INCLUDED

源文件

/*************************
*** File myList.c
**************************/

#include "myList.h"
#include <stdlib.h>
//创建链表
MyList * createMyList()
{
    MyList * re = (MyList *) malloc(sizeof(MyList));
    re->count = 0;
    re->first = NULL;
    re->last = NULL;
    re->equal = NULL;
    return re;
}

//释放链表
void freeMyList(MyList * list)
{
    MyNode * p;
    while (list->first)
    {
        p = list->first->next;
        free(list->first);
        list->first = p;
    }
    free(list);
}

//插入在尾部
void myListInsertDataAtLast(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;
    if (list->count)
    {
        list->last->next = node;
        list->last = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//插入在首部
void myListInsertDataAtFirst(MyList * const list, void* const data)
{
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    if (list->count)
    {
        node->next = list->first;
        list->first = node;
    }
    else
    {
        list->first = node;
        list->last = node;
    }
    (list->count)++;
}

//长度
int myListGetSize(const MyList * const list)
{
    return list->count;
}

//打印
void myListOutput(const MyList * const list, void(*pt)(const void * const))
{
    MyNode * p = list->first;
    while (p)
    {
        (*pt)(p->data);
        p = p->next;
    }
}

//删除在尾部
void* myListRemoveDataAtLast(MyList* const list)
{
    if (list->count == 1)
    {
        return myListRemoveDataAtFirst(list);
    }
    MyNode * p = list->first;
    while (p->next != list->last)
    {
        p = p->next;
    }
    void *re = list->last->data;
    free(list->last);
    p->next = NULL;
    list->last = p;
    (list->count)--;
    return re;
}

//删除在首部
void* myListRemoveDataAtFirst(MyList * const list)
{
    MyNode *p = list->first;
    list->first = p->next;
    void * re = p->data;
    free(p);
    (list->count)--;
    if (list->count == 0)
    {
        list->last = NULL;
    }
    return re;
}

//插入
void myListInsertDataAt(MyList * const list, void* const data, int index)
{
    if (index == 0)
    {
        myListInsertDataAtFirst(list, data);
        return;
    }
    if (index == list->count)
    {
        myListInsertDataAtLast(list, data);
        return;
    }
    MyNode * node = (MyNode *) malloc(sizeof(MyNode));
    node->data = data;
    node->next = NULL;

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++)
    {
        p = p->next;
    }
    node->next = p->next;
    p->next = node;

    (list->count)++;
}

//删除
void* myListRemoveDataAt(MyList* const list, int index)
{
    if (index == 0)
    {
        return myListRemoveDataAtFirst(list);
    }
    if (index == list->count - 1)
    {
        return myListRemoveDataAtLast(list);
    }

    MyNode * p = list->first;
    for (int i = 0; i < index - 1; i++)
    {
        p = p->next;
    }
    MyNode *tp = p->next;
    p->next = p->next->next;
    void * re = tp->data;
    free(tp);
    (list->count)--;
    return re;
}

//取得数据
void* myListGetDataAt(const MyList * const list, int index)
{
    if (index == list->count - 1)
    {
        return myListGetDataAtLast(list);
    }
    MyNode * p = list->first;
    for (int i = 0; i < index; i++)
    {
        p = p->next;
    }
    return p->data;
}

//取得第一个数据
void* myListGetDataAtFirst(const MyList * const list)
{
    return list->first->data;
}

//取得最后一个数据
void* myListGetDataAtLast(const MyList * const list)
{
    return list->last->data;
}

//查找某个数据的位置,如果equal方法为空，比较地址，否则调用equal方法
//如果不存在返回-1，如果存在，返回出现的第一个位置
int myListFindDataIndex(const MyList * const list, void * data)
{
    MyNode * p = list->first;
    int re = 0;
    if (list->equal)
    {
        while (p)
        {
            if (p->data == data || (*(list->equal))(p->data, data))
            {
                return re;
            }
            re++;
            p = p->next;
        }

    }
    else
    {
        while (p)
        {
            if (p->data == data)
            {
                return re;
            }
            re++;
            p = p->next;
        }
    }
    return -1;
}

//创建链表，带有相等参数，用于查找
MyList * createMySearchList(int(*equal)(void * a, void * b))
{
    MyList * re = createMyList();
    re->equal = equal;
    return re;
}

//创建遍历器
MyListIterator* createMyListIterator(const MyList * const list)
{
    MyListIterator * re = (MyListIterator *) malloc(sizeof(MyListIterator));
    re->p = list->first;
    re->allSize = list->count;
    re->count = 0;
    return re;
}

//释放遍历器
void freeMyListIterator(MyListIterator* iterator)
{
    free(iterator);
}

//遍历器是否有下一个元素
int myListIteratorHasNext(const MyListIterator* const iterator)
{
    return iterator->count < iterator->allSize;
}

//返回遍历器的下一个元素
void * myListIteratorNext(MyListIterator* const iterator)
{
    void * re = iterator->p->data;
    iterator->p = iterator->p->next;
    (iterator->count)++;
    return re;
}

//删除对象,返回是否删除成功
int myListRemoveDataObject(MyList* const list, void * data)
{
    MyListIterator * it = createMyListIterator(list);
    int a = 0;
    while (myListIteratorHasNext(it))
    {
        void * ld = myListIteratorNext(it);
        if (data == ld || (list->equal != NULL && (*(list->equal))(ld, data)))
        {
            a = 1;
            break;
        }
    }
    if (a)
    {
        myListRemoveDataAt(list, it->count - 1);
    }
    return a;
}

测试文件

/*************************
*** File main.c
*** test for MyList
**************************/
#include <stdio.h>
#include <stdlib.h>
#include "myList.h"

typedef struct a
{
    int i;
    char c;
} A;

void ppt(const void* const p)
{
    A * pp= p;
    printf("%d(%c) ", pp->i, pp->c);
}

int main()
{
    const int S =10;

    //创建并初始化数据
    A * data= malloc(sizeof(A)*S);
    for (int i=0; i< S; i++)
    {
        data[i].i=i;
        data[i].c=(char)('A'+0);
    }

    //创建链表
    MyList * list= createMyList();

    //测试三种插入方法
    myListInsertDataAtLast( list, &data[0]);
    myListInsertDataAtFirst( list, &data[4]);
    myListInsertDataAt(list, &data[1], 1 );

    //测试查找
    int index = myListFindDataIndex(list, &data[2]);
    printf("%d\n", index);
    index = myListFindDataIndex(list, &data[4]);
    printf("%d\n", index);

    //输出
    myListOutput(list, ppt );
    puts("");

    //测试使用迭代器输出
    MyListIterator * it = createMyListIterator(list);
    while(myListIteratorHasNext(it))
    {
        A * pp = myListIteratorNext(it);
        printf("%d[%c] ", pp->i, pp->c);
    }
    puts("");
    //释放迭代器
    freeMyListIterator(it);

    //释放链表
    freeMyList(list);

    //释放数据
    free(data);
    return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C语言数据结构之判断循环链表空与满

C语言数据结构之判断循环链表空与满前言: 何时队列为空?何时为满? 由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等.因此,我们无法通过front=rear来判断队列"空"还是"满". 注:先进入的为'头',后进入的为'尾'. 解决此问题的方法至少有三种: 其一是另设一个布尔变量以匹别队列的空和满: 其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始
C语言数据结构链表的实例（十九种操作）

C语言数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915
C语言数据结构双向链表的建立与基本操作

C语言数据结构双向链表的建立与基本操作双向链表比单链表有更好的灵活性,其大部分操作与线性表相同.下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题. 1.双向链表的建立双向链表在初始化时,要给首尾两个节点分配内存空间.成功分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是十分关键的一步,因为这是之后用来判断空表的条件.同时,当链表为空时,要将首节点的next指向尾节点,尾节点的prior指向首节点. 2.双向链表的插入操作由于定义双向链表时指针域中
C语言数据结构实现链表去重的实例

C语言数据结构实现链表去重的实例题目及分析链表去重时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入
C语言数据结构链表与归并排序实例详解

C语言数据结构链表与归并排序实例详解归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这
数据结构 C语言实现循环单链表的实例

数据结构 C语言实现循环单链表的实例实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环
C语言数据结构链表队列的实现

C语言数据结构链表队列的实现 1.写在前面队列是一种和栈相反的,遵循先进先出原则的线性表. 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码. 分解代码没有包含在内的代码如下: #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int QElemtype; typedef int status; 2.代码分解 2.1对队列和节点的结构定义 typedef struct
C语言数据结构实现链表逆序并输出

C语言数据结构实现链表逆序并输出将一个链表逆序并输出.我用了两种方法来实现,第一种是借助了一个新的空链表:第二种是在原来链表的基础上直接实现逆序. 实例代码: 头文件: #include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int ElemType; typedef struct Node {//结点结构 ElemType value; //值域 struct Node *next;//指
C语言数据结构之链表实现代码

前言最近在复习数据结构的相关知识,感觉在初学的时候还是有很多东西没有掌握,不过现在终于算是搞得比较有头绪了,所以就在写出来和大家一起分享! 什么是链表简单的说,链表就是由多个结点离散分配,彼此通过指针相连,每个结点只有一个前驱结点和后继结点.首节点无前驱结点,为结点无后继结点的一种存储结构. 链表的结构头结点:链表的第一个有效结点前面的结点,头结点并不存放有效数据,也就是数据域为空,加头结点的主要目的是为了方便链表的操作. 首节点:链表的第一个有效结点,结点包含数据域和指针域. 尾结点:尾
C语言创建和操作单链表数据结构的实例教程

1,为什么要用到链表数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性.但数组也同样存在一些弊病.如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一.我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费. 我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要.链表就是我们需要的动态数组.它是在程序的执行过程中根据需要有数据存储就向系统要求

C语言实现通用数据结构之通用链表

相关推荐

随机推荐