目錄
- 一、易錯的介面實作
- 1.1 新節點開辟函式
- 1.2 尾插
- 1.3 尾刪
- 二、常見簡單介面
- 2.1 列印鏈表
- 2.2 節點計數器
- 2.3 判斷是否為空鏈表
- 2.4 通過值查找節點
- 2.5 頭插
- 2.6 頭刪
- 2.7 在任意節點后插入節點
- 2.8 在任意節點后洗掉節點
- 2.9 銷毀鏈表
- 三、頭檔案相關內容
- 3.1 參考的庫函式
- 3.2 結構體宣告
一、易錯的介面實作
1.1 新節點開辟函式
由于創建一個新節點是頻繁的操作，所以封裝為一個介面最佳，
鏈表節點的屬性有：（1）數值，（2）指向下一個節點的地址，（3）自身地址，
static SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//開辟失敗
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//初始化
newnode->data = x;
newnode->next = NULL;
return newnode;
}
數值和next地址都由此函式初始化，自身地址則由函式的回傳值回傳，
要注意使用malloc函式時，可能存在開辟空間失敗的情況，這時會回傳NULL，
1.2 尾插
尾插的難點在于存在特殊情況，
當對非空鏈表和空鏈表進行尾插時，所需代碼不同，
對非空鏈表尾插時，演算法是：找到此鏈表的尾部，即遍歷此鏈表，直至自定義的結構體指標tail的下一個節點為NULL，結束遍歷，在tail的后面插入一個新節點，
對空鏈表尾插時，演算法是：直接把新節點作為鏈表的頭節點，
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//找尾
SLTNode* tail = *pphead;
if (tail == NULL)
{
tail = BuySListNode(x);
*pphead = tail;
}
else
{
while (tail->next != NULL)
{
tail = tail->next;
}
SLTNode* newnode = BuySListNode(x);
tail->next = newnode;
}
}
1.3 尾刪
此介面也有特殊情況處理，
當鏈表有一個以上的節點時，演算法：遍歷鏈表到尾部，free掉tail所在記憶體，改變tail之前一個節點的next，為NULL，
需要一個結構體指標變數prev來記錄tail的前一個節點，
當鏈表只有一個節點時，演算法：tail一開始就在尾部，直接free掉tail，再把prev指標（初值為NULL）賦值給頭節點*pphead，
如果不單獨考慮這種情況的話，會因為NULL->next而出現記憶體錯誤，
當鏈表沒有節點時，是不可以呼叫尾刪的，直接用assert函式報錯，
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);//沒有節點斷言報錯
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
if (prev != NULL)
prev->next = NULL;
else
*pphead = prev;
}
二、常見簡單介面
2.1 列印鏈表
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
2.2 節點計數器
int SListSize(SLTNode* phead)
{
//計數器
int count = 0;
SLTNode* cur = phead;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
2.3 判斷是否為空鏈表
bool SListEmpty(SLTNode* phead)
{
return phead == NULL;
}
2.4 通過值查找節點
SLTNode* SListFind(SLTNode* phead, SLTDataType data)
{
//通過資料查找節點-遍歷節點，判斷值是否相等
SLTNode* cur = phead;
while (cur)
{
if (cur->data == data)
return cur;
cur = cur->next;
}
return NULL;
}
2.5 頭插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
2.6 頭刪
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = NULL;
*pphead = next;
}
2.7 在任意節點后插入節點
void SListInsert(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
SLTNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
2.8 在任意節點后洗掉節點
void SListErase(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}
2.9 銷毀鏈表
void SListDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur, * nextnode;
cur = *pphead;
nextnode = NULL;
while (cur)
{
nextnode = cur->next;
free(cur);
cur = nextnode;
}
*pphead = NULL;
}
三、頭檔案相關內容
3.1 參考的庫函式
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
3.2 結構體宣告
typedef int SLTDataType;//重定義可便于修改值的資料型別
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;//重定義可減少代碼冗余
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/303044.html
標籤：其他
下一篇：05動態記憶體管理