首頁 > 軟體

C語言 超詳細介紹與實現線性表中的無頭單向非迴圈連結串列

2022-03-29 19:01:27

一、本章重點

  • 無頭單向非迴圈連結串列介紹
  • 無頭單向非迴圈連結串列常用介面實現
  • 線上oj訓練

二、連結串列介紹

概念：連結串列是一種物理儲存結構上非連續、非順序的儲存結構，資料元素的邏輯順序是通過連結串列 中的指標連結次序實現的。

簡單的說：連結串列就是一些結構體相互關聯起來，而關聯的手段就是指標，通過儲存下一個結構體的地址，就能挨個存取存在結構體裡的資料。

相比於順序表來說。連結串列能夠解決順序表的一些缺點。

  • 從記憶體角度來說：無論是靜態順序表還是動態順序表都會有一定的記憶體浪費，連結串列則是用一個節點申請一個節點，無記憶體浪費。
  • 從效率角度上來說：順序表不管是頭插還是中間插入與刪除都要行動資料，時間複雜度是O（N）。而連結串列則只要改變指標指向即可達到插入和刪除的效果。

實際中要實現的連結串列的結構非常多樣，以下情況組合起來就有8種連結串列結構：

1. 單向、雙向

2. 帶頭、不帶頭

3. 迴圈、非迴圈

帶頭：

存在一個哨兵位的節點，該節點不儲存任何有效資料，屬於無效節點，但通過這個無效節點當頭節點讓我們在某些方面使用會有一些優勢。

比如，你頭插新節點時，不需要傳二級指標，因為我們的頭節點始終指向這個無效節點。

帶頭單向非迴圈連結串列

雙向：

指的是節點中不再只有一個指標，而是有兩個指標，一個指向前一個節點，另一個指向後一個節點。

無頭雙向非迴圈連結串列

迴圈：

尾指標不再指向NULL，而是指向頭節點。 

無頭單向迴圈連結串列

三、無頭單向非迴圈連結串列常用介面實現

3.1動態申請一個節點

SLTNode* BuySListNode(SLDataType x)
{
	SLTNode* newnode = malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		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("NULLn");
}

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位置的節點

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訓練

4.1移除連結串列元素（力扣）

給你一個連結串列的頭節點 head 和一個整數 val ，請你刪除連結串列中所有滿足 Node.val == val 的節點，並返回 新的頭節點 。

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

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

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

輸出：[]

 思路：

前後指標（跟班指標），初始轉態prev指向NULL，cur指向head，如果出現cur->val==val.

就進行刪除，刪除步驟為prev->next==cur->next;cur=cur->next。迭代過程為：prev=cur,cur==cur->next。

特殊情況，如果要刪除的val為頭節點，則刪除步驟為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反轉單連結串列（力扣）

給你單連結串列的頭節點 head ，請你反轉連結串列，並返回反轉後的連結串列。

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

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

輸入：head = []

輸出：[]

這裡提供一個頭插思路：newhead=NULL,將head中的資料從左到右依次頭插至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;
}

注意:結束條件是cur==NULL;此時如果next往後走，next=next->next;會出現NULL解除參照的問題。

其次要考慮cur==NULL的問題，不然ListNode* next=cur->next也是對空指標解除參照。

其實可以化簡為：

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

到此這篇關於C語言 超詳細介紹與實現線性表中的無頭單向非迴圈連結串列的文章就介紹到這了,更多相關C語言 無頭單向非迴圈連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！


相關文章

  • 德漢姆中學就讀條件 德漢姆中學就讀條件

    <em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011

    2021-06-01 09:32:01

  • 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列 黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列

    综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所

    2021-06-01 09:31:42

  • 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！ 吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！

    除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让

    2021-06-01 09:31:34

  • IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？ IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？

    目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加

    2021-06-01 09:31:24

  • 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊 有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊

    开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的

    2021-06-01 09:30:48

  • iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？ iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？

    不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它

    2021-06-01 09:30:45

IT145.com E-mail:sddin#qq.com