数据结构与算法(预习)-链表

大概就是一直觉得链表很厉害但是一直没有深入学，因为自己学的语言都是封装好的，不需要再去操作底层了，今天有时间就把基础的单向链表学了一下

链表

定义

用一组任意的存储单元存储线性表中的数据元素；这组存储单元可以是连续的，也可以是不连续的；每个数据元素除了存储数据外，还要存储前驱、后继元素的地址

基本操作

#include < stdio.h >
#include< stdlib.h >
#include < stdbool.h >

typedef int Eletype;

typedef struct node {
    Eletype data;
    struct node* next;
}ListNode, * ListNodePtr;//ListNode是节点别名，ListNodePtr是指向节点的指针

typedef ListNodePtr List, * ListPtr;//List是链表(指针)，ListPtr是指向链表的指针(指针的指针)

typedef enum Status {
    success, fail, fatal, range_error
}Status;

Status List_init(ListPtr L)//链表初始化
{
    Status status = fatal;
    *L = (ListNodePtr)malloc(sizeof(ListNode));
    if (*L)
    {
        (*L)->next = NULL;
        status = success;
    }
    return status;

}
Status List_insert(ListPtr L, int pos, Eletype elem)//添加节点
{
    Status status;
    ListNodePtr p, s;
    status = List_movePtr(L, pos - 1, &p);
    if (status == success)
    {
        s = (ListNodePtr)malloc(sizeof(ListNode));
        if (s)
        {
            s->data = elem;
            s->next = p->next;
            p->next = s;
        }
    }
    else {
        status = fatal;
    }
    return status;
}
Status List_delete(ListPtr L, int pos)//删除节点
{
    Status status;
    ListNodePtr p, pre;
    status = List_movePtr(L, pos - 1, &pre);
    if (status == success)
    {
        p = pre->next;
        pre->next = p->next;
        free(p);
        p = NULL;
    }
    return status;
}

Status List_movePtr(ListPtr L, int pos, ListNodePtr* ptr)//指针移动函数
{
    Status status = fail;
    ListNodePtr p = *L;
    int i = 0;
    while (p && i < pos)
    {
        i++;
        p = p->next;
    }
    if (p && i == pos)
    {
        *ptr = p;
        status = success;
    }
    return status;
}

Status List_GetElem(ListPtr L, int pos, Eletype* elem)//按位查找
{
    Status status = range_error;
    ListNodePtr p;
    status = List_movePtr(L, pos, &p);
    if (status == success)
        *elem = p->data;
    return status;
}

Status List_LocateElem(ListPtr L, Eletype elem, int* pos)//按值查找
{
    Status status = range_error;
    ListNodePtr p = *L;
    int i = 1;
    while (p != NULL)
    {
        if (p->data == elem)
            break;
        i++;
        p = p->next;
    }
    if (p)
    {
        *pos = i;
        status = success;
    }
    return status;
}

int List_long(ListPtr L)//求长度
{
    int length = 0;
    ListNodePtr p = (*L)->next;
    while (p)
    {
        length++;
        p = p->next;
    }
    return length;
}

bool List_empty(ListPtr L)//判空
{
    return (*L)->next == NULL;
}

void List_clear(ListPtr L)//清空链表
{
    ListNodePtr p = *L, q = p->next;
    while (q)
    {
        p->next = q->next;
        free(q);
        q = p->next;
    }
}

void List_destroy(ListPtr L)//销毁链表
{
    List_clear(L);
    free(*L);
}

void List_print(ListPtr L)
{
    int len = List_long(L) + 1;
    for (int i = 1; i < len;i++)
    {
        Status status;
        int p;
        status = List_GetElem(L, i, &p);
        if (status == success)
        {
            printf("第%d号元素是%d\n", i, p);
        }
    }
}

感悟

最开始还觉得为什么教材使用了这么多指针，后来才发现，因为书中都没对变量初始化，如果直接用变量值的话会报错，而传变量地址再通过解引用运算符就可以操作变量值了，学艺不精，呜呜呜:sob:

---

继续加油吧:sparkles: