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

首頁綜合 正文
目錄

柚子快報激活碼778899分享：筆記 數據結構之單鏈表

柚子快報激活碼778899分享：筆記 數據結構之單鏈表

http://yzkb.51969.com/

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

1. 單鏈表的概念

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

所謂鏈表是一種物理存儲結構上非連續(xù)，非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

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

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

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

節(jié)點主要由兩部分組成，當前節(jié)點要保存的數據和保存下一個節(jié)點的地址。

鏈表的性質：

1.鏈式結構在邏輯上是連續(xù)的，在物理結構上不一定是連續(xù)的。

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

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

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

2. 單鏈表的實現

2.1 單鏈表的定義

//鏈表存儲數據類型

typedef int SLDataType;

//單鏈表的定義

typedef struct SinglyLinkedList

{

SLDataType data;//保存的數據

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

}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);

//從指定位置之后開始插入數據

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

//從指定位置之前插入數據

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

//從指定位置刪除數據

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

//銷毀鏈表

void SListDestroy(SList** pphead);

2.2.1 單鏈表尾插

//尾插

void SListPushBack(SList** pphead, SLDataType x)

{

assert(pphead);

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

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

if (NULL == newnode)

{

printf("malloc fail\n");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;*/

//SListBuyNewNode是一個創(chuàng)建新節(jié)點的函數，不僅僅在尾插

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

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

//函數來實現。

SList* newnode = SListBuyNewNode(pphead, x);

//單鏈表為空的情況

if (NULL == *pphead)

{

//plist為空，讓plist指向newnode,指向鏈表的頭結點

*pphead = newnode;

}

else

{

SList* tail = *pphead;

//找尾節(jié)點

while (NULL != tail->next)

{

tail = tail->next;

}

//連接新的節(jié)點

tail->next = newnode;

}

}

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

接下來又分兩種情況：

1.plist指向空，需要讓plist指向鏈表頭結點。

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

assert(pphead);

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

空。對pphead進行斷言，是為了防止參數傳輸錯誤。

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

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

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

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 打印單鏈表

//打印單鏈表

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

void DisplaySList(SList* phead)

{

SList* cur = phead;

while (NULL != cur)

{

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

cur = cur->next;

}

printf("NULL\n");

}

SList* cur=phead,此時cur指向了鏈表的頭結點，只要cur不等于

NULL，就打印鏈表節(jié)點里的數據。然后更新cur,指向下一個節(jié)點。

2.2.4 單鏈表尾刪

//尾刪

void SListPopBack(SList** pphead)

{

assert(pphead);

//單鏈表為空的情況

assert(*pphead);

//單鏈表至少有一個節(jié)點

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

{

free(*pphead);

*pphead = NULL;

}

else

{

SList* tail = *pphead;

SList* prev = NULL;

//找尾節(jié)點

while (NULL != tail->next)

{

prev = tail;

tail = tail->next;

}

prev->next = NULL;

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

free(tail);

tail = NULL;

}

}

這里包含了3種情況：

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

2.有多個節(jié)點

3.只有一個節(jié)點

畫圖分析：

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

一個節(jié)點指向空（防止野指針的出現）

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

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

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

向性，因此還需要一個前驅指針，用來記錄尾節(jié)點的前一個節(jié)點。

2.2.5 單鏈表頭插

//頭插

void SListPushFront(SList** pphead, SLDataType x)

{

assert(pphead);

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

SList* newnode = SListBuyNewNode(pphead, x);

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

newnode->next = *pphead;

//plist指向鏈表的頭結點

*pphead = newnode;

}

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

2.2.6 單鏈表頭刪

//頭刪

void SListPopFront(SList** pphead)

{

assert(pphead);

//單鏈表為空的情況

assert(*pphead);

//記錄當前頭結點

SList* cur = *pphead;

//更新plist

*pphead = (*pphead)->next;

//釋放頭結點的空間

free(cur);

cur = NULL;

}

注意：

1.先讓plist指向當前頭結點的下一個節(jié)點，如果先刪除當前頭

結點，就找不到下一個節(jié)點了。

2.釋放當前頭結點的空間。

2.plist為空，說明鏈表為空，沒有數據刪除。

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é)點的地址，否則返回NULL。

2.2.8 從指定位置之后開始插入數據

//從指定位置之后開始插入數據

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

{

assert(pphead);

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

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;

}

}

}

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

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

2.2.9 從指定位置之前插入數據

//從指定位置之前插入數據

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

{

assert(pphead);

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

SList* newnode = SListBuyNewNode(pphead, x);

if (NULL == *pphead)

{

*pphead = newnode;

}

else

{

SList* cur = *pphead;

//記錄pos位置前一個節(jié)點

SList* prev = NULL;

while (NULL != cur)

{

if (cur == pos)

{

newnode->next = prev->next;

prev->next = newnode;

}

prev = cur;

cur = cur->next;

}

}

}

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

2.2.10 從指定位置刪除數據

//從指定位置刪除數據

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;

}

}

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

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;

}

從頭結點開始遍歷，先讓cur指向頭結點的下一個節(jié)點，再釋放掉當前

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

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

指針。

3. 單鏈表完整代碼的實現

SList.h的實現

#pragma once

#include

#include

#include

typedef int SLDataType;

typedef struct SinglyLinkedList

{

SLDataType data;

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

}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);

//從指定位置之后開始插入數據

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

//從指定位置之前插入數據

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

//從指定位置刪除數據

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

//銷毀鏈表

void SListDestroy(SList** pphead);

SList.c實現

#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é)點

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);

//單鏈表至少有一個節(jié)點

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);

//至少有一個節(jié)點

/*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;

}

//從指定位置之后開始插入數據

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;

}

}

}

//從指定位置之前插入數據

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;

}

}

}

//從指定位置刪除數據

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的實現

#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;

}

柚子快報激活碼778899分享：筆記 數據結構之單鏈表

http://yzkb.51969.com/

推薦閱讀

評論可見，查看隱藏內容

本文內容根據網絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。

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

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

發(fā)布評論

您暫未設置收款碼

請在主題配置——文章設置里上傳

掃描二維碼手機訪問

文章目錄