C语言单向链表的建立与遍历

c语言程序设计实验课已经接近尾声，对于刚刚接触到c语言的我们来说也比较高了，这几节课的链表对相信大家也听得比较头痛。所以希望这篇博客能真正帮助到大家。下文我将利用一个题目，以及链表的解法来加深大家对链表的理解与应用。

题目描述
输入n个有序（从小到大）的整数序列，再插入一个整数，使整个序列保持有序（从小到大）。所有的整数都在int范围内。
输入样例

8
1 2 3 5 6 7 8 9
4

输出样例

1 2 3 4 5 6 7 8 9

分析：相信大家做了这么久，已经有很多方法可以实现了（数组），但上面说了，是要用链表方法做，所以下面我将对链表的实现和遍历进行解释，如果有错误和问题可以私聊我（大佬别喷）

链表的实现首先我们要搞懂他的单位是什么？是一个通过结构体实现的“区块”（还记得听的区块链讲座吗？虽然这不是一个东西）这个结构体里面可以有很多东西（字符，字符串，数字……想要几个都可以）但是，所有的结构体都有一个这样的结构体类型的指针，可以理解为：一个桶子，桶里可以装很多类型的东西，桶子的底部有一个挂钩，用来钩住下一个桶子。（见下图）

因为本题中每个块中只有一个数，所以结构体中只有int 和 next（桶子里只有int和next）。
所以我们的结构体就建好了。

struct Node
{
	int num;
	Node *next;//注意：因为指针指向也是这个结构体，所以结构体的类型也是Node
}

下面我们就是要构建链表了。
我们先要输入n个数，也就是说我们需要n个区块，即：

while(n--)
{
	构造链表
}

怎么造？
现在我们是空白的，什么都还没有，更别说填数了，所以我们要向系统申请一片结构体大小的区域（内存）（每次接下一个区块的时候都要申请一次）

newp=(struct node *)malloc(sizeof(struct node));

可能很多人读不懂这句话，解释见下图

为了能再链表中走，我们需要设置几个指针：head（链表头）tail（链表尾）newp（新建的区块）p（遍历时链表的每个区块）

由于一开始一个区块都没有所以我们要把head和tail都滞空，即令head=tail=NULL（注意大写）。
申请链表（见上文）。
填充链表，这一步就很简单了

scanf("%d",&p->data);

这时候，我们第一个区块已经有了，这就是我们的链表头，所以

if(head==NULL) head=newp;

下面还有没有区块，当前还不清楚，所以我们的链表指针（桶上的钩子）要指向哪里呢？不知道就滞空。

newp->next=NULL;

这第一个区块就完成了（因为只有一个，所以头尾都是这个）。

我们接下来通过while循环，要把每一个区块连成链，上面已经有了建立区块和填充区块的过程，所以只需要重复操作就行了。
唯一的区别就是，刚才的尾区块tail需要指向这个新建的区块newp

if(head==NULL) head=newp;
else tail->next=newp;

最后再把那个tail指向这个新建的newp

填充操作同上，所以这里就可以写成构建链表的全部代码了。

struct node *head,*tail,*p,*newp;
int n;
head=tail=NULL;
scanf("%d",&n);
while(n--)
{
	newp=(struct node *)malloc(sizeof(struct node));
	if(head==NULL) head=newp;
	else tail->next=newp;
	scanf("%d",&newp->data);
	newp->next=NULL;
	tail=newp;
}

输入那个需要插入的数。

int b;
scanf("%d",&b);

上面我们已经定义了一个用来遍历链表的指针*p，所以开始遍历链表，首先将这个p赋初值head
往下走的操作就是p=p->next
p从一个区块，通过那个钩子（p->next），走到了下一个区块(p=p->next)
当遇到某一个区块所指向的下一区块的值大于这个b时，进行链表的插入操作,首先是申请这么一个桶（见上文），然后是前一区块和这个新区快地址的变化。下面通过图解来分布解释一下。



注意指针变换的先后顺序。
附上代码：

p=head;
while(p!=NULL)
{
	if(p->next == NULL || p->next->data >b)
	{
		newp=(struct node *)malloc(sizeof(struct node));
		newp->data=b;
		newp->next=p->next;
		p->next=newp;
		break;
	}
	p=p->next;
}

这里就插入完了！（^ _ ^）！
最后的部分就是通过p指针，再从头遍历一遍，进行链表的输出，当然，上面的插入都会了，那下面的遍历自然不成问题了。
下面是全部的代码。

#include<stdio.h>
#include<stdlib.h>//加载头文件
struct node//定义结构体，也就是上文说的桶子
{
	int data;
	struct node *next;//结构体指针，用于指向下一个区块，也就是上面说的桶后面的钩子
};
int main()
{
	struct node *head,*tail,*p,*newp;//结构体变量*head（链表头）*tail（链表尾）*newp（新建的区块）*p（遍历时链表的每个区块）
	int n;//有n个有序数据
	head=tail=NULL;//初始化链表头尾
	scanf("%d",&n);
	while(n--)//构建n个区块的链表
	{
		newp=(struct node *)malloc(sizeof(struct node));//申请动态内存，上文有解释
		if(head==NULL) head=newp;//如果当前区块是唯一一个区块
		else tail->next=newp;//连接下一个区块
		scanf("%d",&newp->data);//填充区块
		newp->next=NULL;//最后一个区块滞空
		tail=newp;//当前区块就是尾区块
	}
	int b;//需要插入的数
	scanf("%d",&b);
	p=head;//初始化遍历指针
	while(p!=NULL)//当这个指针指到链尾的时候结束
	{
		if(p->next == NULL || p->next->data >b)//判断到最后一个区块或者遇到大于这个插入的数的区块时
		{
			newp=(struct node *)malloc(sizeof(struct node));
			newp->data=b;
			newp->next=p->next;
			p->next=newp;
			break;
		}//区块插入操作
		p=p->next;//继续往下走
	}
 	p=head;//遍历链表操作同上
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	return 0;
}

以上就是这个题的全部过程。
但链表一共有两种，由头到尾的为正向，也就是上面的，还有一种是由尾到头的逆向链表。下面我将解释一下逆向链表的构建和遍历过程。
申请内存和填充就不解释，和上面一样，不同的在于他的连接过程是从右往左的。

新建区块newp，同时新建的next指向head，然后再将head指向新建的next，然后重复上述操作就可以了。

while(构建条件)
    {
    	newp=(Node*)malloc(sizeof(Node));//申请区块
        newp->next=head;//新建区块next指向head
        head=newp;//head指向newp
    }

这就是逆向链表的构建过程，遍历与上面的一样，所以也可以再遍历一遍的时候再进行赋值，这数据上不就是正向的了吗？
——————————————————————————————
链表这个地方是指针，数据类型，控制语句的综合应用，所以比较难理解，但一定要理解，可以自己再纸上或者电脑上画一下图，有助于理解，而且中间许多步骤的顺序可以进行调换，大家可以仔细考虑一下，哪些可以，哪些不可以。