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

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

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

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

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

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

单链表结构体的实现

[cpp] view plain copy print?

  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?

  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?

  1. // 带头结点的单链表  
  2. typedef struct LinkListNode LinkList;  
// 带头结点的单链表
typedef struct LinkListNode LinkList;

[cpp] view plain copy print?

  1. // 不带头结点的单项链表  
  2. typedef struct LinkListNode*  LinkList;  
// 不带头结点的单项链表
typedef struct LinkListNode*  LinkList;

区别

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

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

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

单链表的结点插入和删除，其实就是修改其前驱结点的next指针域的指向，我们学C语言的时候知道，无论什么时候在函数中修改一个变量的值，需要传入这个变量的指针作为参数，具体的参见下面的示例程序

[cpp] view plain copy print?

  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?

  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?

  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?

  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?

  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?

  1. // 带头结点的单链表  
  2. typedef struct LinkListNode LinkList;  
// 带头结点的单链表
typedef struct LinkListNode LinkList;

而不带头结点的时候，实现起来插入删除时候，是需要传入指向头结点的指针的指针，那么还用LinkListNode作为List，传入参数时，就需要List **list了，这样我们几种实现方式的函数定义就不统一了，这种编码方式不是我们喜欢的，因此用

[cpp] view plain copy print?

  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

时间： 2024-10-21 16:40:26

数据结构模版----单链表实现方式总结的相关文章

数据结构模版----单链表SimpleLinkList[带头结点](C语言实现)

前面写的单链表结构体是重新设计的.包含头结点(或者头指针)以及链表长度的结构体,而我们通常实现的链表是直接把单链表结点结构体作为单链表来使用的,下面我们给出z这种实现方式,让我们一起来细细体会他们实现之间的区别 [cpp] view plain copy print? #include <stdio.h>   #include <stdlib.h>   #include <stdbool.h>   #include <assert.h>      //#de

数据结构模版----单链表SimpleLinkList[带头结点&amp;&amp;面向对象设计思想](C语言实现)

链表中的数据是以节点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据.以"结点的序列"表示线性表称作线性链表(单链表) 单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素. [cpp] view plain copy print? #include <stdio.h>   #include <stdlib.h>   #include <

数据结构模版----单链表SimpleLinkList[不带头结点](C语言实现)

下面给出的是单链表不带头结点的另一种实现方式,也是最复杂的一种方式 [cpp] view plain copy print? #include <stdio.h>   #include <stdlib.h>   #include <stdbool.h>   #include <assert.h>      //#define DEBUG             // 调试插桩信息宏      ///*/////////////////////////////

数据结构模版----单链表SimpleLinkList[不带头结点&amp;&amp;伪OO](C语言实现)

上一篇写单链表是带头结点的,但是其他这种写法的单链表中,头结点其实就不是那么必要了,因为我们的单链表结构体中增加了一项m_length 下面的不加头结点的单链表奉上 不带头结点的单链表结构体 [cpp] view plain copy print? #include <stdio.h>   #include <stdlib.h>   #include <stdbool.h>   #include <assert.h>            ///*/////

数据结构实践——单链表：逆置、连接与递增判断

本文针对数据结构基础系列网络课程(2):线性表的实践项目. [项目 - 单链表算法](程序中利用了已经实现的单链表算法,头文件LinkList.h及其中函数的实现见单链表算法库) 1.设计一个算法,将一个带头结点的数据域依次为a1,a2,-,an(n≥3)的单链表的所有结点逆置,即第一个结点的数据域变为an,-,最后一个结点的数据域为a1.实现这个算法,并完成测试. [参考解答] (程序中利用了已经实现的单链表算法,头文件LinkList.h及其中函数的实现见单链表算法库) #include <

数据结构例程——单链表的建立

本文是数据结构基础系列网络课程(2):线性表中第9课时建立单链表中所讲的例程. [例程] 定义单链表存储结构,用头插法和尾插法建立单链表,并显示建立好以后的结果. #include <stdio.h> #include <malloc.h> typedef int ElemType; typedef struct LNode //定义单链表结点类型 { ElemType data; struct LNode *next; //指向后继结点 } LinkList; void Crea

数据结构例程——单链表应用举例

本文针对数据结构基础系列网络课程(2):线性表中第11课时单链表应用举例. 例:拆分单链表 (linklist.h是单链表"算法库"中的头文件,详情单击链接-) #include <stdio.h> #include <malloc.h> #include "linklist.h" void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L-

算法与数据结构之单链表

单链表:#include<stdio.h>#include<malloc.h>#include<windows.h>typedef int elemtype; typedef struct LNode //定义单链表存储类型{elemtype data;struct LNode *next;}linklist; void creatlistf(linklist *&L ) //建立链表(头插法){linklist *s;int i;elemtype a[10];

单链表 数据结构 c++-单链表具体实现实现reverse

问题描述 单链表具体实现实现reverse 用c++语言写,需要完整的程序,能运行的 将链表的顺序颠倒过来,最好写清楚指针的具体实现的过程 谢谢谢谢 解决方案 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node{ int data; struct node *next; }NODE; void insert(NODE **head,NODE *node){ if((*he