数据结构之链表

C++中常见的数据结构-CSDN博客

目录

一、链表的定义

二、链表的创建

三、链表的遍历

四、链表的插入

五、链表的删除

六、总结

链表是计算机科学中常见的一种数据结构，c/c++语言中也有着丰富的链表操作函数库。本文将从链表的定义、创建、遍历、插入、删除等多个方面进行详细讲解，带你从入门到精通。

一、链表的定义

链表是一种动态数据结构，由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表分为单向链表、双向链表和循环链表等多种类型。使用链表可以灵活地插入、删除元素，不需要预先分配固定大小的内存空间。

二、链表的创建

在c/c++中，可以使用结构体来定义一个节点，并用指针来表示节点之间的关系，从而实现链表。下面是一个单向链表的创建示例代码：

#include <stdio.h>
#include <stdlib.h>
struct node
 {
    int data;           //数据域
    struct node *next;//指针域
};
int main()
{
    struct node *head,*p,*q;
    int n,i;
    printf("请输入节点个数n：");
    scanf("%d",&n);
    head = NULL;
    for (i=1; i <=n;i++)
    {
        p =(struct node *)malloc(sizeof(struct node));
        if (p== NULL)
        {
            printf("内存分配失败！");
            exit(1);
        }
        printf("请输入第%d个节点的值：",i);
        scanf("%d",&p->data);
        p->next = NULL;
        if (head == NULL)
        {
            head =p;
        }
        else 
        {
            q->next =p;
        }
        q =p;
   }
    printf("链表各节点的值为：");
    p = head;
    while (p!= NULL)
    {
        printf("%d",p->data);
        p =p->next;
    }
    return 0;
}

三、链表的遍历

链表遍历是指按照一定的顺序依次访问链表中的每一个节点。下面是一个单向链表的遍历示例代码：

cstruct node *p;
p = head;
while (p!= NULL)
{
    //访问节点p
    p =p->next;
}

四、链表的插入

链表插入是指在链表中任意位置插入一个新节点。下面是一个单向链表的插入示例代码：

void insert(struct node *head, int i, int x)
{
    struct node *p,*q,*new_node;
    new_node =(struct node *)malloc(sizeof(struct node));
    if (new_node == NULL)
    {
        printf("内存分配失败！");
        exit(1);
    }
    new_node->data =x;
    p = head;
    for (int j =1; j <=i;j++)
    {
        q =p;
        p =p->next;
    }
    new_node->next =p;
    q->next = new_node;
}

五、链表的删除

链表删除是指在链表中删除一个节点。下面是一个单向链表的删除示例代码：

void delete(struct node *head, int i)
{
    struct node *p,*q;
    p = head;
    for (int j =1; j <=i;j++)
    {
        q =p;
        p =p->next;
    }
    q->next =p->next;
    free(p);
}

六、总结

本文从链表的定义、创建、遍历、插入、删除等多个方面进行了详细讲解，希望能够帮助大家更好地理解和掌握c/c++语言中的链表操作。在实际应用中，需要根据具体情况选择合适的链表类型和操作方式，才能发挥链表的优势。