線性表——單鏈表的增刪查改

?本節復習鏈表的增刪查改

首先， 鏈表不是連續的， 而是通過指針聯系起來的。 如圖：

這四個節點不是連續的內存空間， 但是彼此之間使用了一個指針來連接。 這就是鏈表。?

現在我們來實現鏈表的增刪查改。

目錄

單鏈表的全部接口：

?準備文件

建立結構體藍圖

申請鏈表節點函數接口

單鏈表的打印函數接口

單鏈表尾插函數接口

單鏈表頭插函數接口

?單鏈表尾刪函數接口

單鏈表的頭刪函數接口

?單鏈表查找函數接口

單鏈表pos位置之后插入數據接口

單鏈表刪除pos之后位置的數據

單鏈表在pos位置之前插入數據接口

單鏈表刪除pos位置數據接口

單鏈表的銷毀

單鏈表的全部接口：

//申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos);
//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//單鏈表在pos位置刪除數據接口
void SListPop(SLNode** pphead, SLNode* pos);
//單鏈表的銷毀函數接口
void SLTDestory(SLNode** pphead);
?

---------------------------------------------------------------------------------------------------------------------------------

?準備文件

首先準備好三個文件夾， 一個main.c文件夾， 一個.h文件夾用來聲明鏈表的接口以及定義結構體等。 一個.c文件夾用來實現單鏈表。

---------------------------------------------------------------------------------------------------------------------------------

建立結構體藍圖

首先包含一下頭文件， 定義一下數據類型。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;

接著再建立一個鏈表的結構體

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;

---------------------------------------------------------------------------------------------------------------------------------

申請鏈表節點函數接口

申請鏈表的節點操作， 在尾插， 頭插， 或者特定位置插入的時候都需要， 所以可以封裝成一個函數。 后續直接進行復用就可以。

.h函數聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode //創建結構體
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);

.c函數實現

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}

?在實現的過程中，可以將數據直接儲存到新節點中。 然后讓新節點指向NULL， 然后返回該節點。 然后將鏈表直接連接到這個節點就可以。

---------------------------------------------------------------------------------------------------------------------------------

單鏈表的打印函數接口

為了便于后續的函數接口的調試， 我們先實現單鏈表的打印操作。

.h函數聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);

.c函數實現

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}

---------------------------------------------------------------------------------------------------------------------------------

單鏈表尾插函數接口

.h函數聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);

.c函數實現

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申請節點函數申請節點SLNode* cur = *pphead; //讓cur指向phead所指向空間if (cur == NULL) //cur == NULL代表著phead指向NULL， 這時候讓phead改變指向。傳送phead指針的原因就是{                                              //要改變phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //讓cur遍歷到最后一個節點{cur = cur->next;}cur->next = newnode;//最后}}

尾插接口時傳送phead的指針的原因是因為phead可能改變指向，從空指針變為指向一個節點。要改變phead的指向那就是意味著形參要相對于phead傳址調用，??而phead本身就是一個一級指針， phead取地址就是一個二級指針， 所以形參是二級指針。

---------------------------------------------------------------------------------------------------------------------------------

單鏈表頭插函數接口

.h函數接口


鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);

.c函數實現

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申請節點函數申請節點SLNode* cur = *pphead; //讓cur指向phead所指向空間if (cur == NULL) //cur == NULL代表著phead指向NULL， 這時候讓phead改變指向。傳送phead指針的原因就是{                                              //要改變phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //讓cur遍歷到最后一個節點{cur = cur->next;}cur->next = newnode;//最后}}//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}

現在我們來利用打印接口調試一下我們寫的是否存在問題。?

在main.c中輸入如下代碼

void TestSListNode()
{SLNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPushBack(&phead, 5);SListPushFront(&phead, 0);SListPrint(phead);printf("\n");/*SListPopFront(&phead);SListPopFront(&phead);SListPopFront(&phead);SListPopBack(&phead);SListPrint(phead);printf("\n");SLTDestory(&phead);SListPrint(phead);printf("\n");*/}int main() 
{
//	TestTree();
//	TestStack();
//	TestQueue();
//	TestSeqList();TestSListNode();
//	TestDSLNode();
//	TestOJ();return 0;
}

運行圖如下：?

?通過檢驗，沒有問題。 繼續往下走。?

---------------------------------------------------------------------------------------------------------------------------------

?單鏈表尾刪函數接口

.h文件聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);

.c函數實現

??首先pphead不能為空， 如果phead指向空的話就直接返回。 然后定義cur和prev兩個指針， 遍歷尋找尾節點。 cur領先prev一個節點， cur指向尾節點的時候， 就釋放掉這個節點。 然后prev指向空節點。 尋找尾節點的過程是這樣的：

代碼實現

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申請節點函數申請節點SLNode* cur = *pphead; //讓cur指向phead所指向空間if (cur == NULL) //cur == NULL代表著phead指向NULL， 這時候讓phead改變指向。傳送phead指針的原因就是{                                              //要改變phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //讓cur遍歷到最后一個節點{cur = cur->next;}cur->next = newnode;//最后}}//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //對鏈表進行遍歷。 cur最終會指向尾節點。 prev用來維護鏈表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}

---------------------------------------------------------------------------------------------------------------------------------

單鏈表的頭刪函數接口

.h函數聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);

.c函數實現?

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申請節點函數申請節點SLNode* cur = *pphead; //讓cur指向phead所指向空間if (cur == NULL) //cur == NULL代表著phead指向NULL， 這時候讓phead改變指向。傳送phead指針的原因就是{                                              //要改變phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //讓cur遍歷到最后一個節點{cur = cur->next;}cur->next = newnode;//最后}}//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //對鏈表進行遍歷。 cur最終會指向尾節點。 prev用來維護鏈表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;*pphead = cur->next;free(cur);
}

代碼的意思是， 首先pphead不能為空， 然后phead不能指向空。?然后讓一個cur指針指向頭節點。 然后修改phead的指向， 使其指向第二個節點（當第二個節點是空的時候， 就是指向空）。然后釋放cur指向的節點也就是頭節點。 如圖為過程：

---------------------------------------------------------------------------------------------------------------------------------

?單鏈表查找函數接口

.h接口聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);

.c接口實現

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申請節點函數申請節點SLNode* cur = *pphead; //讓cur指向phead所指向空間if (cur == NULL) //cur == NULL代表著phead指向NULL， 這時候讓phead改變指向。傳送phead指針的原因就是{                                              //要改變phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //讓cur遍歷到最后一個節點{cur = cur->next;}cur->next = newnode;//最后}}//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //對鏈表進行遍歷。 cur最終會指向尾節點。 prev用來維護鏈表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;*pphead = cur->next;free(cur);
}//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x) 
{SLNode* cur = phead;//定義一個指向頭節點的指針， 用于遍歷while (cur != NULL) //向后遍歷{if (cur->data == x) //找到節點后就返回節點的地址。{return cur;}cur = cur->next;}return NULL;
}

?代碼太長， 之后.c文件的代碼只展示相應接口的代碼

---------------------------------------------------------------------------------------------------------------------------------

單鏈表pos位置之后插入數據接口

.h接口聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);

.c接口實現?


//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x) 
{assert(pos);SLNode* newnode = BuySListNode(x);//SLNode* cur = pos->next;newnode->next = cur;pos->next = newnode;
}

?該接口的實現過程如下：

令指針cur指向pos的下一個節點， newnode的next指向cur， pos的next指向newnode

---------------------------------------------------------------------------------------------------------------------------------

單鏈表刪除pos之后位置的數據

.h接口聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos);

.c接口實現


//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos) 
{assert(pos);//SLNode* cur = pos->next;pos->next = pos->next->next;free(cur);
}

該接口實現和單鏈表在pos位置之后插入數據接口實現方式類似， 都是利用一個cur指針指向pos之后的位置作為記憶保存，然后進行插入或者刪除操作。?

---------------------------------------------------------------------------------------------------------------------------------

單鏈表在pos位置之前插入數據接口

該接口的實現有點復雜， 但是實現該接口之后， 對于尾插還有頭插就很好實現了， 尾插和頭插是該接口的兩個特殊情況。 假如pos是頭節點，就是頭插， 假如pos是尾節點， 就是尾插。

.h接口聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos);
//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);

.c接口實現


//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) 
{assert(pphead);//SLNode* newnode = BuySListNode(x);//if (*pphead == NULL) {*pphead = newnode;return;}//if (*pphead == pos) {newnode->next = pos;*pphead = newnode;return;}SLNode* cur = *pphead;while (cur != NULL && cur->next != pos) {cur = cur->next;}newnode->next = pos;cur->next = newnode;
}

該接口分為三種情況：

第一種是鏈表為空， 這個時候直接插入節點。

第二種情況是pos的位置在第一個節點的位置， 這個時候需要改變phead的指向。?

第三種情況就是最普通的情況， 在除頭節點， 鏈表的任意節點前插入。如圖：

?

---------------------------------------------------------------------------------------------------------------------------------

單鏈表刪除pos位置數據接口

和pos位置插入數據接口一樣， 實現了該接口對于尾刪， 頭刪接口就很簡單了。 頭刪， 尾刪都是單鏈表刪除pos位置數據接口的特殊情況。 pos是頭節點， 就是頭刪， pos是尾節點。 就是尾刪。?

.h接口聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos);
//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//單鏈表在pos位置刪除數據接口
void SListPop(SLNode** pphead, SLNode* pos);

.c接口實現


//單鏈表在pos位置刪除數據接口
void SListPop(SLNode** pphead, SLNode* pos) 
{assert(pphead);//if (*pphead == pos) {*pphead = (*pphead)->next;free(pos);}else {SLNode* cur = *pphead;while (cur->next != pos) {cur->next = pos->next;free(pos);}}
}

pos位置刪除分兩種情況

一種是頭刪， 需要phead改變指向。

?一種是其他位置刪除節點

單鏈表的銷毀

?鏈表使用完之后應該銷毀， 放置內存泄漏

.h接口聲明

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos);
//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//單鏈表在pos位置刪除數據接口
void SListPop(SLNode** pphead, SLNode* pos);
//單鏈表的銷毀函數接口
void SLTDestory(SLNode** pphead);

.c接口實現?


//單鏈表的銷毀函數接口
void SLTDestory(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL) {return;}SLNode* prev = (*pphead);SLNode* cur = (*pphead)->next;if (cur == NULL) {*pphead = NULL;free(prev);}else {*pphead = NULL;while(cur != NULL){free(prev);prev = cur;cur = cur->next;}free(prev);}}

銷毀需要一步一步的進行， 如下圖：

現在來看一下總體代碼：

.h文件

鏈表的增刪查改///
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int SLTDataType;typedef struct SListNode 
{struct SListNode* next;SLTDataType data;
}SLNode;//鏈表接口聲明///申請鏈表節點函數接口
SLNode* BuySListNode(SLTDataType x);
//單鏈表的打印函數接口
void SListPrint(SLNode* phead);
//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x);
//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x);
//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead);
//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead);
//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x);
//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x);
//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos);
//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//單鏈表在pos位置刪除數據接口
void SListPop(SLNode** pphead, SLNode* pos);
//單鏈表的銷毀函數接口
void SLTDestory(SLNode** pphead);

.c文件

單鏈表函數實現函數接口//單鏈表申請節點函數接口
SLNode* BuySListNode(SLTDataType x) 
{SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));if (NewNode == NULL) {printf("申請節點失敗\n");return;}//NewNode->data = x;NewNode->next = NULL;
}//單鏈表的節點打印操作
void SListPrint(SLNode* phead) 
{SLNode* cur = phead;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}if (cur == NULL)//最后打印一個NULL{printf("NULL");}}//單鏈表尾插函數接口
void SListPushBack(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//利用申請節點函數申請節點SLNode* cur = *pphead; //讓cur指向phead所指向空間if (cur == NULL) //cur == NULL代表著phead指向NULL， 這時候讓phead改變指向。傳送phead指針的原因就是{                                              //要改變phead的指向。*pphead = newnode;//}else {while (cur->next != NULL) //讓cur遍歷到最后一個節點{cur = cur->next;}cur->next = newnode;//最后}}//單鏈表頭插函數接口
void SListPushFront(SLNode** pphead, SLTDataType x) 
{assert(pphead);SLNode* newnode = BuySListNode(x);//SLNode* cur = *pphead;newnode->next = cur;*pphead = newnode;}//單鏈表尾刪函數接口
void SListPopBack(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;SLNode* prev = *pphead;while (cur->next != NULL) //對鏈表進行遍歷。 cur最終會指向尾節點。 prev用來維護鏈表{prev = cur;cur = cur->next;}if (prev == cur) {free(cur);*pphead = NULL;}else {free(cur);prev = NULL;}}//單鏈表的頭刪函數接口
void SListPopFront(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL)return;//SLNode* cur = *pphead;*pphead = cur->next;free(cur);
}//單鏈表查找函數接口
SLNode* SListFind(SLNode* phead, SLTDataType x) 
{SLNode* cur = phead;//定義一個指向頭節點的指針， 用于遍歷while (cur != NULL) //向后遍歷{if (cur->data == x) //找到節點后就返回節點的地址。{return cur;}cur = cur->next;}return NULL;
}//單鏈表在pos位置之后插入數據接口
void SListInsertAfter(SLNode* pos, SLTDataType x) 
{assert(pos);SLNode* newnode = BuySListNode(x);//SLNode* cur = pos->next;newnode->next = cur;pos->next = newnode;
}//單鏈表在pos之后的位置刪除數據
void SListPopAfter(SLNode* pos) 
{assert(pos);//SLNode* cur = pos->next;pos->next = pos->next->next;free(cur);
}//單鏈表在pos位置之前插入數據接口
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) 
{assert(pphead);//SLNode* newnode = BuySListNode(x);//if (*pphead == NULL) {*pphead = newnode;return;}//if (*pphead == pos) {newnode->next = pos;*pphead = newnode;return;}SLNode* cur = *pphead;while (cur != NULL && cur->next != pos) {cur = cur->next;}newnode->next = pos;cur->next = newnode;
}//單鏈表在pos位置刪除數據接口
void SListPop(SLNode** pphead, SLNode* pos) 
{assert(pphead);//if (*pphead == pos) {*pphead = (*pphead)->next;free(pos);}else {SLNode* cur = *pphead;while (cur->next != pos) {cur->next = pos->next;free(pos);}}
}//單鏈表的銷毀函數接口
void SLTDestory(SLNode** pphead) 
{assert(pphead);if (*pphead == NULL) {return;}SLNode* prev = (*pphead);SLNode* cur = (*pphead)->next;if (cur == NULL) {*pphead = NULL;free(prev);}else {*pphead = NULL;while(cur != NULL){free(prev);prev = cur;cur = cur->next;}free(prev);}}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/717532.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/717532.shtml
英文地址，請注明出處：http://en.pswp.cn/news/717532.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

位運算---求n的二進制表示中第k位是1還是0 (lowbit)

位運算---求n的二進制表示中第k位是1還是0 (lowbit)

操作&#xff1a; 先把第k位移到最后一位&#xff08;右邊第一位&#xff09; 看個位是1還是0 lowbit(x)&#xff1a;返回x的最右邊的1。 原理&#xff1a; 其中 &#xff0c;意思是 是 的補碼。 就可以求出最右邊的一位1。 應用&#xff1a; 當中 的個數。 int re…
閱讀更多...
AI-數學-高中-33概率-事件的關系與運算

AI-數學-高中-33概率-事件的關系與運算

原作者視頻&#xff1a;【概率】【一數辭典】2事件的關系與運算_嗶哩嗶哩_bilibili 事件&#xff1a; 和/并事件&#xff1b;積/交事件&#xff1b;互訴事件&#xff1b;對立(補集)事件&#xff1b;
閱讀更多...
【詳識JAVA語言】面向對象程序三大特性之二：繼承

【詳識JAVA語言】面向對象程序三大特性之二：繼承

繼承 為什么需要繼承 Java中使用類對現實世界中實體來進行描述&#xff0c;類經過實例化之后的產物對象&#xff0c;則可以用來表示現實中的實體&#xff0c;但是 現實世界錯綜復雜&#xff0c;事物之間可能會存在一些關聯&#xff0c;那在設計程序是就需要考慮。 比如&…
閱讀更多...
04.其他方案

04.其他方案

其他方案 1.事務狀態表調??重試接收?冪等 介紹 調??維護?張事務狀態表&#xff08;或者說事務?志、?志流?&#xff09;&#xff0c;在每次調?之前&#xff0c;落盤?條事務流?&#xff0c;?成?個全局的事務ID 事務開始之前的狀態是Begin&#xff0c;全部結束之…
閱讀更多...
Go語言進階篇——文件

Go語言進階篇——文件

文件的打開 文件的常見的兩種打開方式是基于os包所提供的兩個函數: func Open(name string) (*File,error) func OpenFile(name string flag int perm FileMode) (*File,error)相對于前者&#xff0c;OpenFile可以提供更加細致的操作&#xff0c;而前者就是對后者的一個簡單封…
閱讀更多...
碼垛工作站：食品生產企業的轉型助推器

碼垛工作站：食品生產企業的轉型助推器

在當今高度自動化的工業生產中&#xff0c;碼垛工作站的應用正逐漸成為一種趨勢。某食品生產企業在面臨市場競爭加劇、人工成本上升等多重壓力下&#xff0c;決定引入碼垛工作站&#xff0c;以期實現生產流程的升級與變革。 一、碼垛工作站引入背景 該企業主要從事休閑食品的…
閱讀更多...
Android 中的 LinearLayout 布局

Android 中的 LinearLayout 布局

在 Android 開發中&#xff0c;布局是至關重要的一部分&#xff0c;它決定了應用程序的界面結構和用戶體驗。LinearLayout 是 Android 中最常用的布局之一&#xff0c;它以線性方式排列子視圖&#xff0c;可以垂直或水平布局。在這篇博客中&#xff0c;我們將深入了解 LinearLa…
閱讀更多...
數據結構實現-棧和隊列

數據結構實現-棧和隊列

順序棧 #include <iostream> using namespace std; #define MaxSize 50//順序棧 template<typename ElemType> struct SqStack{ElemType data[MaxSize];int top; };//初始化 template<typename ElemType> void InitStack(SqStack<ElemType>&s){s.…
閱讀更多...
Postman和Jmeter的區別

Postman和Jmeter的區別

1.用例組織方式不同 jmeter組織方式相對比較扁平&#xff0c;沒有工作空間的概念&#xff0c;直接就是測試計劃 postman組織方式會比較輕量級&#xff0c;只要是針對單個的HTTP請求 2.支持的接口類型與測試類型上 jmeter會更強大&#xff0c;可以支持REST、Soap等等&#xf…
閱讀更多...
Kotlin 協程遇見 Flow：打造更優雅的數據流處理

Kotlin 協程遇見 Flow：打造更優雅的數據流處理

Kotlin Flow 是 Kotlin 協程庫中的一個組件&#xff0c;它提供了處理異步數據流的能力。Kotlin Flow 類似于 RxJava 中的 Observable&#xff0c;但它完全基于 Kotlin 協程設計&#xff0c;使得異步流的操作變得更加簡單和直觀。 Flow 是冷流&#xff08;cold stream&#xff…
閱讀更多...
【貪心算法】Leetcode 455.分發餅干 376. 擺動序列 53. 最大子數組和

【貪心算法】Leetcode 455.分發餅干 376. 擺動序列 53. 最大子數組和

【貪心算法】Leetcode 455 分發餅干 376. 擺動序列【規律很多】53. 最大子數組和 455 分發餅干局部最優推全局最優&#xff1a;盡量用大餅干去滿足大胃口的小朋友 376. 擺動序列【規律很多】思想&#xff1a;注意考慮一個坡度留首尾兩個點、平坡、首尾 53. 最大子數組和【好思想…
閱讀更多...
15.網絡游戲逆向分析與漏洞攻防-網絡通信數據包分析工具-發送通信數據包至分析工具

15.網絡游戲逆向分析與漏洞攻防-網絡通信數據包分析工具-發送通信數據包至分析工具

上一個內容&#xff1a;14.數據包分析工具界面與通信設計 碼云地址&#xff08;master 分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/titan 碼云版本號&#xff1a;2d6491e3c51a1a7ab4da0ee6dc4cf566a80fd6e1 代碼下載地址&#xff0c;在 titan 目錄下&…
閱讀更多...
模版進階C++

模版進階C++

非類型模版 之前我們寫的模版都是在不知道模版&#xff08;類&#xff09;中有的變量的類型是什么的時候&#xff0c;我們先用模版參數定義&#xff0c;當類實例化的時候在傳參確認 非類型模版&#xff1a;模版參數定義的時候也可以定義整型類型&#xff08;c20之后才支持其…
閱讀更多...
奇點云：SAFe框架下，我們對平臺軟件工程生產線做了4項改造

奇點云：SAFe框架下，我們對平臺軟件工程生產線做了4項改造

導讀&#xff1a; 客戶規模擴大&#xff0c;如何保證大數據軟件產品和服務質量始終如一&#xff1f;幾乎所有成長中的軟件廠商&#xff0c;尤其是需要通過私有化部署交付的廠商&#xff0c;都會面臨這個問題。正如《人月神話》中多次表明的&#xff0c;單純地增加人手、擴大團隊…
閱讀更多...
基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的植物病害檢測系統（Python+PySide6界面+訓練代碼）

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的植物病害檢測系統（Python+PySide6界面+訓練代碼）

摘要&#xff1a;開發高效的植物病害檢測系統對于提升農業生產效率和作物健康管理意義重大。本篇博客詳細闡述了如何運用深度學習技術構建一個植物病害檢測系統&#xff0c;并提供了完整的實現代碼。該系統基于先進的YOLOv8算法&#xff0c;對YOLOv7、YOLOv6、YOLOv5進行了性能…
閱讀更多...
考研數學——高數：微分方程

考研數學——高數：微分方程

一、一階線性微分方程 兩種形式&#xff1a; 非齊次&#xff1a; 齊次&#xff1a; 推導過程 推導公式的過程一般由特殊到一般&#xff1a;所以先求解齊次方程的解 &#xff08;然后對等式兩邊同時積分&#xff09; 再來求非齊次方程的解&#xff0c;由…
閱讀更多...
【測開求職】2023秋招快手一面面經

【測開求職】2023秋招快手一面面經

已經過了百度測開三面，快手這個一面比百度的要難很多，可能也是遇到了比較嚴格的面試官，感覺其他面經沒有這么難。30分鐘實習，20分鐘算法題，20分鐘八股，沒有問項目。 實習 diff遇到了哪些痛點diff是全量還是增量一些字段的增加或者枚舉值的增加可以用diff測嗎有哪些自動化…
閱讀更多...
03-grafana的下拉列表選項制作-grafana的變量

03-grafana的下拉列表選項制作-grafana的變量

一、準備環境 為了實現下拉列表篩選的樣例&#xff0c;我們監控兩個linux節點&#xff1b; 目前&#xff0c;我們已經有了一個節點了&#xff0c;再添加一個&#xff1b; 二、grafana的儀表盤變量 如果想給儀表盤自定義下拉列表&#xff0c;那么&#xff0c;需要設置變量&#…
閱讀更多...
線上問題——2021-12-27 父子線程共用線程池導致死鎖故障

線上問題——2021-12-27 父子線程共用線程池導致死鎖故障

一、事故現象 從早上6點開始edu-wings-admin的timer-task和mq就開始報警任務堆積&#xff0c;且數量持續上升&#xff0c;到6點50左右mq也開始告警&#xff0c;8點左右發現問題&#xff0c;開始排查&#xff0c;直到11點才找到問題&#xff0c;任務開始正常消費。 二、事故影響…
閱讀更多...
haproxy集成國密ssl功能[下]

haproxy集成國密ssl功能[下]

上接[haproxy集成國密ssl功能上 4. 源碼修改解析 以下修改基本圍繞haproxy的ssl_sock.c進行修改來展開的，為了將整個實現邏輯能夠說明清楚，下述內容有部分可能就是直接摘抄haproxy的原有代碼沒有做任何修改，而大部分增加或者修改的內容則進行了特別的說明。 4.1 為bind指令…
閱讀更多...
最新文章

Copyright @ 2022~2023