溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“C語言中單鏈表如何實現”，在日常操作中，相信很多人在C語言中單鏈表如何實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C語言中單鏈表如何實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！
通過對順序表的學習，我們可以發現順序表有以下幾點缺陷：
1.空間不夠時需要擴容，擴容尤其是用realloc進行異地擴容時，是有一定代價的，其次還可能存在一定空間浪費。
2.頭部或者中間插入刪除，需要挪動數據，效率低下。
那我們可以對其所具有的缺陷進行優化：可以按需申請空間同時插入刪除時不挪動數據。而單鏈表就符合這些優化所具有特點。但是我們要注意的是單鏈表具有這些優點并不代表鏈表就可以完全替代順序表。
鏈表是一種物理存儲結構上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
從上圖可以看出，鏈式結構在邏輯上是連續的，但是在物理上不一定連續，物理結構中指針域存儲的是下一個結點的地址；而且鏈式結構的結點一般都是從堆上申請出來的；從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續，也可能不連續。鏈表存儲數據的區域可分為數據域和指針域：
用代碼表示鏈表中的數據域和指針域如下：
typedef int STLDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}STLNode;思考：為什么在申請的時候需要申請堆上的空間？因為堆上申請的空間存儲數據的時候不會因為函數銷毀而銷毀，堆上的空間需要的時候就申請，不需要的時候就釋放；函數棧幀上開辟的空間存儲的數據會因為函數棧幀的銷毀而釋放，后面在進行尾插和頭插時候新的結點不能鏈接到表上。
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;
}
}尾插時，要注意當單鏈表的頭結點為空的時候，要先將新結點作為頭結點。因為當頭結點為空時，需要改變頭指針，所以傳過來的為二級指針（也可以使用一級指針，不過此時要有返回值），要想改變SLTNode*的值，就要傳遞它的地址即SLTNode**類型。
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;
}
}尾刪時也要注意區分是否為頭結點；同時注意刪除后，要將其置空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;
}頭插和頭刪是單鏈表的優勢，尾插和尾刪是順序表的優勢。同時在尾刪時注意將*pphead加上括號用來區分優先級，否則會報錯。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某個數并返回所在位置
{
SLTNode* tail = phead;
while (tail)
{
if (tail->val == x)
{
return tail;
}
tail = tail->next;
}
return NULL;
}注意循環條件，當循環條件寫為while(tail->next)時，會有空指針的風險，同時還會漏掉最后一個結點。
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;
}注意最后要將頭結點置空。
#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語言中單鏈表如何實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
