devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（四）—— 线性表的链式存储_线性表的链式存储结构

作者：知新_RL | 2024-04-15 17:42:28

赞

踩

线性表的链式存储结构

线性表的链式存储

目录

1.链式存储结构与顺序存储结构的比较

2.单链表、双链表与循环链表

3.单链表的实现

1.链式存储结构与顺序存储结构的比较

        顺序存储的特点：已物理相邻表示逻辑关系，任一元素均可随机存取。

        链式存储的特点：用一组物理位置任意的存储单元来存放线性表的数据元素，这组存储单元可以是连续的也可以是不连续的，甚至可以分布在内存中的任意位置上，链表中元素的逻辑次序和物理次序不一定相同。

        两种存储方式可以用下图来辅助理解。

顺序存取：查找第i个位置的数据，需要通过从第一个到第i个，顺序查找，所以存取的时候都是需要按顺序进行，所以叫顺序存取。

随机存取：随便一个i位置的数据，可以通过查找数组第 （i-1）个来查找，存取的时候同样可以存第i个位置或者取第i个位置的元素，所以叫随机存取。

可以用以下图来辅助理解：

2.单链表

        单链表，指结点只有一个指针域的链表，也可以称为线性链表。每个单链表都有一个头指针，也就是链表的首地址，其结点分为两个部分，一个是指针域一个是数据域（如下图所示），其中指针域存下一个结点的地址，而数据域为该结点存放的元素。

        用单链表的方式来表示线性表，有两种方式，带头结点跟不带头结点。不带头结点，顾名思义就是链表的头指针指向的下一个即为首元素结点；而带头结点的链表则头指针指向头结点，而头结点再指向首元素结点。如下图所示：

 

         带头结点的好处：

        便于首元素结点的处理：首元素结点的地址保存在头结点的指针域中，所以在链表中的第一个位置上的操作和其他位置的一致，无需进行特殊处理。

        便于空表和非空表的统一处理：无论链表是否为空，头指针都只想头结点的非空指针，因此空表和非空表的处理也就一致了。

3.单链表的实现

        单链表定义：用结构体的方式定义，定义一个数据域跟一个指针域。这里实现的是不带头结点的单链表。

 这段代码的ElenType为data的类型（相当于结构体的自定义类型）；

  1. typedef int ElemType; //定义数据类型
  2. typedef struct LNode  //声明结点的类型和指向结点的指针类型
  3. {
  4. 	ElemType data;       //结点的数据域
  5. 	struct LNode* next;  //结点的指针域
  6. }LNode,*LinkList;        //LinkList为指向结构体Lnode的指针

注：定义的结构体LNode的类型名称为LNode其指针的为LinkList。即  *LNode = LinkList ,因为后面的函数多数都是对链表的指针域进行操作，所以定义指针类型LinkList方便后面的操作。

定义函数的操作：

  1.  
  2. #define TRUE 1
  3. #define FALSE 0
  4. #define VETERY 1 
  5. #define DEFEAT 0
  6. #define NOFINE 0
  7. typedef int Status;
  8.  
  9. Status InitLinkList(LinkList L); //初始化单链表
  10. LinkList List_HeadInsert(LinkList L); //头插入法
  11. LinkList List_TailInsert(LinkList L); //尾插入法
  12. LNode* GetElem(LinkList L, int i);  //按序号查找结点值
  13. LNode* LocateElem(LinkList L, ElemType e); //按照结点值查找结点
  14. void Delete_Node(LinkList L, int i); //按序号删除结点
  15. void Print_Node(LinkList L);  //打印单链表
  16. int Linklength(LinkList L);   //计算结点个数
  17. int ListEmpty(LinkList L);    //判断单链表是否为空
  18. Status ClearList(LinkList L); //清空单链表
  19. Status DestroyList(LinkList L);  //销毁单链表

 单链表的基本操作：对单链表进行初始化、建立、判断空值、取值、查找、删除、打印、求表长、清空、销毁十一个操作进行编写代码。

代码块粘贴在最后

初始化，即开辟一个空间，创建单链表的头指针；

  1. Status InitLinkList(LinkList L) //初始化单链表
  2. {
  3. 	L = (LinkList)malloc(sizeof(LNode));  //开辟一个指针
  4. 	L->next = NULL; //单链表没有下一个指针
  5. 	return VETERY;
  6. }

注：(强制转换的类型)malloc(sizeof(类型空间))，malloc是C语言进行开辟空间的函数，如果还不理解的话，可以去看看官方文档的解释。

判断单链表是否为空，只要头指针指向的下一个地址不为空，则还有元素结点在。

  1. int ListEmpty(LinkList L)    //判断单链表是否为空
  2. {
  3. 	if (L->next)
  4. 	{
  5. 		printf("链表不为空！\n");
  6. 		return FALSE;
  7. 	}
  8. 		
  9. 	else
  10. 	{
  11. 		printf("链表为空！\n");
  12. 		return TRUE;
  13. 	}		
  14. }

清空单链表

        清空单链表采用两个指针进行操作，通过定义p指针为L->next，则为首元素结点，然后用另外一个q指针指向p->next则为第二个元素结点，然后释放p指针free(p)，在将q指针赋予给p指针，然后通过不断释放p指针从而实则释放全部的元素结点。下图辅助理解：

  1. Status ClearList(LinkList L) //清空单链表
  2. {
  3. 	LinkList p, q;
  4. 	p = L->next;
  5. 	while (p)
  6. 	{
  7. 		q = p->next;
  8. 		free(p);
  9. 		p = q;
  10. 	}
  11. 	L->next = NULL;
  12. 	return VETERY;
  13. }

销毁单链表

        销毁单链表将整个单链表的空间都释放掉，因此是从头指针开始往后释放每一个结点。

  1. Status DestroyList(LinkList L)  //销毁单链表
  2. {
  3. 	LinkList p;
  4. 	while (L)
  5. 	{
  6. 		p = L;
  7. 		L = L->next;
  8. 		free(p);
  9. 	}
  10. 	return VETERY;
  11. }

求单链表长度

  1. int Linklength(LinkList L)   //求单链表长度
  2. {
  3. 	int k = 0;
  4. 	while (L->next != NULL)
  5. 	{
  6. 		k++;
  7. 		L = L->next;	
  8. 	}
  9. 	return k;
  10. }

打印单链表

  1. void Print_Node(LinkList L)   //打印单链表
  2. {
  3. 	while (L->next != NULL)
  4. 	{
  5. 		L = L->next;
  6. 		printf("%d ", L->data);
  7.  
  8. 	}
  9. 	printf("\n");
  10. }

头插法建立单链表

        通过从第一个元素结点进行插入结点，可以由下图辅助理解：

  1. LinkList List_HeadInsert(LinkList L)//头插入法
  2. {
  3. 	LNode *new;
  4. 	int i = 10;
  5. 	for (i = 0; i < 10; i++)
  6. 	{
  7. 		new = (LNode*)malloc(sizeof(LNode));   //开辟一个新指针空间
  8. 		new->data = i;    //给指针的数据域赋值
  9. 		new->next = L->next;   //将新结点的下一个指针指向首元素结点，则代替首元素结点
  10. 		L->next = new;  //头指针指向新结点，即新节点为首元素结点
  11. 	}
  12. 	return L;
  13. }

 尾插法建立单链表

        顾名思义，就是从尾部插入元素，通过下图进行辅助理解：

  1. LinkList List_TailInsert(LinkList L) //尾插入法
  2. {
  3. 	LNode* new;
  4. 	LNode* tail = L;
  5. 	for (int i = 0; i < 10; i++)
  6. 	{
  7. 		new = (LinkList)malloc(sizeof(LNode));
  8. 		new->data = i;
  9. 		tail->next = new; //将最后一个结点下一个指向new指针
  10. 		tail = new;       //最后一个指针为new指针
  11. 	}
  12. 	tail->next = NULL;    //最后一个指针指向NULL
  13. 	return L;
  14. }

 按序号查找结点值

        通过序号 i 来查找相对应的结点值，通过第一个到第 i 个结点，从而返回结点地址，通过结点地址可以获取到对应的结点值。

  1. LinkList GetElem(LinkList L, int i)    //按序号查找结点值
  2. {
  3. 	int j = 1;
  4. 	LNode* p = L->next;  //定义辅助指针p
  5. 	if (i == 0)          //如果为0，则返回头指针地址
  6. 		return L;
  7. 	if (i < 1)           //如果小于1则返回NULL空指针
  8. 		return NULL;
  9. 	while (p && j < i)   //在j>=i和p不为NULL之前，循环继续
  10. 	{
  11. 		p = p->next;     //p指下一个指针
  12. 		j++;             //j+1
  13. 	}                    //查找得到的话为j=i时返回，查找不到，则一直到p为NULL
  14. 	return p;      
  15. }

按值查找表结点

        通过第一个结点的data开始与目标值e进行对比，直到查找到，则返回结点值。若果没有则返回NULL。

  1. LinkList  LocateElem(LinkList L, ElemType e) //按照结点值查找结点
  2. {
  3. 	LNode* p = L->next;
  4. 	while (p->data != e && p != NULL)
  5. 	{
  6. 		p = p->next;
  7. 	}
  8. 	return p;
  9. }

按序号删除结点

        通过GetElem函数查找结点的前驱指针，然后将前驱指针 p 指向待删除结点 q 的后继指针，从而释放待删除结点free(q)。通过下图进行辅助理解：

  1. void Delete_Node(LinkList L, int i) //按序号删除结点
  2. {
  3. 	LinkList  p = GetElem(L, i - 1);  //查找前驱结点
  4. 	LinkList  q;                    
  5. 	q = p->next;                      //令q等于待删除结点
  6. 	p->next = q->next;                //将p的下一个指向q的下一个
  7. 	free(q);                          //删除q
  8. }

代码：

 test.c

  1. #include "LinkList.h"
  2.  
  3. int main()
  4. {
  5. 	LNode L;           //定义链表L
  6. 	InitLinkList(&L);  //初始化链表
  7. 	//List_HeadInsert(&L);   //头插法创建链表
  8. 	//Print_Node(&L);        //打印链表
  9. 	List_TailInsert(&L);     //尾插法创建链表
  10. 	Print_Node(&L);          //打印链表 
  11. 	LNode* p = GetElem(&L, 3);    //查找i = 3 位置的指针
  12. 	printf("查找成功3的数据为%d \n", p->data);    //打印3位置的元素数据
  13. 	LNode* q = LocateElem(&L, 5);                      //查找值为5的元素的指针
  14. 	printf("查找成功5的位置为%p \n", q);          //打印查找的指针值
  15.  
  16. 	int l = LinkLength(&L);                             //链表长度
  17. 	printf("%d\n", l);                            //打印链表长度
  18. 	 
  19. 	Delete_Node(&L, 4);								//删除i = 4的结点
  20. 	printf("删除成功!\n");                        
  21. 	Print_Node(&L);                                     //打印链表
  22.  
  23. 	int i = LinkLength(&L);           
  24. 	printf("%d\n", i);                           //查看链表长度
  25.  
  26. 	ClearList(&L);                                      //清空链表
  27. 	if(!ListEmpty(&L))                                  //判断链表是否为空
  28. 		Print_Node(&L);                                 //不为空则打印链表
  29. 	return 0;
  30. }

LinkList.,h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define VETERY 1 
  7. #define DEFEAT 0
  8. #define NOFINE 0
  9.  
  10. typedef int ElemType; //定义数据类型
  11. typedef int Status;
  12. typedef struct LNode
  13. {
  14. 	ElemType data;       //结点的数据域
  15. 	struct LNode* next;  //结点的指针域
  16. }LNode,*LinkList;        //LinkList为指向结构体Lnode的指针
  17.  
  18.  
  19. Status InitLinkList(LinkList L); //初始化单链表
  20. LinkList List_HeadInsert(LinkList L); //头插入法
  21. LinkList List_TailInsert(LinkList L); //尾插入法
  22. LinkList GetElem(LinkList L, int i);  //按序号查找结点值
  23. LinkList LocateElem(LinkList L, ElemType e); //按照结点值查找结点
  24. void Delete_Node(LinkList L, int i); //按序号删除结点
  25. void Print_Node(LinkList L);  //打印单链表
  26. int LinkLength(LinkList L);   //计算结点个数
  27. int ListEmpty(LinkList L);    //判断单链表是否为空
  28. Status ClearList(LinkList L); //清空单链表
  29. Status DestroyList(LinkList L);  //销毁单链表

LinkList.c

  1. #include "LinkList.h"
  2.  
  3. Status InitLinkList(LinkList L) //初始化单链表
  4. {
  5. 	L = (LinkList)malloc(sizeof(LNode));
  6. 	L->next = NULL;
  7. 	return VETERY;
  8. }
  9. LinkList List_HeadInsert(LinkList L)//头插入法
  10. {
  11. 	LNode *new;
  12. 	int i = 10;
  13. 	for (i = 0; i < 10; i++)
  14. 	{
  15. 		new = (LNode*)malloc(sizeof(LNode));
  16. 		new->data = i;
  17. 		new->next = L->next;
  18. 		L->next = new;
  19. 	}
  20. 	return L;
  21. }
  22. LinkList List_TailInsert(LinkList L) //尾插入法
  23. {
  24. 	LNode* new;
  25. 	LNode* tail = L;
  26. 	for (int i = 0; i < 10; i++)
  27. 	{
  28. 		new = (LinkList)malloc(sizeof(LNode));
  29. 		new->data = i;
  30. 		tail->next = new;
  31. 		tail = new;
  32. 	}
  33. 	tail->next = NULL;
  34. 	return L;
  35. }
  36. LinkList GetElem(LinkList L, int i)    //按序号查找结点值
  37. {
  38. 	int j = 1;
  39. 	LNode* p = L->next;
  40. 	if (i == 0)
  41. 		return L;
  42. 	if (i < 1)
  43. 		return NULL;
  44. 	while (p && j < i)
  45. 	{
  46. 		p = p->next;
  47. 		j++;
  48. 	}
  49. 	return p;
  50. }
  51. LinkList LocateElem(LinkList L, ElemType e) //按照结点值查找结点
  52. {
  53. 	LNode* p = L->next;
  54. 	while (p->data != e && p != NULL)
  55. 	{
  56. 		p = p->next;
  57. 	}
  58. 	return p;
  59. }
  60. void Delete_Node(LinkList L, int i) //按序号删除结点
  61. {
  62. 	LNode* p = GetElem(L, i - 1);
  63. 	LNode* q;
  64. 	q = p->next;
  65. 	p->next = q->next;
  66. 	free(q);
  67. }
  68. void Print_Node(LinkList L)   //打印单链表
  69. {
  70. 	while (L->next != NULL)
  71. 	{
  72. 		L = L->next;
  73. 		printf("%d ", L->data);
  74.  
  75. 	}
  76. 	printf("\n");
  77. }
  78. int LinkLength(LinkList L)   //求单链表长度
  79. {
  80. 	int k = 0;
  81. 	while (L->next != NULL)
  82. 	{
  83. 		k++;
  84. 		L = L->next;	
  85. 	}
  86. 	return k;
  87. }
  88. int ListEmpty(LinkList L)    //判断单链表是否为空
  89. {
  90. 	if (L->next)
  91. 	{
  92. 		printf("链表不为空！\n");
  93. 		return FALSE;
  94. 	}
  95. 		
  96. 	else
  97. 	{
  98. 		printf("链表为空！\n");
  99. 		return TRUE;
  100. 	}		
  101. }
  102. Status ClearList(LinkList L) //清空单链表
  103. {
  104. 	LinkList p, q;
  105. 	p = L->next;
  106. 	while (p)
  107. 	{
  108. 		q = p->next;
  109. 		free(p);
  110. 		p = q;
  111. 	}
  112. 	L->next = NULL;
  113. 	return VETERY;
  114. }
  115. Status DestroyList(LinkList L)  //销毁单链表
  116. {
  117. 	LinkList p;
  118. 	while (L)
  119. 	{
  120. 		p = L;
  121. 		L = L->next;
  122. 		free(p);
  123. 	}
  124. 	return VETERY;
  125. }
  126.

运行截图：

注：当前为单链表的相关操作以及代码展示，链表除了单链表，还有双链表和循环链表，后续学习完再进行学习笔记的编写！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/429181
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号