博客

linklist.h 文件

#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//链表就是一个一个的表通过关系节点连接的
//单向链表
//链表操作精髓在于操作关系节点，引入辅助指针pcurrent,pnext.从表头开始遍历各关系节点。

//让业务节点包含关系节点，并把关系节点放在业务的首地址
//业务的首地址就是关系节点的地址，统一转化

//让无序的数据通过指针组成链表，联系起来
//1，指针指向谁就把谁的地址赋给指针
//2，分清楚链表的操作逻辑和辅助指针变量之间的关系
//3, 链表是链式存储的，无顺序，单向的，找到3必须先找到2，
//找到2必须先找到1，找到1必先找到0，再找到头，故引入辅助指针，不可以[]操作

//实现上层调用和底层分离，不让调用用户知道数据结构
typedef void List;
typedef void ListNode;

#ifndef bool
#define bool int
#define true 1
#define false 0
#endif
//链表就是有很多表格组成，刚开始创建表头格，
//业务节点创建后来的表格，通过关系节点连接起来
/**链表只创建了一个链表头，next指向null。后边添加的节点是在业务节点中产生的。**/

//小节点，等待被业务节点包含。
//由小节点之间的关系连接业务节点。
//被业务节点放在首部，小节点地址与业务节点首地址重合
//链表的算法和业务分离，STL思想

//定义小节点是有联系的 ,小节点的链表
typedef struct _tag_LinkListConnectedNode
{
    struct _tag_LinkListConnectedNode* next;
}LinkListConnectedNode;

//定义链表头，只是链表的头，首地址。通过首地址操作链表
typedef struct _tag_LinkList{
    LinkListConnectedNode head;  //小节点
    int length; //小节点的个数就相当于业务节点的个数
}LinkList;

//用户定义的数据业务模型只要包含关系节点，且关系的节点的地址与表头的关系节点地址相当
//都是每个表格的首地址即可，业务节点就可以与表头串起来
//typedef struct _tag_LinkListData
//{
//  LinkListConnectedNode node;   //关系节点
//  Teacher teacher;     //业务数据
//}LinkListData;

//只是返回链表的首地址，通过链表的首地址完成一系列操作
List* LinkList_Create();
bool LinkList_Destory(List* list);
bool LinkList_Clear(List* list);
int LinkList_GetLength(List* list);
bool LinkList_InsertOneNode(List* list ,ListNode* listnode, int pos);
ListNode* LinkList_GetOneNode(List* list, int pos );
ListNode* LinkList_DeleteOneNode(List* list, int pos);
bool LinkList_DeleteAllNode(List* list);
#endif

linklist.c 文件

#include "linklist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//链表就是一个一个的表通过关系节点连接的
//链表操作精髓在于操作关系节点，引入辅助指针pcurrent,pnext.从表头开始遍历各关系节点。

//底层函数分配链表头的内存，业务链表的内存由调用者分配内存。
//就是调用者分配业务链表中关系连接节点的内存
//对链表的操作实际是通过关系连接节点的操作完成的
//各链表的首地址就是关系连接节点的地址
//链表头的首地址就是第一个关系连接节点的地址
//链表头不存业务数据


//创建链表其实只是创建一个表头格而已。
//每次增加新业务节点时，只需业务创建业余节点，通过关系节点连接起来
//业务节点和链表头都要包含关系节点。

//返回一个链表就是返回链表头的首地址
List* LinkList_Create()
{
    //只创建一个头结点
    List* ret = NULL;
    LinkList* templinklist = NULL;
    templinklist = (LinkList*)malloc(sizeof(LinkList));
    memset(templinklist,0,sizeof(LinkList));
    templinklist->head.next = NULL;
    templinklist->length = 0;
    ret = (List*)templinklist;
    return ret;
}
//传入链表头的首地址即第一个关系连接节点
bool LinkList_Destory(List* list)
{   
    LinkList* templinklist = NULL;
    if (list == NULL)
    {
        return false;
    }
    templinklist = (LinkList*)list;
    free(templinklist);
    templinklist = NULL;
    return true;
}
//让链表恢复到初始化状态
bool LinkList_Clear(List* list)
{
     LinkList* templinklist = NULL;
     if (list == NULL)
     {
         return false;
     }
     templinklist = (LinkList*)list;
     templinklist->length = 0;
     templinklist->head.next = NULL;
     return true;
}

int LinkList_GetLength(List* list)
{
    int ret = 0;
    LinkList* templinklist = NULL;
    if (list == NULL)
    {
        return -1;
    }
    templinklist = (LinkList*)list;
    ret = templinklist->length;
    return ret;
}

bool LinkList_InsertOneNode(List* list ,ListNode* listnode, int pos)
{
    LinkList* templinklist = NULL;
    LinkListConnectedNode* pcurrent = NULL; //辅助指针
    LinkListConnectedNode* linklistconnectednode = NULL;
    int i = 0;
    if (list == NULL || listnode == NULL || pos < 0)
    {
        return false;
    }
    templinklist = (LinkList*)list;
    //业务节点先转换成ListNode*，再转换成小节点，由小节点穿起来
    linklistconnectednode = (LinkListConnectedNode*)listnode;
    //辅助指针指向链表的头部，带头的链表，头部之后就是0位置存业务节点；
    //头部只存小节点，不存业务节点。头部只是指向整个链表的首地址
    pcurrent = &(templinklist->head); 
    //辅助指针从头部跳到（pos-1） 处；头部、0、1、2、。。
    for ( i = 0; (i < pos && (pcurrent->next != NULL)); i++)
    {
        pcurrent = pcurrent->next;
    }
    //头，0,1,2,3,4, 要在3号插入，pcurrent 指向2，pcurrent->next 指向3
    //插入新节点后，新节点的next应该指向原来的3即上面的pcurrent->next，pcurrent->next应该指向新节点了
    //当前节点的next 指向要插入新节点的next
    linklistconnectednode->next = pcurrent->next;
    //当前节点的next指向要插入新节点的地址
    pcurrent->next = linklistconnectednode;
    templinklist->length++;
    return true;
}

ListNode* LinkList_GetOneNode(List* list, int pos )
{
    LinkList* templinklist = NULL;
    LinkListConnectedNode* pcurrent = NULL; //辅助指针
    ListNode* ret = NULL;
    int i = 0;
    if (list == NULL || pos < 0)
    {
        return NULL;
    }
    templinklist = (LinkList*)list;
    if (templinklist->length <= 0 || pos >= templinklist->length)
    {
        return NULL;
    }
    //辅助指针指向链表的头部，带头的链表，头部之后就是0位置存业务节点；
    //头部只存小节点，不存业务节点。头部只是指向整个链表的首地址
    pcurrent = &(templinklist->head); //辅助指针指向链表头部
    //辅助指针从头部跳到（pos-1） 处；头部、0、1、2、。。
    for (i = 0; (i < pos && (pcurrent->next != NULL)); i++) //跳pos次，到pos-1处，刚开始指向头部，跳1次指向0
    {
        pcurrent = pcurrent->next;
    }
    ret  = (ListNode*)(pcurrent->next);
    return ret;
}

ListNode* LinkList_DeleteOneNode(List* list, int pos)
{
    LinkList* templinklist = NULL;
    LinkListConnectedNode* pcurrent = NULL; //辅助指针
    LinkListConnectedNode* pdelete = NULL; //缓存要删除的节点
    ListNode* ret = NULL;
    int i = 0;
    if (list == NULL || pos < 0)
    {
        return NULL;
    }
    templinklist = (LinkList*)list;
    if (templinklist->length <= 0 || pos >= templinklist->length)
    {
        return NULL;
    }
    //辅助指针指向链表的头部，带头的链表，头部之后就是0位置存业务节点；
    //头部只存小节点，不存业务节点。头部只是指向整个链表的首地址
    pcurrent = &(templinklist->head); //辅助指针指向链表头部
    //辅助指针从头部跳到（pos-1） 处；头部、0、1、2、。。
    for (i = 0; (i < pos && (pcurrent->next != NULL)); i++) //跳pos次，到pos-1处，刚开始指向头部，跳1次指向0
    {
        pcurrent = pcurrent->next;
    }
    //得到要删除的节点
    pdelete = pcurrent->next;
    pcurrent->next = pdelete->next;
    templinklist->length--;
    ret = (ListNode*)pdelete;
    return ret;
}

bool LinkList_DeleteAllNode(List* list)
{
    LinkList* templinklist = NULL;
    if (list == NULL)
    {
        return false;
    }
    templinklist = (LinkList*)list;
    while(templinklist->length > 0)
    {
        LinkList_DeleteOneNode(list,0);
    }
    return true;
}

/***********************以下为测试代码************************/

/*

//方法1：在业务节点中定义链表的一格的关系节点
//typedef struct _tag_Teacher{
//  LinkListConnectedNode node;
//  int age;
//  char name[64];
//}Teacher;

//方法2：把业务直接定义到链表一格的关系节点之下
//用户定义的数据业务模型只要包含关系节点，
//且关系的节点的地址与表头的关系节点地址相当
//都是每个表格的首地址即可，业务节点就可以与表头串起来
typedef struct _tag_Teacher{
    //LinkListConnectedNode node;
    int age;
    char name[64];
}Teacher;
typedef struct _tag_LinkListData
{
    LinkListConnectedNode node;
    Teacher teacher;
}LinkListData;

void main()
{

    int k = 0;
    List* list = NULL;
    LinkListData t1,t2,t3,t4,t5;
    t1.teacher.age = 21;t2.teacher.age = 22;t3.teacher.age = 23;t4.teacher.age = 24;t5.teacher.age = 25;
    list = LinkList_Create();
    if (list == NULL)
    {
        printf("list创建失败");
    }

    //头插法，插入元素
    //业务节点强制转换为ListNode* ,ListNode* 强制转换为小节点LinkListConnectedNode*;
    LinkList_InsertOneNode(list,(ListNode*)&t1,0);
    LinkList_InsertOneNode(list,(ListNode*)&t2,0);
    LinkList_InsertOneNode(list,(ListNode*)&t3,0);
    LinkList_InsertOneNode(list,(ListNode*)&t4,0);
    LinkList_InsertOneNode(list,(ListNode*)&t5,0);
    printf("链表长度是：%d \n", LinkList_GetLength(list));
    //遍历链表
    for (k = 0; k < LinkList_GetLength(list); k ++)
    {
        LinkListData* teachertemp = (LinkListData* )LinkList_GetOneNode(list,k); 
        printf("老师%d的年龄是%d \n",k,teachertemp->teacher.age);
    }
    LinkList_DeleteAllNode(list);
    printf("链表长度是：%d \n", LinkList_GetLength(list));
    LinkList_Destory(list);
    system("pause");
}
*/

可能调用其它头文件或源文件，如果调用，请翻看我的其它博客，对其头文件或源文件的实现方式。

good luck !