通用链表变形

1. 头文件

#ifndef LinkList_h
#define LinkList_h

#include <stdio.h>

typedef struct Node{
    
    struct Node *next;
    
}Node;

typedef struct LinkList{
    
    //链表长度
    int length;
    
    //链表的头结点
    Node node;
    
    //销毁函数，此函数实现多态
    void (*free)(void *node);
    
}LinkList;

//初始化链表
void initList(LinkList *list);

//判断链表是否为空
int emptyList(LinkList *list);

//清空链表
void clearList(LinkList *list);

//获取指定位置的数
void getDataByIndex(LinkList *list, int index, void **da);

//在指定位置插入数据
void insertDataByIndex(LinkList *list,int index, void *da);

//删除指定位置的数据
void deleteDataByIndex(LinkList *list, int index);

//获取链表的长度
int getLength(LinkList *list);


#endif /* LinkList_h */

2.api实现

#include "LinkList.h"

//初始化链表
void initList(LinkList *list){
    
    list->length = 0;
    list->node.next = NULL;
    list->free = NULL;
}

//判断链表是否为空
int emptyList(LinkList *list){
    
    if (list->length > 0) {
        
        return 1;
    }
    
    return 0;
}

//清空链表
void clearList(LinkList *list){
    
    while (emptyList(list)) {
        
        deleteDataByIndex(list, 0);
    }

}

//获取指定位置的数
void getDataByIndex(LinkList *list, int index, void **da){
    
    if (index < 0 || index >= list->length ) {
        
        return;
    }
  
    Node *pNode = &list->node;
    
    for (int i =  0;  i <= index; i++) {
        
        pNode = pNode->next;
    }
    
    *da = (void *)pNode;
    
}

//在指定位置插入数据
void insertDataByIndex(LinkList *list,int index, void *da){
    
    if (index < 0 || index > list->length) {
        
        return;
    }
    
    //记录插入点的前一个结点
    Node *pNode = &list->node;
    
    for (int i = 0; i < index; i++) {
        
        pNode = pNode->next;;
        
    }
    
    Node *iNode = (Node *)da;
    
    iNode->next = pNode->next;
    pNode->next = iNode;
    
    list->length++;
}

//删除指定位置的数据，并把数据存到da中
void deleteDataByIndex(LinkList *list, int index){

    if (index < 0 || index >= list->length ) {
        
        return;
    }
    
    //记录插入点的前一个结点
    Node *pNode = &list->node;
    
    for (int i = 0; i < index; i++) {
        
        pNode = pNode->next;;
    }
    
    Node *dNode = pNode->next;
    
    pNode->next = pNode->next->next;

    
    if (list->free != NULL) {
        
        //调用外部函数实现节点的销毁
        list->free(dNode);
    }
    
    list->length--;
}

//获取链表的长度
int getLength(LinkList *list){
    
    return list->length;
}

3.测试

• (1)存放结构体

typedef struct MyStruct{
    
    Node node;
    int age;
    char name[30];
}MyStruct;

void printMS(MyStruct *ms);


void free_(void *node){
   
    MyStruct *ms = (MyStruct *)node;
   
    printf("--------要销毁的数据------------\n");
    printMS(ms);
    
    free(ms);
}

void printMS(MyStruct *ms){
    
    printf("名字:%s, 年龄:%d\n",ms->name,ms->age);
}

//下面是存放结构数据
void linkListTest(){
    
    LinkList linkList;
    initList(&linkList);
    
    linkList.free = free_;
    
    for (int i = 0; i < 6; i++) {
        
        MyStruct *ms = calloc(1, sizeof(*ms));
        ms->node.next = NULL;
        ms->age = 20 + i %10;
        char name[30];
        sprintf(name, "zhangsan%d", i);
        strcpy(ms->name, name);
        
        insertDataByIndex(&linkList, i, ms);
    }
    
    for (int i = 0; i < linkList.length; i++) {
        
        MyStruct *ms;
        getDataByIndex(&linkList, i, (void **)&ms);
        
        //打印
        printMS(ms);
    }
    
    clearList(&linkList);
    
}

• (2)存放int类型

void free_int(void *node){
    
    int *in =(int *)( (char *)node + sizeof(Node));
    
    printf("--------要销毁的数据------------\n");
    
    printf("%d\n", *in);
    
    free(node);
}

void print_int(void *e){
    
    int *in =(int *)( (char *)e + sizeof(Node));
    
    printf("%d\n", *in);
}


//下面是存放整型数据
void linkListTest01(){
    
    LinkList linkList;
    initList(&linkList);
    
    linkList.free = free_int;
    
    for (int i = 0; i < 10; i++) {
        
        char *p = calloc(1, sizeof(Node)  + sizeof(int));
        
        int *in = (int *)(p + sizeof(Node));
        *in = i + 2;
        
        insertDataByIndex(&linkList, 0, (void *)p);
    }
    
    for (int i = 0; i < linkList.length; i++) {
        
        void *ms;
        getDataByIndex(&linkList, i, &ms);
        
        //打印
        print_int(ms);
    }

    clearList(&linkList);
}