有那种网站的浏览器,wordpress调用当前分类文章,网站建设待遇,竞价推广账户竞价托管#x1f331;博客主页#xff1a;青竹雾色间. #x1f618;博客制作不易欢迎各位#x1f44d;点赞⭐收藏➕关注 ✨人生如寄#xff0c;多忧何为 ✨ 目录
前言
单链表的基本概念
节点
头节点
尾节点
单链表的基本操作
创建单链表
头插法#xff1a;
尾插法#… 博客主页青竹雾色间. 博客制作不易欢迎各位点赞⭐收藏➕关注 ✨人生如寄多忧何为 ✨ 目录
前言
单链表的基本概念
节点
头节点
尾节点
单链表的基本操作
创建单链表
头插法
尾插法
插入增操作 删除删操作
查找查操作
修改改操作
遍历链表
单链表的应用场景 前言
在本篇博客中我们将深入探索一种常见的数据结构——单链表。单链表是一种线性数据结构它由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是插入和删除操作非常简单但是查找和遍历操作可能会比较耗时。我们将学习单链表的基本概念、操作以及实现方式。 单链表的基本概念
下面我们来介绍一下单链表的基本概念和操作。 节点
单链表中的每个节点都包含两个部分数据域(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; // 将新节点的数据域设置为eif (p NULL) *head newNode; // 如果指定位置的前一个节点是空的则将新节点作为新的头结点else newNode-next p-next; // 否则将新节点插入到指定位置的前一个节点后面p-next newNode; // 将新节点插入到链表中
} 删除删操作 从单链表中删除一个节点重新连接链表中的其他节点。 若要删除的节点为头节点直接将头节点指向下一个节点即可。若要删除的节点不是头节点遍历链表找到该节点的前一个节点。将前一个节点的next指针指向要删除节点的下一个节点。 查找查操作 在单链表中查找特定的元素。 从头节点开始遍历链表逐个比较节点的数据与目标数据是否相等。若找到相等的节点则返回该节点或其他需要的信息。若遍历完整个链表仍未找到目标数据则表示目标数据不存在于链表中。 //在单链表中查找值为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;//计数器jwhile (p ! NULL){p p-next;j;}printf(%d, j);return 0;
} 修改改操作 更新单链表中节点的数据。 从头节点开始遍历链表逐个比较节点的数据与目标数据是否相等。若找到相等的节点则将该节点的数据更新为新的数据。 //链表内容的修改在链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {Node *pL-next;int i0;while(p){if(p-datax){p-datak;}pp-next;}return L;
} 遍历链表
在单链表中遍历链表的操作可以通过以下步骤实现
a. 从头结点开始遍历链表
b. 对于每个节点执行相应的操作(如打印数据元素)。
void Print(LinkList L)
{Node* p L-next;while (p) {printf(%c , p-data);p p-next;}
} 单链表的应用场景
单链表在实际的软件开发中有广泛的应用例如
数据库系统中的链表索引。 实现栈和队列等其他数据结构。图算法中的邻接表表示。
