单链表的基本操作-白红宇

单链表的基本操作

阅读量：6882 次

发布时间：2019-06-27

本文共 7036 字，大约阅读时间需要 23 分钟。

链表概述
　　链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
链表的各类操作包括：单向链表的创建、删除（头删、尾删）、插入（头插、C和C++尾插）、输出、查找某一个结点、指定位置删除某结点等。

各种操作代码如下：

#include"SListNode.h"SListNode* _BuyNode(DataType x)//开辟新节点{	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));	tmp->data = x;	tmp->next = NULL;	return tmp;}void PrintSList(SListNode* & pHead)//打印单链表{	SListNode* cur = pHead;	if (pHead == NULL)	{		printf("SListNode is NULL!\n");		return;	}	while (cur)	{		printf("%d->", cur->data);		cur = cur->next;	}	printf("NULL");}void DestoryList(SListNode* & pHead)//释放空间{	SListNode* cur = pHead;	while (cur)	{		SListNode* tmp = cur;		cur = cur->next;//顺序不可以颠倒		free(tmp);	}	pHead = NULL;}void PushBack_C(SListNode** pHead, const DataType x)//c尾插{	//情况1.单链表为空；情况2.单链表不为空	assert(pHead);	if (*pHead == NULL)		*pHead = _BuyNode(x);	else	{		SListNode* tail = *pHead;		while (tail->next != NULL)//找尾			tail = tail->next;		tail->next = _BuyNode(x);	}}void PushBack_Cpp(SListNode* & pHead, const DataType x)//c++尾插,使用引用{//引用相当于定义一个别名,不需断言指针	//情况1.单链表为空；情况2.单链表不为空	if (pHead == NULL)		pHead = _BuyNode(x);	else	{		SListNode* tail = pHead;		while (tail->next != NULL)//找尾			tail = tail->next;		tail->next = _BuyNode(x);	}}void PopBack(SListNode* & pHead)//尾删{	// 注意：单链表为空、一个节点以及多个节点的情况	if (pHead == NULL)	{		printf("SListNode is NULL!\n");		return;	}	else if (pHead->next == NULL)	{//删除节点时置空并释放空间		pHead = NULL;		free(pHead);	}	else	{		SListNode* tail = pHead;		while (tail->next->next != NULL)		{//1 2 3 4删除4需要找到3(tail)			tail = tail->next;		}		tail->next = NULL;		free(tail->next);	}}void PushFront(SListNode* & pHead, const DataType x)//头插{//单链表为空、不为空	if (pHead == NULL)		pHead = _BuyNode(x);	else	{//利用两个指针pHead、tmp移动		SListNode* tmp = _BuyNode(x);		tmp->next = pHead;//针对没有头结点的情况		pHead = tmp;	}}void PopFront(SListNode* & pHead)//头删{	// 注意：单链表为空、一个节点以及多个节点的情况	if (pHead == NULL)	{		printf("SListNode is NULL!\n");		return;	}	else	{		SListNode* newhead = pHead->next;		free(pHead);		pHead = newhead;	}}SListNode* Find(SListNode* pHead, const DataType x)//查找某数结点{	SListNode* cur = pHead;	while (cur)	{		if (cur->data == x)			return cur;		cur = cur->next;	}	printf("%d Position is not exist!", x);	return NULL;}void Insert(SListNode* pos, const DataType x)//指定位置pos后插入新结点{	assert(pos);//断言pos有效性	SListNode* tmp = _BuyNode(x);	tmp->next = pos->next;	pos->next = tmp;}void Erase(SListNode* & pHead, SListNode* pos)//删除某结点{//考虑单链表是否空、pos是否为首元节点	assert(pos);	if (pos == pHead)	{		pHead = pHead->next;		free(pos);	}	SListNode* prev = pHead;	while (prev)	{//1 2 3 4删除第三个节点3需找到其前一个节点2		if (prev->next == pos)		{			prev->next = pos->next;			pos = NULL;			free(pos);			return;		}		prev = prev->next;	}}

各函数测试用例如下：

#include"SListNode.h"void Test1(){//尾插尾删	SListNode *phead = NULL;//注意需要置空	PushBack_C(&phead, 1);	PushBack_C(&phead, 2);	PushBack_Cpp(phead, 3);	PushBack_Cpp(phead, 4);	PrintSList(phead);	PopBack(phead);	PopBack(phead);	printf("\n---------------------\n");	PrintSList(phead);	PopBack(phead);	PopBack(phead);	printf("\n---------------------\n");	PopBack(phead);	printf("\n---------------------\n");	PrintSList(phead);	DestoryList(phead);}void Test2(){//头插头删	SListNode *phead = NULL;	PushFront(phead, 1);	PushFront(phead, 2);	PushFront(phead, 3);	PushFront(phead, 4);	PrintSList(phead);	PopFront(phead);	PopFront(phead);	printf("\n---------------------\n");	PrintSList(phead);	PopFront(phead);	PopFront(phead);	printf("\n---------------------\n");	PopFront(phead);	printf("\n---------------------\n");	PrintSList(phead);	DestoryList(phead);}void Test3(){//查找某数节点、插入/删除新结点	SListNode *phead = NULL;	PushBack_Cpp(phead, 1);	PushBack_Cpp(phead, 2);	PushBack_Cpp(phead, 3);	PushBack_Cpp(phead, 5);	PushBack_Cpp(phead, 7);	PushBack_Cpp(phead, 6);	PrintSList(phead);	printf("\n---------------------\n");	printf("%d\n", Find(phead, 3)->data);	printf("\n---------------------\n");	Insert(Find(phead, 3), 4);	PrintSList(phead);	printf("\n---------------------\n");	Erase(phead, Find(phead, 7));	PrintSList(phead);	DestoryList(phead);}int main(){	Test1();	printf("\n***********************\n");	Test2();	printf("\n***********************\n");	Test3();	system("pause");}

头文件如下：

#pragma once#ifndef __SLISTNODE_H__#define __SLISTNODE_H__#define _CRT_SECURE_NO_WARNINGS 1#include 
     
      #include 
      
       #include
       
        typedef int DataType; typedef struct SListNode{	DataType data;	struct SListNode* next;}SListNode;SListNode* _BuyNode(DataType x);//开辟新节点void PrintSList(SListNode* & pHead);//打印单链表void PushBack_Cpp(SListNode* & pHead, const DataType x);//c++尾插void PushBack_C(SListNode** pHead, const DataType x);//c尾插void PopBack(SListNode* & pHead);//尾删void PushFront(SListNode* & pHead, const DataType x);//头插void PopFront(SListNode* & pHead);//头删SListNode* Find(SListNode*  pHead, const DataType x);//查找某数结点void Insert(SListNode* pos, const DataType x);//指定位置pos后插入新结点void Erase(SListNode* & pHead, SListNode* pos);//删除某结点void DestoryList(SListNode* & pHead);//释放空间void PrintTailToHead(SListNode* pHead);//从尾到头打印单链表void DelNonTailNode(SListNode* pos);//删除一个无头单链表的非尾节点void InsertFrontNode(SListNode* pos, DataType x);//在无头单链表的一个非头结点前插入一个节点SListNode* Rverse(SListNode* pHead);//逆置/反转单链表SListNode* FindMidNode(SListNode* pHead);//查找单链表的中间节点，要求只能遍历一次链表SListNode* FindMidNode(SListNode* pHead, DataType k);//查找单链表的倒数第k个节点，要求只能遍历一次链表SListNode* MergeList(SListNode* L1, SListNode* L2);//合并两个有序链表，合并后依然有序void BubbleSort(SListNode* pHead);//冒泡排序单链表SListNode* JosephCycle(SListNode* pHead, int k);//单链表实现约瑟夫环//判断单链表是否带环？若带环，求环长度，求环入口点SListNode* CheckCycle(SListNode* pHead);//检查是否带环int GetCycleLength(SListNode* MeetNode);//求环的长度SListNode* GetEntryNode1(SListNode* pHead);//求环的入口地址SListNode* GetEntryNode2(SListNode* pHead);//求环的入口地址#endif //__SLISTNODE_H__

链表操作的其他实现见本人博客：

【面试题】单链表的操作1

【面试题】单链表的操作2

堆栈的简述：

1、管理方式和碎片问题

对于栈来讲，是由编译器自动管理，无须手工控制；对于堆来说，释放工作由程序员来控制，容易产生内存碎片；对于堆，频繁的new / delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序的效率降低。对于栈来讲，则不会出现这样的问题，因为栈是先进后出的队列，不可能有一个非栈顶的内存块从栈中间弹出，在它弹出之前，它上面后进的栈内容已经被弹出，因此不会出现不连续的碎片。

-----------------------------------------------------------------------------------------

2、分配效率

栈是系统提供的数据结构，计算机会在底层对栈提供支持，分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C / C++提供的，它的机制相对复杂；例如分配一块内存，会按照一定的算法（内存分配算法）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的内存空间（可能由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低很多。

-----------------------------------------------------------------------------------------

3、增长的方向不同

栈内存由一个栈指针esp来开辟和回收，栈内存是从高地址向低地址增长的，增长时，栈指针是向低地址方向移动，指针的地址值也就相应的减小；回收时，栈指针向高地址方向移动，地址值也就增加。所以栈内存的开辟与回收都只是指针的加减。

对于堆来讲，增长的方向是向上的，也就是向着内存高地址的方向移动；回收时，指针向低地址方向移动，地址值也就减小。

-----------------------------------------------------------------------------------------

4、空间大小不同

一般来讲32位的系统下，堆内存可以达到4GB的空间，从这个角度来看堆内存几乎是没什么限制的。但是对于栈来讲，一般都有一定的空间大小。无论是堆还是栈，都要防止越界现象的发生，因为越界的结果要么是程序崩溃，要么是摧毁程序的堆、栈结构，产生意想不到的结果。

转载于:https://blog.51cto.com/luoyafei/1736387

你可能感兴趣的文章