当前位置：主页 > c/c++教程 > C语言链表

C语言学习之链表的实现详解

发布：2023-03-10 09:00:01 59

为找教程的网友们整理了相关的编程文章，网友后沈靖根据主题投稿了本篇教程内容，涉及到C语言、链表实现、C语言、链表、C语言链表相关内容，已被517网友关注，涉猎到的知识点内容可以在下方电子书获得。

C语言链表

一、链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

二、链表的结构

（1）单链表

（2）带头结点的单链表

（3）双向链表

（4）循环单链表

（5）双向循环链表

注释：

（1）无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

（2）带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

三、顺序表和链表的区别和联系

（1）顺序表：

优点： 空间连续，支持随机访问。

缺点： 中间或前面部分的插入删除时间复杂度为O（n），并且增容代价比较大。

（2）链表

优点： 任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。

缺点： 以节点为单位存储，不支持随机访问。

四、链表的实现

（1）单链表的增删查找等操作

#pragma once
#include"common.h"


typedef struct SListNode
{
	ElemType data;
	struct SListNode* next;
}SListNode;

typedef struct SList
{
	SListNode* head;
}SList;

///
///
//单链表的函数接口声明
void SListInit(SList* plist);
static SListNode* _Buynode(ElemType x);
void SListPushBack(SList* plist, ElemType item);//1
void SListPushFront(SList* plist, ElemType item);//2
void SListShow(SList* plist);//3
void SListPopBack(SList* plist);//4
void SListPopFront(SList* plist);//5
void SListInsertVal(SList* plist, ElemType val);//7
void SqListDeleteByVal(SList* plist, ElemType val);//9
SListNode* SListFind(SList* plist, ElemType key);//10
size_t SListLength(SList* plist);//11

void SListSort(SList* plist);//13
void SListReverse(SList* plist);//14
void SListClear(SList* plist);//15
void SListDestroy(SList* plist);

///
///
//单链表的函数接口实现
void SListInit(SList* plist)
{
	plist->head = NULL;
}
static SListNode* _Buynode(ElemType x)
{
	SListNode* s = (SListNode*)malloc(sizeof(SListNode));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	return s;
}
//1
void SListPushBack(SList* plist, ElemType item)
{
	assert(plist != NULL);
	SListNode* s = _Buynode(item);
	//插入的节点为第一个节点
	if (plist->head == NULL)
	{
		plist->head = s;
		return;
	}
	//O(n)
	SListNode* p = plist->head;
	//查找链表的尾部节点
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = s;
}
//2
void SListPushFront(SList* plist, ElemType item)
{
	assert(plist != NULL);
	SListNode* s = _Buynode(item);
	s->next = plist->head;
	plist->head = s;
}
//3
void SListShow(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	while (p != NULL)
	{
		printf("%d-->", p->data);
		p = p->next;
	}
	printf("Over.\n");
}
//4
void SListPopBack(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	if (plist->head == NULL)
	{
		printf("单链表为空，输出失败!\n");
		return;
	}
	if (p->next == NULL)
	{
		plist->head = NULL;
		return;
	}
	SListNode* prev = NULL;
	while (p->next != NULL)
	{
		prev = p;
		p = p->next;
	}
	prev->next = NULL;
	free(p);
}
//5
void SListPopFront(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	if (plist->head == NULL)
	{
		printf("单链表为空，输出失败!\n");
		return;
	}
	plist->head = p->next;
	free(p);
}
//6

//7
void SListInsertVal(SList* plist, ElemType val)
{
	assert(plist != NULL);
	SListNode* prev = NULL;
	SListNode* p = plist->head;
	SListNode* s = _Buynode(val);
	while (p != NULL && val > p->data)
	{
		prev = p;
		p = p->next;
	}
	if (prev == NULL)
	{
		s->next = p;
		plist->head = s;
	}
	else
	{
		s->next = prev->next;
		prev->next = s;
	}
}
//10
SListNode* SListFind(SList* plist, ElemType key)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	while (p != NULL && p->data != key)
		p = p->next;
	return p;
}
//9
void SqListDeleteByVal(SList* plist, ElemType val)
{
	assert(plist != NULL);
	SListNode* prev = NULL;
	SListNode* p = SListFind(plist, val);
	if (p == NULL)
	{
		printf("要删除的节点不存在.\n");
		return;
	}

	if (p == plist->head)
		plist->head = p->next;
	else
	{
		prev = plist->head;
		while (prev->next != p)
			prev = prev->next;

		//删除
		prev->next = p->next;
	}
	free(p);
}

//11
size_t SListLength(SList* plist)
{
	assert(plist != NULL);
	size_t len = 0;
	SListNode* p = plist->head;
	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	return len;
}

//13
void SListSort(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head->next;
	SListNode* q, * t, * prev = NULL;

	plist->head->next = NULL;  //断开链表

	t = plist->head;
	while (p != NULL)
	{
		q = p->next;
		while (t != NULL && p->data > t->data)
		{
			prev = t;
			t = t->next;
		}
		if (prev == NULL)
		{
			p->next = plist->head;
			plist->head = p;
		}
		else //if(prev->next!=NULL)
		{
			p->next = prev->next;
			prev->next = p;
		}
		p = q;
		t = plist->head;
	}
}

//14
void SListReverse(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head->next;
	SListNode* q;
	if (p->next == NULL)
		return;
	//断开第一个节点
	plist->head->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		p->next = plist->head;
		plist->head = p;
		p = q;
	}
}


//15
void SListClear(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	while (p != NULL)
	{
		plist->head = p->next;
		free(p);
		p = plist->head;
	}
}
void SListDestroy(SList* plist)
{
	SListClear(plist);
	plist->head = NULL;
}
```c

（2）带头的双循环链表的实现

#pragma once
#include"common.h"

/
//带头的双循环链表
typedef struct DCListNode
{
	ElemType data;
	struct  DCListNode* next;
	struct DCListNode* prev;
}DCListNode;

typedef struct DCList
{
	DCListNode* head;
}DCList;

static DCListNode* _Buydnode(ElemType x);
void DCListInit(DCList* plist);
void DCListDestroy(DCList* plist);
void DCListPushBack(DCList* plist, ElemType x);//1
void DCListPushFront(DCList* plist, ElemType x);//2
void DCListShow(DCList* plist);//3
void DCListPopBack(DCList* plist);//4
void DCListPopFront(DCList* plist);//5
void DCListInsertByVal(DCList* plist, ElemType val);//7
void DCListDeleteByVal(DCList* plist, ElemType val);//9
size_t DCListLength(DCList* plist);//11
void DCListSort(DCList* plist);//13
void DCListReverse(DCList* plist);//14
void DCListClear(DCList* plist);//15



DCListNode* DCListFind(DCList* plist, ElemType key);//10

static DCListNode* _Buydnode(ElemType x)
{
	DCListNode* s = (DCListNode*)malloc(sizeof(DCListNode));
	assert(s != NULL);
	s->data = x;
	s->next = s->prev = s;
	return s;
}

void DCListInit(DCList* plist)
{
	plist->head = _Buydnode(0);
}

//1
void DCListPushBack(DCList* plist, ElemType x)
{
	assert(plist != NULL);
	DCListNode* s = _Buydnode(x);
	s->prev = plist->head->prev;
	s->prev->next = s;
	s->next = plist->head;
	plist->head->prev = s;
}

//2
void DCListPushFront(DCList* plist, ElemType x)
{
	assert(plist != NULL);
	DCListNode* s = _Buydnode(x);

	s->next = plist->head->next;
	s->next->prev = s;
	plist->head->next = s;
	s->prev = plist->head;

}


//3
void DCListShow(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	while (p != plist->head)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("Over.\n");
}

//4
void DCListPopBack(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->prev;
	if (plist->head->next == plist->head)
		//if(p == plist->head)
	{
		printf("循环双链表只有头结点,操作失败.\n");
		return;
	}

	plist->head->prev = p->prev;
	p->prev->next = plist->head;
	free(p);
}

//5
void DCListPopFront(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	if (p == plist->head)
	{
		printf("循环双链表只有头结点,操作失败.\n");
		return;
	}

	plist->head->next = p->next;
	p->next->prev = plist->head;
	free(p);
}

//7
void DCListInsertByVal(DCList* plist, ElemType val)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	while (p != plist->head && p->data < val)
	{
		p = p->next;
	}
	DCListNode* s = _Buydnode(val);
	s->next = p;
	s->prev = p->prev;
	p->prev->next = s;
	p->prev = s;
}

//9
void DCListDeleteByVal(DCList* plist, ElemType val)
{
	assert(plist != NULL);
	DCListNode* p = DCListFind(plist, val);
	if (p == NULL)
		return;
	p->next->prev = p->prev;
	p->prev->next = p->next;
	free(p);
}


//10
DCListNode* DCListFind(DCList* plist, ElemType key)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	if (p == plist->head)
	{
		printf("双循环链表只有头结点，查找失败.\n");
		return 0;
	}
	while (p != plist->head && p->data != key)
	{
		p = p->next;
	}
	if (p != plist->head)
		return p;
	return NULL;
}


//11
size_t DCListLength(DCList* plist)
{
	assert(plist != NULL);
	size_t len = 0;
	DCListNode* p = plist->head->next;
	while (p != plist->head)
	{
		len++;
		p = p->next;
	}
	return len;
}

//13
void DCListSort(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	DCListNode* q = p->next;

	//断开链表
	p->next = plist->head;
	plist->head->prev = p;

	while (q != plist->head)
	{
		p = q;
		q = q->next;

		//寻找p插入的位置
		DCListNode* t = plist->head->next;
		while (t != plist->head && t->data < p->data)
			t = t->next;

		p->next = t;
		p->prev = t->prev;
		p->next->prev = p;
		p->prev->next = p;

		p = q;
	}
}

//14  
void DCListReverse(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	DCListNode* q = p->next;
	//断开链表
	p->next = plist->head;
	plist->head->prev = p;
	while (q != plist->head)
	{
		p = q;
		q = q->next;

		p->next = plist->head->next;
		p->prev = plist->head;
		p->next->prev = p;
		p->prev->next = p;  //plist->head->next = p;
	}
}

//15
void DCListClear(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	while (p != plist->head)
	{
		p->next->prev = p->prev;
		p->prev->next = p->next;
		free(p);
		p = plist->head->next;
	}
}

void DCListDestroy(DCList* plist)
{
	DCListClear(plist);
	free(plist->head);
	plist->head = NULL;
}

以上就是C语言学习之链表的实现详解的详细内容，更多关于C语言链表的资料请关注码农之家其它相关文章！

参考资料

相关文章

  • C语言实现经典扫雷小游戏的示例代码

    发布：2023-03-10

    扫雷游戏是在一个指定的二维空间里，随机布置雷，把不是雷的位置都找出来，在你点一个位置的时候它会显示它周围全部雷的个数，根据这个线索去找 ，会更容易赢。本文将用C语言实现这一经典游戏，感兴趣的可以尝试一下

  • Linux中使用C语言的fork()函数创建子进程的实例教程

    Linux中使用C语言的fork()函数创建子进程的实例教程

    发布：2022-07-25

    给大家整理了关于C语言的教程，fork是一个在Linux系统环境下专有的函数,现有的进程调用fork后将会创建一个新的进程,这里我们就来看一下Linux中使用C语言的fork()函数创建子进程的实例教程

  • C语言数据结构不挂科指南之线性表详解

    发布：2023-03-02

    线性表是由 n(n≥0)个数据元素组成的有穷序列，这篇文章主要来和大家来了C语言数据结构中的线性表，感兴趣的小伙伴可以跟随小编一起了解一下

  • C语言实现C++继承和多态的实例内容

    发布：2021-06-10

    本文主要给大家简单讲诉了C和C++的区别以及如何使用C语言模拟实现C++继承和多态，并附上示例代码，是篇相当不错的文章，推荐给喜欢C语言的小伙伴们

  • C语言 实现归并排序算法

    C语言 实现归并排序算法

    发布：2022-06-26

    为网友们分享了关于C语言的教程，这篇文章主要介绍了C语言 实现归并排序算法的相关资料,需要的朋友可以参考下

  • VScode上配置 c语言环境的图文教程

    发布：2022-04-16

    这篇文章主要介绍了配置VScode c语言环境，本文通过图文并茂的形式给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下

  • C语言实现单链表的基本操作分享

    发布：2023-03-06

    单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。本文将为大家介绍C语言中单链表的基本操作，需要的可以参考一下

  • C语言中-a++和-++a运算顺序实例解析

    发布：2023-03-12

    C语言中的a++和++a的区别在于混合表达式中运算符的处理顺序,下面这篇文章主要给大家介绍了关于C语言中-a++和-++a运算顺序的相关资料,文中通过图文介绍的非常详细,需要的朋友可以参考下

网友讨论

最新更新
最近更新
热门资源