?
??博客主頁：青竹霧色間.
??博客制作不易歡迎各位??點贊+?收藏+?關注
??人生如寄，多憂何為??
目錄
前言
單鏈表的基本概念
節(jié)點
頭節(jié)點
尾節(jié)點
單鏈表的基本操作
創(chuàng)建單鏈表
頭插法：
尾插法：
插入（增）操作
?刪除（刪）操作：
查找（查）操作：
修改（改）操作：
遍歷鏈表
單鏈表的應用場景
前言
在本篇博客中，我們將深入探索一種常見的數(shù)據(jù)結構——單鏈表。單鏈表是一種線性數(shù)據(jù)結構，它由一系列節(jié)點組成，每個節(jié)點包含一個數(shù)據(jù)元素和一個指向下一個節(jié)點的指針。單鏈表的特點是插入和刪除操作非常簡單，但是查找和遍歷操作可能會比較耗時。我們將學習單鏈表的基本概念、操作以及實現(xiàn)方式。
單鏈表的基本概念
下面我們來介紹一下單鏈表的基本概念和操作。
-
節(jié)點
單鏈表中的每個節(jié)點都包含兩個部分：數(shù)據(jù)域(DATA)和指針域(NEXT)。
數(shù)據(jù)域用于存儲數(shù)據(jù)元素可以是數(shù)組，可以是int，甚至可以是結構體，
指針域用于存儲指向下一個節(jié)點的指針。
typedef int ElemType; //定義單鏈表結構
typedef struct Node{
ElemType data;//數(shù)據(jù)域
struct Node *next;//指針域
} LinkList;//初始化-
頭節(jié)點
單鏈表的第一個節(jié)點稱為頭節(jié)點，它不包含任何數(shù)據(jù)元素，只包含一個指向第一個節(jié)點的指針。在單鏈表中，頭節(jié)點通常被定義為全局變量或者靜態(tài)變量。
//創(chuàng)建頭結點，并將數(shù)據(jù)存入頭結點中
LinkList CreateList(ElemType n){
LinkList head = (LinkList)malloc(sizeof(struct Node));
head->data = n;
head->next = NULL;
return head;
}-
尾節(jié)點
單鏈表的最后一個節(jié)點稱為尾節(jié)點，它也不包含任何數(shù)據(jù)元素，只包含一個指向最后一個節(jié)點的指針。在單鏈表中，尾節(jié)點通常被定義為全局變量或者靜態(tài)變量。
鏈表的尾節(jié)點NEXT指向NULL（空），因為尾部沒有任何可以指向的空間了.
單鏈表的基本操作
單鏈表是一種常見的數(shù)據(jù)結構，支持以下四種基本操作：插入（增）、刪除（刪）、查找（查）、修改（改）。下面將逐一介紹這些操作的實現(xiàn)方法。
創(chuàng)建單鏈表
頭插法：
我們首先創(chuàng)建一個頭結點，然后將新節(jié)點插入到頭結點的后面。具體實現(xiàn)時，我們可以使用指針來遍歷鏈表，找到最后一個節(jié)點，然后將新節(jié)點插入到該節(jié)點的后面。這樣就可以保證新節(jié)點始終位于鏈表的頭部。
// 頭插法
Node* insertAtHead(Node *head, int data) {
Node *newNode = (Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = head;
return newNode;
}尾插法：
我們首先創(chuàng)建一個頭結點，然后將新節(jié)點插入到頭結點的后面。具體實現(xiàn)時，我們可以使用指針來遍歷鏈表，找到最后一個節(jié)點，然后將新節(jié)點插入到該節(jié)點的后面。這樣就可以保證新節(jié)點始終位于鏈表的尾部。
// 尾插法
Node* insertAtTail(Node *head, int data) {
Node *newNode = (Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (head == NULL) { // 如果鏈表為空，則直接將新節(jié)點作為頭結點。
newNode->next = NULL;
return newNode;
} else if (head->next == NULL) { // 如果鏈表只有一個元素，則直接將新節(jié)點插入到該元素后面。
head->next = newNode;
return head;
} else { // 否則，找到最后一個節(jié)點，然后將新節(jié)點插入到該節(jié)點的后面。
Node *temp = head;
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
return head;
}
}-
插入（增）操作
? ? ? ? ? 在單鏈表中插入一個新節(jié)點，將其鏈接到鏈表中的其他節(jié)點。
// 在指定位置插入一個新節(jié)點
void insertAtPos(Node** head, int pos, ElemType e) {
Node* p = *head;
int i = 1; // i表示當前節(jié)點的位置，從第二個節(jié)點開始計算
while (i < pos && p != NULL) p = p->next, i++; // 從第二個節(jié)點開始遍歷到指定位置的前一個節(jié)點
Node* newNode = (Node*)malloc(sizeof(struct Node));
if (newNode == NULL) exit(0); // 如果分配失敗則退出程序
newNode->data = e; // 將新節(jié)點的數(shù)據(jù)域設置為e
if (p == NULL) *head = newNode; // 如果指定位置的前一個節(jié)點是空的，則將新節(jié)點作為新的頭結點
else newNode->next = p->next; // 否則將新節(jié)點插入到指定位置的前一個節(jié)點后面
p->next = newNode; // 將新節(jié)點插入到鏈表中
}
-
?刪除（刪）操作：
?????????從單鏈表中刪除一個節(jié)點，重新連接鏈表中的其他節(jié)點。
- 若要刪除的節(jié)點為頭節(jié)點，直接將頭節(jié)點指向下一個節(jié)點即可。
- 若要刪除的節(jié)點不是頭節(jié)點，遍歷鏈表找到該節(jié)點的前一個節(jié)點。
- 將前一個節(jié)點的
next指針指向要刪除節(jié)點的下一個節(jié)點。
?
-
查找（查）操作：
????????在單鏈表中查找特定的元素。
- 從頭節(jié)點開始遍歷鏈表，逐個比較節(jié)點的數(shù)據(jù)與目標數(shù)據(jù)是否相等。
- 若找到相等的節(jié)點，則返回該節(jié)點或其他需要的信息。
- 若遍歷完整個鏈表仍未找到目標數(shù)據(jù)，則表示目標數(shù)據(jù)不存在于鏈表中。
//在單鏈表中查找值為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("該數(shù)值不在鏈表里。\n");
return 0;
}
}//求單鏈表的長度
int ListLength(LinkList L)
{
Node* p;
p = L->next;
int j = 0;//計數(shù)器j
while (p != NULL)
{
p = p->next;
j++;
}
printf("%d", j);
return 0;
}-
修改（改）操作：
????????更新單鏈表中節(jié)點的數(shù)據(jù)。
- 從頭節(jié)點開始遍歷鏈表，逐個比較節(jié)點的數(shù)據(jù)與目標數(shù)據(jù)是否相等。
- 若找到相等的節(jié)點，則將該節(jié)點的數(shù)據(jù)更新為新的數(shù)據(jù)。
//鏈表內容的修改，在鏈表中修改值為x的元素變?yōu)闉閗。
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;
}-
遍歷鏈表
在單鏈表中，遍歷鏈表的操作可以通過以下步驟實現(xiàn)：
a. 從頭結點開始遍歷鏈表；
b. 對于每個節(jié)點，執(zhí)行相應的操作(如打印數(shù)據(jù)元素)。
void Print(LinkList L)
{
Node* p = L->next;
while (p)
{
printf("%c ", p->data);
p = p->next;
}
}單鏈表的應用場景
單鏈表在實際的軟件開發(fā)中有廣泛的應用，例如：
- 數(shù)據(jù)庫系統(tǒng)中的鏈表索引。
文章來源：http://www.zghlxwxcb.cn/news/detail-475220.html
- 實現(xiàn)棧和隊列等其他數(shù)據(jù)結構。
- 圖算法中的鄰接表表示。
文章來源地址http://www.zghlxwxcb.cn/news/detail-475220.html
到了這里，關于深入淺出：單鏈表的實現(xiàn)和應用的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
