前言
本期和大家主要分享的是關(guān)于數(shù)據(jù)結(jié)構(gòu)中雙向鏈表的實(shí)現(xiàn)過程，那么話不多說，來具體看看吧！
一、鏈表結(jié)構(gòu)體定義
來分析一下，這里呢定義了一個(gè)int的數(shù)據(jù)類型，表明整個(gè)鏈表存放的是整形的數(shù)據(jù)；其次定義了鏈表節(jié)點(diǎn)的數(shù)據(jù)類型，其中包括了此節(jié)點(diǎn)存放的數(shù)據(jù)以及鏈接向下一個(gè)節(jié)點(diǎn)的地址；最主要的呢我們的鏈表是有頭的（且鏈表類型結(jié)構(gòu)體中存放了當(dāng)前鏈表中的元素），并且鏈表頭（鏈表類型，并不是一個(gè)節(jié)點(diǎn)）后的第一個(gè)節(jié)點(diǎn)是空節(jié)點(diǎn)，我們的有效節(jié)點(diǎn)是從這個(gè)空節(jié)點(diǎn)后面的這個(gè)節(jié)點(diǎn)開始存放數(shù)據(jù)的；
#ifndef __LINKLIST_H__
#define __LINKLIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 存儲(chǔ)數(shù)據(jù)的類型 */
typedef int DataType;
/* 鏈表節(jié)點(diǎn)類型 */
typedef struct node
{
DataType Data; //數(shù)據(jù)域
struct node *pNext; //指向下一個(gè)節(jié)點(diǎn)的指針
}LinkNode;
/* 鏈表表頭類型 */
typedef struct list
{
LinkNode *pHead;
int clen;
}LinkList;
extern LinkList *CreateLinkList(void);
extern LinkList *InsertHeadLinkList(LinkList *pTmpList, DataType TmpData);
extern int ShowLinkList(LinkList *pTmpList);
extern LinkNode *SearchLinkList(LinkList *pTmpList, DataType TmpData);
extern int UpdateLinkList(LinkList *pTmpList, DataType OldData, DataType NewData);
extern int InsertTailLinkList(LinkList *pTmpList, DataType TmpData);
extern int DeleteLinkList(LinkList *pTmpList, DataType TmpData);
extern int DestroyLinkList(LinkList **ppTmpList);
extern LinkNode *FindMidLinkNode(LinkList *pTmpList);
extern int ReverseLinkList(LinkList *pTmpList);
extern int BubbleSort(LinkList *pTmpList);
extern int ChoiceSortLinkList(LinkList *pTmpList);
#endif
二、具體實(shí)現(xiàn)過程
下面呢具體來看一下數(shù)據(jù)結(jié)構(gòu)中鏈表的主要實(shí)現(xiàn)過程，其中包括了鏈表的創(chuàng)建，插入，刪除，修改以及銷毀，每個(gè)模塊的代碼如下：
#include "linklist.h"
/* 創(chuàng)建鏈表 */
LinkList *CreateLinkList(void)
{
LinkList *pTmpList = NULL
pTmpList = malloc(sizeof(LinkList));
if (NULL == pTmpList)
{
perror("fail to malloc");
return NULL;
}
pTmpList->clen = 0;
pTmpList->pHead = malloc(sizeof(LinkNode));
if (pTmpList->pHead == NULL)
{
perror("fail to malloc");
return NULL;
}
pTmpList->pHead->pNext = NULL;
return pTmpList;
}
/* 頭插法插入數(shù)據(jù) */
LinkList *InsertHeadLinkList(LinkList *pTmpList, DataType TmpData)
{
LinkNode *pTmpNode = NULL;
pTmpNode = malloc(sizeof(LinkNode));
if (NULL == pTmpNode)
{
perror("fail to malloc");
return NULL;
}
pTmpNode->Data = TmpData;
pTmpNode->pNext = pTmpList->pHead->pNext;
pTmpList->pHead->pNext = pTmpNode;
pTmpList->clen++;
return pTmpList;
}
/* 鏈表遍歷 */
int ShowLinkList(LinkList *pTmpList)
{
LinkNode *pTmpNode = NULL;
pTmpNode = pTmpList->pHead->pNext;
while (pTmpNode != NULL)
{
printf("%d ", pTmpNode->Data);
pTmpNode = pTmpNode->pNext;
}
putchar('\n');
return 0;
}
/* 查找元素 */
LinkNode *SearchLinkList(LinkList *pTmpList, DataType TmpData)
{
LinkNode *pTmpNode = NULL;
pTmpNode = pTmpList->pHead->pNext;
while (pTmpNode != NULL)
{
if (pTmpNode->Data == TmpData)
{
return pTmpNode;
}
pTmpNode = pTmpNode->pNext;
}
return NULL;
}
/* 修改元素 */
int UpdateLinkList(LinkList *pTmpList, DataType OldData, DataType NewData)
{
LinkNode *pTmpNode = NULL;
pTmpNode = pTmpList->pHead->pNext;
while (pTmpNode != NULL)
{
if (pTmpNode->Data == OldData)
{
pTmpNode->Data = NewData;
}
pTmpNode = pTmpNode->pNext;
}
return 0;
}
/* 尾插法插入元素 */
int InsertTailLinkList(LinkList *pTmpList, DataType TmpData)
{
LinkNode *pTmpNode = NULL;
LinkNode *pptmNode = NULL;
pTmpNode = pTmpList->pHead;
pptmNode = malloc(sizeof(LinkNode));
if (pptmNode == NULL)
{
perror("fail to malloc");
return -1;
}
while (pTmpNode->pNext != NULL) //訪問NULL的空間會(huì)段錯(cuò)誤，這個(gè)就是第一個(gè)節(jié)點(diǎn)存在的好處
{
pTmpNode = pTmpNode->pNext; //跳出后為最后一個(gè)節(jié)點(diǎn)
}
pptmNode->Data = TmpData;
pTmpNode->pNext = pptmNode;
pptmNode->pNext = NULL;
pTmpList->clen++;
return 0;
}
/* 刪除一個(gè)鏈表節(jié)點(diǎn)(所有相同的元素都刪除) */
int DeleteLinkList(LinkList *pTmpList, DataType TmpData)
{
LinkNode *preLinkNode = NULL;
LinkNode *desLinkNode = NULL;
preLinkNode = pTmpList->pHead;
desLinkNode = pTmpList->pHead->pNext;
while (desLinkNode != NULL)
{
if (desLinkNode->Data == TmpData)
{
preLinkNode->pNext = desLinkNode->pNext;
free(desLinkNode);
desLinkNode = preLinkNode->pNext;
pTmpList->clen--;
}
else
{
preLinkNode = preLinkNode->pNext;
desLinkNode = desLinkNode->pNext;
}
}
return 0;
}
/* 銷毀鏈表 */
int DestroyLinkList(LinkList **ppTmpList)
{
LinkNode *pFreeNode = NULL;
LinkNode *pTmpNode = NULL;
pFreeNode = (*ppTmpList)->pHead;
pTmpNode = (*ppTmpList)->pHead;
while (pTmpNode != NULL)
{
pTmpNode = pTmpNode->pNext;
free(pFreeNode);
pFreeNode = pTmpNode;
}
free(*ppTmpList);
*ppTmpList = NULL;
return 0;
}
/* 以下為鏈表的高級(jí)操作 */
/* 查找中間節(jié)點(diǎn) */
LinkNode *FindMidLinkNode(LinkList *pTmpList)
{
LinkNode *pFast = NULL;
LinkNode *pSlow = NULL;
pFast = pTmpList->pHead->pNext;
pSlow = pTmpList->pHead->pNext;
while (pFast != NULL)
{
pFast = pFast->pNext;
if (NULL == pFast)
{
break;
}
pFast = pFast->pNext; //快指針走兩步(分兩步,防止出現(xiàn)非法訪問地址)
if (NULL == pFast)
{
break;
}
pSlow = pSlow->pNext; //慢指針走一步
}
return pSlow;
}
/* 鏈表倒置(頭插法) */
/* 將鏈表斷開，再次用頭插法插入即可實(shí)現(xiàn)鏈表倒置 */
int ReverseLinkList(LinkList *pTmpList)
{
LinkNode *pTmpNode = NULL;
LinkNode *pInsertNode = NULL;
pTmpNode = pTmpList->pHead->pNext;
pTmpList->pHead->pNext = NULL;
while (pTmpNode != NULL)
{
pInsertNode = pTmpNode;
pTmpNode = pTmpNode->pNext;
pInsertNode->pNext = pTmpList->pHead->pNext;
pTmpList->pHead->pNext = pInsertNode;
}
return 0;
}
三、排序方法
這里給出兩種排序方法，可能大家用c語言實(shí)現(xiàn)排序的時(shí)候比較簡(jiǎn)單，但是過渡到數(shù)據(jù)結(jié)構(gòu)會(huì)有一點(diǎn)難度，這是沒有關(guān)系的，主要是多畫圖多理解多思考；幾遍下來比較難的問題就會(huì)變得容易許多；數(shù)據(jù)結(jié)構(gòu)中前面會(huì)學(xué)習(xí)到順序表和鏈?zhǔn)奖恚竺鏁?huì)緊接著學(xué)習(xí)順序棧和鏈?zhǔn)綏＃虼嗣康揭粋€(gè)地方，都可以自己手動(dòng)的去練習(xí)一下，這些都是一些最基本的模塊化的程序，在程序設(shè)計(jì)上可以根據(jù)自己的需要在定義數(shù)據(jù)類型時(shí)適當(dāng)進(jìn)行增加都是可以的；
1. 冒泡排序
/* 冒泡排序(最后一次不需要進(jìn)行比較) */
int BubbleSort(LinkList *pTmpList)
{
LinkNode *preTmpNode = NULL;
LinkNode *deTmpNode = NULL;
LinkNode *pEndTmpNode = NULL;
DataType TmpData = 0;
preTmpNode = pTmpList->pHead->pNext; //前一個(gè)指向第一個(gè)節(jié)點(diǎn)
if (preTmpNode == NULL || preTmpNode->pNext == NULL) //第一個(gè)節(jié)點(diǎn)沒存數(shù)據(jù)或者只有第一個(gè)節(jié)點(diǎn)存儲(chǔ)了數(shù)據(jù)不用排序
{
return 0;
}
deTmpNode = preTmpNode->pNext; //后一個(gè)指針指向第一個(gè)指針的下一個(gè)節(jié)點(diǎn)
while (deTmpNode != pEndTmpNode) //前一個(gè)指針和后一個(gè)指針不是同一個(gè)節(jié)點(diǎn)，pEndTmpNode為每次比較后的最后一個(gè)節(jié)點(diǎn)
{
while (deTmpNode != pEndTmpNode)
{
if (preTmpNode->Data > deTmpNode->Data)
{
TmpData = preTmpNode->Data;
preTmpNode->Data = deTmpNode->Data;
deTmpNode->Data = TmpData;
}
preTmpNode = preTmpNode->pNext;
deTmpNode = deTmpNode->pNext;
}
pEndTmpNode = preTmpNode;
preTmpNode = pTmpList->pHead->pNext;
deTmpNode = preTmpNode->pNext;
}
return 0;
}
2. 選擇排序
/* 選擇排序 */
int ChoiceSortLinkList(LinkList *pTmpList)
{
LinkNode *pMinNode = NULL; //每輪找出最小的一個(gè)，與pSwapNode交換值
LinkNode *pTmpNode = NULL; //每次從 pSwapNode的后一個(gè)開始往后尋找最小的數(shù)（與pMinNode比較）
LinkNode *pSwapNode = NULL; //每次尋找的開頭（前面已經(jīng)找好最小的數(shù)排列完畢）
DataType TmpData;
if (pTmpList->pHead->pNext == NULL || pTmpList->pHead->pNext->pNext == NULL) //如果空節(jié)點(diǎn)后面的第一個(gè)節(jié)點(diǎn)無元素或者之后的第二個(gè)節(jié)點(diǎn)無元素(全部鏈表只有一個(gè)元素)則不用排序
{
return 0;
}
pSwapNode = pTmpList->pHead->pNext;
while (pSwapNode->pNext != NULL)
{
pMinNode = pSwapNode; //每輪開始從 pSwapNode開始
pTmpNode = pSwapNode->pNext; //從后一個(gè)往后開始比較尋找比最小的還小的
while (pTmpNode != NULL)
{
if (pTmpNode->Data < pMinNode->Data)
{
pMinNode = pTmpNode; //找到后將最小的地址賦值給 pMinNode
}
pTmpNode = pTmpNode->pNext; //接著往后找
}
if (pMinNode != pSwapNode) //如果最小的不是第一個(gè)就交換，若是第一個(gè)則不用進(jìn)行操作
{
TmpData = pMinNode->Data;
pMinNode->Data = pSwapNode->Data;
pSwapNode->Data = TmpData;
}
pSwapNode = pSwapNode->pNext; //此位置已經(jīng)排列完畢，開始從下一個(gè)位置開始
}
return 0;
}
3. 判斷一個(gè)鏈表是否有環(huán)
/* 如何判斷一個(gè)鏈表是否有環(huán)（用快慢指針的方法） */
int IsCircleLinkList(LinkList *pTmpList, int *pn, LinkNode *ppNode) //未理解
{
LinkNode *pFast = NULL;
LinkNode *pSlow = NULL;
LinkNode *pTmpNode = NULL;
int cnt = 1;
pFast = pTmpList->pHead->pNext;
pSlow = pTmpList->pHead->pNext;
while (pFast != NULL)
{
pFast = pFast->pNext;
if (NULL == pFast)
{
return 0;
}
pFast = pFast->pNext;
if (NULL == pFast)
{
return 0;
}
pSlow = pSlow->pNext;
if (pFast == pSlow)
{
pTmpNode = pSlow->pNext;
while (pTmpNode != pSlow)
{
cnt++;
pTmpNode = pTmpNode->pNext;
}
*pn = cnt;
pFast = pTmpList->pHead->pNext;
while (1)
{
pSlow = pSlow->pNext;
pFast = pFast->pNext;
if (pSlow == pFast)
{
*ppNode = pSlow;
break;
}
}
return 1;
}
}
return 0;
}
總結(jié)
鏈表的優(yōu)點(diǎn)：原則上只要系統(tǒng)的內(nèi)存足夠大，那么鏈表能夠進(jìn)行無限存儲(chǔ)；而且存一個(gè)申請(qǐng)一個(gè)，不會(huì)提前占用空間，它是一種空間上不連續(xù)的存儲(chǔ)方式；文章來源：http://www.zghlxwxcb.cn/news/detail-787946.html
本期的分享就到這里結(jié)束啦，總結(jié)一下，鏈表是必須掌握的一種數(shù)據(jù)結(jié)構(gòu)，是閉著眼睛都要能寫出來的一種數(shù)據(jù)結(jié)構(gòu)，所以必須多練習(xí)，多思考；
最后，各位小伙伴們?nèi)绻矚g我的分享可以點(diǎn)贊收藏哦，你們的認(rèn)可是我創(chuàng)作的動(dòng)力，一起加油！文章來源地址http://www.zghlxwxcb.cn/news/detail-787946.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)中鏈表的實(shí)現(xiàn)以及排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語言][數(shù)據(jù)結(jié)構(gòu)][鏈表] 單鏈表的從零實(shí)現(xiàn)!](https://imgs.yssmx.com/Uploads/2024/04/847183-1.png)
