欧美free性护士vide0shd,老熟女,一区二区三区,久久久久夜夜夜精品国产,久久久久久综合网天天,欧美成人护士h版

首頁綜合 正文
目錄

柚子快報(bào)激活碼778899分享：筆記 數(shù)據(jù)結(jié)構(gòu)之單鏈表

柚子快報(bào)激活碼778899分享：筆記 數(shù)據(jù)結(jié)構(gòu)之單鏈表

http://yzkb.51969.com/

前言：上一篇文章我們了解到順序表，這一次來看另一種線性表-------單鏈表。

1. 單鏈表的概念

單鏈表，想必很多人會感到陌生吧。那么，到底什么是單鏈表呢？先了解清楚單鏈表的概念及特性，才能夠更好的實(shí)現(xiàn)單鏈表。

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

單鏈表就像火車車廂一樣，每節(jié)車廂都通過鏈條進(jìn)行鏈接。

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

不過，在數(shù)據(jù)結(jié)構(gòu)里“車廂”有一個(gè)專屬名詞-----節(jié)點(diǎn)（結(jié)點(diǎn)）。與順序表不同的是，鏈表里的每節(jié)車廂都是獨(dú)立申請下來的空間，我們稱之為節(jié)點(diǎn)。

節(jié)點(diǎn)主要由兩部分組成，當(dāng)前節(jié)點(diǎn)要保存的數(shù)據(jù)和保存下一個(gè)節(jié)點(diǎn)的地址。

鏈表的性質(zhì)：

1.鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，在物理結(jié)構(gòu)上不一定是連續(xù)的。

2.節(jié)點(diǎn)一般是從堆上申請的。

3.從堆上申請出來的空間可能連續(xù)也可能不連續(xù)。

現(xiàn)在我們已經(jīng)了解到了鏈表的結(jié)構(gòu)，接下來要該如何設(shè)計(jì)鏈表呢？在節(jié)點(diǎn)里需要保存數(shù)據(jù)及保存下一個(gè)節(jié)點(diǎn)的地址。這是兩個(gè)不同的數(shù)據(jù)類型，因此使用結(jié)構(gòu)體，也便于代碼的可讀性與可維護(hù)性。

2. 單鏈表的實(shí)現(xiàn)

2.1 單鏈表的定義

//鏈表存儲數(shù)據(jù)類型

typedef int SLDataType;

//單鏈表的定義

typedef struct SinglyLinkedList

{

SLDataType data;//保存的數(shù)據(jù)

struct SinglyLinkedList* next;//存儲下一個(gè)節(jié)點(diǎn)的地址

}SList;

2.2 單鏈表的接口

//打印單鏈表

void DisplaySList(SList* phead);

//尾插

void SListPushBack(SList** pphead, SLDataType x);

//尾刪

void SListPopBack(SList** pphead);

//頭插

void SListPushFront(SList** pphead, SLDataType x);

//頭刪

void SListPopFront(SList** pphead);

//單鏈表查找

SList* SListFind(SList* phead, SLDataType x);

//從指定位置之后開始插入數(shù)據(jù)

void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//從指定位置之前插入數(shù)據(jù)

void SListInsert(SList** pphead, SList* pos, SLDataType x);

//從指定位置刪除數(shù)據(jù)

void SListErase(SList** pphead, SList* pos);

//銷毀鏈表

void SListDestroy(SList** pphead);

2.2.1 單鏈表尾插

//尾插

void SListPushBack(SList** pphead, SLDataType x)

{

assert(pphead);

//開辟一個(gè)節(jié)點(diǎn)大小的空間，開辟失敗就退出程序。

/*SList* newnode = (SList*)malloc(sizeof(SList));

if (NULL == newnode)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;*/

//SListBuyNewNode是一個(gè)創(chuàng)建新節(jié)點(diǎn)的函數(shù)，不僅僅在尾插

//中需要?jiǎng)?chuàng)建節(jié)點(diǎn)，在頭插中也需要。因此為了避免代碼冗余以

//及代碼的可讀性與可維護(hù)性，將創(chuàng)建新節(jié)點(diǎn)的功能封裝成一個(gè)

//函數(shù)來實(shí)現(xiàn)。

SList* newnode = SListBuyNewNode(pphead, x);

//單鏈表為空的情況

if (NULL == *pphead)

{

//plist為空，讓plist指向newnode,指向鏈表的頭結(jié)點(diǎn)

*pphead = newnode;

}

else

{

SList* tail = *pphead;

//找尾節(jié)點(diǎn)

while (NULL != tail->next)

{

tail = tail->next;

}

//連接新的節(jié)點(diǎn)

tail->next = newnode;

}

}

尾插數(shù)據(jù)需要一個(gè)節(jié)點(diǎn)大小的空間，用來存儲數(shù)據(jù)及保存下一個(gè)節(jié)點(diǎn)的地址。因此首先申請一塊節(jié)點(diǎn)大小的空間。

接下來又分兩種情況：

1.plist指向空，需要讓plist指向鏈表頭結(jié)點(diǎn)。

2.plist不指向空，新申請的結(jié)點(diǎn)直接連接在鏈表尾節(jié)點(diǎn)的后面。

assert(pphead);

pphead保存的是一級指針變量plist的地址，所以pphead一定不為

空。對pphead進(jìn)行斷言，是為了防止參數(shù)傳輸錯(cuò)誤。

還有一個(gè)問題，不知道大家發(fā)現(xiàn)沒有。這里為什么要用二級指針呢？答案很簡單。plist是一個(gè)結(jié)構(gòu)體指針，在尾插中有可能要改變plist，因此要用二級指針。這涉及到了實(shí)參與形參的關(guān)系。

2.2.2 創(chuàng)建新節(jié)點(diǎn)

//創(chuàng)建新節(jié)點(diǎn)

SList* SListBuyNewNode(SList** pphead,SLDataType x)

{

SList* newnode = (SList*)malloc(sizeof(SList));

if (NULL == newnode)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

return newnode;

}

2.2.3 打印單鏈表

//打印單鏈表

//這里也可以用二級指針來接收，保持代碼風(fēng)格的一致性

void DisplaySList(SList* phead)

{

SList* cur = phead;

while (NULL != cur)

{

printf("%d->", cur->data);

cur = cur->next;

}

printf("NULL\n");

}

SList* cur=phead,此時(shí)cur指向了鏈表的頭結(jié)點(diǎn)，只要cur不等于

NULL，就打印鏈表節(jié)點(diǎn)里的數(shù)據(jù)。然后更新cur,指向下一個(gè)節(jié)點(diǎn)。

2.2.4 單鏈表尾刪

//尾刪

void SListPopBack(SList** pphead)

{

assert(pphead);

//單鏈表為空的情況

assert(*pphead);

//單鏈表至少有一個(gè)節(jié)點(diǎn)

if (NULL == (*pphead)->next)

{

free(*pphead);

*pphead = NULL;

}

else

{

SList* tail = *pphead;

SList* prev = NULL;

//找尾節(jié)點(diǎn)

while (NULL != tail->next)

{

prev = tail;

tail = tail->next;

}

prev->next = NULL;

//釋放尾節(jié)點(diǎn)的空間

free(tail);

tail = NULL;

}

}

這里包含了3種情況：

1.plist指向空，代表沒有鏈表（沒有數(shù)據(jù)可以刪除）

2.有多個(gè)節(jié)點(diǎn)

3.只有一個(gè)節(jié)點(diǎn)

畫圖分析：

1.尾刪節(jié)點(diǎn)首先將尾節(jié)點(diǎn)的空間還給操作系統(tǒng)，然后再讓尾節(jié)點(diǎn)的前

一個(gè)節(jié)點(diǎn)指向空（防止野指針的出現(xiàn)）

2.一直尾刪，直到剩下一個(gè)節(jié)點(diǎn)。這個(gè)時(shí)候再尾刪就要改變plist指針

了，因此尾刪也需要二級指針

3.在尾刪節(jié)點(diǎn)的時(shí)候，需要找到尾節(jié)點(diǎn)才能刪除，由于單鏈表具有單

向性，因此還需要一個(gè)前驅(qū)指針，用來記錄尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。

2.2.5 單鏈表頭插

//頭插

void SListPushFront(SList** pphead, SLDataType x)

{

assert(pphead);

//創(chuàng)建新節(jié)點(diǎn)

SList* newnode = SListBuyNewNode(pphead, x);

//新節(jié)點(diǎn)成為鏈表的頭結(jié)點(diǎn)

newnode->next = *pphead;

//plist指向鏈表的頭結(jié)點(diǎn)

*pphead = newnode;

}

注意：一定要先讓新節(jié)點(diǎn)的next保存當(dāng)前plist的值，再更新plist，指向新的頭結(jié)點(diǎn)。

2.2.6 單鏈表頭刪

//頭刪

void SListPopFront(SList** pphead)

{

assert(pphead);

//單鏈表為空的情況

assert(*pphead);

//記錄當(dāng)前頭結(jié)點(diǎn)

SList* cur = *pphead;

//更新plist

*pphead = (*pphead)->next;

//釋放頭結(jié)點(diǎn)的空間

free(cur);

cur = NULL;

}

注意：

1.先讓plist指向當(dāng)前頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，如果先刪除當(dāng)前頭

結(jié)點(diǎn)，就找不到下一個(gè)節(jié)點(diǎn)了。

2.釋放當(dāng)前頭結(jié)點(diǎn)的空間。

2.plist為空，說明鏈表為空，沒有數(shù)據(jù)刪除。

2.2.7 單鏈表查找

//單鏈表查找

SList* SListFind(SList* phead, SLDataType x)

{

//單鏈表為空不查找

assert(phead);

SList* cur = phead;

while (NULL != cur)

{

if (cur->data == x)

{

return cur;

}

cur = cur->next;

}

return NULL;

}

從頭結(jié)點(diǎn)開始遍歷進(jìn)行查找，找到了就返回該節(jié)點(diǎn)的地址，否則返回NULL。

2.2.8 從指定位置之后開始插入數(shù)據(jù)

//從指定位置之后開始插入數(shù)據(jù)

void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)

{

assert(pphead);

//創(chuàng)建新節(jié)點(diǎn)

SList* newnode = SListBuyNewNode(pphead, x);

//鏈表為空

if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

SList* cur = *pphead;

//找pos位置

while (NULL != cur)

{

if (cur == pos)

{

newnode->next = cur->next;

cur->next = newnode;

}

cur = cur->next;

}

}

}

從頭結(jié)點(diǎn)開始遍歷找pos位置，找到pos位置將新節(jié)點(diǎn)插入進(jìn)去。

注意：讓新節(jié)點(diǎn)的next保存pos位置下一個(gè)節(jié)點(diǎn)的地址，再讓pos位置的節(jié)點(diǎn)的next保存新節(jié)點(diǎn)的地址。

2.2.9 從指定位置之前插入數(shù)據(jù)

//從指定位置之前插入數(shù)據(jù)

void SListInsert(SList** pphead, SList* pos, SLDataType x)

{

assert(pphead);

//創(chuàng)建新節(jié)點(diǎn)

SList* newnode = SListBuyNewNode(pphead, x);

if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

SList* cur = *pphead;

//記錄pos位置前一個(gè)節(jié)點(diǎn)

SList* prev = NULL;

while (NULL != cur)

{

if (cur == pos)

{

newnode->next = prev->next;

prev->next = newnode;

}

prev = cur;

cur = cur->next;

}

}

}

從頭結(jié)點(diǎn)開始遍歷找pos位置，找到pos位置，讓pos位置的前一個(gè)節(jié)點(diǎn)的next保存新節(jié)點(diǎn)的地址，新節(jié)點(diǎn)的next保存pos位置節(jié)點(diǎn)的地址。

2.2.10 從指定位置刪除數(shù)據(jù)

//從指定位置刪除數(shù)據(jù)

void SListErase(SList** pphead, SList* pos)

{

assert(pphead);

//單鏈表為空

assert(*pphead);

SList* cur = *pphead;

//找pos位置

while (NULL != cur->next)

{

if (cur->next == pos)

{

cur->next = pos->next;

free(pos);

pos = NULL;

}

cur = cur->next;

}

}

單鏈表不能為空，為空說明沒有數(shù)據(jù)可以刪除。找到pos位置，讓pos位置的前一個(gè)節(jié)點(diǎn)的next指向pos位置節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，然后再釋放掉pos位置的節(jié)點(diǎn)。

2.2.11 銷毀鏈表

//銷毀鏈表

void SListDestroy(SList** pphead)

{

assert(pphead);

SList* cur = *pphead;

while (NULL != cur)

{

SList* prev = cur;

cur = cur->next;

free(prev);

prev = NULL;

}

*pphead=NULL;

}

從頭結(jié)點(diǎn)開始遍歷，先讓cur指向頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，再釋放掉當(dāng)前

的頭結(jié)點(diǎn)。最后再讓*pphead=NULL。在循環(huán)過程中，*pphead的指

向一直沒有發(fā)生改變，銷毀鏈表時(shí)，也要讓plist指向空，防止出現(xiàn)野

指針。

3. 單鏈表完整代碼的實(shí)現(xiàn)

SList.h的實(shí)現(xiàn)

#pragma once

#include

#include

#include

typedef int SLDataType;

typedef struct SinglyLinkedList

{

SLDataType data;

struct SinglyLinkedList* next;//存儲下一個(gè)節(jié)點(diǎn)的地址

}SList;

//打印單鏈表

void DisplaySList(SList* phead);

//尾插

void SListPushBack(SList** pphead, SLDataType x);

//尾刪

void SListPopBack(SList** pphead);

//頭插

void SListPushFront(SList** pphead, SLDataType x);

//頭刪

void SListPopFront(SList** pphead);

//單鏈表查找

SList* SListFind(SList* phead, SLDataType x);

//從指定位置之后開始插入數(shù)據(jù)

void SListInsertAfter(SList** pphead, SList* pos, SLDataType x);

//從指定位置之前插入數(shù)據(jù)

void SListInsert(SList** pphead, SList* pos, SLDataType x);

//從指定位置刪除數(shù)據(jù)

void SListErase(SList** pphead, SList* pos);

//銷毀鏈表

void SListDestroy(SList** pphead);

SList.c實(shí)現(xiàn)

#define _CRT_SECURE_NO_WARNINGS

#include"SList.h"

//打印單鏈表

void DisplaySList(SList* phead)

{

SList* cur = phead;

while (NULL != cur)

{

printf("%d->", cur->data);

cur = cur->next;

}

printf("NULL\n");

}

//創(chuàng)建新節(jié)點(diǎn)

SList* SListBuyNewNode(SList** pphead,SLDataType x)

{

SList* newnode = (SList*)malloc(sizeof(SList));

if (NULL == newnode)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

return newnode;

}

//尾插

void SListPushBack(SList** pphead, SLDataType x)

{

assert(pphead);

/*SList* newnode = (SList*)malloc(sizeof(SList));

if (NULL == newnode)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;*/

SList* newnode = SListBuyNewNode(pphead, x);

//單鏈表為空的情況

if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

SList* tail = *pphead;

while (NULL != tail->next)

{

tail = tail->next;

}

tail->next = newnode;

}

}

//尾刪

void SListPopBack(SList** pphead)

{

assert(pphead);

//單鏈表為空的情況

assert(*pphead);

//單鏈表至少有一個(gè)節(jié)點(diǎn)

if (NULL == (*pphead)->next)

{

free(*pphead);

*pphead = NULL;

}

else

{

SList* tail = *pphead;

SList* prev = NULL;

while (NULL != tail->next)

{

prev = tail;

tail = tail->next;

}

prev->next = NULL;

free(tail);

tail = NULL;

}

}

//頭插

void SListPushFront(SList** pphead, SLDataType x)

{

assert(pphead);

/*SList* newnode = (SList*)malloc(sizeof(SList));

if (NULL == newnode)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;*/

SList* newnode = SListBuyNewNode(pphead, x);

//至少有一個(gè)節(jié)點(diǎn)

/*if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

newnode->next = *pphead;

*pphead = newnode;

}*/

newnode->next = *pphead;

*pphead = newnode;

}

//頭刪

void SListPopFront(SList** pphead)

{

assert(pphead);

//單鏈表為空的情況

assert(*pphead);

SList* cur = *pphead;

*pphead = (*pphead)->next;

free(cur);

cur = NULL;

}

//單鏈表查找

SList* SListFind(SList* phead, SLDataType x)

{

//單鏈表為空不查找

assert(phead);

SList* cur = phead;

while (NULL != cur)

{

if (cur->data == x)

{

return cur;

}

cur = cur->next;

}

return NULL;

}

//從指定位置之后開始插入數(shù)據(jù)

void SListInsertAfter(SList** pphead, SList* pos, SLDataType x)

{

assert(pphead);

SList* newnode = SListBuyNewNode(pphead, x);

if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

SList* cur = *pphead;

while (NULL != cur)

{

if (cur == pos)

{

newnode->next = cur->next;

cur->next = newnode;

}

cur = cur->next;

}

}

}

//從指定位置之前插入數(shù)據(jù)

void SListInsert(SList** pphead, SList* pos, SLDataType x)

{

assert(pphead);

SList* newnode = SListBuyNewNode(pphead, x);

if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

SList* cur = *pphead;

SList* prev = NULL;

while (NULL != cur)

{

if (cur == pos)

{

newnode->next = prev->next;

prev->next = newnode;

}

prev = cur;

cur = cur->next;

}

}

}

//從指定位置刪除數(shù)據(jù)

void SListErase(SList** pphead, SList* pos)

{

assert(pphead);

//單鏈表為空

assert(*pphead);

SList* cur = *pphead;

while (NULL != cur->next)

{

if (cur->next == pos)

{

cur->next = pos->next;

free(pos);

pos = NULL;

}

cur = cur->next;

}

}

//銷毀鏈表

void SListDestroy(SList** pphead)

{

assert(pphead);

SList* cur = *pphead;

while (NULL != cur)

{

SList* prev = cur;

cur = cur->next;

free(prev);

prev = NULL;

}

*pphead=NULL;

}

test.c的實(shí)現(xiàn)

#define _CRT_SECURE_NO_WARNINGS

#include"SList.h"

void TestSList1()

{

SList* plist = NULL;

SListPushBack(&plist, 1);

SListPushBack(&plist, 2);

SListPushBack(&plist, 3);

SListPushBack(&plist, 4);

SListPushBack(&plist, 5);

DisplaySList(plist);

SListPopBack(&plist);

SListPopBack(&plist);

SListPopBack(&plist);

SListPopBack(&plist);

SListPopBack(&plist);

DisplaySList(plist);

}

void TestSList2()

{

SList* plist = NULL;

SListPushFront(&plist, 10);

SListPushFront(&plist, 20);

SListPushFront(&plist, 30);

SListPushFront(&plist, 40);

DisplaySList(plist);

SListPopFront(&plist);

DisplaySList(plist);

SList* pos = SListFind(plist, 50);

if (NULL != pos)

{

printf("%d\n", pos->data);

}

else

{

printf("找不到\n");

}

}

void TestSList3()

{

SList* plist = NULL;

SListInsertAfter(&plist, NULL, 10);

DisplaySList(plist);

SListPushBack(&plist, 1);

SListPushBack(&plist, 2);

SListPushBack(&plist, 3);

SListPushBack(&plist, 4);

SListPushBack(&plist, 5);

SList* pos = SListFind(plist, 4);

SListInsertAfter(&plist, pos, 20);

DisplaySList(plist);

pos = SListFind(plist, 2);

SListInsert(&plist, pos, 30);

DisplaySList(plist);

pos = SListFind(plist, 3);

SListErase(&plist, pos);

DisplaySList(plist);

SListDestroy(&plist);

}

int main()

{

//TestSList1();

//TestSList2();

TestSList3();

return 0;

}

柚子快報(bào)激活碼778899分享：筆記 數(shù)據(jù)結(jié)構(gòu)之單鏈表

http://yzkb.51969.com/

推薦閱讀

評論可見，查看隱藏內(nèi)容

本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。

轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。

本文鏈接：http://gantiao.com.cn/post/19597257.html

發(fā)布評論

您暫未設(shè)置收款碼

請?jiān)谥黝}配置——文章設(shè)置里上傳

掃描二維碼手機(jī)訪問

文章目錄