當前位置：首頁 > news >正文

織夢做的的網(wǎng)站首頁顯示空白站長工具箱

news 2025/7/7 15:12:15

織夢做的的網(wǎng)站首頁顯示空白,站長工具箱,網(wǎng)站建設投資,小型教育網(wǎng)站的開發(fā)與建設目錄 1.鏈表的概念及結(jié)構(gòu) 2.單鏈表功能的實現(xiàn) 2.1打印單鏈表 2.2創(chuàng)建節(jié)點 2.3單鏈表尾插 2.3單鏈表頭插 2.5單鏈表尾刪 2.6單鏈表頭刪 2.7單鏈表的查找 2.8在指定位置之前插入數(shù)據(jù) 2.9在指定位置之后插入數(shù)據(jù) 2.10刪除pos節(jié)點 2.11刪除pos之后的節(jié)點 2.12銷毀鏈表…

1.鏈表的概念及結(jié)構(gòu)

2.單鏈表功能的實現(xiàn)

2.1打印單鏈表

2.2創(chuàng)建節(jié)點

2.3單鏈表尾插

2.3單鏈表頭插

2.5單鏈表尾刪

2.6單鏈表頭刪

2.7單鏈表的查找

2.8在指定位置之前插入數(shù)據(jù)

2.9在指定位置之后插入數(shù)據(jù)

2.10刪除pos節(jié)點

2.11刪除pos之后的節(jié)點

2.12銷毀鏈表

3.完整代碼

SList.h

SList.c

1.鏈表的概念及結(jié)構(gòu)

線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，采用順序存儲結(jié)構(gòu)為順序表，采用鏈式存儲結(jié)構(gòu)為線性鏈表。

概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

鏈表的結(jié)構(gòu)跟火車車廂相似，淡季時火車的車廂會相應減少，旺季時火車的車廂會額外增加幾節(jié)。只需要將某節(jié)車廂去掉或者加上，不影響其他車廂，每節(jié)車廂都是獨立存在的。

且每節(jié)車廂都有車門，假設每節(jié)車廂的車門都是鎖上的狀態(tài)，需要不同的鑰匙才能解鎖，每次只能攜帶一把鑰匙的情況下如何從車頭走到車尾？ 最簡單的做法：每節(jié)車廂里都放一把下一節(jié)車廂的鑰匙。

在鏈表里，每節(jié)“車廂”是什么樣的呢？

與順序表不同的是，鏈表里的每節(jié)"車廂"都是獨立申請下來的空間，我們稱之為“結(jié)點/節(jié)點” ，節(jié)點的組成主要有兩個部分：要保存的數(shù)據(jù)和下一個節(jié)點的地址（指針變量）。

圖中指針變量 plist保存的是第一個節(jié)點的地址，我們稱plist此時“指向”第一個節(jié)點，如果我們希望plist“指向”第二個節(jié)點時，只需要修改plist保存的內(nèi)容為0x0012FFA0。

為什么還需要指針變量來保存下一個節(jié)點的位置？

鏈表中每個節(jié)點都是獨立申請的（即需要插入數(shù)據(jù)時才去申請一塊節(jié)點的空間），通過指針變量保存下一個節(jié)點位置才能從當前節(jié)點找到下一個節(jié)點。

注意：

鏈式結(jié)構(gòu)在邏輯上是連續(xù)的，在物理結(jié)構(gòu)上不一定連續(xù)。
節(jié)點一般是從堆上申請的。
從堆上申請來的空間，是按照一定策略分配出來的，每次申請的空間可能連續(xù)，可能不連續(xù)。

2.單鏈表功能的實現(xiàn)

2.1打印單鏈表

void SLPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf("%d->", pcur->data);pcur = pcur->next; //將指針指向下一個節(jié)點}printf("NULL\n");
}

2.2創(chuàng)建節(jié)點

單鏈表每次插入都需要插入一個節(jié)點，所以我們最好寫一個創(chuàng)建節(jié)點的函數(shù)方便后續(xù)調(diào)用。

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL)  //申請失敗{perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

2.3單鏈表尾插

尾插時需要找到最后一個節(jié)點的位置，再插入數(shù)值，但是要注意假如傳進來一個空鏈表，ptail=NULL；那么對它進行找尾操作勢必會造成ptail->next這句代碼對空指針進行解引用，所以分成兩種情況：

1.如果鏈表為空，直接插入即可。

2.如果鏈表不為空，需要找到尾節(jié)點再插入。

輸出結(jié)果：

我們發(fā)現(xiàn)輸出結(jié)果不是1，而是NULL，這是為什么呢？

SLTPushBack(plist, 1);

一級指針不能實現(xiàn)的原因：傳參的時候另外創(chuàng)建一個一級指針phead接收plist傳過來的值，它和plist指針一樣指向NULL（這里屬于傳值調(diào)用，雖然plist變量存儲的值是地址），尾插數(shù)據(jù)后，再讓phaed指針指向newnode,在此期間plist仍然指向NULL，沒有發(fā)生任何改變，因為形參的改變無法影響實參，調(diào)用鏈表打印函數(shù)，打印字符NULL。

當鏈表為空時，一開始plist指向空指針，然后需要plist指向newnode，需要改變plist的指向，這里用一級指針是實現(xiàn)不了的，需要用二級指針，二級指針才能改變一級指針plist的指向。若鏈表不為空，不需要改變plist的指向，程序依然可以正常運行。

小貼士

一級指針的作用 : 將普通變量的一級指針傳入函數(shù)作為參數(shù) ,可以在函數(shù)中訪問該一級指針指向的普通變量, 并且可以修改該普通變量的值,但是該普通變量所在內(nèi)存地址不能被修改。?

傳參的時候傳一級指針變量的地址&plist，使用pphead二級指針來接收：

尾插代碼

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);  //不能傳空指針，不能對空指針進行解引用//空鏈表和非空鏈表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)    //*pphead是指向第一個節(jié)點的指針{*pphead = newnode;}else{//找尾SLTNode* ptail =*pphead;while (ptail->next)//ptail->next!=NULL{ptail = ptail->next;}//ptail指向的就是尾節(jié)點ptail->next = newnode;}	
}

2.3單鏈表頭插

頭插數(shù)據(jù)需要改變一級指針plist的指向，這里也需要二級指針改變一級指針plist的指向。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead; //將newnode和頭結(jié)點連接在一起*pphead = newnode;       //將鏈表頭結(jié)點指向新的頭
}

2.5單鏈表尾刪

與單鏈表尾插類似，當鏈表只有一個頭結(jié)點時需要將plist置為空，所以也需要二級指針。

void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//鏈表不能為空//鏈表只有一個節(jié)點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//鏈表有多個節(jié)點SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next)   //找尾節(jié)點{prev = ptail;ptail = ptail->next;}free(ptail);	//釋放掉ptail指向的空間ptail = NULL;prev->next = NULL;//將ptail前一個節(jié)點next指針置為空，防止野指針}
}

2.6單鏈表頭刪

先創(chuàng)建一個指針next,保存第二個節(jié)點的位置，防止釋放頭結(jié)點導致找不到第二個節(jié)點。

void SLPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//鏈表不能為空SLTNode* next = (*pphead)->next;//保存第二個節(jié)點free(*pphead);*pphead = next; //第二個節(jié)點作為鏈表新頭，頭指針走到新頭的位置
}

2.7單鏈表的查找

查找數(shù)據(jù)不需要改變指針plist的指向，這里使用一級指針傳參即可。如果找到就返回這個節(jié)點的地址，否則就返回空指針NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;//再定義一個指針，phead指針可能后續(xù)還要用，不希望改變phead指針while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur==NULL  沒有找到！return NULL;
}

2.8在指定位置之前插入數(shù)據(jù)

當鏈表在頭節(jié)點插入時使用頭插。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(*pphead);assert(pos);//若pos==*pphead;說明是頭插if (pos == *pphead){SLTPushFront(pphead, x);//調(diào)用頭插}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos)//找pos的前一個節(jié)點prev{prev = prev->next;}//將prev  newnode  pos 三個節(jié)點連起來newnode->next = pos;prev->next = newnode;}	
}

2.9在指定位置之后插入數(shù)據(jù)

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos  newnode  pos->nextnewnode->next = pos->next;//這里一定要注意順序問題!pos->next = newnode;
}

2.10刪除pos節(jié)點

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos是頭節(jié)點/pos不是頭節(jié)點if (pos == *pphead){//頭刪SLPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos)//找pos的前一個節(jié)點prev{prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}	
}

2.11刪除pos之后的節(jié)點

void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;//pos  del  del->nextpos->next = del->next;free(del);del = NULL;
}

2.12銷毀鏈表

void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3.完整代碼

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定義節(jié)點的結(jié)構(gòu)
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//鏈表打印
void SLPrint(SLTNode* phead);//鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾刪
void SLTPopBack(SLTNode** pphead);//頭刪
void SLPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插?數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插?數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//刪除pos節(jié)點
void SLTErase(SLTNode** pphead, SLTNode* pos);//刪除pos之后的節(jié)點
void SLTEraseAfter(SLTNode* pos);//銷毀鏈表
void SListDesTroy(SLTNode** pphead);

SList.c

#include"SList.h"
//打印鏈表
void SLPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//申請一個新節(jié)點
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//鏈表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);  //不能傳空指針，不能對空指針進行解引用//空鏈表和非空鏈表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)    //*pphead是指向第一個節(jié)點的指針{*pphead = newnode;}else{//找尾SLTNode* ptail =*pphead;while (ptail->next)//ptail->next!=NULL{ptail = ptail->next;}//ptail指向的就是尾節(jié)點ptail->next = newnode;}	
}//鏈表頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead; //將newnode和頭結(jié)點連接在一起*pphead = newnode;       //將鏈表頭結(jié)點指向新的頭
}//尾刪
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//鏈表不能為空//鏈表只有一個節(jié)點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//鏈表有多個節(jié)點SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);	//釋放掉ptail指向的空間ptail = NULL;prev->next = NULL;//將ptail前一個節(jié)點next指針置為空，防止野指針}
}//頭刪
void SLPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//鏈表不能為空SLTNode* next = (*pphead)->next;//先保存第二個節(jié)點的位置，防止釋放頭結(jié)點導致找不到第二個節(jié)點free(*pphead);*pphead = next; //第二個節(jié)點作為鏈表新頭，頭指針走到新頭的位置
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//不需要改變plist指向，傳一級指針即可
{SLTNode* pcur = phead;//再定義一個指針，phead指針可能后續(xù)還要用，不希望改變phead指針while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur==NULL  沒有找到！return NULL;
}//在指定位置之前插?數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(*pphead);assert(pos);//若pos==*pphead;說明是頭插if (pos == *pphead){SLTPushFront(pphead, x);//調(diào)用頭插}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos)//找pos的前一個節(jié)點prev{prev = prev->next;}//將prev  newnode  pos 三個節(jié)點連起來newnode->next = pos;prev->next = newnode;}	
}//在指定位置之后插?數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos  newnode  pos->nextnewnode->next = pos->next;//這里一定要注意順序問題!pos->next = newnode;
}//刪除pos節(jié)點
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos是頭節(jié)點/pos不是頭節(jié)點if (pos == *pphead){//頭刪SLPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos)//找pos的前一個節(jié)點prev{prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}	
}//刪除pos之后的節(jié)點
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* del = pos->next;//pos  del  del->nextpos->next = del->next;free(del);del = NULL;
}//銷毀鏈表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

查看全文

http://aloenet.com.cn/news/45803.html

国产亚洲精品福利在线无卡一,国产精久久一区二区三区,亚洲精品无码国模,精品久久久久久无码专区不卡

織夢做的的網(wǎng)站首頁顯示空白站長工具箱

1.鏈表的概念及結(jié)構(gòu)

2.單鏈表功能的實現(xiàn)

2.1打印單鏈表

2.2創(chuàng)建節(jié)點

2.3單鏈表尾插

2.3單鏈表頭插

2.5單鏈表尾刪

2.6單鏈表頭刪

2.7單鏈表的查找

2.8在指定位置之前插入數(shù)據(jù)

2.9在指定位置之后插入數(shù)據(jù)

2.10刪除pos節(jié)點

2.11刪除pos之后的節(jié)點

2.12銷毀鏈表

3.完整代碼

SList.h

SList.c

相關(guān)文章：