单链表的创建

忘是亡心i 2023-05-31 04:59 5阅读 0赞

## **学习链表需要了解的基本知识点：** ##

**首先**，想要熟练使用链表，就要知道两大类基本知识点：  
**1. 指针 2.结构体**  
(如果对两个知识点有疑惑请百度一下，没有什么问题是百度一下解决不了的，如果有就百度两下，哈哈)

结构体定义部分：  
`struct node{int num;struct node *next };`  
带头节点的链表示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NwcmltZXNwbHVz_size_16_color_FFFFFF_t_70]  
上图就是链接后每个节点的状态，单链表每个节点保存下一个节点的地址(struct node \*next)，环环相扣，因此称之为链表。知道这两个知识点后，我们就可以开始写链表了。首先是定义结构体，struct node\{…\}; **千万不要忘了结构体定义后的分号！**

## 关于typedef的问题： ##

Typedef是用来为复杂的声明定义简单的别名，比如typedef struct node\}\{…\}Lnode;  
这句话的意思即使用Lnode来代替struct node这句声明。  
好处是什么？  
我认为有如下：  
**首先：** 在复杂的程序里，很容易打错一些字，比如把struct打成stuct,把struct node 打成struct ndoe blablabla~，用typedef可以避免这种错误发生。  
**其次：** 简单省事，struct node \*head; 和 Lnode \*head;都是定义头节点的作用，但显然后者更加便捷。(当然不怕麻烦并且足够自信的话用第一个也完全没问题)

## 关于创建单链表(createlink)： ##

如果想使用一个链表，我们就需要知道他的头在哪，因此在Createlink()函数中，需要返回head(也就是这条链子的头部)，这样顺着头我们就可以一直找到链表的每一个元素，直到尾部(p若为最后一个链结的话，那么p->next==NULL)。  
因为需要返回head这个指针，因此需要这样写：  
（可能有小伙伴会有疑问：都说通过传递指针给函数就可以改变实参的值，还有必要返回指针吗？有兴趣的读者可以跳转到我的这篇博客：[关于传递指针与传递引用作参数的测试][Link 1]）

struct node *createlink()
    {
        
    	.....//这些是创建的过程
    	return head;
    }
    
     
      
     
      
       1 
       2 
       3 
       4 
       5

返回值类型搞定之后，我们便可以进入创建链表的环节。

**单链表分为两种：**  
（1）不带头节点的链表：此种链表的head即保存第一个数据，访问时从head开始。不利于删除或者添加指定位置数据的操作。  
（2）带头节点的链表：此种链表保存数据是从head->next开始的，head中并未保存有数据，访问时自然head->next开始，优点就是方便操作。

**这里先以不带头节点的链表的创建为例：**  
首先，我们需要有一个结构体指针来保存头节点，方便于之后的使用，所以：struct node \*head;  
注意：这里的head是不能变的，,**不变的意思不是他的值不变，而是他永远固定在链表的首位，作为链表的头部**，方便之后的索引。  
因此，当我们每新加入一个元素时，不是直接更新head的值。不妨用一个结构体指针pnew来记录新加入的值，通过旧节点pend与新节点的相连来构造一个链表，示意图如下：  
![这里写图片描述][70]  
显然，pend所指向的单位，实际就是上一次的pnew（可以理解为，pnew作为新元素被成功加入到链表之后，它便变成了旧节点，两个字概括为：**更替**）  
欸？是不是还有一个变量忘了声明？没错，那就是整型n，用来表示新加入的值。这样我们便可以通过输入n并且给节点赋值，只要输入不为-1，那么继续进行输入，否则终止循环。

**不带头节点单链表代码的实现：**  
首先，我们定义head,最初的时候链表还没有添加元素，因此head=NULL;  
然后，输入一个元素代表将要添加的值。判断元素是否符合条件（这里以元素>=0为条件），如果满足，就进入添加环节。

scanf("%d",&num);
    while(num>=0)
    {
        
    //操作
    	scanf("%d",&num);
    }
    
     
      
     
      
       1 
       2 
       3 
       4 
       5 
       6

在循环中，因为要添加值，所以要先为pnew分配内存，这样才能对pnew进行赋值操作。

pnew=(struct node*)malloc(sizeof(struct node));
    pnew->num=num;
    pnew->next=NULL; //新创建的指针的下一个位置还没有定
    
     
      
     
      
       1 
       2 
       3

因为我们想要创建不带头节点的单链表，因此如果是第一次添加值（第一次添加的判断是，如果head指向NULL，证明还未加入元素），那么head就应该指向pnew的位置，然后pnew（也就是head）的位置变为旧位置pend。

if(head==NULL)
    {
        
    	head=pnew;
    	pend=head;
    }
    
     
      
     
      
       1 
       2 
       3 
       4 
       5

如果不是第一次添加了，那么此时存放旧地址的就应该是pend，观察上图，只需要如下操作进行连接就可以了：

else{
        
    	pend->next=pnew;
    	pend=pnew;//一定注意，操作的位置是内存
    	//因此进行上面一步之后，pend->next这块内存已经有了指向
    }
    
     
      
     
      
       1 
       2 
       3 
       4 
       5

这样，便成功创建了不带头节点的单链表。  
**完整代码：**

scanf("%d",&num);
    while(num>=0)
    {
        
    	pnew=(struct node*)malloc(sizeof(struct node));
    	pnew->num=num;
    	pnew->next=NULL; //新创建的指针的下一个位置还没有定
    	if(head==NULL)
    	{
        
    		head=pnew;
    		pend=head;
    	}
    	else
    	{
        
    		pend->next=pnew;
    		pend=pnew;
    	}
    	scanf("%d",&num);
    }
    
     
      
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18

**带头节点单链表代码的实现：**  
带有头节点的单链表创立，只需稍微改变代码即可。  
既然是带有头节点，那么头节点里肯定是不需要赋值的，因此在创建时，我们直接最开始就让头节点作为旧节点，这样头节点就可以不用被赋值了。

head=(struct node*)malloc(sizeof(struct node));
    head->next=NULL;
    pend=head;
    scanf("%d",&n);
    While(n!=-1)
    {
        
    	pnew=(struct node *)malloc(sizeof(struct node));	//这里一定要为pnew开辟内存！
    	//想象一下，你无法int *a;后直接赋值a=3;必须先分配内存，同理。
    	pnew->num=n;
    	pnew->next=NULL;//新节点指向空，因为后面还没有元素加入
    	pend->next=pnew;	//旧节点的指针指向新节点
    	pend=pnew;		//新节点变为旧节点
    	scanf(“%d”,&n);
    }
    
     
      
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NwcmltZXNwbHVz_size_16_color_FFFFFF_t_70]: /images/20230531/c76ecc2403de4cbc9459fc2d220249ed.png
[Link 1]: https://blog.csdn.net/cprimesplus/article/details/89547879
[70]: /images/20230531/13211a219f64437089380eaeac7e73af.png

单链表的创建

发表评论取消回复

还没有评论，来说两句吧...

相关阅读