當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

数据结构与算法：单链表（超详细实现）

發布時間：2025/3/15 编程问答 21 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构与算法：单链表（超详细实现）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

實現算法預覽

這次博主寫的單鏈表主要實現了以下算法。所有功能可進行循環運行測試。歡迎各位指正。

LinkList.h

#pragma once #ifndef __LINKLIST_H__ #define __LINKLIST_H__ #define _CRT_SECURE_NO_WARNINGS typedef struct LinkNode LinkNode; typedef struct LinkNode {int data;LinkNode* next; }LinkNode;//初始化鏈表數據 LinkNode* initLinkList();//插入結點根據查詢的值的在其前面插入新的值 int insertLinkList(LinkNode* pHeader, int oldVal, int newVal);//獲取鏈表結點個數 int getLengthLinkList(LinkNode* pHeader);//遍歷鏈表進行打印結點 int printLinkList(LinkNode* pHeader);//刪除結點根據查詢的值刪除相應的結點 int deleteLinkList(LinkNode* pHeader, int val);//清空鏈表保留頭結點，仍然可以進行單鏈表相關操作 int clearLinkList(LinkNode* pHeader);//銷毀鏈表連頭結點都釋放 int destroyLinkList(LinkNode* pHeader);//loc 插入到鏈表的第幾個位置，從1開始 loc <=1 放在第一個位置，超過結點最后一個位置放在尾結點 int insertPositionLinkList(LinkNode* pHeader, int loc, int val);//刪除第loc位置的元素，loc 如果不合法（<1或>結點個數不刪除元素），通過指針將結點數據返回 int delPositionLinkList(LinkNode* pHeader, int loc, int* val);//鏈表反轉 int reverseLinkList(LinkNode* pHeader);//利用遞歸進行逆序遍歷 void printRerverseLinkList(LinkNode* pHeader);#endif // !__LINKLIST_H__

單鏈表簡要介紹

單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。

單鏈表代碼展示

LinkList.c

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include "LinkList.h"LinkNode* list = NULL; //初始化鏈表數據 LinkNode* initLinkList() {LinkNode *head = (LinkNode *)malloc(sizeof(LinkNode));LinkNode* cur = head;while (1){printf("請輸入結點數據（-1退出）：");int val = 0;scanf("%d", &val);if (val == -1){break;}LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));node->next = NULL;node->data = val;cur->next = node;cur = node;}return head; }//插入結點往查詢的值的前面插入新的值 int insertLinkList(LinkNode* pHeader, int oldVal, int newVal) {if (pHeader == NULL){return 0;}LinkNode* pre = pHeader;LinkNode* cur = pHeader->next;while (cur!=NULL){if (cur->data == oldVal){break;}pre = pre->next;cur = cur->next;}//創建新結點LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));newNode->data = newVal;newNode->next = NULL;pre->next = newNode;newNode->next = cur;return 1; } //獲取鏈表結點個數 int getLengthLinkList(LinkNode* pHeader) {if (pHeader == NULL){return 0;}LinkNode* cur = pHeader;int length = 0;while (cur->next != NULL){cur = cur->next;length++;}return length; }//打印結點 int printLinkList(LinkNode* pHeader) {if (pHeader == NULL){return 0;}if (pHeader->next == NULL){printf("當前鏈表為空！\n");}LinkNode* cur = pHeader->next;int num = 1;while (cur!=NULL){printf("第%d個結點data: %d\n", num, cur->data);cur = cur->next;num++;}return 0; } //刪除結點 int deleteLinkList(LinkNode* pHeader,int val) {if (pHeader == NULL){return 0;}LinkNode* pre = pHeader;LinkNode* cur = pHeader->next;while (cur != NULL){if (cur->data == val){break;}pre = pre->next;cur = cur->next;}if (cur != NULL){pre->next = cur->next;free(cur);cur = NULL;}return 1; } //清空鏈表保留頭結點 int clearLinkList(LinkNode* pHeader) {if (pHeader == NULL){return 0;}LinkNode* cur = pHeader->next;while (cur != NULL){LinkNode* next = cur->next;free(cur);cur = next;}pHeader->next = NULL;return 1; } //銷毀鏈表 int destroyLinkList(LinkNode* pHeader) {if (pHeader == NULL){return 0;}clearLinkList(pHeader);free(pHeader);return 1; } //loc 插入到鏈表的第幾個位置，從1開始 loc <=1 放在第一個位置，超過結點最后一個位置放在尾結點 int insertPositionLinkList(LinkNode* pHeader,int loc, int val) {if (pHeader == NULL){return 0;}LinkNode* cur = pHeader;int i = 1;while (cur->next!=NULL && i<loc){i++;cur = cur->next;}//cur 為插入元素的前驅結點LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));newNode->data = val;newNode->next = cur->next;cur->next = newNode;return 1; } //刪除第loc位置的元素，loc 如果不合法（<1或>結點個數不刪除元素），通過指針將結點數據返回 int delPositionLinkList(LinkNode* pHeader, int loc, int* val) {if (pHeader == NULL || loc < 1){return 0;}LinkNode* cur = pHeader;int i = 1;while (cur->next != NULL&&i<loc){i++;cur = cur->next;}//cur 為刪除元素的前驅結點if (i == loc && cur->next!=NULL){LinkNode* del = cur->next;*val = del->data;cur->next = del->next;free(del);del = NULL;return 1;}return 0; } //鏈表反轉 int reverseLinkList(LinkNode* pHeader) {if (pHeader == NULL){return 0;}LinkNode* pre = NULL;LinkNode* cur = pHeader->next;LinkNode* next = NULL;while (cur !=NULL){//保存當前節點的下一個結點next = cur->next;//將當前節點的next域指向前一個結點cur->next = pre;//pre、cur 往后移動pre = cur;cur = next;}//循環結束 pre 指向最后一個結點，將頭結點指向它pHeader->next = pre;return 1; }void printRerverseLinkList(LinkNode * pHeader) {LinkNode* cur = pHeader->next;if (cur == NULL){return;}printRerverseLinkList(cur);printf("%d ", cur->data); }void fun01_init() {list = initLinkList();printLinkList(list);return; } void fun02_valueInsert() {int oldVal = 0, newVal = 0;printf("請輸入查詢的值：");scanf("%d", &oldVal);printf("請輸入要插入值：");scanf("%d", &newVal);int ret = insertLinkList(list, oldVal, newVal);if (ret){printf("插入成功\n");}else{printf("插入失敗\n");}printLinkList(list);return; } void fun03_valueInsertPosition() {int loc = 0, newVal = 0;printf("請輸入插入的位置：");scanf("%d", &loc);printf("請輸入要插入值：");scanf("%d", &newVal);int ret = insertPositionLinkList(list, loc, newVal);if (ret){printf("插入成功\n");}else{printf("插入失敗\n");}printLinkList(list);return; } void fun04_valueDel() {int val = 0;printf("請輸入要刪除的值：");scanf("%d", &val);int ret = deleteLinkList(list,val);if (ret){printf("刪除成功\n");}else{printf("刪除失敗\n");}printLinkList(list);return; } void fun05_valueDelPosition() {int loc = 0,val = 0;printf("請輸入刪除元素的位置：");scanf("%d", &loc);int ret = delPositionLinkList(list, loc,&val);if (ret){printf("刪除成功,刪除元素的值：%d\n",val);}else{printf("刪除失敗\n");}printLinkList(list);return; } void fun06_reverseLinkList() {reverseLinkList(list);printLinkList(list);return; } void fun07_clearLinkList() {clearLinkList(list);return; } void fun08_destroyLinkList() {destroyLinkList(list);return; }int main(int argc, char *argv[]) {int menu = 0;while (1){printf("---菜單-----------------------\n");printf("---1、初始化鏈表--------------\n");printf("---2、通過結點值插入結點------\n");printf("---3、通過位置插入結點--------\n");printf("---4、通過結點值刪除結點------\n");printf("---5、通過位置刪除結點--------\n");printf("---6、反轉鏈表----------------\n");printf("---7、清空鏈表----------------\n");printf("---8、銷毀鏈表----------------\n");printf("---9、遍歷鏈表----------------\n");printf("--10、鏈表長度----------------\n");printf("--11、逆序遍歷----------------\n");printf("---0、退出--------------------\n請輸入:");scanf("%d",&menu);if (menu == 0){break;}switch (menu){case 1:fun01_init();break;case 2:fun02_valueInsert();break;case 3:fun03_valueInsertPosition();break;case 4:fun04_valueDel();break;case 5:fun05_valueDelPosition();break;case 6:fun06_reverseLinkList();break;case 7:fun07_clearLinkList();break;case 8:fun08_destroyLinkList();break;case 9:printLinkList(list);break;case 10:printf("鏈表元素個數：%d\n",getLengthLinkList(list));break;case 11:printRerverseLinkList(list);printf("\n");break;default:break;}}return 0; }

運行結果測試

???

總結

以上是生活随笔為你收集整理的数据结构与算法：单链表（超详细实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。