C語言中單鏈表(不帶頭結點)基本操作的實現詳解
更新時間：2022年11月14日 11:36:24 作者：蝸牛牛啊
鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。本文主要和大家聊聊C語言中單鏈表(不帶頭結點)的基本操作，感興趣的小伙伴可以了解一下
通過對順序表的學習，我們可以發(fā)現順序表有以下幾點缺陷：
1.空間不夠時需要擴容，擴容尤其是用realloc進行異地擴容時，是有一定代價的，其次還可能存在一定空間浪費。
2.頭部或者中間插入刪除，需要挪動數據，效率低下。
那我們可以對其所具有的缺陷進行優(yōu)化：可以按需申請空間同時插入刪除時不挪動數據。而單鏈表就符合這些優(yōu)化所具有特點。但是我們要注意的是單鏈表具有這些優(yōu)點并不代表鏈表就可以完全替代順序表。
一、單鏈表的概念
鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
從上圖可以看出，鏈式結構在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)，物理結構中指針域存儲的是下一個結點的地址；而且鏈式結構的結點一般都是從堆上申請出來的；從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續(xù)，也可能不連續(xù)。鏈表存儲數據的區(qū)域可分為數據域和指針域：
用代碼表示鏈表中的數據域和指針域如下：
typedef int STLDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}STLNode;
思考：為什么在申請的時候需要申請堆上的空間？因為堆上申請的空間存儲數據的時候不會因為函數銷毀而銷毀，堆上的空間需要的時候就申請，不需要的時候就釋放；函數棧幀上開辟的空間存儲的數據會因為函數棧幀的銷毀而釋放，后面在進行尾插和頭插時候新的結點不能鏈接到表上。
二、單鏈表的基本操作
1.創(chuàng)建單個結點
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuySLTNode malloc");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
2.創(chuàng)建具有n個結點的鏈表
SLTNode* CreateSList(int n)
{
int i = 0;
SLTNode* ptail = NULL,*phead = NULL;
for (i = 0; i < n; i++)
{
SLTNode* newnode = BuySLTNode(i);
if (phead == NULL)
{
ptail = phead = newnode;
}
else
{
ptail->next = newnode;
ptail = newnode;
}
}
return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
// int i = 0;
// SLTNode* ptail = NULL;
// for (i = 0; i < n; i++)
// {
// SLTNode* newnode = BuySLTNode(i);
// if (*pphead == NULL)
// {
// ptail = *pphead = newnode;
// }
// else
// {
// ptail->next= newnode;
// ptail = newnode;
// }
// }
//}上述代碼中提供了兩種實現方式，沒有注釋的是返回頭指針的，注釋內容是沒有返回值，形參使用的是二級指針改變頭指針指向的地址。
3.打印單鏈表
void SLTPrint(SLTNode* phead)
{
SLTNode* tail = phead;
while (tail)
{
printf("%d ", tail->val);
tail = tail->next;
}
printf("\n");
}
4.尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
SLTNode* tail = *pphead;
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}尾插時，要注意當單鏈表的頭結點為空的時候，要先將新結點作為頭結點。因為當頭結點為空時，需要改變頭指針，所以傳過來的為二級指針（也可以使用一級指針，不過此時要有返回值），要想改變SLTNode*的值，就要傳遞它的地址即SLTNode**類型。
5.尾刪
void SLTPopBack(SLTNode** pphead)//尾刪
{
assert(*pphead);
if ((*pphead)->next==NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}尾刪時也要注意區(qū)分是否為頭結點；同時注意刪除后，要將其置空prev->next = NULL。
6.頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
7.頭刪
void SLTPopFront(SLTNode** pphead)//頭刪
{
assert(*pphead);
SLTNode* nextnode = (*pphead)->next;
free(*pphead);
*pphead = nextnode;
}
頭插和頭刪是單鏈表的優(yōu)勢，尾插和尾刪是順序表的優(yōu)勢。同時在尾刪時注意將*pphead加上括號用來區(qū)分優(yōu)先級，否則會報錯。
8.查找某個結點
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某個數并返回所在位置
{
SLTNode* tail = phead;
while (tail)
{
if (tail->val == x)
{
return tail;
}
tail = tail->next;
}
return NULL;
}
注意循環(huán)條件，當循環(huán)條件寫為while(tail->next)時，會有空指針的風險，同時還會漏掉最后一個結點。
9.在某個結點后面插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某個結點的后面插入某個數
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
SLTNode* tail = pos->next;
pos->next = newnode;
newnode->next = tail;
}
10.在某個結點前面插入
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某個結點的前面插入某個數
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
if (pos == *pphead)
{
/*newnode->next = *pphead;
*pphead = newnode;*/
SLTPushBack(pphead, x);
}
else
{
SLTNode* tail = *pphead;
while (tail->next != pos)
{
tail = tail->next;
}
tail->next = newnode;
newnode->next = pos;
}
}11.刪除某個位置后面的結點
void SLTEraseAfter(SLTNode* pos)//刪除pos位置之后的那個位置
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* tail = pos->next;
pos->next = tail->next;
free(tail);
}
}
12.刪除某個結點
void SLTErase(SLTNode** pphead, SLTNode* pos)//刪除pos位置
{
assert(pos);
SLTNode* tail = *pphead;
if (pos == *pphead)
{
SLTNode* nextNode = (*pphead)->next;
free(*pphead);
*pphead = nextNode;
}
else
{
while (tail->next != pos)
{
tail = tail->next;
}
tail->next = pos->next;
free(pos);
}
}13.銷毀單鏈表
void SLTDestroy(SLTNode** pphead)//銷毀
{
assert(*pphead);
SLTNode* tail = *pphead;
while (tail)
{
SLTNode* next = tail->next;
free(tail);
tail = next;
}
*pphead = NULL;
}
注意最后要將頭結點置空。
三、測試代碼
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SList {
struct Slist* next;
SLTDataType val;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuySLTNode malloc");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
SLTNode* CreateSList(int n)
{
int i = 0;
SLTNode* ptail = NULL, * phead = NULL;
for (i = 0; i < n; i++)
{
SLTNode* newnode = BuySLTNode(i);
if (phead == NULL)
{
ptail = phead = newnode;
}
else
{
ptail->next = newnode;
ptail = newnode;
}
}
return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
// int i = 0;
// SLTNode* ptail = NULL;
// for (i = 0; i < n; i++)
// {
// SLTNode* newnode = BuySLTNode(i);
// if (*pphead == NULL)
// {
// ptail = *pphead = newnode;
// }
// else
// {
// ptail->next= newnode;
// ptail = newnode;
// }
// }
//}
void SLTPrint(SLTNode* phead)
{
SLTNode* tail = phead;
while (tail)
{
printf("%d ", tail->val);
tail = tail->next;
}
printf("\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
SLTNode* tail = *pphead;
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLTPopBack(SLTNode** pphead)//尾刪
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)//頭刪
{
assert(*pphead);
SLTNode* nextnode = (*pphead)->next;
free(*pphead);
*pphead = nextnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某個數并返回所在位置
{
SLTNode* tail = phead;
while (tail)
{
if (tail->val == x)
{
return tail;
}
tail = tail->next;
}
return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某個結點的后面插入某個數
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
SLTNode* tail = pos->next;
pos->next = newnode;
newnode->next = tail;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某個結點的前面插入某個數
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
if (pos == *pphead)
{
/*newnode->next = *pphead;
*pphead = newnode;*/
SLTPushBack(pphead, x);
}
else
{
SLTNode* tail = *pphead;
while (tail->next != pos)
{
tail = tail->next;
}
tail->next = newnode;
newnode->next = pos;
}
}
void SLTEraseAfter(SLTNode* pos)//刪除pos位置之后的那個位置
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
SLTNode* tail = pos->next;
pos->next = tail->next;
free(tail);
}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//刪除pos位置
{
assert(pos);
SLTNode* tail = *pphead;
if (pos == *pphead)
{
SLTNode* nextNode = (*pphead)->next;
free(*pphead);
*pphead = nextNode;
}
else
{
while (tail->next != pos)
{
tail = tail->next;
}
tail->next = pos->next;
free(pos);
}
}
void SLTDestroy(SLTNode** pphead)//銷毀
{
assert(*pphead);
SLTNode* tail = *pphead;
while (tail)
{
SLTNode* next = tail->next;
free(tail);
tail = next;
}
*pphead = NULL;
}
void TestSL()
{
SLTNode* plist = CreateSList(2);
/*SLTNode* plist = NULL;
CreateSList(&plist,10);//沒有返回值
SLTPrint(plist);*/
SLTPushBack(&plist, 600);
SLTPushBack(&plist, 200);
SLTPushBack(&plist, 300);
SLTPushBack(&plist, 400);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPopBack(&plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPushFront(&plist, 100);
SLTPushFront(&plist, 200);
SLTPushFront(&plist, 300);
SLTPushFront(&plist, 400);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPopFront(&plist);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 600);
if (pos)
{
SLInsertAfter(pos, 700);
SLTInsert(&plist, pos, 500);
SLTEraseAfter(pos);
//SLTErase(&plist, pos);
}
SLTPrint(plist);
SLTDestroy(&plist);
SLTPrint(plist);
}
int main()
{
TestSL();
return 0;
}
以上就是C語言中單鏈表(不帶頭結點)基本操作的實現詳解的詳細內容，更多關于C語言單鏈表的資料請關注腳本之家其它相關文章！
相關文章
在編寫C程序時,類型轉換是確保數據正確性和一致性的關鍵環(huán)節(jié),無論是隱式轉換還是顯式轉換,都各有特點和應用場景,本文將詳細探討C語言中的類型轉換機制,幫助您更好地理解并在實際編碼中靈活運用這些知識,需要的朋友可以參考下2025-02-02
繼承就是可以直接使用前輩的屬性和方法。自然界如果沒有繼承，那一切都是處于混沌狀態(tài)。多態(tài)是同一個行為具有多個不同表現形式或形態(tài)的能力。多態(tài)就是同一個接口，使用不同的實例而執(zhí)行不同操作2022-02-02
在類中 只有靜態(tài)變量能賦值 如果你不賦值 編譯器會認為你這個變量根本沒用 不能被修改 又沒有初始值 兩個辦法 在構造函數的初始化列表賦值 或者在const前面加一個static2015-07-07
這篇文章主要介紹了C語言中的浮點數據類型，文章會從處理帶小數的數值的相關資料開始介紹,感興趣的小伙伴的可以參考下面 文章的具體內容2021-10-10
這篇文章主要和大家分享一下五個嵌入式C語言中的實用技巧，文中的示例代碼講解詳細，對我們學習C語言有一定的幫助，需要的可以參考一下2022-12-12
這篇文章主要匯總介紹了STL區(qū)間成員函數及區(qū)間算法，有需要的小伙伴可以參考下。2015-07-07
subplot()是將多個圖畫到一個平面上的工具,下面這篇文章主要給大家介紹了關于MATLAB中subplot函數的語法與使用的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-08-08
這篇文章主要為大家詳細介紹了C語言實現單詞小幫手,文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
C++?Stack（堆棧）?是一個容器類的改編，為程序員提供了堆棧的全部功能，也就是說實現了一個先進后出（FILO）的數據結構，許多程序都使用了?queue?容器。queue?容器可以用來表示超市的結賬隊列或服務器上等待執(zhí)行的數據庫事務隊列2022-03-03
這篇文章主要為大家詳細介紹了C語言實現BMP圖像閉運算處理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10