個(gè)人主頁 ： 水月夢(mèng)鏡花
個(gè)人專欄 ： 《C語言》 《數(shù)據(jù)結(jié)構(gòu)》
前言
本博客將要實(shí)現(xiàn)的無頭單向不循環(huán)鏈表。
一、單鏈表實(shí)現(xiàn)思路和圖解
1.節(jié)點(diǎn)的定義(SListNode)
我們將節(jié)點(diǎn)定義為如下結(jié)構(gòu)：
其成員變量有data，next。
將int重命名為STLDataType，方便我們以后修改數(shù)據(jù)域的內(nèi)容。
//無頭單向不循環(huán)鏈表
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
2.申請(qǐng)一個(gè)節(jié)點(diǎn)(BuySListNode)
動(dòng)態(tài)申明一個(gè)空間，來放置數(shù)據(jù)。如下：
將data的內(nèi)容置成形參x，next置NULL。
//申請(qǐng)一個(gè)節(jié)點(diǎn)
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
retur
3.單鏈表打印(SListPrint)
循環(huán)遍歷鏈表，直到尾節(jié)點(diǎn)。創(chuàng)建一個(gè)結(jié)構(gòu)體指針變量cur，循環(huán)cur = cur->next，并打印cur->data的內(nèi)容，直到cur == NULL。
//單鏈表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
4.單鏈表尾插(SListPushBack)
- 如果鏈表不為NULL(鏈表中有元素)，要先遍歷鏈表找到尾節(jié)點(diǎn)，在讓尾節(jié)點(diǎn)指向新節(jié)點(diǎn)，完成尾插。
- 如果鏈表為NULL(鏈表中沒有元素)，此時(shí)應(yīng)該直接讓新節(jié)點(diǎn)等于頭結(jié)點(diǎn)，完成尾插。(本鏈表是無哨兵位的)
- 如果傳入的頭結(jié)點(diǎn)無效，直接判錯(cuò)。
當(dāng)鏈表為NULL，我們就要修改頭結(jié)點(diǎn)本身的內(nèi)容，所以我們需要頭結(jié)點(diǎn)的指針，而本文中頭結(jié)點(diǎn)本身就是結(jié)構(gòu)體指針，所以尾插函數(shù)參數(shù)我們需要二級(jí)指針。
//單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
if (*pplist != NULL)
{
SListNode* cur = *pplist;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
else
{
*pplist = newnode;
}
}
5.單鏈表的頭插(SListPushFront)
對(duì)于頭插而言，鏈表是否有元素并不重要，我們只需要讓新節(jié)點(diǎn)的指向頭結(jié)點(diǎn)，并將頭結(jié)點(diǎn)等于新節(jié)點(diǎn)。
因?yàn)轭^插鏈表，一定會(huì)改變頭結(jié)點(diǎn)的內(nèi)容，所以我們頭插函數(shù)的形參也是二級(jí)指針。
//單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
6.單鏈表的尾刪(SListPopBack)
- 如果鏈表元素有兩個(gè)及兩以上，我們需要兩個(gè)指針變量prev，next來找尾節(jié)點(diǎn)，循環(huán)prev = cur，cur = cur->next，使next指向尾節(jié)點(diǎn)，prev指向尾節(jié)點(diǎn)的前一個(gè)，free尾節(jié)點(diǎn)，prev指向的節(jié)點(diǎn)指向NULL。
- 如果鏈表元素只有一個(gè)，直接free頭結(jié)點(diǎn)，使頭結(jié)點(diǎn)置NULL。
- 如果鏈表沒有元素，直接判錯(cuò)。
當(dāng)鏈表元素只有一個(gè)時(shí)，此時(shí)尾刪鏈表，要修改頭結(jié)點(diǎn)的內(nèi)容，尾刪函數(shù)的形參需要二級(jí)指針。
//單鏈表的尾刪
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//鏈表為NULL
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* cur = *pplist;
SListNode* prev = NULL;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
free(cur);
}
}
7.單鏈表頭刪(SListPopFront)
我們需要一個(gè)結(jié)構(gòu)體指針變量next，來保存頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后free頭結(jié)點(diǎn)，使頭結(jié)點(diǎn) = 指針變量next。
- 如果鏈表沒有元素，直接判錯(cuò)。
//單鏈表頭刪
void SListPopFront(SListNode** pplist)
{
assert(pplist);
assert(*pplist);
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
8.單鏈表的查找(SListFind)
我們需要一個(gè)結(jié)構(gòu)體指針變量cur，來遍歷鏈表比較cur->data == x，如果相等，放回此時(shí)cur的內(nèi)容(該節(jié)點(diǎn)的地址)。如果遍歷完鏈表，并沒有相等元素，放回NULL。
//單鏈表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
9.單鏈表在pos位置之后插入x(SListInsertAfter)
我們讓newnode指向pos下一個(gè)的節(jié)點(diǎn)，pos指向newnode。
- 如果我們先讓pos指向newnode，newnode在指向pos的下一個(gè)節(jié)點(diǎn)，就會(huì)造成newnode指向自己，導(dǎo)致鏈表成環(huán)。
- 該函數(shù)不會(huì)影響頭結(jié)點(diǎn)的內(nèi)容，所以函數(shù)的形參不用二級(jí)指針。
//單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
10.單鏈表刪除在pos位置之后的值(SListEraseAfter)
我們需要一個(gè)結(jié)構(gòu)體指針變量next，記錄pos下一個(gè)節(jié)點(diǎn)的地址，然后是pos指向next的下一個(gè)節(jié)點(diǎn)，接著free(next)。
- 如果鏈表只有一個(gè)元素，我們不能調(diào)用該函數(shù)，否則會(huì)導(dǎo)致NULL指針的解引用。
- 該函數(shù)不會(huì)改變頭結(jié)點(diǎn)的內(nèi)容，所以形參我們不用二級(jí)指針。
//單鏈表刪除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos && pos->next);
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
11.單鏈表的銷毀(SListDestroy)
我們需要兩個(gè)結(jié)構(gòu)體指針prev，cur。先讓prev = cur ，cur再指向下一個(gè)節(jié)點(diǎn)，free(prev)，重復(fù)上述操作，直到cur指向NULL。
需要我們?cè)诤瘮?shù)調(diào)用完后，自己對(duì)頭結(jié)點(diǎn)置NULL。
//單鏈表的銷毀
void SListDestroy(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur != NULL)
{
SListNode* prev = cur;
cur = cur->next;
free(prev);
}
}
二、代碼實(shí)現(xiàn)
//slist.h 文件
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//無頭單向不循環(huán)鏈表
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SListNode;
//申請(qǐng)一個(gè)節(jié)點(diǎn)
SListNode* BuySListNode(SLTDataType x);
//單鏈表打印
void SListPrint(SListNode* plist);
//單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
//單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDataType x);
//單鏈表的尾刪
void SListPopBack(SListNode** pplist);
//單鏈表頭刪
void SListPopFront(SListNode** pplist);
//單鏈表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
//單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
//單鏈表刪除在pos位置之后的值
void SListEraseAfter(SListNode* pos);
//單鏈表的銷毀
void SListDestroy(SListNode* plist);
//slist.c 文件
#include "slist.h"
//申請(qǐng)一個(gè)節(jié)點(diǎn)
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//單鏈表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
if (*pplist != NULL)
{
SListNode* cur = *pplist;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
else
{
*pplist = newnode;
}
}
//單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
//單鏈表的尾刪
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//鏈表為NULL
assert(*pplist);
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SListNode* cur = *pplist;
SListNode* prev = NULL;
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
prev->next = NULL;
free(cur);
}
}
//單鏈表頭刪
void SListPopFront(SListNode** pplist)
{
assert(pplist);
assert(*pplist);
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
//單鏈表的查找
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//單鏈表刪除在pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos && pos->next);
SListNode* next = pos->next;
pos->next = next->next;
free(next);
}
//單鏈表的銷毀
void SListDestroy(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur != NULL)
{
SListNode* prev = cur;
cur = cur->next;
free(prev);
}
}
總結(jié)
以上就是我對(duì)于無頭單向不循環(huán)鏈表的實(shí)現(xiàn)?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-624210.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-624210.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：?jiǎn)捂湵淼膶?shí)現(xiàn)(C語言)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
