国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除

2年前作者：敲敲er分類：Toy博客閱讀(25)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

目錄

?單向鏈表的概念及結(jié)構(gòu)

?尾插

頭插

尾刪

?編輯

?頭刪

?查找

?在pos位置前插

?在pos位置后插

?刪除pos位置

?刪除pos的后一個(gè)位置

總結(jié)

代碼?

?單向鏈表的概念及結(jié)構(gòu)

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

?單向鏈表的結(jié)構(gòu)：【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

注意:

  1. 從上圖可看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)。
  2. 現(xiàn)實(shí)中的結(jié)點(diǎn)一般都是從堆上申請出來的。
  3. 從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續(xù)，也可能不連續(xù)。?
  • ?無頭單向非循環(huán)鏈表:結(jié)構(gòu)簡單, 一般不會單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

?尾插

尾插分為兩種情況：

  1. 一開始沒有鏈表：當(dāng)開始沒有鏈表，直接將newnode賦給*pphead，通過二級指針改變plist。
  2. 一開始有鏈表：當(dāng)開始有鏈表，創(chuàng)建一個(gè)結(jié)構(gòu)體指針tail，來找到最后一個(gè)節(jié)點(diǎn)，再將newnode賦給最后一個(gè)節(jié)點(diǎn)的next。

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

頭插

頭插分為兩種情況，開始有鏈表和開始沒有鏈表，但是兩種情況不需要分類考慮，先將*pphead即plist賦給newnode->next，再將newnode連上*pphead。

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

尾刪

?尾刪分兩種情況考慮：

  1. 只有一個(gè)節(jié)點(diǎn)：給*pphead賦空值
  2. 一個(gè)以上節(jié)點(diǎn)：確定尾節(jié)點(diǎn)tail后，通過tail的前一個(gè)節(jié)點(diǎn)tailprev，進(jìn)行tailprev->next=NULL賦空值或者直接通過tail->next->next找倒數(shù)第二個(gè)節(jié)點(diǎn)，再給tail->next賦空值。

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?頭刪

?頭刪不需要分情況，直接將第一個(gè)節(jié)點(diǎn)的next即第二個(gè)節(jié)點(diǎn)的地址通過newnode的中轉(zhuǎn)賦給*pphead。【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?查找

創(chuàng)建一個(gè)結(jié)構(gòu)體指針cur，鏈表中遍歷查找cur->data==x的節(jié)點(diǎn)，找到后返回cur，方便后面的修改功能。

?（不需要修改，所以傳入函數(shù)的是一級指針）

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?在pos位置前插

?分兩種情況考慮：

  1. 當(dāng)pos為第一個(gè)節(jié)點(diǎn)，相當(dāng)于頭插，調(diào)用頭插函數(shù)即可。
  2. 當(dāng)pos不為第一個(gè)節(jié)點(diǎn)，通過pos的前一個(gè)節(jié)點(diǎn)prev，將newnode插入pos前面。?

??????【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?在pos位置后插

在pos位置后插，先將pos->next賦給newnode->next，把newnode和d3連上，再將newnode賦給pos->next,連上d2。

注意：在兩個(gè)語句不能換位置，不然成環(huán)，循環(huán)打印

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?刪除pos位置

?分兩種情況：

  1. pos在第一個(gè)節(jié)點(diǎn)位置，直接調(diào)用頭刪函數(shù)即可。
  2. pos不在第一個(gè)節(jié)點(diǎn)位置，通過pos的前一個(gè)節(jié)點(diǎn)prev，將pos->next賦給prev->next，達(dá)到將pos節(jié)點(diǎn)刪除的效果。

?【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?刪除pos的后一個(gè)位置

刪除pos的后一個(gè)位置，需要先檢測pos->next是否為空值，為空值就直接返回，若pos->next不為空賦給posNext，再將posNext->next賦給pos->next達(dá)到刪除posNext節(jié)點(diǎn)，后面可以free(posNext)釋放posNext節(jié)點(diǎn)，再posNext=NULL給它賦空值。

?【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

無頭刪除pos位置

?不給頭節(jié)點(diǎn)的情況下，可以先通過pos->data=posNext->data的方式交換內(nèi)容，再刪除pos的下一節(jié)點(diǎn)posNext，將pos替換為posNext，達(dá)到和刪除pos一樣的效果。

但是這種方法的缺點(diǎn)是當(dāng)pos本身為尾節(jié)點(diǎn)時(shí)，不能通過下一節(jié)點(diǎn)posNext來使用替換法。

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

?

代碼

【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

總結(jié)

?在上面眾多單向鏈表的實(shí)現(xiàn)中，很多并不實(shí)用，當(dāng)需要大量的頭插頭刪時(shí)，使用單向鏈表會更高效。

代碼?

?SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>




typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//typedef struct SListNode SLTNode;

//打印
void SLTPrint(SLTNode* phead);


SLTNode* BuySListNode(SLTDataType x);


//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);


//尾刪
void SLTPopBack(SLTNode** pphead);


//頭插
void SLTPushBack(SLTNode** pphead, SLTDataType);


//頭刪
void SLTPopFront(SLTNode** pphead);


//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);


//在pos位置前插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);


//在pos位置后插
void SLTInsertAfter(SLTNode* pos, SLTDataType x);


//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);


//刪除pos的后一個(gè)位置
void SLTEraseAfter(SLTNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"


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



SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;

}

尾插  phead是plist的形參   //開始就有鏈表
//void SLTPushBack(SLTNode* phead, SLTDataType x)
//{
//	SLTNode* newnode = BuySListNode(x);
//	SLTNode* tail = phead;
//	while (tail->next != NULL)
//	{
//		tail = tail->next;
//	}
//	tail->next = newnode;
//}

//尾插  //包括一開始沒有鏈表
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		//改變結(jié)構(gòu)體的指針，所以要用二級指針
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//改變的結(jié)構(gòu)體，用結(jié)構(gòu)體的指針即可
		tail->next = newnode;
	}
}



//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}



//尾刪
void SLTPopBack(SLTNode** pphead)
{
	//1.空
	assert(*pphead);
	//2、一個(gè)節(jié)點(diǎn)
	//3、一個(gè)以上節(jié)點(diǎn)
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//方法1.
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
		
		方法2.
		//SLTNode* tail = *pphead;
		//while (tail->next->next)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	}

}



//頭刪
void SLTPopFront(SLTNode** pphead)
{
	//空
	assert(*pphead);

	//非空
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}


//查找是否有x這個(gè)數(shù),找到返回指向該數(shù)的指針
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


//在pos位置前插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);

	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}


//在pos位置后插
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);
	
	//下面兩句不能交換位置，否則會成環(huán)
	newnode->next = pos->next;
	pos->next = newnode;
}


//刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);

	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	//else if (pos->next == NULL)
	//{
	//	SLTPopBack(pphead);
	//}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}		
		//free(prev->next);//不要free，不然這個(gè)節(jié)點(diǎn)后面全沒了
		prev->next = pos->next;		
	}
}



//刪除pos后一個(gè)位置
void SLTEraseAfter(SLTNode* pos)
{
	//
	assert(pos);

	//檢測pos是否是尾節(jié)點(diǎn)
	//assert(pos->next);//暴力檢測
	if (pos->next == NULL)//溫和檢測
	{
		return NULL;
	}

	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;

}

?Test.c文章來源地址http://www.zghlxwxcb.cn/news/detail-743505.html

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"


void TestSList1()
{
	int n;
	printf("請輸入鏈表的長度：");
	scanf("%d", &n);
	printf("\n請依次輸入每個(gè)節(jié)點(diǎn)的值：");
	SLTNode* plist = NULL;

	for (size_t i = 0; i < n; i++)
	{
		int val;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);


		//頭插
		newnode->next = plist;
		plist = newnode;

	}

	SLTPrint(plist);
	SLTPushBack(&plist, 1000);
	SLTPrint(plist);

}

void TestSList2()
{
	SLTNode* plist = NULL;
	
	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);
}


void TestSList3()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	頭插
	//SLTPushFront(&plist, 10);
	//SLTPushFront(&plist, 20);
	//SLTPushFront(&plist, 30);
	//SLTPushFront(&plist, 40);
	//SLTPrint(plist);

	//尾刪
	SLTPopBack(&plist);
	//SLTPopBack(&plist);
	//SLTPopBack(&plist);
	//SLTPopBack(&plist);
	//SLTPopBack(&plist);
	SLTPrint(plist);


}



void TestSList4()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);




	//頭刪
	SLTPopFront(&plist);
	SLTPrint(plist);
}


void TestSList5()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);


	//查找
	SLTNode* pos = SLTFind(plist, 40);
	if (pos)
	{
		pos->data *= 10;
	}
	SLTPrint(plist);
}

void TestSList6()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);

	//在pos位置前插
	int x;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsert(&plist, pos, x * 10);
	}
	SLTPrint(plist);
}


void TestSList7()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);

	//在pos位置后插
	int x;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTInsertAfter(pos, x * 10);
	}
	SLTPrint(plist);
}


void TestSList8()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);

	//刪除pos位置
	int x;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTErase(&plist, pos);
		pos = NULL;
	}
	SLTPrint(plist);
}



void TestSList9()
{
	SLTNode* plist = NULL;

	//尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);

	//頭插
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushFront(&plist, 40);
	SLTPrint(plist);

	//刪除pos后一個(gè)位置
	int x;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	if (pos)
	{
		SLTEraseAfter(pos);
		pos = NULL;
	}
	SLTPrint(plist);
}








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




int main()
{
	
	//TestSList1();
	// 頭插 尾插
	//TestSList2();
	// 尾刪
	//TestSList3();
	// 頭刪
	//TestSList4();
	// 查找
	//TestSList5();
	// pos位置前插
	//TestSList7();
	// pos位置后插
	//TestSList8();
	// 刪除pos位置
	TestSList9();
	//刪除pos的后一個(gè)位置
	//TestSList10();

	return 0;
}

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】單向鏈表的增刪查改以及指定pos位置的插入刪除的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包