深入理解數(shù)據(jù)結(jié)構(gòu)中的單向鏈表
————后面附有全部代碼————
數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)中扮演著重要角色，它用于組織和管理數(shù)據(jù)，提高數(shù)據(jù)的操作和訪問效率。單向鏈表是一種簡單但非常重要的數(shù)據(jù)結(jié)構(gòu)。本文將深入探討單向鏈表的定義、特點、基本操作。
一、什么是單向鏈表？
單向鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點組成。每個節(jié)點包含兩個部分：數(shù)據(jù)和指向下一個節(jié)點的引用（也稱為指針）。節(jié)點之間通過這個引用連接在一起，形成鏈表結(jié)構(gòu)。最后一個節(jié)點的引用指向空值，表示鏈表的結(jié)束。
二、單向鏈表的特點：
有空狀態(tài)（只有頭節(jié)點）但沒有滿狀態(tài)（理論上是可以無限裝節(jié)點）
優(yōu)點
動態(tài)性：單向鏈表的長度可以動態(tài)地增加或減少，相比于靜態(tài)數(shù)據(jù)結(jié)構(gòu)，它更加靈活。
插入和刪除操作高效：由于單向鏈表的節(jié)點包含了指向下一個節(jié)點的引用，插入和刪除操作只需要修改節(jié)點的引用，時間復(fù)雜度為O(1)。
缺點
隨機(jī)訪問（修改和查詢）低效：單向鏈表只能從頭節(jié)點開始，按照順序一個一個地訪問節(jié)點，因此在查找特定節(jié)點時效率較低，時間復(fù)雜度為O(n)。
三、單向鏈表的基本操作：
①創(chuàng)建鏈表頭節(jié)點
②判斷鏈表是否為空
③插入元素（1.在頭節(jié)點插入、2.在尾節(jié)點插入、3.在任意位置插入）
④刪除元素（1.刪除頭節(jié)點、2.刪除尾節(jié)點、3.刪除任意節(jié)點）
⑤查找元素（1.按值查找下標(biāo)、2. 按下標(biāo)查找值）
⑥修改元素（1.按下標(biāo)修改對應(yīng)元素值、2.按原值修改新值）
⑦獲取鏈表長度
⑧遍歷鏈表
⑩清空表
四、分析
①創(chuàng)建鏈表頭節(jié)點
②判斷鏈表是否為空
③插入元素（1.在頭節(jié)點插入、2.在尾節(jié)點插入、3.在任意位置插入）
1.在頭節(jié)點插入
2.在尾節(jié)點插入
3.在任意位置插入
④刪除元素（1.刪除頭節(jié)點、2.刪除尾節(jié)點、3.刪除任意節(jié)點）
1.刪除頭節(jié)點
2.刪除尾節(jié)點
3.刪除任意節(jié)點
⑤查找元素（1.按值查找、2. 按下標(biāo)查找）
⑥修改元素（1.按下標(biāo)修改對應(yīng)元素值、2.按原值修改新值）
1.按下標(biāo)修改對應(yīng)元素值
2.按原值修改新值
⑦獲取鏈表長度
⑧遍歷鏈表
⑩清空表
全部代碼
①接口文件linklist.h、②接口實現(xiàn)文件linklist.c、③主函數(shù)文件linklist_main.c
①linklist.h
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
#define typData int //宏定義數(shù)據(jù)類型，取別名為typData
// 鏈表節(jié)點結(jié)構(gòu)體
typedef struct Node {
typData data;// 節(jié)點數(shù)據(jù)
int tail;//記錄節(jié)點數(shù)
struct Node *next;//指向下一個節(jié)點的指針
} Linklist, *Plinklist;
// 創(chuàng)建鏈表
Plinklist createLinkedList(Plinklist *list);
// 判斷鏈表是否為空
int isEmpty(Plinklist list);
// 在鏈表頭部插入元素
void insertAtHead(Plinklist list, typData value);
// 在鏈表尾部插入元素
void insertAtTail(Plinklist list, typData value);
// 在指定位置插入元素
void insertAtPosition(Plinklist list, int position, typData value);
// 刪除頭節(jié)點
void deleteHead(Plinklist list);
// 刪除尾節(jié)點
void deleteTail(Plinklist list);
// 刪除指定位置的節(jié)點
void deleteAtPosition(Plinklist list, int position);
// 按值查找節(jié)點的位置
int findPositionByValue(Plinklist list, typData value);
// 按下標(biāo)查找節(jié)點的值
int findValueByPosition(Plinklist list, int position);
// 修改指定位置的節(jié)點值
void modifyByPosition(Plinklist list, int position, typData value);
// 修改指定值的節(jié)點值
void modifyValue(Plinklist list, typData oidValue, typData newValue);
// 獲取鏈表長度
int getLength(Plinklist list);
// 遍歷鏈表并打印節(jié)點值
void traverse(Plinklist list);
// 清空鏈表
void clearList(Plinklist list);
#endif
②接口實現(xiàn)文件linklist.c
#include "linklist.h"
// 初始（創(chuàng)建）化鏈表
Plinklist createLinkedList(Plinklist *list) {
*list = (Plinklist)malloc(sizeof(Linklist)); // 創(chuàng)建頭節(jié)點,頭節(jié)點不存放數(shù)據(jù)
if((*list == NULL)){
perror("cretelinklist malloc");
}
(*list)->tail = 0;
(*list)->next = NULL; // 頭節(jié)點的下一個節(jié)點置為空
return *list;
}
// 判斷鏈表是否為空
int isEmpty(Plinklist list) {
if(list == NULL || list->tail == 0){
return 1;//真空
}else{
return 0;//非空
}
//return list->next == NULL;
}
// 在頭部插入節(jié)點
void insertAtHead(Plinklist list, typData value) {
if(list == NULL){
puts("insert head arg err");
return ;
}
Plinklist newNode = (Plinklist)malloc(sizeof(Linklist)); // 創(chuàng)建新節(jié)點
if(newNode == NULL){
perror("insert head malloc");
return ;
}
newNode->data = value; // 設(shè)置新節(jié)點的數(shù)據(jù)值
newNode->next = list->next; // 新節(jié)點的下一個節(jié)點指向原頭節(jié)點的下一個節(jié)點
list->next = newNode; // 頭節(jié)點的下一個節(jié)點指向新節(jié)點，實現(xiàn)插入操作
list->tail++;
}
// 在尾部插入節(jié)點
void insertAtTail(Plinklist list, typData value) {
Plinklist newNode = (Plinklist)malloc(sizeof(Linklist)); // 創(chuàng)建新節(jié)點
newNode->data = value; // 設(shè)置新節(jié)點的數(shù)據(jù)值
Plinklist current = list; // 從頭節(jié)點開始遍歷鏈表，找到尾節(jié)點
while (current->next != NULL) {
current = current->next;
}
newNode->next = NULL; // 新節(jié)點的下一個節(jié)點置為空
current->next = newNode; // 尾節(jié)點的下一個節(jié)點指向新節(jié)點，實現(xiàn)插入操作
}
// 在任意位置插入節(jié)點
void insertAtPosition(Plinklist list, int position, typData value) {
if (position < 0) {
printf("無效的插入位置\n");
return;
}
Plinklist newNode = (Plinklist)malloc(sizeof(Linklist)); // 創(chuàng)建新節(jié)點
newNode->data = value; // 設(shè)置新節(jié)點的數(shù)據(jù)值
Plinklist current = list; // 從頭節(jié)點開始遍歷鏈表，找到插入位置的前一個節(jié)點
int count = 0;
while (current != NULL && count < position - 1) {
current = current->next;
count++;
}
if (current == NULL) {
printf("無效的插入位置\n");
return;
}
newNode->next = current->next; // 新節(jié)點的下一個節(jié)點指向插入位置的節(jié)點
current->next = newNode; // 插入位置的前一個節(jié)點的下一個節(jié)點指向新節(jié)點，實現(xiàn)插入操作
}
// 刪除頭節(jié)點
void deleteHead(Plinklist list) {
if (isEmpty(list)) {
printf("鏈表為空，無法刪除頭節(jié)點\n");
return;
}
Plinklist head = list->next; // 保存頭節(jié)點的下一個節(jié)點
list->next = head->next; // 頭節(jié)點的下一個節(jié)點指向頭節(jié)點的下下一個節(jié)點，實現(xiàn)刪除操作
free(head); // 釋放頭節(jié)點的內(nèi)存
}
// 刪除尾節(jié)點
void deleteTail(Plinklist list) {
if (isEmpty(list)) {
printf("鏈表為空，無法刪除尾節(jié)點\n");
return;
}
Plinklist current = list; // 從頭節(jié)點開始遍歷鏈表，找到尾節(jié)點的前一個節(jié)點
while (current->next != NULL && current->next->next != NULL) {
current = current->next;
}
Plinklist tail = current->next; // 保存尾節(jié)點
current->next = NULL; // 尾節(jié)點的前一個節(jié)點的下一個節(jié)點置為空，實現(xiàn)刪除操作
free(tail); // 釋放尾節(jié)點的內(nèi)存
}
// 刪除任意位置的節(jié)點
void deleteAtPosition(Plinklist list, int position) {
if (isEmpty(list)) {
printf("鏈表為空，無法刪除節(jié)點\n");
return;
}
Plinklist current = list; // 從頭節(jié)點開始遍歷鏈表，找到要刪除節(jié)點的前一個節(jié)點
int count = 0;
while (current->next != NULL && count < position - 1) {
current = current->next;
count++;
}
if (current->next == NULL) {
printf("無效的刪除位置\n");
return;
}
Plinklist nodeToDelete = current->next; // 保存要刪除的節(jié)點
current->next = nodeToDelete->next; // 要刪除節(jié)點的前一個節(jié)點的下一個節(jié)點指向要刪除節(jié)點的后一個節(jié)點，實現(xiàn)刪除操作
free(nodeToDelete); // 釋放要刪除節(jié)點的內(nèi)存
}
// 按值查找元素的下標(biāo)
int findPositionByValue(Plinklist list, typData value) {
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
int position = 0;
while (current != NULL) {
if (current->data == value) {
return position; // 找到節(jié)點的數(shù)據(jù)值等于目標(biāo)值，返回節(jié)點的下標(biāo)
}
current = current->next;
position++;
}
return -1; // 未找到目標(biāo)值，返回-1
}
// 按下標(biāo)查找元素的值
int findValueByPosition(Plinklist list, int position) {
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
int count = 0;
while (current != NULL && count < position) {
current = current->next;
count++;
}
if (current == NULL) {
printf("無效的下標(biāo)\n");
return -1;
}
return current->data; // 返回找到的節(jié)點的數(shù)據(jù)值
}
// 修改指定位置的節(jié)點值
void modifyByPosition(Plinklist list, int position,typData value){
if (isEmpty(list)) {
printf("鏈表為空，無法修改元素\n");
return;
}
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
int count = 0;
while (current != NULL && count < position) {
current = current->next;
count++;
}
if (current == NULL) {
printf("無效的下標(biāo)\n");
return;
}
current->data = value; // 修改節(jié)點的數(shù)據(jù)值
}
// 修改指定值的節(jié)點值
void modifyValue(Plinklist list, typData oldValue, typData newValue) {
if (isEmpty(list)) {
printf("鏈表為空，無法修改節(jié)點值\n");
return;
}
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
while (current != NULL) {
if (current->data == oldValue) {
current->data = newValue; // 找到節(jié)點的數(shù)據(jù)值等于舊值，更新節(jié)點的數(shù)據(jù)值為新值
return;
}
current = current->next;
}
printf("未找到目標(biāo)值\n");
}
// 獲取鏈表長度
int getLength(Plinklist list) {
if(list == NULL){
puts("getLength arg err");
return -1;
}
if(isEmpty(list)){
puts("表為空,長度為0");
return -1;
}
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
return list->tail;
}
// 遍歷鏈表
void traverse(Plinklist list) {
if(list == NULL){
puts("traverse arg eer");
return ;
}
if (isEmpty(list)) {
printf("鏈表為空\n");
return;
}
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 清空鏈表并釋放內(nèi)存
void clearList(Plinklist list) {
Plinklist current = list->next; // 從第一個節(jié)點開始遍歷鏈表
while (current != NULL) {
Plinklist temp = current;
current = current->next;
free(temp); // 釋放節(jié)點的內(nèi)存
}
list->next = NULL; // 頭節(jié)點的下一個節(jié)點置為空，鏈表清空
}
③主函數(shù)文件linklist_main.c文章來源：http://www.zghlxwxcb.cn/news/detail-796461.html
#include "linklist.h"
#include "linklist.c"
int main() {
Plinklist list;
createLinkedList(&list);
int choice, value, position, oldValue, newValue;
while (1) {
printf("\n*****************************鏈表操作菜單*****************************\n");
printf("1. 在頭部插入元素 2. 在尾部插入元素 3. 在任意位置插入元素\n");
printf("4. 刪除頭節(jié)點 5. 刪除尾節(jié)點 6. 刪除任意位置的節(jié)點\n");
printf("7. 按值查找元素的位置 8. 按位置查找元素的值 9. 修改指定位置的節(jié)點值\n");
printf("10. 修改指定值的節(jié)點值 11. 獲取鏈表長度 12. 遍歷鏈表\n");
printf("13. 清空鏈表并退出程序\n");
printf("*********************************************************************\n");
printf("請輸入操作編號：");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("請輸入要插入的元素值：");
scanf("%d", &value);
insertAtHead(list, value);
traverse(list);
break;
case 2:
printf("請輸入要插入的元素值：");
scanf("%d", &value);
insertAtTail(list, value);
traverse(list);
break;
case 3:
printf("請輸入要插入的位置下標(biāo)：");
scanf("%d", &position);
printf("請輸入要插入的元素值：");
scanf("%d", &value);
insertAtPosition(list, position, value);
traverse(list);
break;
case 4:
deleteHead(list);
traverse(list);
break;
case 5:
deleteTail(list);
traverse(list);
break;
case 6:
printf("請輸入要刪除的位置下標(biāo)：");
scanf("%d", &position);
deleteAtPosition(list, position);
traverse(list);
break;
case 7:
printf("請輸入要查找的元素值：");
scanf("%d", &value);
position = findPositionByValue(list, value);
if (position != -1) {
printf("元素值 %d 的位置下標(biāo)是：%d\n", value, position);
}
break;
case 8:
printf("請輸入要查找的位置下標(biāo)：");
scanf("%d", &position);
value = findValueByPosition(list, position);
if (value != -1) {
printf("位置下標(biāo) %d 上的元素值是：%d\n", position, value);
}
break;
case 9:
printf("請輸入要修改的位置下標(biāo)：");
scanf("%d", &position);
printf("請輸入修改后的元素值下標(biāo)：");
scanf("%d", &value);
modifyByPosition(list, position, value);
traverse(list);
break;
case 10:
printf("請輸入要修改的元素值：");
scanf("%d", &oldValue);
printf("請輸入修改后的元素值：");
scanf("%d", &newValue);
modifyValue(list, oldValue, newValue);
traverse(list);
break;
case 11:
printf("鏈表的長度是：%d\n", getLength(list));
break;
case 12:
traverse(list);
break;
case 13:
clearList(list);
exit(0);
default:
printf("無效的操作編號！\n");
break;
}
}
return 0;
}
五、結(jié)論：
單向鏈表作為一種常見的數(shù)據(jù)結(jié)構(gòu)，在計算機(jī)科學(xué)和軟件開發(fā)中有著廣泛的應(yīng)用。通過理解單向鏈表的定義、特點和基本操作，我們可以更好地應(yīng)用它來解決實際問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-796461.html
到了這里，關(guān)于四、數(shù)據(jù)結(jié)構(gòu)——單向鏈表的基本操作詳解：創(chuàng)建、插入（頭插法、尾插法、任意點插法）、刪除（頭刪法、尾刪法、任意位置刪法）、查詢（按值查下標(biāo)、按下標(biāo)查值）、遍歷鏈表和清空鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
