[数据结构与算法] C语言单向链表正向、反向、排序插入和链表逆转

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C语言单向链表正向、反向、排序插入和链表逆转 -> 正文阅读

[数据结构与算法]C语言单向链表正向、反向、排序插入和链表逆转

一、链表定义

单向链表就像一根绳子一样，拿出来是一串，顺序表也是一串，但和单向链表不同，顺序表是连续存储的，不用管下一个节点位置在哪，反正就在后面，而单向链表在内存中是不连续存储的，看到有坑就放进去，然后还得保存放置的地址。所以，定义单向链表就是定义一个结构体，结构体里有两个成员，一个是要保存的数据，一个是下一个节点的地址。

typedef struct NODE{
	int data;
	struct NODE *next;
}NODE,*NEXT;

我这里用typedef取别名取了一个结构体和结构体指针，定义的这个结构体NODE其实没什么作用，主要是开辟内存的时候malloc函数要传入一个整数，用sizeof求NODE需要要多大的字节然后传入到malloc中获得一个节点的空间。

二、初始化链表

初始化一个链表，就先初始化链表的头，有头才能有后面的节点。

    int temp;
	NEXT node = NULL;
	node = GetNewNode();
	scanf("%d",&temp);
	getchar();
	node->data = temp;

这里定义了一个temp变量，用来获取从键盘中输入的数据，定义一个指针node先指向NULL，然后获取一个节点的内存并返回给node，最后通过键盘输入获取数据赋值给data，第一个节点就算完成了。
getNewNode函数

NEXT GetNewNode(){
	NEXT node = malloc(sizeof(NODE));
	node->next = NULL;//先让该节点的下一个节点为空
	return node;
}

三、输入链表

初始化完成后，就开始从键盘中一个一个输入节点的数据了，这里就要用的while循环了，因为我这里数据定义的是int型的，所以我加了一个跳出循环的条件，就是输入非数字的时候跳出循环，结束输入。
具体代码如下：

while(1){
		NEXT next = GetNewNode();
		if(scanf("%d",&temp)==1){
			getchar();
		    next->data = temp;
		    InsertNodeLast(node,next);//新节点插入到旧节点后面
		    ShowNode(node);
		}else{
			printf("停止输入");
		    break;	}
	}

原理就是先获取一个新节点内存，然后给新节点赋值，然后让新节点插到旧节点后面，最后输出该链表所有内容。
其中注意的点：如果scanf其实是有返回值的，如果返回值为1就是输入的数字，还有，scanf停止输入的条件是用户按了回车键，也就是输入了换行符“\n”就会停止从输入缓冲区中读取数据，但是换行符会一直存在输入缓冲区不会被丢弃，影响下一次的输入，所以可以使用getchar把换行符从输入缓冲区给拿出来。
下面给出InsertNodeLast函数代码

void InsertNodeLast(NEXT old,NEXT new){
	while(old->next!=NULL){//遍历链表，直到到最后一个节点
		old = old->next;
	}
	old -> next = new;
	new->next = NULL;
}

ShowNode函数

void ShowNode(NEXT node){
	while(node->next!=NULL){
		printf("%d\t",node->data);
		node = node->next;
	}
	printf("%d\t",node->data);//跳出循环的时候其实还有最后一个节点没输出
	printf("\n");
}

四、反向、排序插入和逆转

1、反向插入
反向插入就是创建一个节点让它插在链表的最前面，当头结点。
我的实现方法就是：把新节点的值和原来头节点的值进行互换，然后让原来头结点指向新节点，让新节点指向原来头结点的下一个节点，这样就算插入到第一个了。
原理图大概就是这个样子。
在这里插入图片描述
给出实现代码：

//从前面插入
void InsertNodeFirst(NEXT old,NEXT new){
	int temp = old->data;
	old->data = new->data;
	new->data = temp;
	new->next = old->next;
	old->next = new;
}

2、排序插入
我这里实现的是按从小到大排序，从大到小排序可以看完之后自己去设计。
原理主要是三种情况，将新节点的数据与链表中的数据进行逐一比较，
①比第一个节点数据还小，那就直接插到最前面；
②比最后一个数据还大，那就直接插到最后面；
③中间值，那就先找到一个比他小的节点，然后判断该节点的后面的一个节点是否比新节点大，如果满足就插在两个节点中间，不满足继续遍历。
这里给出第三种情况的示意图
在这里插入图片描述
给出该函数完整代码：

//从小到大排序
int InsertNodeSort(NEXT old,NEXT new){
	NEXT f = old;
	if(old->next==NULL){//如果是第二个节点
		if(old->data>new->data)//如果小于第一个节点就插到前面
			InsertNodeFirst(old,new);
		else
			InsertNodeLast(old,new);//否则插到后面
	}else{
		while(old->next!=NULL){//如果要插入的不是第二个节点
			if(f->data>new->data){//先判断是否第一个节点大于新节点
				int temp = old->data;
				old->data = new->data;
				new->data = temp;
				new->next = old->next;
				old->next = new;
				return 1;//跳出循环
			}else if(old->data<=new->data){//如果节点小于或等于新节点
				NEXT n = old->next;//该节点的下一个节点
				if(n->data>new->data||n == NULL){//判断下一个节点是否大于新节点
					old->next = new;//大于就插到该节点和下一个节点之间
					new->next = n;
					return 1;//跳出循环，插入结束
				}
			}
			old = old->next;
	    }
	    old->next = new;
	    new->next = NULL;
	}
	return 1;
}

这里的返回值没什么意义，主要是用来结束函数执行，break只能跳出循环，return是跳出整个函数。
3、链表逆转
这个功能真得写了我很久很久，试了很多种方法，一直都是失败的，最终想到一种很简单的方法，原理简单概括就是：将头结点的后面的节点一个一个往前面移动，最终返回最后移到前面的节点的地址，赋值给原来的头节点。
原理图：
在这里插入图片描述
画得不太清除，因为有些东西真的是只能意会不能言传。
给出代码帮助理解：

//翻转
NEXT ReverseNode(NEXT node){
	NEXT nodes = node ->next;
	NEXT temp = node;//定义一个指针始终指在链表最前面
	NEXT rt;
	while(node->next!=NULL){
		node->next = nodes->next;
		nodes->next = temp;//指向最前面的节点
		temp = nodes;//将最前面的节点再赋值给temp
		rt = temp;//temp作为返回值
		nodes = node ->next;
	}
	return rt;
}

五、总结

其实只要理解链表的结构，不管怎么插入或者怎么输出都能写出算法，最后给出完整代码，不理解可以私信或者评论。

#include<stdio.h>
#include<stdlib.h>
typedef struct NODE{
	int data;
	struct NODE *next;
}NODE,*NEXT;
NEXT GetNewNode(){
	NEXT node = malloc(sizeof(NODE));
	node->next = NULL;
	return node;
}
//从前面插入
void InsertNodeFirst(NEXT old,NEXT new){
	int temp = old->data;
	old->data = new->data;
	new->data = temp;
	new->next = old->next;
	old->next = new;
}
//从后面插入
void InsertNodeLast(NEXT old,NEXT new){
	while(old->next!=NULL){//遍历链表，直到到最后一个节点
		old = old->next;
	}
	old -> next = new;
	new->next = NULL;
}
//从小到大排序
int InsertNodeSort(NEXT old,NEXT new){
	NEXT f = old;
	if(old->next==NULL){//如果是第二个节点
		if(old->data>new->data)//如果小于第一个节点就插到前面
			InsertNodeFirst(old,new);
		else
			InsertNodeLast(old,new);//否则插到后面
	}else{
		while(old->next!=NULL){//如果要插入的不是第二个节点
			if(f->data>new->data){//先判断是否第一个节点大于新节点
				int temp = old->data;
				old->data = new->data;
				new->data = temp;
				new->next = old->next;
				old->next = new;
				return 1;//跳出循环
			}else if(old->data<=new->data){//如果节点小于或等于新节点
				NEXT n = old->next;//该节点的下一个节点
				if(n->data>new->data||n == NULL){//判断下一个节点是否大于新节点
					old->next = new;//大于就插到该节点和下一个节点之间
					new->next = n;
					return 1;//跳出循环，插入结束
				}

			}
			old = old->next;
	    }
	    old->next = new;
	    new->next = NULL;

	}
	return 1;
	
}
//翻转
NEXT ReverseNode(NEXT node){
	NEXT nodes = node ->next;
	NEXT temp = node;//定义一个指针始终指在链表最前面
	NEXT rt;
	while(node->next!=NULL){
		node->next = nodes->next;
		nodes->next = temp;//指向最前面的节点
		temp = nodes;//将最前面的节点再赋值给temp
		rt = temp;//temp作为返回值
		nodes = node ->next;

	}
	return rt;
}

void ShowNode(NEXT node){
	while(node->next!=NULL){
		printf("%d\t",node->data);
		node = node->next;
	}
	printf("%d\t",node->data);
	printf("\n");
}
int main(){
	int temp;
	NEXT node = NULL;
	node = GetNewNode();
	scanf("%d",&temp);
	getchar();
	node->data = temp;
	ShowNode(node);
	while(1){
		NEXT next = GetNewNode();
		if(scanf("%d",&temp)==1){
			getchar();
		    next->data = temp;
		    InsertNodeLast(node,next);//调用不同方法插入方式不同
		    ShowNode(node);
		}else{
		    break;	}
	}
	ShowNode(node);
	node = ReverseNode(node);
	ShowNode(node);
	return 0;
}