• 【玩转408数据结构】线性表——单链表的定义以及增删改查（线性表的链式表示 上）

    知识回顾

            到这里我们已经了解到线性表是具有相同数据类型的有限个数据元素序列，而线性表的顺序存储也就是顺序表，顺序表的存储形式十分直观，我们在实现时使用数组进行实现，但顺序表在插入或者删除元素时需要移动大量元素，那么怎么样才能在插入删除元素时不需要大费周章的移动如此之多的元素呢？为了解决这个问题，今天我们就来继续了解一下线性表的链式存储——链表。

    单链表定义

            线性表的链式存储又叫单链表，既然是属于线性表的一种存储方式，那么其应该满足线性表的特征（具有相同数据类型的有限个数据元素序列）。

            那么什么是链式存储呢？我们不难想象，就像链条一样，我们存在很多个相同的结点，这些结点之间进行相连最终称为一个链条；那么链式存储也跟其类似，其也是有很多个相同的结点所组成，之后我们在将其结点按次序逐个串联，这样就可以形成一个链表。

            不过这样的定义显然是不准确的，我们线性表的链式存储结构指用一组任意的存储单元来存储线性表中的数据元素(这组存储单元可以是连续的，也可以是不连续的) ；既然我们不对其存储单元做连续的要求的话，我们应该去设法建立其数据间的存储关系；那么为了保持链表中的元素a_{i}和其下一个元素 a_{i+1} 之间的逻辑关系，那么对于数据元素 a_{i} 来说，其不仅需要存储其本身的信息，还需要开辟一块空间去存放其直接后续的信息（也就是直接后续的存储位置）；那么我们在设计时，就可以使用指针去指向该元素的直接后续元素存储位置，这样在查找时就可以通过指针去直接查找出当前元素的直接后续元素；所以我们的数据元素并不单单指的是其本身的信息，而是由这两个部分同时构成其数据元素  a_{i} （我们称其为 结点 ）。

    定义单链表结点类型

            我们已经了解到其结点的构成，那么我们在实现时就需要使用代码去构造出其结点类型。

    1. //结点
    2. typedef struct LNode{
    3. 	int data;
    4. 	struct LNode *next;
    5. }LNode, *LinkList;

             这里我们同样使用struct关键字定义一个新类型，通过前面的分析，我们不难观察出其中需要一个data存放数据本身，因此其类型也就和我们需要存放数据本身类型一致即可；之后我们需要存放一个指针去存放下一个结点的地址，其类型自然也就是我们struct新定义的类型了。

    如何增加新结点

            前面我们已经可以将链表中单个结点的数据类型定义出来了，可是这里我们只是存在这个类型，但我们在实际的使用中是需要不断的开辟新的空间去存放这一个个的结点；那么我们就需要了解如何去添加新结点（开辟出一个新空间去存放新节点的数据）。

            这里我们需要使用到malloc函数去申请一片新的内存空间，下面的代码也就是使用malloc函数去申请一个新的内存空间存放结点；下面的代码中malloc内部写明的是需要开辟空间的大小，这里也就是使用sizeof求出我们前面定义新类型的大小（在这里也就是int + LNode*），至于malloc前面的括号则是C++中的强制类型转换，将其转换为LNode * 类型。

    LNode * p = (LNode *) malloc(sizeof(LNode));

            由于单链表的元素都是一个个单独的结点，且其元素离散的分布在存储空间之中，我们只能通过指针去按顺序一个个寻找其元素，因此单链表是非随机存取的存储结构 （也就是不可以直接找到表中的某个特定的结点）。

    分析LNode和*LinkList

            我们在观察结点类型的构造时会发现，其存在两个命名（LNode，*LinkList） ，对于这两个实际上存在这样的关系：

    LNode * = LinkList

            既然这样为什么这里我们要去分别起两个名字呢？其实只有一个也是可以完成该链表的代码实现的，只不过为了提升我们代码的可读性，也就是方便我们以后在阅读代码时可以更好的理解，我们在这里使用这两个命名。

            在这里我们如果在代码中想要，强调我们传入或者返回的是一个单链表，需要使用LinkList；如果我们想要强调传入或者返回的是一个结点，需要使用LNode *;通过这样分辨，我们可以很好的将代码中的结点和链表区分开，提高我们代码的阅读性。

    单链表头结点的分析

            在链表中，我们通常需要一个头指针去标识一个链表，其指向我们链表的头部，如果单链表的头指针为NULL，也就意味着此时为一个空链表；此时为了操作的方便我们可以选择去在头指针后加上一个空的结点，这个结点被称为头结点。头结点数据域不需要设置任何信息，当然也可以去记录表长。

    不带头结点的单链表

            如果我们不设置头节点的话，我们在单链表初始化时其头指针将直接指向NULL，此时也就说明其单链表为空，当我们后续插入元素时，再更改其头指针的指向即可。 

     

    带头结点的单链表

            对于含有头结点的指针，我们的头指针就需要指向头结点，而头结点指向NULL才表明我们的链表为空，当然使用这种方法我们再添加结点时就只需要更改头结点的指向即可，不需要更改头指针的指向（其主要原因也是其头部已经固定，就是我们的头结点）。

    两种方式的分析 

            不论链表是否带头结点，我们的头指针始终指向链表的第一个结点，只不过头结点是带头结点链表的第一个结点，只不过该结点不存储信息。

            如果单链表中不带头结点，我们在写代码时相对麻烦，对第一个数据结点和后续数据结点的 处理需要用不同的代码逻辑 对空表和非空表的处理需要用不同的代码逻辑。

    而使用头结点会使我们在使用时更加方便：

    • 由于第一个数据结点位置被存放在头结点的指针域，因此在链表上第一个位置上的操作就与在其他位置上的操作一致，不需要特殊处理。
    • 不论链表是否为空，其头结点都是指向头结点的非空指针（空表中的头结点指针域为空），因此空表和非空表的处理也就得到了统一。   

            因此我们可以发现 使用头结点可以避免掉我们不少的麻烦。

    单链表的基本操作实现

            既然我们了解了单链表，也知道了其类型的定义，那么接下来我们就需要尝试着去实现它的功能。

    单链表的插入

             既然要学习一个链表，那么首先我们就要知道如何在链表中添加元素，也就是下面我们所学习的单链表的插入。

            通过上文可知，我们的单链表分为含头结点与不含头结点的两种单链表，不同的单链表在执行有些插入操作的方法也存在一些差异。

            对于插入操作我们在这里主要介绍：按位序插入、指定结点的后插、指定结点的前插。由于指定节点的前后插操作是已经指定过节点，所以对此情况我们单链表是否带头结点对其没什么影响；只有按位序插入时，单链表是否带头结点会影响其实现，接下来我们在分析按位序插入时也将是否带头结点来分开讨论。 

    按位序插入

            按位序插入，顾名思义也就是在我们需要插入的地方，插入一个值即可，在这里我们创建该函数表示：

    ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。 

            由于链表的特殊性，我们无法跟顺序表一样，可以直接的找到其第i个位置；我们知道，单链表就是由很多结点相连，所以我们要想找到第i个位置的结点，就需要从头部向后，顺着我们结点中指向下一个结点的指针，逐步向后查找，知道找到第i个即可。由于需要从头部开始查找，所以带头结点的单链表插入与不带头结点的单链表插入，在实现上就存在一定的不同。 

    带头结点

             由上文我们已经了解到了带头结点的单链表，那么在这里对于带头结点的链表就不作描述。既然我们需要在第i个位置上插入一个元素，那么首先我们要做的就是检查i是否合法（如果i的值为0，我们的链表怎么会有第0位呢？或者是i的值超出我们链表的长度呢？这样就是不合法）。

     

            我们核验完i的合法性后，就需要思考如何在第i个位置上插入一个结点；以图为例：如果我们要在第二个位置插入一个结点e，那么首先我们要做的是使用malloc函数开辟出一片新的空间（前文有malloc描述）；开辟出一段空间之后，我们就需要去查找出链表中第二个结点前的位置，这是因为我们需要在第二个位置插入元素的话，就需要将元素插入到第一个元素和第二个元素之间（这样我们插入的元素就成为了第二个元素）；又由于在我们的单链表中 ，前一个结点中存在一个指针指向下一个结点的地址，当我们找到第一个元素时，也相当于找到了第二个元素的位置，这时，我们让新插入的结点中的指针指向原链表中的第二个结点位置，而原链表中第一个元素的指针则指向新插入结点的位置；这样我们是不是就成功的将其连接起来了。

            又因为我们这里在第一个结点前是存在一个头结点的，所以当我们想要在第一个位置插入一个元素时，这时待插入的位置是头结点和原链表中第一个结点之间，由于同样是在两个结点之间，所以其插入方法也同上。

             由于我们在进行按位插入时需要从头部循环向后遍历到第i-1个结点，所以需要遍历i-1次；那么其平均复杂度也就是O(n);同理，当我们需要插入的位置在第一个时，我们就不需要遍历，那个我们这是的时间复杂度就是最优时间复杂度：O(1)。

            需要注意的是，我们在进行插入操作时，其顺序可不可以更改？也就是如上图所示：正常来说，我们需要首先让e的指针指向a_{1}的地址，之后让头结点指针指向e的地址；那么我们可以不可以颠倒顺序呢？

            答案当然是不可以的。其主要原因就是，由于我们头结点的指针初始是存放的 a_{1} 的地址（我们只能通过头结点的指针寻找到其地址），那么按照我们最初的方法，是需要将存放的这个a_{1} 的地址赋值给e结点中指针，之后我们再更换掉头结点指针的指向（由于e为malloc开辟的空间，所以我们在开辟时会创建出一个指针直接存放其地址，所以我们可以直接通过这个指针对其赋值）；而当我们首先将头结点指针的指向更改为e的存储地址后，在后面我们e中指针指向 a_{1} 地址时，我们会将头结点的指针指向位置值赋给e中指针，但此时头结点指针的指向已经不是a_{1} 地址了，这样就会造成如上图所示的错误。

             当然由于是从前向后遍历，那么最差的时间复杂度当然就是在最末位插入结点了，其时间复杂度为：O(n)。

    1. //插入 : 在第i个位置插入(含头节点） 
    2. bool ListInsert(LinkList &L, int i, int e) {
    3. 	if(i<1)	return false ;
    4. 	LNode *p ;	//扫描指针
    5. 	int j = 0;	//带头节点 从0开始
    6. 	
    7. 	p = L;
    8. 	while(p != NULL && j < i-1) {	//找到 i-1 的位置 
    9. 		p = p->next ;
    10. 		j++;
    11. 	}
    12. 	
    13. 	if(p == NULL)	return false;
    14. 	
    15. 	LNode *s = (LNode *)malloc(sizeof(LNode)) ;
    16. 	s->data = e;
    17. 	s->next = p->next;
    18. 	p->next = s;
    19. 	return true;
    20. }

    需要注意的是：由于我们这里的链表是没有记录长度的，所以我们在while循环中 p!=NULL 是为了判断i是否会超出链表长度。 当然也可以写出一个计算长度的函数，其原理大致就是从头结点开始向后遍历，直到循环到该结点指针指向NULL即可，在循环中，每执行一次就让记录长度的变量自增即可。

    不带头结点

             由于这里单链表不存在头结点，所以这里在i=1时，我们需要特殊处理以下；当i>1且合法时，我们此时插入前后都是结点，这时方法就同带头结点单链表的插入方法。

             这里我们只需分析插入第一个位置的情况，由于我们不存在头结点，所以当我们想要插入第一个元素时，就需要利用头指针；在插入前，我们的头指针指向的是当时的第一个结点，也是我们插入后的第二个结点；那么我们在插入时，首先需要使插入结点e的指针指向a_{1}（也就是L指向的位置），之后我们更改L头指针的指向，使其指向e结点的位置即可。（当然这里我们的存储指向顺序也是不可以颠倒的，如果颠倒会同上面一样，形成一个闭环）

            除了头部的插入以外，其余的插入方法就同带头结点单链表插入的方法相同，我们在这里就不做多描述，其时间复杂度也同带头结点的插入相同。

    综上来看：

            带头结点与不带头结点的单链表在按位序插入中，其基本实现方法是相同的，仅仅只在头结点插入时略有不同；其时间复杂度也都是相同的：最优为O(1),最差为O(n)。 

    指定结点后插

            对于指定结点后插的操作，其实现方法其实是跟前面的按位序插入是类似的。

            我们回想以下，我们在实现按位序插入时，是要找的插入位置的前一个结点的位置进行操作的，而这里是直接给出需要插入位置的前一个结点位置，那么我们只需按照之前按位序插入的方法执行一遍即可（首先让e结点的指针指向y，也就是x结点指针的指向；之后让x指针的指向e的存储位置即可） 。

    1.  
    2. bool InsertNextNode (LNode *p, ElemType e) {
    3.     if (p == NULL)	return false ;
    4.     
    5.     LNode *s = (LNode *) malloc(sizeof(LNode));
    6.     
    7.     if(s==NULL)	return false	//内存分配失败
    8. 	
    9. 	s->data = e;
    10. 	s->next = p->next;
    11. 	p->next = s;
    12. 	return true; 
    13. }

             在实现时需要判断以下其内存是否分配成功，也就是 s 是否为 NULL。

    指定结点前插

    InsertPriorNode (LNode *p, ElemType e) ：在p结点之前插入元素e 

             在这种情况下，看似跟之前很像，但不太一样，由于我们的 p 指向的为插入结点后的元素，而我们单链表又无法找到结点x前驱结点，那么我们就很难通过之前的办法让x的前驱结点指向我们需要插入结点的存储位置，那么我们就需要更改方法。

            首先，提供一种简单的方法，若函数可以传入单链表的头指针，此时我们只需从头指针向后遍历，遍历到某结点的指针指向为p即可，这时我们就成功找到其插入后的前驱结点，就可以按我们之前的方法去进行插入了。

            不过这种方法是复杂的，其需要遍历，所以其时间复杂度为O(n);那么我们用什么办法可以使得其不从头遍历也可以前插呢？

            

            在这里，我们按照之前的办法，在结点e的后面插入一个结点x，这就等同于我们之前的方法，并不难实现。

             紧接着呢，我们定义一个与结点中数据同类型的变量，利用该变量颠倒e与x的存储数位置，这样我们就等同于在p的前面插入一个结点了，只不过此时p指向的是我们所插入的结点。

    1. bool InsertPriorNode (LNode *p, ElemType e) {
    2.     if (p == NULL)	return false ;
    3.     
    4.     LNode *s = (LNode *) malloc(sizeof(LNode));
    5.     
    6.     if(s==NULL)	return false	//内存分配失败
    7. 	
    8. 	s->next = p->next;
    9. 	p->next = s;	//新结点相连 
    10. 	s->data = p->data;	//p中元素给s 
    11. 	p->data = e;	// e的值给p 
    12. 	return true; 
    13. }

            由于我们只在单个的位置中插入，该算法的时间复杂度为:O(1)。 

    单链表的删除

    按位序删除 

     ListDelete(&L, i, &e) ：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

             由于我们的链表是有单个的结点不断相连的，所以我们在删除某一节点时，只需要更改其相连的方向即可，不需要向顺序表一样，将删除结点后的结点均向前移动，这样就提高了效率。

    带头结点

            由于我们需要删除第i个元素，那么我们在删除操作中，首先需要找到第i-1个结点的位置，然后我们直接更改其i-1结点的指针指向，使其指向i+1结点的存储位置；这样在后面我们遍历时，就可以直接跳过第i个元素了。

     

            我们的删除操作只是需要改一个删除结点前的结点指针指向即可，其时间复杂度为O(1);所以其整体的删除操作时间主要耗费在寻找第i-1个结点的位置上；根据我们前面的分析，寻找需要从头循环遍历，所以其平均时间复杂度则是O(n);那么最好的时间复杂度则是在第一个位置插入，为O(1);最差的时间复杂度则是在最末尾插入，时间复杂度为O(n) 。

            对于含有头结点的单链表而言，其在第一个删除时前面存在头结点，所以插入的方式就跟在后面结点插入的方式相同。

    1. //删除 : 删除第i个位置的元素 并返回 （含头节点）
    2. bool ListDelete(LinkList &L, int i, int &e) {
    3. 	if(i<1)	return false;
    4. 	LNode *p;
    5. 	int j=0;
    6. 	
    7. 	p = L;
    8. 	
    9. 	while(p != NULL && j < i-1) {
    10. 		p = p->next;
    11. 		j++;
    12. 	}
    13. 	
    14. 	if(p == NULL) return false;
    15. 	
    16. 	e = p->next->data;
    17. 	p->next = p->next->next;
    18. 	
    19. 	/*
    20. 	LNode *q = p->next;
    21. 	e = q->data;
    22. 	p->next = q->next;
    23. 	free(q);
    24. 	*/
    25. 	
    26. 	return true;
    27. }

     

    不带头结点 

            对于不含头结点的单链表，其除在头部的删除外，其余的方法均与带头结点的单链表相同，所以这里我们只讨论起头部的删除。

            由于不带头结点的单链表删除头部时 前面无头结点，只有一个头指针指向其存储位置，所以我们在删除时，只需要将头指针指向第二个结点的存储位置即可。

    1. //删除 : 删除第i个位置的元素 并返回 （不含头节点）
    2. bool ListDelete(LinkList &L, int i, int &e) {
    3. 	if(i<1)	return false;
    4. 	LNode *p;
    5. 	int j=1;
    6. 	
    7. 	p = L;
    8. 	
    9. 	if(i==1) {
    10. 		e = p->data ;
    11. 		L = p->next;
    12. 	} 
    13. 	
    14. 	while(p != NULL && j < i-1) {
    15. 		p = p->next;
    16. 		j++;
    17. 	}
    18. 	
    19. 	if(p == NULL) return false;
    20. 	
    21. 	e = p->next->data;
    22. 	p->next = p->next->next;
    23. 	
    24. 	/*
    25. 	LNode *q = p->next;
    26. 	e = q->data;
    27. 	p->next = q->next;
    28. 	free(q);
    29. 	*/
    30. 	
    31. 	return true;
    32. }

     指定结点删除

    DeleteNode(LNode *p)        删除指定结点 p

            这里，我们若要删除p指向的结点，就需要更改其前驱结点的指向，但是我们并不能通过p去找到其前驱结点，那么如果这里我们引入一个头指针L，从头部向后遍历寻找其前驱结点，这样我们就可以根据上面的删除方法对其进行删除了。

            该种方法由于要从前遍历寻找，所以其时间复杂度为O(n)。 

            还有一种办法，我们只需要将p后续结点的数据值存入p指向的结点中，之后让p指向的结点的指针直接跳过其后继结点，指向指向其后面的那个即可。也就是我们将y的值存入x的位置，然后让p指向的结点直接跳过q指向下一个即可。

    1. //删除指定节点 (删除 p 节点） 
    2. bool DeleteNode(LNode *p, LinkList &L) {
    3. 	if(p == NULL) return false;
    4. 	
    5. 	if(p == L) {
    6. 		L = p->next;
    7. 	}
    8. 	
    9. 	p->data = p->next->data;
    10. 	p->next = p->next->next;
    11. 	
    12. 	/*
    13. 	LNode *q;
    14. 	q = p->next;
    15. 	p->data = q->data;
    16. 	p->next = q->next;
    17. 	free(q);
    18. 	*/
    19. 	
    20. 	return true;
    21. }

            这种办法只需要更改其指向即可，所以其时间复杂度为O(1)。 

    单链表的查找

            对于单链表的查找，其实我们实现的底层逻辑都是相同的，就是从头指针开始向后遍历，知道寻找到我们需要查找的结点为止；由于需要从前向后遍历查找，所以其时间复杂度自然为:O(n)。

    按位查找

     GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

             对于按位查找，我们只需要利用一个for循环，使其循环i次，其循环到的结果自然就是我们元素的值了；不过需要注意的是，在循环过程中，需要判断一个i的合法性，避免长度超出我们链表长度。

    1. //按位查找 
    2. LNode *GetElem(LinkList L, int i){
    3. 	if(i<0)		return NULL;
    4. 	
    5. 	LNode *p;
    6. 	int j=0;
    7. 	
    8. 	p = L;
    9. 	while(p!=NULL && j
    10. 		p = p->next;
    11. 		j++;
    12. 	}
    13. 	
    14. 	//if(p==NULL)	return NULL;
    15. 	return p;
    16. }

    按值查找

     LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

             按值查找的方法与按位查找略有不同，按值查找需要遍历整个链表，之后在每次遍历时都要判断一下其是否为我们需要寻找的值，如果遍历到NULL还未找到，则说明该值不在链表之中。

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

    单链表建立

            前面我们学习了那么多的单链表操作，那么我们对单链表一定有了一个基本的了解；那么我们在初始化链表时，一定要将很多个结点相连到一起，那么我们该如何实现该问题呢？ 在这里我们提供头插法和尾插法两种方法。

    头插法

            如下图所示，头插法顾名思义也就是从头部开始插入，我们每次插入一个新的元素，都需要从其头部插入（如果是不含头结点的链表，我们需要更改其头指针）；这样逐个的插入。 

     

            不过这样每次插入头部方法，会使我们先插入链表的结点在后面，而后插入的结点在链表的前面。这个可以用于链表的逆置。

            由于是需要一个一个插入，其总的时间复杂度为O(n)。

    1. //头插法建立
    2. LinkList List_HeadInsert(LinkList &L) {	
    3. 	LNode *s; int x;
    4. 	L = (LinkList)malloc(sizeof(LNode)) ;
    5. 	L->next = NULL;	//创建头结点 
    6. 	
    7. 	cin >> x ;
    8. 	
    9. 	while(x != 9999){
    10. 		s = (LinkList)malloc(sizeof(LNode));
    11. 		s->data = x;
    12. 		s->next = L->next ;
    13. 		L->next = s ;
    14. 		cin >> x ;
    15. 	}
    16. 	
    17. 	return L ;
    18. }

    尾插法

             至于尾插法，顾名思义就是在链表的尾部插入一个结点；这种插入方法我们需要时刻更改尾部结点的指针指向，所以我们需要一个指针一直指向尾部结点，方便我们去更改；尾部插入的方法，其插入顺序和在链表中的排列顺序是相同的。

            由于是需要一个一个插入，其总的时间复杂度为O(n)。

    1. //尾插法建立
    2. LinkList List_TailInsert(LinkList &L) {
    3. 	int x;
    4. 	cin >> x;
    5. 	
    6. 	L = (LinkList)malloc(sizeof(LNode));
    7. 	LNode *s, *r = L;
    8. 	
    9. 	while(x!=9999) {
    10. 		s = (LNode *)malloc(sizeof(LNode));
    11. 		s->data = x;
    12. 		r->next = s;
    13. 		r = s;
    14. 		cin >> x;
    15. 	}
    16. 	
    17. 	r->next = NULL;
    18. 	return L;
    19. }

     单链表代码

    含头结点单链表代码

     

    1. //2.3 链表 单链表（带头节点） 
    2.  
    3. #include
    4.  
    5. using namespace std ;
    6.  
    7. //结点
    8. typedef struct LNode{
    9. 	int data;
    10. 	struct LNode *next;
    11. }LNode, *LinkList; 
    12.  
    13. //头插法建立
    14. LinkList List_HeadInsert(LinkList &L) {	
    15. 	LNode *s; int x;
    16. 	L = (LinkList)malloc(sizeof(LNode)) ;
    17. 	L->next = NULL;	//创建头结点 
    18. 	
    19. 	cin >> x ;
    20. 	
    21. 	while(x != 9999){
    22. 		s = (LinkList)malloc(sizeof(LNode));
    23. 		s->data = x;
    24. 		s->next = L->next ;
    25. 		L->next = s ;
    26. 		cin >> x ;
    27. 	}
    28. 	
    29. 	return L ;
    30. }
    31.  
    32. //尾插法建立
    33. LinkList List_TailInsert(LinkList &L) {
    34. 	int x;
    35. 	cin >> x;
    36. 	
    37. 	L = (LinkList)malloc(sizeof(LNode));
    38. 	LNode *s, *r = L;
    39. 	
    40. 	while(x!=9999) {
    41. 		s = (LNode *)malloc(sizeof(LNode));
    42. 		s->data = x;
    43. 		r->next = s;
    44. 		r = s;
    45. 		cin >> x;
    46. 	}
    47. 	
    48. 	r->next = NULL;
    49. 	return L;
    50. }
    51.  
    52. //插入 : 在第i个位置插入(含头节点） 
    53. bool ListInsert(LinkList &L, int i, int e) {
    54. 	if(i<1)	return false ;
    55. 	LNode *p ;	//扫描指针
    56. 	int j = 0;	//带头节点 从0开始
    57. 	
    58. 	p = L;
    59. 	while(p != NULL && j < i-1) {	//找到 i-1 的位置 
    60. 		p = p->next ;
    61. 		j++;
    62. 	}
    63. 	
    64. 	if(p == NULL)	return false;
    65. 	
    66. 	LNode *s = (LNode *)malloc(sizeof(LNode)) ;
    67. 	s->data = e;
    68. 	s->next = p->next;
    69. 	p->next = s;
    70. 	return true;
    71. } 
    72.  
    73. //删除 : 删除第i个位置的元素 并返回 （含头节点）
    74. bool ListDelete(LinkList &L, int i, int &e) {
    75. 	if(i<1)	return false;
    76. 	LNode *p;
    77. 	int j=0;
    78. 	
    79. 	p = L;
    80. 	
    81. 	while(p != NULL && j < i-1) {
    82. 		p = p->next;
    83. 		j++;
    84. 	}
    85. 	
    86. 	if(p == NULL) return false;
    87. 	
    88. 	e = p->next->data;
    89. 	p->next = p->next->next;
    90. 	
    91. 	/*
    92. 	LNode *q = p->next;
    93. 	e = q->data;
    94. 	p->next = q->next;
    95. 	free(q);
    96. 	*/
    97. 	
    98. 	return true;
    99. } 
    100.  
    101. //删除指定节点 (删除 p 节点） 
    102. bool DeleteNode(LNode *p) {
    103. 	if(p == NULL) return false;
    104. 	
    105. 	p->data = p->next->data;
    106. 	p->next = p->next->next;
    107. 	
    108. 	/*
    109. 	LNode *q;
    110. 	q = p->next;
    111. 	p->data = q->data;
    112. 	p->next = q->next;
    113. 	free(q);
    114. 	*/
    115. 	
    116. 	return true;
    117. }
    118.  
    119. //按位查找 
    120. LNode *GetElem(LinkList L, int i){
    121. 	if(i<0)		return NULL;
    122. 	
    123. 	LNode *p;
    124. 	int j=0;
    125. 	
    126. 	p = L;
    127. 	while(p!=NULL && j
    128. 		p = p->next;
    129. 		j++;
    130. 	}
    131. 	
    132. 	//if(p==NULL)	return NULL;
    133. 	return p;
    134. } 
    135.  
    136. //按值查找 
    137. LNode *LocateElem(LinkList L, int e) {
    138. 	LNode *p = L; //初始化
    139. 	while(p != NULL && p->data != e) {
    140. 		p = p->next;
    141. 	} 
    142. 	
    143. 	return p;
    144. } 
    145.  
    146. //展示当前链表
    147. void ShowList(LinkList L) {
    148. 	LNode *p = L->next;
    149. 	
    150. 	while(p!=NULL) {
    151. 		cout << p->data << " ";
    152. 		p = p->next;
    153. 	}
    154. 	
    155. 	cout << endl;
    156. } 
    157.  
    158. //初始化 
    159. bool InitList(LinkList &L) {
    160. 	L = NULL;
    161. 	return true;
    162. }
    163.  
    164. int main(){
    165. 	
    166. 	LinkList L;
    167. 	
    168. 	InitList(L);	//初始化
    169. 	
    170. 	int x ;
    171. 	cout << "请选择头插（1、尾插（2："; 
    172. 	cin >> x ;
    173. 	if(x == 1) {
    174. 		cout << "头插法：" ;
    175. 		List_HeadInsert(L);		//头插法创建 
    176. 		ShowList(L);
    177. 	}
    178. 	else {
    179. 		cout << "尾插法： " ;
    180. 		List_TailInsert(L);		//尾插法创建
    181. 		ShowList(L);
    182. 	}	
    183. 	
    184. 	ListInsert(L, 2, 3);	//插入 
    185. 	ShowList(L);
    186. 	
    187. 	int e; 
    188. 	ListDelete(L, 2, e);	//删除
    189. 	ShowList(L);
    190. 	
    191. 	// GetElem(L, 3);	//查找按位
    192. 	ShowList(L);
    193. 	cout <<  GetElem(L, 3)->data << endl;
    194. 	
    195. 	// LocateElem(L, 3);	//按值查 
    196. 	ShowList(L);
    197. 	cout << LocateElem(L, 3)->data << endl;
    198. 	DeleteNode(LocateElem(L, 3));
    199. 	ShowList(L);
    200. 	 
    201. 	return 0;
    202. }

    不含头结点单链表代码

    1. //2.3 链表 单链表（不带头节点） 
    2.  
    3. #include
    4.  
    5. using namespace std ;
    6.  
    7. //结点
    8. typedef struct LNode{
    9. 	int data;
    10. 	struct LNode *next;
    11. }LNode, *LinkList; 
    12.  
    13. //头插法建立
    14. LinkList List_HeadInsert(LinkList &L) {	
    15. 	LNode *s; int x;
    16. 	cin >> x;
    17. 	L = (LinkList)malloc(sizeof(LNode)) ;	
    18. 	L->data = x;
    19. 	L->next = NULL;
    20. 	cin >> x;
    21. 	
    22. 	while(x != 9999){
    23. 		s = (LinkList)malloc(sizeof(LNode));
    24. 		s->data = x;
    25. 		s->next = L ;
    26. 		L = s ;
    27. 		cin >> x ;
    28. 	}
    29. 	
    30. 	return L ;
    31. }
    32.  
    33. //尾插法建立
    34. LinkList List_TailInsert(LinkList &L) {
    35. 	
    36. 	int x ;
    37. 	cin >> x;
    38. 	
    39. 	L = (LinkList)malloc(sizeof(LNode));
    40. 	LNode *s, *r = L;
    41. 	L->data = x;
    42. 	cin >> x;
    43.  
    44. 	while(x!=9999) {
    45. 		s = (LNode *)malloc(sizeof(LNode));
    46. 		s->data = x;
    47. 		r->next = s;
    48. 		r = s;
    49. 		cin >> x;
    50. 	}
    51. 	
    52. 	r->next = NULL;
    53. 	return L;
    54. }
    55.  
    56. //插入 : 在第i个位置插入(不含头节点） 
    57. bool ListInsert(LinkList &L, int i, int e) {
    58. 	if(i<1)	return false ;
    59. 	 
    60. 	LNode *p ;	//扫描指针
    61. 	int j = 1;	//不带头节点 从1开始
    62. 	
    63. 	p = L;
    64. 	
    65. 	if(i==1) {
    66. 		LNode *s = (LNode *)malloc(sizeof(LNode)) ;
    67. 		s->data = e;
    68. 		s->next = p;
    69. 		p = s;
    70. 		return true;
    71. 	}
    72. 	
    73. 	while(p != NULL && j < i-1) {	//找到 i-1 的位置 
    74. 		p = p->next ;
    75. 		j++;
    76. 	}
    77. 	
    78. 	if(p == NULL)	return false;
    79. 	
    80. 	LNode *s = (LNode *)malloc(sizeof(LNode)) ;
    81. 	s->data = e;
    82. 	s->next = p->next;
    83. 	p->next = s;
    84. 	return true;
    85. } 
    86.  
    87. //删除 : 删除第i个位置的元素 并返回 （不含头节点）
    88. bool ListDelete(LinkList &L, int i, int &e) {
    89. 	if(i<1)	return false;
    90. 	LNode *p;
    91. 	int j=1;
    92. 	
    93. 	p = L;
    94. 	
    95. 	if(i==1) {
    96. 		e = p->data ;
    97. 		L = p->next;
    98. 	} 
    99. 	
    100. 	while(p != NULL && j < i-1) {
    101. 		p = p->next;
    102. 		j++;
    103. 	}
    104. 	
    105. 	if(p == NULL) return false;
    106. 	
    107. 	e = p->next->data;
    108. 	p->next = p->next->next;
    109. 	
    110. 	/*
    111. 	LNode *q = p->next;
    112. 	e = q->data;
    113. 	p->next = q->next;
    114. 	free(q);
    115. 	*/
    116. 	
    117. 	return true;
    118. } 
    119.  
    120. //删除指定节点 (删除 p 节点） 
    121. bool DeleteNode(LNode *p, LinkList &L) {
    122. 	if(p == NULL) return false;
    123. 	
    124. 	if(p == L) {
    125. 		L = p->next;
    126. 	}
    127. 	
    128. 	p->data = p->next->data;
    129. 	p->next = p->next->next;
    130. 	
    131. 	/*
    132. 	LNode *q;
    133. 	q = p->next;
    134. 	p->data = q->data;
    135. 	p->next = q->next;
    136. 	free(q);
    137. 	*/
    138. 	
    139. 	return true;
    140. }
    141.  
    142. //按位查找 
    143. LNode *GetElem(LinkList L, int i){
    144. 	if(i<=0)		return NULL;
    145. 	
    146. 	LNode *p;
    147. 	int j=1;
    148. 	
    149. 	p = L;
    150. 	while(p!=NULL && j
    151. 		p = p->next;
    152. 		j++;
    153. 	}
    154. 	
    155. 	//if(p==NULL)	return NULL;
    156. 	return p;
    157. } 
    158.  
    159. //按值查找 
    160. LNode *LocateElem(LinkList L, int e) {
    161. 	LNode *p = L; //初始化
    162. 	while(p != NULL && p->data != e) {
    163. 		p = p->next;
    164. 	} 
    165. 	
    166. 	return p;
    167. } 
    168.  
    169. //展示当前链表
    170. void ShowList(LinkList L) {
    171. 	LNode *p = L;
    172. 	
    173. 	while(p!=NULL) {
    174. 		cout << p->data << " ";
    175. 		p = p->next;
    176. 	}
    177. 	
    178. 	cout << endl;
    179. } 
    180.  
    181. //初始化 
    182. bool InitList(LinkList &L) {
    183. 	L = NULL;
    184. 	return true;
    185. }
    186.  
    187. int main(){
    188. 	
    189. 	LinkList L;
    190. 	
    191. 	InitList(L);	//初始化
    192. 	
    193. 	int x ;
    194. 	cout << "请选择头插（1、尾插（2："; 
    195. 	cin >> x ;
    196. 	if(x == 1) {
    197. 		cout << "头插法：" ;
    198. 		List_HeadInsert(L);		//头插法创建 
    199. 		ShowList(L);
    200. 	}
    201. 	else {
    202. 		cout << "尾插法： " ;
    203. 		List_TailInsert(L);		//尾插法创建
    204. 		ShowList(L);
    205. 	}	
    206. 	
    207. 	ListInsert(L, 2, 3);	//插入 
    208. 	ShowList(L);
    209. 	
    210. 	int e; 
    211. 	ListDelete(L, 2, e);	//删除
    212. 	ShowList(L);
    213. 	
    214. 	// GetElem(L, 3);	//查找按位
    215. 	ShowList(L);
    216. 	cout <<  GetElem(L, 3)->data << endl;
    217. 	
    218. 	// LocateElem(L, 3);	//按值查 
    219. 	ShowList(L);
    220. 	cout << LocateElem(L, 3)->data << endl;
    221. 	DeleteNode(LocateElem(L, 3), L);
    222. 	ShowList(L);
    223. 	 
    224. 	return 0;
    225. } 
    226.  
    227.

    运行结果如下： 

             第一行是我们头插法后单链表的展示，我们可以看出，其头插法的存储会与我们输入链表的顺序相反；第二行就是我们的插入操作结果，第三行就是我们的删除操作结果，第4-7行就是查找第三个位置的元素和3在什么位置并返回；最后一行则是删除第三个结点。

             第一行是我们尾插法后单链表的展示，我们可以看出，其尾插法的存储会与我们输入链表的顺序相同（为1-7）；第二行就是我们的插入操作结果（在第二个位置插入3），第三行就是我们的删除操作结果（删除第二个位置的结点），第4-7行就是查找第三个位置的元素和3在什么位置并返回（这里我们查找3所在的位置和第三个元素与头插法查找的结果就是不同的）；最后一行则是删除第三个结点。

             到这里我们对于单链表的基本学习也就结束了，至于一些其他的操作例如：求长度，这些简单的循环我们就不在这里过多叙述；相信各位大佬通过上面的学习，可以轻松的实现这些简单的功能。

  • 相关阅读:
    搭建源码调试环境—RocketMQ源码分析（一）
    RabbitMQ事务机制和确认机制
    Spring面试题16：Spring框架中的单例bean是线程安全的吗?Spring框架中bean的生命周期？哪些是重要的bean生命周期方法？
    笔记-fabric.js的使用-参考官网
    【C#】项目中添加png文件时，设置其“生成操作”（Build Action）属性
    【DAY04 软考中级备考笔记】数据结构基本结构和算法
    小微企业低成本获客攻略，媒介盒子无偿分享
    【广州华锐互动】VR景区云游：打造沉浸式网上虚拟旅游体验
    2023年上半年系统集成项目管理工程师什么时候报考?（附具体报名步骤）
    LeetCode数据流的第 K 大数值
  • 原文地址：https://blog.csdn.net/qq_62464995/article/details/136108445