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

C語言?超詳細(xì)介紹與實(shí)現(xiàn)線性表中的無頭單向非循環(huán)鏈表

 更新時(shí)間:2022年03月29日 16:42:16   作者:李逢溪  
無頭單向非循環(huán)鏈表:結(jié)構(gòu)簡單,一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu),如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多

一、本章重點(diǎn)

  • 無頭單向非循環(huán)鏈表介紹
  • 無頭單向非循環(huán)鏈表常用接口實(shí)現(xiàn)
  • 在線oj訓(xùn)練

二、鏈表介紹

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

簡單的說:鏈表就是一些結(jié)構(gòu)體相互關(guān)聯(lián)起來,而關(guān)聯(lián)的手段就是指針,通過存儲(chǔ)下一個(gè)結(jié)構(gòu)體的地址,就能挨個(gè)訪問存在結(jié)構(gòu)體里的數(shù)據(jù)。

相比于順序表來說。鏈表能夠解決順序表的一些缺點(diǎn)。

  • 從內(nèi)存角度來說:無論是靜態(tài)順序表還是動(dòng)態(tài)順序表都會(huì)有一定的內(nèi)存浪費(fèi),鏈表則是用一個(gè)節(jié)點(diǎn)申請(qǐng)一個(gè)節(jié)點(diǎn),無內(nèi)存浪費(fèi)。
  • 從效率角度上來說:順序表不管是頭插還是中間插入與刪除都要移動(dòng)數(shù)據(jù),時(shí)間復(fù)雜度是O(N)。而鏈表則只要改變指針指向即可達(dá)到插入和刪除的效果。

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

1. 單向、雙向

2. 帶頭、不帶頭

3. 循環(huán)、非循環(huán)

帶頭:

存在一個(gè)哨兵位的節(jié)點(diǎn),該節(jié)點(diǎn)不存儲(chǔ)任何有效數(shù)據(jù),屬于無效節(jié)點(diǎn),但通過這個(gè)無效節(jié)點(diǎn)當(dāng)頭節(jié)點(diǎn)讓我們?cè)谀承┓矫媸褂脮?huì)有一些優(yōu)勢(shì)。

比如,你頭插新節(jié)點(diǎn)時(shí),不需要傳二級(jí)指針,因?yàn)槲覀兊念^節(jié)點(diǎn)始終指向這個(gè)無效節(jié)點(diǎn)。

帶頭單向非循環(huán)鏈表

雙向:

指的是節(jié)點(diǎn)中不再只有一個(gè)指針,而是有兩個(gè)指針,一個(gè)指向前一個(gè)節(jié)點(diǎn),另一個(gè)指向后一個(gè)節(jié)點(diǎn)。

無頭雙向非循環(huán)鏈表

循環(huán):

尾指針不再指向NULL,而是指向頭節(jié)點(diǎn)。?

無頭單向循環(huán)鏈表

三、無頭單向非循環(huán)鏈表常用接口實(shí)現(xiàn)

3.1動(dòng)態(tài)申請(qǐng)一個(gè)節(jié)點(diǎn)

SLTNode* BuySListNode(SLDataType x)
{
	SLTNode* newnode = malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

3.2單鏈表打印

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3單鏈表尾插

void SListPushBack(SLTNode** pphead, SLDataType x)
{
	if (*pphead==NULL)
	{
		*pphead = BuySListNode(x);
		return;
	}
	else
	{
		SLTNode* tail;
		tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = BuySListNode(x);
		return;
	}
}

3.4單鏈表的頭插

void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.5單鏈表的尾刪

void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if((*pphead)->next==NULL)
	{
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

3.6單鏈表頭刪

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLTNode* temp = *pphead;
		(*pphead) = (*pphead)->next;
		free(temp);
	}
}

3.7單鏈表查找

SLTNode* SListSearch(SLTNode* phead, SLDataType x)
{
	while (phead)
	{
		if (phead->data == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}

3.8單鏈表在pos位置之前插入x

void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		return;
	}
	else if(*pphead==pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		newnode->next = pos;
		cur->next = newnode;
	}
}

3.9單鏈表刪除pos位置的節(jié)點(diǎn)

void SListErase(SLTNode** phead, SLTNode* pos)
{
	if (*phead == NULL)
	{
		return;
	}
	else if (*phead == pos)
	{
		*phead == NULL;
	}
	else
	{
		SLTNode* cur = *phead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

四、在線oj訓(xùn)練

4.1移除鏈表元素(力扣)

給你一個(gè)鏈表的頭節(jié)點(diǎn)?head?和一個(gè)整數(shù)?val?,請(qǐng)你刪除鏈表中所有滿足?Node.val == val?的節(jié)點(diǎn),并返回?新的頭節(jié)點(diǎn)?。

輸入:head = [1,2,6,3,4,5,6], val = 6

輸出:[1,2,3,4,5]

輸入:head = [7,7,7,7], val = 7

輸出:[]

?思路:

前后指針(跟班指針),初始轉(zhuǎn)態(tài)prev指向NULL,cur指向head,如果出現(xiàn)cur->val==val.

就進(jìn)行刪除,刪除步驟為prev->next==cur->next;cur=cur->next。迭代過程為:prev=cur,cur==cur->next。

特殊情況,如果要?jiǎng)h除的val為頭節(jié)點(diǎn),則刪除步驟為head=cur->next;free(cur);cur=head。

代碼參考:

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
    ListNode* cur=head;
    ListNode* prev=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                 prev->next=cur->next;
                 cur=cur->next;
            }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

4.2反轉(zhuǎn)單鏈表(力扣)

給你單鏈表的頭節(jié)點(diǎn)?head?,請(qǐng)你反轉(zhuǎn)鏈表,并返回反轉(zhuǎn)后的鏈表。

輸入:head = [1,2,3,4,5]

輸出:[5,4,3,2,1]

輸入:head = []

輸出:[]

這里提供一個(gè)頭插思路:newhead=NULL,將head中的數(shù)據(jù)從左到右依次頭插至newhead鏈表中。

typedef struct ListNode ListNode; 
struct ListNode* reverseList(struct ListNode* head)
{
    ListNode* newhead=NULL;
    ListNode* cur=head;
    if(cur==NULL)
    {
        return cur;
    }
    ListNode* next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        next=next->next;
    }
    return newhead;
}

注意:結(jié)束條件是cur==NULL;此時(shí)如果next往后走,next=next->next;會(huì)出現(xiàn)NULL解引用的問題。

其次要考慮cur==NULL的問題,不然ListNode* next=cur->next也是對(duì)空指針解引用。

其實(shí)可以化簡為:

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
       struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next; 
    }
    return newhead;
}

到此這篇關(guān)于C語言?超詳細(xì)介紹與實(shí)現(xiàn)線性表中的無頭單向非循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言 無頭單向非循環(huán)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言memset函數(shù)詳解

    C語言memset函數(shù)詳解

    這篇文章主要介紹了C語言中的memset()函數(shù),包括其與memcpy()函數(shù)的區(qū)別,需要的朋友可以參考下,希望能夠給你帶來幫助
    2021-09-09
  • 基于C++實(shí)現(xiàn)去除字符串頭尾指定字符功能

    基于C++實(shí)現(xiàn)去除字符串頭尾指定字符功能

    編程時(shí)我們經(jīng)常需要對(duì)字符串進(jìn)行操作,其中有一項(xiàng)操作就是去除字符串的頭(尾)指定的字符,比如空格。本文為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)這一效果,需要的可以參考一下
    2022-04-04
  • 二叉樹前序遍歷的非遞歸算法

    二叉樹前序遍歷的非遞歸算法

    這篇文章主要介紹了二叉樹前序遍歷的非遞歸算法,需要的朋友可以參考下
    2014-02-02
  • 用c++實(shí)現(xiàn)x的y次冪的代碼

    用c++實(shí)現(xiàn)x的y次冪的代碼

    以下實(shí)例是對(duì)使用c++實(shí)現(xiàn)x的y次冪的解決方法進(jìn)行了介紹。需要的朋友參考下
    2013-05-05
  • C語言修煉之路數(shù)據(jù)類型悟正法?解析存儲(chǔ)定風(fēng)魔上篇

    C語言修煉之路數(shù)據(jù)類型悟正法?解析存儲(chǔ)定風(fēng)魔上篇

    使用編程語言進(jìn)行編程時(shí),需要用到各種變量來存儲(chǔ)各種信息。變量保留的是它所存儲(chǔ)的值的內(nèi)存位置。這意味著,當(dāng)您創(chuàng)建一個(gè)變量時(shí),就會(huì)在內(nèi)存中保留一些空間。您可能需要存儲(chǔ)各種數(shù)據(jù)類型的信息,操作系統(tǒng)會(huì)根據(jù)變量的數(shù)據(jù)類型,來分配內(nèi)存和決定在保留內(nèi)存中存儲(chǔ)什么
    2022-02-02
  • 解析C++中的5個(gè)存儲(chǔ)類的作用

    解析C++中的5個(gè)存儲(chǔ)類的作用

    這篇文章主要介紹了C++中的5個(gè)存儲(chǔ)類的作用,存儲(chǔ)類是管理對(duì)象的生存期、鏈接和內(nèi)存位置的類型說明符,需要的朋友可以參考下
    2016-05-05
  • 淺析VSCode tasks.json中的各種替換變量的意思 ${workspaceFolder} ${file} ${fileBasename} ${fileDirname}等

    淺析VSCode tasks.json中的各種替換變量的意思 ${workspaceFolder} ${file} ${

    這篇文章主要介紹了關(guān)于VSCode tasks.json中的各種替換變量的意思 ${workspaceFolder} ${file} ${fileBasename} ${fileDirname}等,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有參考借鑒價(jià)值,需要的朋友可以參考下
    2020-03-03
  • C經(jīng)典算法之二分查找法

    C經(jīng)典算法之二分查找法

    這篇文章主要介紹了C經(jīng)典算法之二分查找法的相關(guān)資料,這里提供兩種方法幫助大家實(shí)現(xiàn)這樣的功能,需要的朋友可以參考下
    2017-10-10
  • Qt6遠(yuǎn)程連接MySQL數(shù)據(jù)庫的簡單易上手版

    Qt6遠(yuǎn)程連接MySQL數(shù)據(jù)庫的簡單易上手版

    在Qt應(yīng)用程序里,可實(shí)現(xiàn)遠(yuǎn)程MySQL服務(wù)器的連接操作,本文就來介紹一下Qt6遠(yuǎn)程連接MySQL數(shù)據(jù)庫,具有一定的參考價(jià)值,感興趣的可以了解一下
    2023-11-11
  • MFC程序中使用QT開發(fā)界面的實(shí)現(xiàn)步驟

    MFC程序中使用QT開發(fā)界面的實(shí)現(xiàn)步驟

    本文主要介紹了MFC程序中使用QT開發(fā)界面的實(shí)現(xiàn)步驟,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-12-12

最新評(píng)論