【数据结构与算法】深入浅出:单链表的实现和应用

 

🌱博客主页:青竹雾色间.

😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注

 ✨人生如寄,多忧何为 

目录

前言

链表的基本概念

节点

头节点

尾节点

单链表的基本操作

创建单链表

头插法:

尾插法:

插入(增)操作

 删除(删)操作:

查找(查)操作:

修改(改)操作:

遍历链表

单链表的应用场景


前言

在本篇博客中,我们将深入探索一种常见的数据结构——单链表。单链表是一种线性数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是插入和删除操作非常简单,但是查找和遍历操作可能会比较耗时。我们将学习单链表的基本概念、操作以及实现方式。

单链表的基本概念

下面我们来介绍一下单链表的基本概念和操作。

  • 节点

单链表中的每个节点都包含两个部分:数据域(DATA)和指针域(NEXT)。

数据域用于存储数据元素可以是数组,可以是int,甚至可以是结构体,

指针域用于存储指向下一个节点的指针

typedef int ElemType; //定义单链表结构
typedef struct Node{
    ElemType data;//数据域
    struct Node *next;//指针域
} LinkList;//初始化
  • 头节点

单链表的第一个节点称为头节点,它不包含任何数据元素,只包含一个指向第一个节点的指针。在单链表中,头节点通常被定义为全局变量或者静态变量。

//创建头结点,并将数据存入头结点中
LinkList CreateList(ElemType n){
    LinkList head = (LinkList)malloc(sizeof(struct Node));
    head->data = n;
    head->next = NULL;
    return head;
}
  • 尾节点

单链表的最后一个节点称为尾节点,它也不包含任何数据元素,只包含一个指向最后一个节点的指针。在单链表中,尾节点通常被定义为全局变量或者静态变量。

链表的尾节点NEXT指向NULL(空),因为尾部没有任何可以指向的空间了.

单链表的基本操作

单链表是一种常见的数据结构,支持以下四种基本操作:插入(增)、删除(删)、查找(查)、修改(改)。下面将逐一介绍这些操作的实现方法。

创建单链表

头插法:

我们首先创建一个头结点,然后将新节点插入到头结点的后面。具体实现时,我们可以使用指针来遍历链表,找到最后一个节点,然后将新节点插入到该节点的后面。这样就可以保证新节点始终位于链表的头部。

// 头插法
Node* insertAtHead(Node *head, int data) {
    Node *newNode = (Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    return newNode;
}

尾插法:

我们首先创建一个头结点,然后将新节点插入到头结点的后面。具体实现时,我们可以使用指针来遍历链表,找到最后一个节点,然后将新节点插入到该节点的后面。这样就可以保证新节点始终位于链表的尾部。

// 尾插法
Node* insertAtTail(Node *head, int data) {
    Node *newNode = (Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    if (head == NULL) { // 如果链表为空,则直接将新节点作为头结点。
        newNode->next = NULL;
        return newNode;
    } else if (head->next == NULL) { // 如果链表只有一个元素,则直接将新节点插入到该元素后面。
        head->next = newNode;
        return head;
    } else { // 否则,找到最后一个节点,然后将新节点插入到该节点的后面。
        Node *temp = head;
        while (temp->next != NULL) temp = temp->next;
        temp->next = newNode;
        return head;
    }
}

  • 插入(增)操作

          在单链表中插入一个新节点,将其链接到链表中的其他节点。

// 在指定位置插入一个新节点
void insertAtPos(Node** head, int pos, ElemType e) {
    Node* p = *head;
    int i = 1; // i表示当前节点的位置,从第二个节点开始计算
    while (i < pos && p != NULL) p = p->next, i++; // 从第二个节点开始遍历到指定位置的前一个节点
    Node* newNode = (Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) exit(0); // 如果分配失败则退出程序
    newNode->data = e; // 将新节点的数据域设置为e
    if (p == NULL) *head = newNode; // 如果指定位置的前一个节点是空的,则将新节点作为新的头结点
    else newNode->next = p->next; // 否则将新节点插入到指定位置的前一个节点后面
    p->next = newNode; // 将新节点插入到链表中
}

  •  删除(删)操作

         从单链表中删除一个节点,重新连接链表中的其他节点。

  1. 若要删除的节点为头节点,直接将头节点指向下一个节点即可。
  2. 若要删除的节点不是头节点,遍历链表找到该节点的前一个节点。
  3. 将前一个节点的next指针指向要删除节点的下一个节点。

 

  • 查找(查)操作

        在单链表中查找特定的元素。

  1. 从头节点开始遍历链表,逐个比较节点的数据与目标数据是否相等。
  2. 若找到相等的节点,则返回该节点或其他需要的信息。
  3. 若遍历完整个链表仍未找到目标数据,则表示目标数据不存在于链表中。
//在单链表中查找值为x的结点
int Locate(LinkList L, int x)
{
    LinkList p;
    int j = 1;
    p = L->next;
    while (p != NULL && p->data != x)
    {
        p = p->next;
        j++;
    }
    if (p)
    {
        printf("%d在链表中,是第%d个元素", p->data - 48, j);//由于是ASCII,所以-48
    }
    else
    {
        printf("该数值不在链表里。\n");
        return 0;
    }
}

//求单链表的长度
int ListLength(LinkList L)
{
    Node* p;
    p = L->next;
    int j = 0;//计数器j
    while (p != NULL)
    {
        p = p->next;
        j++;
    }
    printf("%d", j);
    return 0;
}
  • 修改(改)操作

        更新单链表中节点的数据。

  1. 从头节点开始遍历链表,逐个比较节点的数据与目标数据是否相等。
  2. 若找到相等的节点,则将该节点的数据更新为新的数据。
//链表内容的修改,在链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
  • 遍历链表

在单链表中,遍历链表的操作可以通过以下步骤实现:

a. 从头结点开始遍历链表;

b. 对于每个节点,执行相应的操作(如打印数据元素)。

void Print(LinkList L) 
{
    Node* p = L->next;
    while (p) 
    {
        printf("%c ", p->data);
        p = p->next;
    }
}

单链表的应用场景

单链表在实际的软件开发中有广泛的应用,例如:

  • 数据库系统中的链表索引。

  • 实现栈和队列等其他数据结构。
  • 算法中的邻接表表示。
转载请说明出处内容投诉
CSS教程_站长资源网 » 【数据结构与算法】深入浅出:单链表的实现和应用

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买