C语言——链表简单介绍

article/2025/10/5 19:39:31

一、链表的引入

我们至少可以通过两种结构存储数据。

数组：数组是一个固定长度的存储相同数据类型的数据结构，数组中的元素被存储在一段连续的内存空间中。

优点：存取速度快。

缺点：需要一个连续的很大的内存；

插入和删除元素效率很低。

链表：链表是一种物理存储结构上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

优点：插入和删除元素效率高；

不需要一个连续很大的内存。

缺点：查找某位置元素效率低。

二.链式存储结构——链表

链表是一种常见的采用动态存储分配方式的数据结构。在链表中，每一个元素包含两个部分：数据部分（数据域）和指针部分（指针域）。数据部分用来存放元素所包含的数据，指针部分用来指向下一个元素。最后一个元素的指针指向NULL，表指向的地址为空。

链表结构示意图

1、链表相关专有名词

首节点：存放第一个有效数据的节点。

尾节点：存放最后一个有效数据的节点。

头结点：头结点是首节点前的节点，头结点并不存放数据；

头结点的数据类型和首节点的数据类型一模一样；

头结点的设置是为了方便链表的使用。

头指针：存放头结点地址的指针变量。

2、确定一个链表需要一个参数

头指针（可以通过头指针推算出链表其他所有的参数）

3、链表的分类

单链表
双向链表
循环链表
非循环链表

<1>单链表

在链表中，每个结点只有一个指针，所有的结点都是单线联系，除末尾结点指针为外，每个结点都指向下一个结点，一环扣一环形成一条线性链，称此链表为单向链表或简称为单链表。

单链表结构示意图

<2>双向链表

双向链表中的每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。所以，在这里一个节点包括了三部分，前驱、数据、后驱。

双向链表示意图

<3>循环链表

循环链表是一种头尾相接的链表。表中的最后一个结点的指针域指向头结点，整个链表形成环状结构。循环链表来源于单链表，所以结构与单链表相似。

<4> 非循环链表

三、链表的初始化、插入、删除、创建以及查询

1、链表的初始化（以单链表为例）

单链表的初始化就是创建一个头结点，头结点的数据域可以不使用，头结点的指针域为空，表示空单链表。

/*单链表初始化*/
LinkList InitList()
{LinkList head;                     /*定义头指针变量*/head=(Node*)malloc(sizeof(Node));  /*头指针指向分配的头结点内存空间*/head->next=NULL;                   /*头结点的指针域为空*/return head;                       /*返回头结点的地址，即头指针*/
}

2、链表的插入

链表的插入操作可以在链表头指针位置进行插入，也可以在链表中某个结点的位置进行插入，或者在链表的最后面添加结点。虽然有三种插入操作，但是操作的思想是一样的。

单链表插入操作

/*单链表的插入操作*/
void Insert(LinkList head,int i)
{Node *p=head,*s;int j=0;while(j<i-1 && p)                       //找到第i-1个结点的地址p{p=p->next;j++;}if(p){s=(Node*)malloc(sizeof(Node));    //定义s指向新分配的空间scanf("%s",s->name);scanf("%d",&s->number);s->next=p->next;                  //新结点指向原来的第i个结点p->next=s;                        //新结点成为新链表的第i个结点}
}

在该程序中，首先从链表的头结点开始，找到第i-1个结点的地址p。如果该结点存在，则可以在第i-1个结点后插入第i个结点。为插入的新结点分配内，然后向新结点输入数据。插入时，首先将新结点的指针s指向原来的第i个结点（s->next=p->next），然后将第i-1个结点指向新结点（p->next=s），这样就完成了插入结点的操作。

3.链表的删除

Delete函数中有两个参数，其中head表示链表的头指针，pos表示要删除结点在链表中的位置。定义整型变量j来控制循环的次数，然后定义指针变量p表示该结点之前的结点。接着利用循环找到要删掉结点之前的结点p，如果该结点存在并且待删除结点存在，则将指针变量q指向待删除结点（q=p->next），再连接要删除结点两边的结点（p->next=q->next），并使用free函数将q指向的内存空间进行释放。

单链表删除操作

/*单链表的删除操作*/
void Delete(LinkList head,int pos)
{Node *p=head,*q;int j=0;while(j<pos-1 && p)          //通过循环，找到第pos-1个结点的地址{p=p->next;j++;}if(p==NULL || p->next==NULL)   //第pos个结点不存在printf("the pos is ERROR!");else{q=p->next;                //q指向第pos个结点p->next=q->next;          //连接删除结点两边的结点free(q);                  //释放要删除结点的内存空间}
}

<4>链表的创建

创建链表前需要先创建结构体作为节点和头指针：

/*单链表的创建*/
typedef struct Node  //typedef方法函数可以对于struct Node进行重命名
{char name[20];int number;struct Node *next;}LNode,*LinkList;  //定义一个结构体指针方便后续的操作

<5>链表的查询

Search函数有两个参数，其中head表示链表的头指针，name表示要查找的值。定义指针变量p，使其从首元结点开始到链表结束。如果某结点的成员和给定不等，则继续查找下一个结点（p=p->next）。如果查找成功，则返回结点的地址值；若查找失败，则打印提示信息，并返回NULL。

/*单链表的查询*/
Node *Search(LinkList head,char name[])   //在单链表head中找到值为name的结点
{Node *p=head->next;while(p){if(strcmp(p->name,name)!=0)p=p->next;elsebreak;                          //查找成功}if(p==NULL)printf("没有找到值为%s的结点！"，name)；return p;
}

这里对单链表的插入等操作都是以创建一个链表表示班级，其中结点表示学生。