欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言深入講解鏈表的使用

 更新時間:2022年05月26日 10:40:20   作者:披星戴月的賈維斯  
當我們在寫一段代碼時,如果要頻繁的在一塊區(qū)域進行插入或者刪除操作時,會發(fā)現(xiàn)用數(shù)組實現(xiàn)會比較復雜,這時候我們就要用另一種數(shù)據(jù)結(jié)構(gòu),鏈表來實現(xiàn)

現(xiàn)實生活中的火車就像一個完整的鏈表,現(xiàn)在我們來深入理解一下鏈表這個數(shù)據(jù)結(jié)構(gòu)。

一、鏈表的概念

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

注:

1、從上圖中可看出,鏈式結(jié)構(gòu)在邏輯上是連續(xù)的,但是在物理上不一定連續(xù)。

2、從現(xiàn)實中的結(jié)點一般是通過malloc函數(shù)申請的,所以其內(nèi)存分配是在堆區(qū)。

3、從堆上申請的空間,是按照一定的策略來分配的,則一個節(jié)點的大小為8個字節(jié)。

二、鏈表的分類

實際中鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu):

1. 單向或者雙向鏈表

2. 帶頭或者不帶頭(是否有自帶哨兵位頭結(jié)點)

第二個鏈表的d1指向了我們的哨兵位頭結(jié)點。

3. 循環(huán)或者非循環(huán)鏈表

4. 無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表

1. 無頭單向非循環(huán)鏈表:結(jié)構(gòu)簡單,一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu),如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

2. 帶頭雙向循環(huán)鏈表:結(jié)構(gòu)最復雜,一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向 循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復雜,但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢,實現(xiàn)反而 簡單了。

3、鏈表的實現(xiàn)(代碼和注釋)

無頭+單向+非循環(huán)鏈表增刪查改實現(xiàn)

頭文件:

#pragma once 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//要求存儲的數(shù)據(jù)從0開始,依次存儲
//靜態(tài)的順序表
//問題:開小了,不夠用,開大了,存在浪費。
//struct SeqList
//{
//	int a[N];
//	int size;//記錄存儲了多少個數(shù)據(jù)。
//};
typedef int SLDateType;//宏定義我們的 SLDateType是int類型的
//動態(tài)的順序表
typedef struct SeqList
{
	SLDateType* a;
	int size;	//存儲數(shù)據(jù)個數(shù)
	int capacity;//存儲空間大小
}SL, SeqList;
void SeqListPrint(SeqList* psl);//鏈表的打印
void SeqListInit(SeqList* psl);//鏈表的初始化
void SeqListDestroy(SeqList* psl);//鏈表的銷毀
void SeqListCheckCapacity(SeqList* psl);//檢查內(nèi)存空間是否足夠
//時間復雜度是o(1)
void SeqListPushBack(SeqList* psl, SLDateType x);//鏈表的尾插
void SeqListPopBack(SeqList* psl);//鏈表的尾刪
//時間復雜度是o(n)
void SeqListPushFront(SeqList* psl, SLDateType x);//鏈表的頭插
void SeqListPopFront(SeqList* psl);//鏈表的頭刪
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x);
// 刪除pos位置的數(shù)據(jù)
void SeqListErase(SeqList* psl, size_t pos);
// 順序表查找
int SeqListFind(SeqList* psl, SLDateType x);

鏈表的函數(shù)實現(xiàn)部分的代碼:

#include"SeqList.h"
#include<assert.h>
void SeqListPrint(SeqList* psl)//結(jié)構(gòu)體指針傳參
{
	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
void SeqListInit(SeqList* psl)
{
	assert(psl);//斷言psl不為空
	psl->a = NULL;//a就相當于是鏈表的頭
	psl->size = 0;
	psl->capacity = 0;
}
void SeqListDestroy(SeqList* psl)//鏈表的刪除
{
	assert(psl);
	free(psl->a);//free掉鏈表中a這個節(jié)點的位置
	psl->a = NULL;//將a指向空
	psl->capacity = psl->size = 0;//將鏈表的內(nèi)存大小置為0
}
void SeqListCheckCapacity(SeqList* psl)//檢查鏈表的內(nèi)存,如果不夠就增容。
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		//capacity == 0,所以要先特判一下capacity 的值
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//初始節(jié)點數(shù)為4,如果內(nèi)存現(xiàn)在為0就擴大一倍
		SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//申請空間
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;//原來的空間變?yōu)樾驴臻g
		}
	}
}
void SeqListPushBack(SeqList* psl, SLDateType x)
{
	//如果滿了,要擴容
	if (psl->size == psl->capacity)
	{
		//capacity == 0,所以要先特判一下capacity 的值
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
	psl->a[psl->size] = x;
	psl->size++;
}
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	if (psl->size > 0)
	{ 
		psl->size--;//尾刪就size--就好了
	}
}
void SeqListPushFront(SeqList* psl, SLDateType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)//所有的數(shù)據(jù)往后挪1位
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;//兩種操作是等價的
	psl->size++;
	//SeqListInsert(psl, 0, x);在頭部插入。
}
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	if (psl->size > 0)
	{
		int begin = 1;
		while (psl->size > begin)
		{
			psl->a[begin - 1] = psl->a[begin];
			++begin;
		}
		--psl->size;
	}
}
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
	// 暴力檢查
	assert(psl);
	// 溫和檢查
	if (pos > psl->size)
	{
		printf("pos 越界:%d\n", pos);
		return;
		//exit(-1);
	}
	// 暴力檢查
	//assert(pos <= psl->size);
	SeqListCheckCapacity(psl);
	//int end = psl->size - 1;
	//while (end >= (int)pos)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}

4、鏈表oj題(小試牛刀)

1、leetcode203移除鏈表元素力扣

包含三種情況

畫個圖分析:

思路:情況一和情況二都可以用prev和cur指針遍歷數(shù)組的兩個元素, if cur指針不等于6,prev指針和cur指針都往前走,如果cur = 6,prev跳到cur的下一個位置

如果是第三種情況,則需先找到head != val的位置,再重復進行如上操作。

代碼示例:

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val != val)//當cur這個位置的值不等于val時往下走
        {
            prev = cur;//prev跳到cur位置
             cur = cur->next;//cur指針繼續(xù)往下走
        }
        else
        {
            struct ListNode* next = cur->next;//定義一個新的指針
            if(prev == NULL)//頭刪,head為空的狀態(tài)
            {
                free(cur);
                head = next;//繼續(xù)往后面走
                cur = next;
            }
            else
            {
                free(cur);//free掉cur這個節(jié)點
                prev->next = next;//跳過了cur這個點
                cur = next;//cur繼續(xù)往后走
            }
        }
    }
    return head;
}

2、leetcode206反轉(zhuǎn)鏈表力扣

思路1:反轉(zhuǎn)指針方向

思路二:用三個指針, n1, n2, n3 分別存放NULL, head, head->next;

代碼示例:

struct ListNode* reverseList(struct ListNode* head)
{
    if(head == NULL) return NULL;
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;//n3的地址是n2的下一位
    while(n2)
    {
        n2->next = n1;//n2 的下一位指向 n1;起到掉頭的作用
        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
    }
    return n1;
}

方法2:頭插法

殊途同歸。newhead 相當于之前的n1, cur = n2, next = n3;
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //頭插
        cur->next = NewHead;//代表鏈表的指向方向。
        NewHead = cur;//接著把地址傳過來(更新)
        cur = next;//(更新)
    }
    return NewHead;
}

3、leetcode 876鏈表的中間結(jié)點力扣

思路:快慢指針法

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;//剛開始slow和fast指針都指向頭
    while(fast && fast->next) //想的是結(jié)束的條件,寫的是繼續(xù)的條件
    {
        slow = slow->next;
        fast = fast->next->next;//fast 每次走兩步
    }
    return slow;
}

總結(jié)

這里我?guī)Т蠹覐逆湵淼母拍?,鏈表的分類,鏈表的簡單實現(xiàn)以及3題oj題四個方面帶大家認識鏈表

到此這篇關(guān)于C語言深入講解鏈表的使用的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • c++傳輸文件到不同計算機上的示例代碼

    c++傳輸文件到不同計算機上的示例代碼

    這篇文章主要為大家詳細介紹了c++傳輸文件到不同計算機上的相關(guān)知識,文中的示例代碼簡潔易懂,感興趣的小伙伴可以跟隨小編一起學習一下
    2024-03-03
  • Qt物聯(lián)網(wǎng)管理平臺之實現(xiàn)告警短信轉(zhuǎn)發(fā)

    Qt物聯(lián)網(wǎng)管理平臺之實現(xiàn)告警短信轉(zhuǎn)發(fā)

    系統(tǒng)在運行過程中,會實時采集設備的數(shù)據(jù),當采集到的數(shù)據(jù)發(fā)生報警后,可以將報警信息以短信的形式發(fā)送給指定的管理員。本文將利用Qt實現(xiàn)告警短信轉(zhuǎn)發(fā),感興趣的可以嘗試一下
    2022-07-07
  • C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷實例分析

    C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷實例分析

    這篇文章主要介紹了C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷,實例分析了C++實現(xiàn)圖的遍歷技巧,非常具有實用價值,需要的朋友可以參考下
    2015-04-04
  • VS2019項目打包生成.exe文件與Setup的步驟實現(xiàn)

    VS2019項目打包生成.exe文件與Setup的步驟實現(xiàn)

    這篇文章主要介紹了VS2019項目打包生成.exe文件與Setup的步驟實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-03-03
  • C++中模板和STL介紹詳解

    C++中模板和STL介紹詳解

    今天小編就為大家分享一篇關(guān)于C++模板和STL的介紹,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2021-09-09
  • C++存儲持續(xù)性生命周期原理解析

    C++存儲持續(xù)性生命周期原理解析

    這篇文章主要為大家介紹了C++存儲持續(xù)性生命周期原理解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-01-01
  • C 語言實現(xiàn)一個簡單的 web 服務器的原理解析

    C 語言實現(xiàn)一個簡單的 web 服務器的原理解析

    這篇文章主要介紹了C 語言實現(xiàn)一個簡單的 web 服務器的原理解析,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-11-11
  • C++實現(xiàn)單例模式的方法

    C++實現(xiàn)單例模式的方法

    這篇文章主要為大家介紹了C++實現(xiàn)單例模式的方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-12-12
  • C++中vector與remove()函數(shù)詳解

    C++中vector與remove()函數(shù)詳解

    這篇文章主要介紹了C++中vector與remove()函數(shù),本文實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-06-06
  • C++設計模式之抽象工廠模式

    C++設計模式之抽象工廠模式

    這篇文章主要介紹了C++設計模式之抽象工廠模式,本文要講的抽象工廠模式,就是工廠方法模式的擴展和延伸,需要的朋友可以參考下
    2014-09-09

最新評論