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

一文弄懂C語言如何實現(xiàn)單鏈表

 更新時間：2021年09月06日 16:20:29   作者：忱叁  
單鏈表是由多個結(jié)點鏈接組成,它的每個結(jié)點包含兩個域,一個數(shù)據(jù)域和一個鏈接域(地址域),下面這篇文章主要給大家介紹了關(guān)于C語言如何實現(xiàn)單鏈表的相關(guān)資料,需要的朋友可以參考下

一、單鏈表與順序表的區(qū)別：

一、順序表：

1、內(nèi)存中地址連續(xù)

2、長度可以實時變化

3、不支持隨機查找

4、適用于訪問大量元素的，而少量需要增添/刪除的元素的程序

5、中間插入或者刪除比較方便，內(nèi)存命中率較高

二、鏈表

1、內(nèi)存中地址不連續(xù)（邏輯上連續(xù)，物理上不連續(xù)）

2、長度可以實時變化（避免浪費空間）

3、不支持隨機查找，查找的時間復(fù)雜度為o(1),

4、適用于訪問大量元素的，對訪問元素?zé)o要求的程序

5、中間插入或者刪除比較方便，效率高

二、關(guān)于鏈表中的一些函數(shù)接口的作用及實現(xiàn)

1、創(chuàng)建接口，開辟空間

2、尾插尾刪

3、頭插頭刪

4、查找并修改

5、中插中刪

ps：我看了許多的單鏈表文章，在插刪的接口實現(xiàn)上大多數(shù)是往前進(jìn)行插刪，這里寫的則是往后進(jìn)行插刪

1、頭文件里的結(jié)構(gòu)體和函數(shù)聲明等等

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
 
typedef int SListDataType;
//節(jié)點
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SListNode;
 
//struct SList
//{
//	SListNode* head;
//	SListNode* tail;
//};
 
//尾插尾刪
void SListPushBack(SListNode** pphead, SListDataType x);
void SListPopBack(SListNode** pphead);
 
//頭插頭刪
void SListPushFront(SListNode**  pphead, SListDataType x);
void SListPopFront(SListNode** pphaed);
 
void SListPrint(SListNode* phead);
//查找并修改
SListNode* SListFind(SListNode* phead, SListDataType x);
//中插中刪
void SListInserAfter(SListNode**pphead,SListNode* pos, SListDataType x);
void SListEraseAfter(SListNode* pos);
 
//從頭到尾打印鏈表
void PrintTailToHead(SListNode* pList);

2、創(chuàng)建接口空間

//開辟的下一個空間
SListNode* BuySListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		printf("申請結(jié)點失敗\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
 
}

3.尾插尾刪

//尾插
void SListPushBack(SListNode** pphead, SListDataType x)
{
	SListNode* newNode = BuySListNode(x);//我們指向頭指針的那個結(jié)點是**pphead，*pphead就是頭指針的地址
	//如果頭指針的地址為空，我們就把新開辟的這個空間指針（已經(jīng)傳入值）再賦給頭指針，也就是下面的這個if循環(huán)
	if (*pphead == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		//找尾巴，判斷尾巴是不是空地址,這個函數(shù)實現(xiàn)的是尾插，我們找到尾巴后，如果尾巴是空地址，我們將插入的newNode賦給尾巴，此時
		//實現(xiàn)了尾插，在下面的代碼中，我們首先把頭指針當(dāng)成尾巴，從頭指針開始依次往后找，如果下一個不是空指針，我們就令
		//tail=tail->next,此時指向下一個結(jié)點，進(jìn)入循環(huán)繼續(xù)判斷，當(dāng)找到后，我們再令尾巴=newNode,在上面我們也判斷了頭指針為空的情況
		SListNode* tail = *pphead;
		while (tail->next!= NULL)
		{
			tail = tail -> next;
		}
		tail->next = newNode;
	}
}
void SListPopBack(SListNode** pphead)
{
	//1、空
	//2、一個結(jié)點
	//3、一個以上
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
 
		}
		free(tail);
		//tail = NULL;//這個無所謂，因為我們釋放后，出了這個作用域，tail和prev都被銷毀，沒人能拿到，所以不會被再找到
		prev->next = NULL;	
	}
}

4、頭插頭刪

//頭插頭刪
void SListPushFront(SListNode** pphead, SListDataType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SListPopFront(SListNode** pphead)
{
	//1、空
	//2、一個結(jié)點+3、一個以上
	
	if (*pphead == NULL)
	{
		return;
	}
	//(*phead)->next:*和>都是解引用，同一優(yōu)先級，我們需要給*pphead帶括號，(*pphead)->next才是下一個結(jié)點
	
	else{
		//我們頭刪也會遇到情況，我們刪除第一個的話，第一個里面還存有第二個結(jié)點的地址，我們必須在刪除前，保存第二個結(jié)點的地址
		SListNode* next = (*pphead)->next;
		free(*pphead);//通過調(diào)試我們發(fā)現(xiàn)：free前后，*pphead的地址不變，但是*pphead里的值被置為隨機值，free不僅僅把這塊空間還給操作系統(tǒng)
		  //而且還把這塊空間存的值和地址都置為隨機值
		*pphead = next;
	}
 
}

 5、單鏈表查找

//單鏈表查找
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

6、中間插入（在pos后面進(jìn)行插入）

void SListInserAfter(SListNode** pphead,SListNode* pos, SListDataType x)
{
	assert(pos && pphead);
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* newnode = BuySListNode(x);
		SListNode* tmp = *pphead;
		while (tmp->next != pos)
		{
			tmp = tmp->next;
		}
		tmp->next = pos;
		pos->next = newnode;
 
	}
	
}

 7、中間刪除（在pos后面進(jìn)行刪除）

void SListEraseAfter(SListNode* pos)
{
	//刪除pos后面的
	assert(pos);
	if (pos->next)
	{
		//pos->next=pos->next->next//不推薦
		SListNode* next = pos->next;
		SListNode* nextnext = next->next;
		pos->next = nextnext;
		free(next);
	}
}

8、單獨打印鏈表和從頭到尾打印鏈表

void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
 
 
void PrintTailToHead(SListNode* pList)
{
	if (pList == NULL)
	{
		return;
	}
	PrintTailToHead(pList->next);
	printf("%d->",pList->data);
}

9、test.c

#include"SList.h"
 
TestSList1()
{
 
	SListNode* pList = NULL;//這個結(jié)構(gòu)體指針指向開辟的空間,頭指針指向鏈表的開頭
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPrint(pList);
 
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPrint(pList);
 
	SListPushFront(&pList, 1);
	SListPushFront(&pList, 2);
	SListPushFront(&pList, 6);
	SListPushFront(&pList, 4);
	SListPushFront(&pList, 5);
	SListPrint(pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPrint(pList);
 
 
}
 
TestSList2()
{
	SListNode* pos1;
	SListNode* pList = NULL;//這個結(jié)構(gòu)體指針指向開辟的空間,頭指針指向鏈表的開頭
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPrint(pList);
	SListNode* pos = SListFind(pList, 3);
	if (pos)
	{
		pos->data = 30;//這里將cur-data改為pos->data,然后再將pos-data原來的值改為30
	}
	SListPrint(pList);
	pos1 = SListFind(pList, 30);//我們先去找到這個pos1的位置，然后再去插入
	SListInserAfter(&pList,pos1,50);//函數(shù)傳參要對應(yīng)起來，我們用指針傳用指針接收，不能在pos1位置直接寫個數(shù)字
	SListPrint(pList);
	SListEraseAfter(pos1);//pList指向第一個結(jié)點，pList->next指向第二個結(jié)點，那么我們刪除的是目標(biāo)節(jié)點后面
	SListPrint(pList);
	//PrintTailToHead(&pList);
}
int main()
{
	TestSList1();
	TestSList2();
	return 0;
	
 
}

總結(jié)

到此這篇關(guān)于C語言如何實現(xiàn)單鏈表的文章就介紹到這了,更多相關(guān)C語言實現(xiàn)單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • C++使用數(shù)組來實現(xiàn)哈夫曼樹

    C++使用數(shù)組來實現(xiàn)哈夫曼樹

    給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman?Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近
    2022-05-05
  • 使用C語言實現(xiàn)掃雷游戲

    使用C語言實現(xiàn)掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了使用C語言實現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-08-08
  • C語言動態(tài)鏈表實現(xiàn)學(xué)生學(xué)籍管理系統(tǒng)

    C語言動態(tài)鏈表實現(xiàn)學(xué)生學(xué)籍管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言動態(tài)鏈表實現(xiàn)學(xué)生學(xué)籍管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-07-07
  • 詳解C語言結(jié)構(gòu)體,枚舉,聯(lián)合體的使用

    詳解C語言結(jié)構(gòu)體,枚舉,聯(lián)合體的使用

    這篇文章主要給大家介紹一下關(guān)于C語言中結(jié)構(gòu)體、枚舉、聯(lián)合體的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考一下
    2022-07-07
  • C語言超詳細(xì)講解隊列的實現(xiàn)及代碼

    C語言超詳細(xì)講解隊列的實現(xiàn)及代碼

    隊列（Queue）與棧一樣，是一種線性存儲結(jié)構(gòu)，它具有如下特點：隊列中的數(shù)據(jù)元素遵循“先進(jìn)先出”（First?In?First?Out）的原則，簡稱FIFO結(jié)構(gòu)。在隊尾添加元素，在隊頭刪除元素
    2022-04-04
  • 詳解Matlab如何繪制圓角半透明圖例

    詳解Matlab如何繪制圓角半透明圖例

    目前MATLAB的legend圖例是不支持圓角和半透明的，所以本文將自制實現(xiàn)圓角半透明圖例。文中的示例代碼講解詳細(xì)，需要的可以參考一下
    2022-05-05
  • C++中字符串與整型及浮點型轉(zhuǎn)換全攻略

    C++中字符串與整型及浮點型轉(zhuǎn)換全攻略

    C++算法刷題等過程中經(jīng)常會遇到字符串與數(shù)字類型的轉(zhuǎn)換，在這其中雖然樸素的算法有不少，但是對于double等類型還是可以說遇到一些麻煩，所以今天就來說說使用C++標(biāo)準(zhǔn)庫中的函數(shù)實現(xiàn)這些功能。感興趣的小伙伴一起參與閱讀吧
    2021-09-09
  • C++版圖書管理系統(tǒng)

    C++版圖書管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++版圖書管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-03-03
  • 帶你了解C++初階之引用

    帶你了解C++初階之引用

    這篇文章主要為大家介紹了C++初階之引用，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-01-01
  • C語言可變長的參數(shù)列表詳解

    C語言可變長的參數(shù)列表詳解

    這篇文章主要為大家介紹了C語言可變長的參數(shù)列表，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-01-01

最新評論