• [C/C++]数据结构 链表(单向链表,双向链表)

    前言:

            上一文中我们介绍了顺序表的特点及实现,但是顺序表由于每次扩容都是呈二倍增长(扩容大小是自己定义的),可能会造成空间的大量浪费,但是链表却可以解决这个问题.

    概念及结构:

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

    注意:

    1. 链式结构在逻辑上是连续的,但是在物理上不一定连续
    2. 结点一般都是从堆上申请出来的
    3. 从堆上申请的空间是按照一定的策略来分配的,两次申请的空间可能连续也可能不连续

        分类:

    1. 单向或双向
    2. 带头或不带头
    3. 循环或不循环

        虽然链表有这么多种结构,但是在实际中最常用的还是两种结构:

    • 无头单向非循环链表:

              结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈       希桶、图的邻接表等等。       

    •  带头双向循环链表:

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

    无头单向非循环链表

    接口:

    1. typedef int SLTDateType;
    2. typedef struct SListNode
    3. {
    4. 	SLTDateType data;
    5. 	struct SListNode* next;
    6. }SListNode;
    7.  
    8. // 动态申请一个节点
    9. SListNode* BuySListNode(SLTDateType x);
    10. // 单链表打印
    11. void SListPrint(SListNode* plist);
    12. // 单链表尾插
    13. void SListPushBack(SListNode** pplist, SLTDateType x);
    14. // 单链表的头插
    15. void SListPushFront(SListNode** pplist, SLTDateType x);
    16. // 单链表的尾删
    17. void SListPopBack(SListNode** pplist);
    18. // 单链表头删
    19. void SListPopFront(SListNode** pplist);
    20. // 单链表查找
    21. SListNode* SListFind(SListNode* plist, SLTDateType x);
    22. // 单链表在pos位置之后插入x
    23. void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x);
    24. // 单链表删除pos位置之后的值
    25. void SListEraseAfter(SListNode** pphead,SListNode* pos);
    26. // 在pos的前面插入
    27. SListNode* SListInsertFront(SListNode** pphead, SListNode* pos, SLTDateType x);
    28. // 删除pos位置
    29. void SLTErase(SListNode** pphead, SListNode* pos);
    30. //单链表摧毁
    31. void SLTDestroy(SLNode** pphead);

    1.动态申请结点

    1. SListNode* BuySListNode(SLTDateType x)
    2. {
    3. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    4. 	if (newnode == NULL)
    5. 	{
    6. 		perror("malloc");
    7. 		return;
    8. 	}
    9. 	newnode->data = x;
    10. 	newnode->next = NULL;
    11. }

    2.单链表打印

    1. void SListPrint(SListNode* plist)
    2. {
    3. 	SListNode* cur = plist;
    4.  
    5. 	 while (cur != NULL)
    6. 	{
    7. 		printf("%d->", cur->data);
    8. 		cur = cur->next;
    9. 	}
    10. 	printf("NULL\n");
    11. }

    3.单链表尾插

    1. void SListPushBack(SListNode** pplist, SLTDateType x)
    2. {
    3. 	SListNode* newnode = BuySListNode(x);
    4.    
    5. 	if (*pplist == NULL)
    6. 	{
    7. 		*pplist = newnode;
    8. 	}
    9. 	else
    10. 	{
    11. 		SListNode* tail = *pplist;
    12. 		while (tail->next)
    13. 		{
    14. 			tail = tail->next;
    15. 		}
    16. 		tail->next = newnode;
    17. 	}
    18. }

    4.单链表头插

    1. void SListPushFront(SListNode** pplist, SLTDateType x)
    2. {
    3. 	SListNode* newnode = BuySListNode(x);
    4. 	newnode->next = *pplist;
    5. 	*pplist = newnode;
    6. }

    5.单链表尾删

    1. void SListPopBack(SListNode** pplist)
    2. {
    3. 	assert(*pplist);
    4.  
    5.  
    6. 	SListNode* pre = NULL;
    7. 	SListNode* tail = *pplist;
    8.  
    9.  
    10. 	if ((*pplist)->next == NULL)
    11. 	{
    12. 		*pplist = NULL;
    13. 	}
    14. 	else
    15. 	{
    16. 	   /* while (tail->next)
    17. 	   {
    18. 		 pre = tail; 
    19. 		 tail = tail->next;
    20. 	   }
    21. 	     free(tail);
    22. 	     tail = NULL;
    23. 	     pre->next = NULL;*/
    24. 		SListNode* tail = *pplist;
    25. 		while (tail->next->next)
    26. 		{
    27. 			tail = tail->next;
    28. 		}
    29. 		free(tail->next);
    30. 		tail->next = NULL;
    31. 	} 
    32. }

    6.单链表头删

    1. void SListPopFront(SListNode** pplist)
    2. {
    3. 	assert(pplist);
    4.  
    5.  
    6. 	if ((*pplist)->next == NULL)
    7. 	{
    8. 		*pplist = NULL;
    9. 	}
    10. 	else
    11. 	{
    12. 		SListNode* ret = ((*pplist)->next);
    13. 		free(*pplist);
    14. 		*pplist = ret;
    15. 	}
    16. }

    7.单链表查找

    1. SListNode* SListFind(SListNode* plist, SLTDateType x)
    2. {
    3. 	assert(plist);
    4.  
    5.  
    6. 	SListNode* ret = plist;
    7. 	while (ret->data != x&&ret->next)
    8. 	{
    9. 		ret=ret->next;
    10. 	}
    11. 	if (ret->next == NULL && ret->data != x)
    12. 		return NULL;
    13. 	else
    14. 		return ret; 
    15. }

    8.摧毁单链表

    1. void SLTDestroy(SListNode** pphead)
    2. {
    3. 	SListNode* cur = *pphead;
    4. 	SListNode* ret = NULL;
    5.  
    6.  
    7. 	while (cur)
    8. 	{
    9. 		ret = cur->next;
    10. 		free(cur);
    11. 		cur = ret;
    12. 	}
    13. 	*pphead = NULL;
    14. }

    9.在pos位置之后插入x

    1. // 单链表在pos位置之后插入x
    2. void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x)
    3. {
    4. 	assert(pphead);
    5. 	//检测插入位置是否存在
    6. 	assert(pos); 
    7. 	assert(*pphead);
    8.  
    9. 	SListNode* newnode=BuySListNode(x);
    10. 	newnode->next = pos->next;
    11. 	pos->next = newnode;
    12. }

    10.删除pos位置之后的值

    1. // 单链表删除pos位置之后的值
    2. void SListEraseAfter(SListNode** pphead,SListNode* pos)
    3. {
    4. 	assert(pphead);
    5. 	assert(pos);
    6. 	assert(pos->next);
    7. 	assert(*pphead);
    8.  
    9. 	SListNode* tmp = pos->next;
    10. 	pos->next = pos->next->next;
    11. 	free(tmp);
    12. 	tmp = NULL;
    13. }

    11.在pos位置之前插入x

    1. SListNode* SListInsertFront(SListNode** pphead, SListNode* pos, SLTDateType x)
    2. {
    3. 	assert(pphead);
    4. 	assert(pos);
    5. 	assert(*pphead);
    6.  
    7. 	SListNode* newnode = BuySListNode(x);
    8. 	SListNode* pre = *pphead;
    9.  
    10. 	if (*pphead == pos)
    11. 	{
    12. 		SListPushFront(pphead,x);
    13. 	}
    14. 	else
    15. 	{
    16. 		while (pre->next != pos)
    17. 		{
    18. 			pre = pre->next;
    19. 		}
    20. 		newnode->next = pos;
    21. 		pre->next = newnode;
    22. 	}
    23. 	
    24.  
    25. }

    12.删除pos位置

    1. void SLTErase(SListNode** pphead, SListNode* pos)
    2. {
    3. 	assert(pphead);
    4. 	assert(pos);
    5. 	assert(*pphead);
    6. 	if (*pphead == pos)
    7. 	{
    8. 		SListPopFront(pphead);
    9. 	}
    10. 	else
    11. 	{
    12. 		SListNode* pre = *pphead;
    13. 		while (pre->next != pos)
    14. 		{
    15. 			pre = pre->next;
    16. 		}
    17. 		pre->next = pos->next;
    18. 		free(pos);
    19. 		pos = NULL;
    20. 	}
    21.  
    22. }

     

    带头双向循环链表

    接口:

    1. // 带头+双向+循环链表增删查改实现
    2. typedef int LTDataType;
    3. typedef struct ListNode
    4. {
    5. 	LTDataType _data;
    6. 	struct ListNode* _next;
    7. 	struct ListNode* _prev;
    8. }ListNode;
    9.  
    10. // 创建返回链表的头结点.
    11. ListNode* ListCreate();
    12. // 双向链表销毁
    13. void ListDestory(ListNode* pHead);
    14. // 双向链表打印
    15. void ListPrint(ListNode* pHead);
    16. // 双向链表尾插
    17. void ListPushBack(ListNode* pHead, LTDataType x);
    18. // 双向链表尾删
    19. void ListPopBack(ListNode* pHead);
    20. // 双向链表头插
    21. void ListPushFront(ListNode* pHead, LTDataType x);
    22. // 双向链表头删
    23. void ListPopFront(ListNode* pHead);
    24. // 双向链表查找
    25. ListNode* ListFind(ListNode* pHead, LTDataType x);
    26. // 双向链表在pos的前面进行插入
    27. void ListInsert(ListNode* pos, LTDataType x);
    28. // 双向链表删除pos位置的节点
    29. void ListErase(ListNode* pos);

    1.创建返回链表的头节点

    1. ListNode* ListCreate(LTDataType x)
    2. {
    3. 	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    4. 	if (node == NULL)
    5. 	{
    6. 		perror("malloc");
    7. 		exit(-1);
    8. 	}
    9. 	node->_data = x;
    10. 	node->_next = NULL;
    11. 	node->_prev = NULL;
    12. 	return node;
    13. }

    2.双向链表销毁

    1. void ListDestory(ListNode* pHead)
    2. {
    3. 	assert(pHead);
    4.  
    5.  
    6. 	ListNode* cur = pHead->_next;
    7. 	while (cur != pHead)
    8. 	{
    9. 		ListNode* next = cur->_next;
    10. 		free(cur);
    11. 		cur = next;
    12. 	}
    13. 	free(pHead);
    14. }

    3.双向链表打印

    1. void ListPrint(ListNode* pHead)
    2. {
    3. 	assert(pHead);
    4. 	ListNode* cur = pHead->_next;
    5. 	while (cur != pHead)
    6. 	{
    7. 		printf("%d <-> ", cur->_data);
    8. 		cur = cur->_next;
    9. 	}
    10. }

    4.双向链表尾插

    1. void ListPushBack(ListNode* pHead, LTDataType x)
    2. {
    3. 	ListNode* newnode = ListCreate(x);
    4. 	ListNode* tail = pHead->_prev;     //尾指针
    5.  
    6.  
    7. 	tail->_next = newnode;
    8. 	newnode->_next = pHead;
    9. 	newnode->_prev = tail;
    10. 	pHead->_prev = newnode;
    11. }

    5.双向链表尾删

    1. void ListPopBack(ListNode* pHead)
    2. {
    3. 	assert(pHead);
    4. 	assert(pHead->_next!=pHead);
    5.  
    6.  
    7. 	ListNode* tail = pHead->_prev;
    8.  
    9.  
    10. 	pHead->_prev = tail->_prev;
    11. 	tail->_prev->_next = pHead;
    12. 	free(tail);
    13. 	tail = NULL;
    14. }

    6.双向链表头插

    1. void ListPushFront(ListNode* pHead, LTDataType x)
    2. {
    3. 	assert(pHead);
    4.  
    5.  
    6. 	ListNode* newnode = ListCreate(x);
    7.  
    8.  
    9. 	newnode->_next = pHead->_next;
    10. 	pHead->_next->_prev = newnode;
    11. 	pHead->_next = newnode;
    12. 	newnode->_prev = pHead;
    13. }

    7.双向链表头删

    1. void ListPopFront(ListNode* pHead)
    2. {
    3. 	ListNode* pHeadNext = pHead->_next;
    4.  
    5.  
    6. 	pHeadNext->_next->_prev = pHead;
    7. 	pHead->_next = pHeadNext->_next;
    8.  
    9.  
    10. 	free(pHeadNext);
    11. 	pHeadNext = NULL;
    12. }

    8.双向链表查找

    1.  
    2. ListNode* ListFind(ListNode* pHead, LTDataType x)
    3. {
    4. 	assert(pHead);
    5. 	ListNode* cur = pHead->_next;
    6. 	while (cur != pHead)
    7. 	{
    8. 		if (cur->_data == x)
    9. 			return cur;
    10.  
    11.  
    12. 		cur = cur->_next;
    13. 	}
    14. 	return NULL;
    15. }

    9.双向链表在pos的前面进行插入

    1. void ListInsert(ListNode* pos, LTDataType x)
    2. {
    3. 	assert(pos);
    4.  
    5.  
    6. 	ListNode* posprev = pos->_prev;
    7. 	ListNode* newnode = ListCreate(x);
    8. 	newnode->_next = pos;
    9. 	pos->_prev = newnode;
    10. 	posprev->_next = newnode;
    11. 	newnode->_prev = pos->_prev;
    12. }

    10.双向链表删除pos位置的节点

    1. void ListErase(ListNode* pos)
    2. {
    3. 	assert(pos);
    4. 	
    5. 	ListNode* posprev = pos->_prev;
    6. 	ListNode* posnext = pos->_next;
    7.  
    8.  
    9. 	posprev->_next = posnext;
    10. 	posnext->_prev = posprev;
    11. 	free(pos);
    12. }

  • 相关阅读:
    window.addEventListener相关参数介绍说明
    llama笔记：官方示例解析 example_chat_completion.py
    [BJDCTF 2020]Easy
    项目立项管理
    Promise的Catch报错总结
    开源在线课堂知识付费源码系统 PHP+MySQL组合开发 支持视频、音频、图文章节 带完整的搭建教程
    设计模式浅析(一) ·策略模式
    进制转换（二进制、八进制、十进制、十六进制）
    纯前端读写文件？
    docker安装及使用-Linux
  • 原文地址：https://blog.csdn.net/m0_74910646/article/details/134474797