备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

数据结构模版----单链表实现方式总结

2016-05-18 1409
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

数据结构模版----单链表实现方式总结

前面我们提供了四种方式实现的单链表，有带头结点的不带头结点的，而单链表的结构体定义也有两种方式，那么这些实现方式，到底有什么区别呢，为什么会出现这么多种实现方式呢，下面我们就来细细体会

一 单链表结构体的实现区别

首先我们对比一下，单链表结构体

不同方式的单链表实现时，链表结点的实现是相同的，不同之处在于单链表结构体的实现上

单链表结构体的实现

[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. typedef int ElemType;       // 自定义数据类型  
  2.   
  3. //typedef struct LinkListNode*  PLinkListNode;          // 链表结点指针域  
  4.   
  5. // 链表结点数据域  
  6. typedef struct LinkListNode  
  7. {  
  8.     ElemType            m_data;         // 数据域  
  9.     struct LinkListNode *m_next;            // 指针域  
  10. }LinkListNode;  
typedef int ElemType;		// 自定义数据类型

//typedef struct LinkListNode*	PLinkListNode;			// 链表结点指针域

// 链表结点数据域
typedef struct LinkListNode
{
	ElemType			m_data;			// 数据域
	struct LinkListNode	*m_next;			// 指针域
}LinkListNode;

①带length标识的单链表结构体

[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. typedef struct LinkList  
  2. {  
  3.     LinkListNode    *m_head;                // 链表头结点  
  4.     int             m_length;           // 单链表数据结点个数指针域  
  5. }LinkList;  
typedef struct LinkList
{
	LinkListNode	*m_head;				// 链表头结点
	int				m_length;			// 单链表数据结点个数指针域
}LinkList;

①不带length标识的单链表结构体

[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 带头结点的单链表  
  2. typedef struct LinkListNode LinkList;  
// 带头结点的单链表
typedef struct LinkListNode LinkList;

[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 不带头结点的单项链表  
  2. typedef struct LinkListNode*  LinkList;  
// 不带头结点的单项链表
typedef struct LinkListNode*  LinkList;

区别

    对于一个单链表来说，查找其长度的时，需要从前往后遍历一遍单链表，因此时间复杂度是O(N)，为了能更快的获取其长度，我们设计了带length标识的单链表结构体，这对于经常获取链表长度时，效率是十分客观的，

而我们又发现同样时不带length标识的单链表结构体，定义的方式却又出现了细微的差别。这个又是为什么呢？、

这个区别的根本就在于就是带头结点的单链表和不带头结点的单链表的区别了。

单链表的结点插入和删除，其实就是修改其前驱结点的next指针域的指向，我们学C语言的时候知道，无论什么时候在函数中修改一个变量的值，需要传入这个变量的指针作为参数，具体的参见下面的示例程序
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.   
  4.   
  5. // 函数中修改一个变量的值  
  6. void Modify1(int value);        // 变量作为参数  
  7. void Modify2(int *value);       // 变量指针作为参数  
  8.   
  9. int main(void)  
  10. {  
  11.     int value = 0;  
  12.     Modify1(value);  
  13.     printf("value = %d after func\n\n", value);     // modify failed  
  14.   
  15.     Modify2(&value);  
  16.     printf("value = %d after func\n\n", value);     // modify success  
  17.   
  18.     return EXIT_SUCCESS;  
  19. }  
  20.   
  21.   
  22. // 变量作为参数  
  23. void Modify1(int value)  
  24. {  
  25.     value = 10;  
  26.     printf("value = %d in %s\n", value, __func__);  
  27. }  
  28.   
  29. // 变量指针作为参数  
  30. void Modify2(int *value)  
  31. {  
  32.     *value = 10;  
  33.     printf("value = %d in %s\n", *value, __func__);  
  34. }  
#include <stdio.h>
#include <stdlib.h>


// 函数中修改一个变量的值
void Modify1(int value);		// 变量作为参数
void Modify2(int *value);		// 变量指针作为参数

int main(void)
{
	int value = 0;
	Modify1(value);
	printf("value = %d after func\n\n", value);		// modify failed

	Modify2(&value);
	printf("value = %d after func\n\n", value);		// modify success

	return EXIT_SUCCESS;
}


// 变量作为参数
void Modify1(int value)
{
	value = 10;
	printf("value = %d in %s\n", value, __func__);
}

// 变量指针作为参数
void Modify2(int *value)
{
	*value = 10;
	printf("value = %d in %s\n", *value, __func__);
}
那么单链表中删除删除元素时，需要修改在函数中修改指针的指向（尤其在插入首元时，需要修改头指针的指向），因此需要使用指针的指针（即二重指针）
为了保证我们实现的代码的一致性，我们所有参数的传递均使用LinkList *list，作为参数传递到函数中
这样在带length标识的单链表结构体中，修改指针的指向时其实使用的已经是
LinkListNode *pNode = list->m_head; // 传入的是Linlist *, 而修改的是*list中的LinkListNode *m_head可见已经是二重指针
那么是作为二重指针，是可以修改掉m_head的指向的(我们可可以这样理解，传入的是LinkList* list即变量的指针，那么毕竟可以修改掉变量*list的值，变量*list作为结构体，他的数据就是*m_head和m_length，即可以修改掉指针的指向)
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.   
  4.   
  5. // 函数中修改一个变量的值  
  6. typedef struct  
  7. {  
  8.     int *value;  
  9.     int length  
  10. }List;  
  11.   
  12. int gloValue1 = 0;  
  13. int gloValue2 = 10;                     // 全局变量  
  14.   
  15. void Modify1(List list);        // 变量作为参数  
  16. void Modify2(List *list);       // 变量的指针作为参数  
  17.   
  18.   
  19. int main(void)  
  20. {  
  21.   
  22.     List list = {&gloValue1, 0};  
  23.     printf("&gloValue1 = %p, &gloValue = %p\n", &gloValue1, &gloValue2);  
  24.     printf("value = %d, addr = %p, length = %d after func\n\n", *(list.value), list.value, list.length);  
  25.   
  26.     Modify1(list);  
  27.     printf("value = %d, addr = %p, length = %d after Modify1\n\n", *(list.value), list.value, list.length);  
  28.   
  29.     Modify2(&list);  
  30.     printf("value = %d, addr = %p, length = %d after Modify2\n\n", *(list.value), list.value, list.length);  
  31.     return EXIT_SUCCESS;  
  32. }  
  33.   
  34.   
  35. // 变量作为参数  
  36. void Modify1(List list)  
  37. {  
  38.     list.value = &gloValue2;                                // 修改指针的值(即指针的指向)  failed  
  39.     list.length = 10;                                       // failed  
  40.     printf("value = %d, addr = %p, length = %d in %s\n", *(list.value), list.value, list.length, __func__);  
  41. }  
  42.   
  43.   
  44. // 变量作为参数  
  45. void Modify2(List *list)  
  46. {  
  47.     list->value = &gloValue2;                                // 修改指针的值(即指针的指向) success  
  48.     list->length = 10;                                       //                        success  
  49.     printf("value = %d, addr = %p, length = %d in %s\n", *(list->value), list->value, list->length, __func__);  
  50. }  
#include <stdio.h>
#include <stdlib.h>


// 函数中修改一个变量的值
typedef struct
{
	int *value;
	int length
}List;

int gloValue1 = 0;
int gloValue2 = 10;						// 全局变量

void Modify1(List list);		// 变量作为参数
void Modify2(List *list);		// 变量的指针作为参数


int main(void)
{

	List list = {&gloValue1, 0};
	printf("&gloValue1 = %p, &gloValue = %p\n", &gloValue1, &gloValue2);
	printf("value = %d, addr = %p, length = %d after func\n\n", *(list.value), list.value, list.length);

	Modify1(list);
	printf("value = %d, addr = %p, length = %d after Modify1\n\n", *(list.value), list.value, list.length);

	Modify2(&list);
	printf("value = %d, addr = %p, length = %d after Modify2\n\n", *(list.value), list.value, list.length);
	return EXIT_SUCCESS;
}


// 变量作为参数
void Modify1(List list)
{
	list.value = &gloValue2;								// 修改指针的值(即指针的指向)  failed
	list.length = 10;										// failed
	printf("value = %d, addr = %p, length = %d in %s\n", *(list.value), list.value, list.length, __func__);
}


// 变量作为参数
void Modify2(List *list)
{
	list->value = &gloValue2;								// 修改指针的值(即指针的指向) success
	list->length = 10;										//						  success
	printf("value = %d, addr = %p, length = %d in %s\n", *(list->value), list->value, list->length, __func__);
}
    那么现在问题就清楚了，要想修改一个指针的指向，需要传入指针的指针作为参数，那么我们在插入删除的过程中，在那里修改了指针的指向呢？
    其实归根结底修改了两个地方，我们参见不带头结点的单链表实现方式2中插入函数的实现
①是修改结点本身的指向，需要传入二重指针
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 不带头结点的单链表插入首元时，需要修改头指针的指向  
  2. (*list) = newNode;                  // 此时修改指针本身的指向需要传入LinkListNode **  
  3. // 不带头结点的单项链表声明  
  4. typedef struct LinkListNode*  LinkList;  
  5. //函数声明    
  6. LinkListNode* InsertNode(LinkList *list,    // LinkList * == LinkListNode**    
  7.                          int position,   
  8.                          ElemType data)  
// 不带头结点的单链表插入首元时，需要修改头指针的指向
(*list) = newNode;					// 此时修改指针本身的指向需要传入LinkListNode **
// 不带头结点的单项链表声明
typedef struct LinkListNode*  LinkList;
//函数声明	
LinkListNode* InsertNode(LinkList *list,	// LinkList * == LinkListNode**	 
						 int position, 
						 ElemType data)

②是修改结点的指针域的指向，传入指向结点的指针即可
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 将newNode插入pNode之后时，需要修改newNode和pNode指针域的指向  
  2. newNode->m_next = pNode->m_next;  // 此时只需要传入LinkListNode *即可, 因为指针域m_next是node的数据成员, 已经是个指针成员变量  
  3. pNode->m_next = newNode;         // 传入LinkListNode *, m_next就成为一个指针的指针  
  4. // 函数声明  
  5. LinkListNode *AddNode(LinkList *list,                             
  6.                       LinkListNode *prevNode,               // 传入LinkListNode *, 即可修改prevNode->m_next = @@@@@  
  7.                       ElemType data)  
// 将newNode插入pNode之后时，需要修改newNode和pNode指针域的指向
newNode->m_next = pNode->m_next;	// 此时只需要传入LinkListNode *即可, 因为指针域m_next是node的数据成员, 已经是个指针成员变量
pNode->m_next = newNode;			// 传入LinkListNode *, m_next就成为一个指针的指针
// 函数声明
LinkListNode *AddNode(LinkList *list,							
					  LinkListNode *prevNode,				// 传入LinkListNode *, 即可修改prevNode->m_next = @@@@@
					  ElemType data)
现在问题明了了，但是为什么两种方式定义的单链表结构体却不一样呢
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 不带头结点的单项链表  
  2. typedef struct LinkListNode*  LinkList;  
  3. // 带头结点的单链表  
  4. typedef struct LinkListNode LinkList;  
// 不带头结点的单项链表
typedef struct LinkListNode*  LinkList;
// 带头结点的单链表
typedef struct LinkListNode LinkList;
这就是不带头结点的单链表和带头结点的单链表实现地方的区别了

二 不带头结点的单链表和带头结点的单链表的区别

我们很容易发现带头结点的单链表实现起来要比不带头结点的单链表要简单，这个是为什么呢
继续接着上面的讲，插入和删除时，要修改其前驱指针的指向，特别的插入和删除第一个元素（即首元结点）时，我们需要更改头指针的指向，很明显头指针是没有前驱的，这样我们实现起来的时候
对于非头结点，我们直接找到其前驱，然后修改其前驱结点的指针域的指向就好了(传入指向结点的指针即可)
对于头结点，没有前驱结点，我们需要特殊判断，而直接修改头指针本身的指向(传入指向头结点的指针的指针)
怎么规避这个问题呢，那就在链表头的位置添加一个头结点，初始化时候将头结点创建好，这样我们即使插入首元结点，首元结点也是有一个前驱（即头结点的），这样我们修改头指针，也就变成了修改头结点的指针域的指向，这样我们传参和插入删除的实现就统一了。实现起来也简单
好了不带头结点和带头结点我么明了了，接着来回答上面那个问题，为什么，单链表的结构体不一样呢。。
带头结点的时候，我们传入参数其实已经不需要传入二重指针了，统一传入指向链表结点的指针即可，因此用下面的实现即可
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 带头结点的单链表  
  2. typedef struct LinkListNode LinkList;  
// 带头结点的单链表
typedef struct LinkListNode LinkList;
而不带头结点的时候，实现起来插入删除时候，是需要传入指向头结点的指针的指针，那么还用LinkListNode作为List，传入参数时，就需要List **list了，这样我们几种实现方式的函数定义就不统一了，这种编码方式不是我们喜欢的，因此用
[cpp] view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. // 不带头结点的单项链表  
  2. typedef struct LinkListNode*  LinkList;  
// 不带头结点的单项链表
typedef struct LinkListNode*  LinkList;
无独有偶，上面带头节点的单链表也是可以用typedef struct LinkListNode*  LinkList;，只是传参时候用List list即可，函数命名也不统一了，而若是将参数统一为List *list,那么里面代码实现的时候，全部用(*list)表示指向头结点的指针，实现起来不容易理解，因此我们选用了typedef struct LinkListNode  LinkList

转载： http://blog.csdn.net/gatieme/article/details/42673493
文章标签：
C++
机器学习/深度学习
C语言
关键词：
数据结构单链表
数据结构实现
数据结构模版
shy丶gril
目录
相关文章
游客yit5ffk3osumc
|
22天前
|
存储 算法 索引
数据结构与算法：单链表
朋友们大家好，本节来到数据结构与算法的新内容：单链表 在上篇文章中，我们知道顺序表通常需要预分配一个固定大小的内存空间， 通常以二倍的大小进行增容，可能会造成空间的浪费，本篇文章我们介绍的链表可以解决这个问题
游客yit5ffk3osumc
19 1
起飞的风筝
|
1月前
|
存储
【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
起飞的风筝
32 0
诡异森林。
|
存储
数据结构--单链表
数据结构--单链表
诡异森林。
24 0
卫卫周大胖
|
1月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
卫卫周大胖
24 2
大耳朵土土垚
|
1月前
|
存储
数据结构——lesson3单链表介绍及实现
数据结构——lesson3单链表介绍及实现
大耳朵土土垚
37 0
玛丽亚后
|
3月前
|
存储 编译器
数据结构——单链表
数据结构——单链表
玛丽亚后
33 0
认真学习的小雅兰.
|
2天前
|
存储 算法
单链表——“数据结构与算法”
单链表——“数据结构与算法”
认真学习的小雅兰.
5 0
阿森要自信
|
16天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
11 1
阿森要自信
|
16天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
阿森要自信
20 0
起飞的风筝
|
1月前
|
存储 算法
数据结构——单链表的基本操作
数据结构——单链表的基本操作
起飞的风筝
11 0

热门文章

最新文章

  • 1
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
  • 2
    Java 学习路线：基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
  • 3
    C++关联容器深度解析：提升数据结构操作的艺术
  • 4
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 5
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 6
    Java数据结构与算法-java数据结构与算法（二）
  • 7
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 8
    【软件设计师备考 专题 】数据结构深度解析：从数组到图
  • 9
    【C/C++ 数据结构 线性表】深入理解与实现栈：从基础到应用的全面探索
  • 10
    C/C++ 数据结构设计与应用（二）：自定义数据结构的设计 (Design of Custom Data Structures)
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    34
  • 3
    【排序算法】数据结构排序详解
    41
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    34
  • 5
    【堆】数据结构堆的实现（万字详解）
    50
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    23
  • 7
    【双向链表】数据结构双向链表的实现
    20
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    33
  • 10
    数据结构——二叉树的链式结构
    34

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云oss简介和使用流程