2022年阅读书单

本文目录

1. 1、参考
2. 2、单链表的基本操作（创建、查找、插入、删除、遍历）
3. THE END!

1、参考

C语言描述链表的实现及操作
线性表的基本操作及应用（单链表的创建、插入、删除、查找、显示）
《大话数据结构–程杰》

2、单链表的基本操作（创建、查找、插入、删除、遍历）

线性表是一种重要的数据结构。
线性表的链式存储结构就是单链表。
线性表的顺序存储结构就是数组。

下面是C语言实现的单链表的代码。

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

typedef int ElemType;
// 单链表的声明
typedef struct _Node_S
{
    ElemType data;            // 数据域
    struct  _Node_S *next;    // 指针域
} Node, *LinkList;

// 1、创建：从尾部开始创建链表（尾插法）
LinkList CreateLinkListTail(int n)
{
    int i = 0;
    int x = 0;
    Node *L, *pTail;
    L = (Node*) malloc(sizeof(Node)); // 整个链表
    pTail = L;  //尾结点
    pTail->next = NULL;
    printf("顺序输入元素: \n");

    for (i = 0; i < n; ++i)
    {
        Node* p; //the node to inserted
        p = (Node*) malloc(sizeof(Node));
        scanf("%d", &x);
        // 新加入的结点都作为尾结点放到最后
        p->data = x;     // 数据域赋值
        pTail->next = p; // 尾结点指针指向新结点
        p->next = NULL;  // 新结点指针指向空
        pTail = p;         // 将新结点赋值给尾结点
    }

    //pTail->next = NULL;
    return L;
}

// 2、创建：从头部开始创建链表（头插法）
LinkList CreateLinkListHead(int n)
{
    int i;
    int x;
    Node* L, *pTail;
    L = (Node*) malloc(sizeof(Node)); // 头结点
    L->next = NULL;
    printf("逆序输入元素: \n");

    for (i = 0; i < n; ++i)
    {
        Node* p; //the node to inserted
        p = (Node*) malloc(sizeof(Node));
        scanf("%d", &x);
        // 将新加入的结点插入到头结点的后面
        p->data = x;     // 数据域赋值
        p->next = L->next; // 将新节点的指针指向头结点的指针
        L->next = p;       // 将头结点的指针指向新结点
    }

    return L;
}

//  3、查找：查找链表中的第i个元素
int GetEleInLinkList(LinkList l, int i, ElemType* e)
{
    int j;
    LinkList p;
    p = l->next;

    j = 1;
    // 从链表头部开始遍历
    while(p && j<i)
    {
        p = p->next;
        j++;
    }

    if (!p || j>i)
    {
        printf("没有查找到\n");
        return -1;
    }
    *e = p->data;
    printf("The %dth element: %d \n",i, *e);
    return 0;
}

// 4、插入：在链表中第i个数据插入结点
int InsertNodeInLinkList(LinkList ll, int i, ElemType* m)
{
    int j = 1;
    LinkList p;
    Node* newNode;
    p = ll->next;

    while (p && j<i)
    {
        p = p->next;
        j++;
    }
    if (!p || j<i)
    {
        printf("没有查找到第%d个数据\n", i);
        return -1;
    }

    // 查找成功，创建空节点
    newNode = (Node*) malloc(sizeof(Node));
    if (NULL == newNode)
    {
        printf("malloc error!\n");
        return -1;
    }
    newNode->data = *m;
    newNode->next = p->next;
    p->next = newNode;

    return 0;
}

// 5、遍历输出：遍历链表中的每个元素并输出
int TranvesalLinkList(LinkList ll)
{
    LinkList p;
    p = ll->next;

    if (!p)
    {
        printf("空链表！\n");
        return -1;
    }
    while (p)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");

    return 0;
}

// 6、删除：删除链表中的第i个结点，并取出该结点的值
int DeleteNodeInLinkList(LinkList ll, int i, ElemType *e)
{
    int j = 1;
    LinkList p, q;
    p = ll->next;

    while (p && j < i)
    {
        j++;
        p = p->next;
    }

    if (!p || j>i)
    {
        printf("没有找到第%d个结点！\n", i);
    }

    q = p->next;
    p->next = q->next;
    *e = q->data;

    printf("The deleted node data: %d\n", *e);
    free(q);

    return 0;
}

// 7、整表删除
int DeletedAllNodeInLinkList(LinkList ll)
{
    LinkList p = ll->next;
    LinkList q;

    while (p)
    {
        q = p->next;  // 将下一个结点赋值给q
        free(p);      // 释放该结点p
        p = q;         
    }
    ll->next = NULL;

    return 0;
}

int main(int argc, int argv[])
{
    LinkList ll;
    int elem = 0;
    int value = 50;

    // 创建单链表
    ll = CreateLinkListTail(5);

    // 遍历输出单链表
    TranvesalLinkList(ll);

    // 查找单链表中结点
    GetEleInLinkList(ll, 4, &elem);

    // 插入结点
    InsertNodeInLinkList(ll, 1, &value);

    // 遍历输出单链表
    TranvesalLinkList(ll);

    // 删除结点
    DeleteNodeInLinkList(ll, 1, &elem);

    // 遍历输出单链表
    TranvesalLinkList(ll);

    // 删除整个链表
    DeletedAllNodeInLinkList (ll);

    // 遍历输出单链表
    TranvesalLinkList(ll);

    return 0;
}

THE END!

---

本博文只能阅读，谢绝转载，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2963033731@qq.com