单向动态链表-蒲公英云

单向动态链表

什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)

单向动态链表实现

①头文件代码

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct LinkNode { 
    struct LinkNode* Next;
    int Value;
}LinkNode;
typedef struct LinkList { 
    struct LinkNode* head;
    int size;
}LinkList;
//初始化链表
LinkList* Init_LinkList();
//在指定位置插入结点
void Insert_LinkList(LinkList* list, int pos,int Value);
//删除指定位置的结点
void Remove_LinkList(LinkList* list, int pos);
//获得链表的长度
void Size_LinkList(LinkList* list);
//查找链表位置
void Find_LinkList(LinkList* list, int Value);
//打印链表
void Printf_LinkList(LinkList* list);
//返回第一个结点位置
void* Frist_LinkList(LinkList* list);
//释放链表内存
void Free_LinkList(LinkList* list);

②函数文件代码

#include "Linklist.h"
//初始化
LinkList* Init_LinkList() { 
    LinkList* list = (LinkList*)malloc(sizeof(LinkList));
    list->head = (LinkNode*)malloc(sizeof(LinkNode));
    list->head->Value =0;
    list->head->Next = NULL;
    list->size = 0;
    return list;
}
//在指定位置插入结点
void Insert_LinkList(LinkList* list, int pos, int Value) { 
    if (list == NULL) { 
        return;
    }
    if (pos<0 || pos>list->size) { 
        pos = list->size;
    }
    //创建新结点
    LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
    NewNode->Value = Value;
    NewNode->Next = NULL;
    //找结点
    //辅助指针变量
    LinkNode* Pcur = list->head;
    for (int i = 0; i < pos; ++i) { 
        Pcur = Pcur->Next;
    }
    //插入结点
    NewNode->Next = Pcur->Next;
    Pcur->Next = NewNode;
    ++list->size;
}
//删除指定位置的结点
void Remove_LinkList(LinkList* list, int pos) { 
    if (list == NULL) { 
        return;
    }
    if (pos < 0 || pos >= list->size) { 
        printf("您输入的位置不合法\n");
    }
    //创建辅助指针,需要两个辅助指针
    LinkNode* Pcur=list->head;
    LinkNode* Ppre = Pcur;//用来保存上一个结点的位置
    for (int i = 0; i < pos; ++i) { 
        Ppre = Pcur;
        Pcur = Pcur->Next;
    }
    Ppre->Next = Pcur->Next;
    free(Pcur);
    --list->size;
}
//获得链表的长度
void Size_LinkList(LinkList* list) { 
    if (list == NULL) { 
        return;
    }
    printf("这个链表现在有%d个结点", list->size - 1);
}
//查找链表位置
void Find_LinkList(LinkList* list, int Value) { 
    if (list == NULL) { 
        return;
    }
    LinkNode* Pcur = list->head;
    Pcur = Pcur->Next;
    for (int i = 0; i < list->size; ++i) { 
        if (Pcur->Value == Value) { 
            printf("这个值在第%d个结点上\n", i);
            break;
        }
        Pcur = Pcur->Next;
    }
}
//打印链表
void Printf_LinkList(LinkList* list) { 
    if (list == NULL) { 
        return;
    }
    LinkNode* Pcur = list->head;
    for (int i = 0; i < list->size; ++i) { 
        Pcur = Pcur->Next;
        printf("%d--->", Pcur->Value);
    }
    printf("NULL\n");
}
//返回第一个结点位置
void* Frist_LinkList(LinkList* list) { 
    return list->head->Next;
}
//释放链表内存
void Free_LinkList(LinkList* list) { 
    if (list == NULL) { 
        return;
    }
    //辅助指针
    LinkNode* Pcur = list->head;
    while (Pcur != NULL) { 
        LinkNode* Ppre = Pcur->Next;
        free(Pcur);
        Pcur = Ppre;
    }
    free(list);
}

③测试文件代码

#include <stdio.h>
#include <stdlib.h>
#include "Linklist.h"
void test01() { 
    //初始化
    LinkList* list = Init_LinkList();
    //插入新结点
    for (int i = 0; i < 15; ++i) { 
        Insert_LinkList(list, i, 2 * i);
    }
    //打印结点
    Printf_LinkList(list);
    //删除结点
    Remove_LinkList(list, 5);
    Printf_LinkList(list);
    //查找
    Find_LinkList(list, 10);
    //释放内存
    Free_LinkList(list);
}
int main() { 
    test01();
    system("pause");
    return 0;
}