单链表的创建–从零开始
本文最后更新于915天前,其中的信息可能已经有所发展或是发生改变。

学习链表需要了解的基本知识点:
首先,想要熟练使用链表,就要知道两大类基本知识点:

  1. 指针 2.结构体
    (如果对两个知识点有疑惑请百度一下,没有什么问题是百度一下解决不了的,如果有就百度两下,哈哈)

结构体定义部分:
Struct node{int num;struct node *next };

带头节点的链表示意图:

这里写图片描述

上图就是链接后每个节点的状态,单链表每个节点保存下一个节点的地址(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这个指针,因此需要这样写:

如果想使用一个链表,我们就需要知道他的头在哪,因此在Createlink()函数中,需要返回head(也就是这条链子的头部),这样顺着头我们就可以一直找到链表的每一个元素,直到尾部(p若为最后一个链结的话,那么p->next==NULL)。
因为需要返回head这个指针,因此需要这样写:

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

返回值类型搞定之后,我们便可以进入创建链表的环节。
单链表分为两种:
(1)不带头节点的链表:此种链表的head即保存第一个数据,访问时从head开始。不利于删除或者添加指定位置数据的操作。
(2)带头节点的链表:此种链表保存数据是从head->next开始的,head中并未保存有数据,访问时自然head->next开始,优点就是方便操作。
这里先以不带头节点的链表的创建为例:
首先,我们需要有一个结构体指针来保存头节点,方便于之后的使用,所以:struct node *head;
注意:这里的head是不能变的,,不变的意思不是他的值不变,而是他永远固定在链表的首位,作为链表的头部,方便之后的索引。
因此,当我们每新加入一个元素时,不是直接更新head的值。不妨用一个结构体指针pnew来记录新加入的值,通过旧节点pend与新节点的相连来构造一个链表,示意图如下:

这里写图片描述

显然,pend所指向的单位,实际就是上一次的pnew(可以理解为,pnew作为新元素被成功加入到链表之后,它便变成了旧节点,两个字概括为:更替
欸?是不是还有一个变量忘了声明?没错,那就是整型n,用来表示新加入的值。这样我们便可以通过输入n并且给节点赋值,只要输入不为-1,那么继续进行输入,否则终止循环。
不带头节点单链表代码的实现:
首先,我们定义head,最初的时候链表还没有添加元素,因此head=NULL;
然后,输入一个元素代表将要添加的值。判断元素是否符合条件(这里以元素>=0为条件),如果满足,就进入添加环节。

scanf("%d",&num);
while(num>=0)
{
//操作
    scanf("%d",&num);
}

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

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

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

if(head==NULL)
{
    head=pnew;
    pnew=pend;
}

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

scanf("%d",&num);
while(num>=0)
{
    pnew=(struct node*)malloc(sizeof(struct node));
    pnew->num=num;
    pnew->next=NULL; //新创建的指针的下一个位置还没有定
    if(head==NULL)
    {
        head=pnew;
        pnew=pend;
    }
    else
    {
        pend->next=pnew;
        pend=pnew;
    }
    scanf("%d",&num);
}

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

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);
}

点击数:108

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇