从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

四种创建单链表的方法_单链表的创建

作者：从前慢现在也慢 | 2024-04-22 21:18:51

踩

单链表的创建

学习了这么久的数据结构，终于把链表吃透啦，下面是我整理的四种创建单链表的的方法

以及一些非常容易犯的错误，让我们一起来看看吧~

一、单链表的分类

单链表一共有两种，一个是带头结点的单链表，还有一个是不带头结点的单链表

总的来说，带头结点的单链表相对于不带头结点的单链表来说，更加方便对链表基本操作的实现

（带头结点的单链表操作起来更方便，所以很多时候我们都是用带头结点的单链表）

二、单链表的初始化

单链表的初始化，我们分不带头结点和带头结点两种情况

2.1 初始化不带头结点的单链表

不带头结点的单链表，说明头指针指向了第一个有效的结点


PNode Init_1_Node(){
	PNode head;          
	head=NULL;      //因为不带头结点，所以我们只要让头结点为空
	return head;
}

2.2 初始化带头结点的单链表

带头结点的单链表，头指针要指向头结点（头结点不存放数值，可将头结点理解为无效结点）


PNode Init_2_Node(){
	PNode head;
	head=(PNode)malloc(sizeof(Node));     //申请一个头结点
	head->next=NULL;                      //头结点指针域指向空
	return head;
}

三、单链表的创建

单链表的创建，我们分不带头结点和带头结点来介绍，具体再分为头插法和尾插法两种方法

3.1 创建不带头结点的单链表

3.1.1 头插法

头插法嘛，顾名思义，每次都在链表的前面插入，这样最先输入的结点最后输出，最后输入的结点最先输出。例如你输入的是1，2，3。那么打印出来的将是3，2，1。


void Creat_1_Node(PNode *head){       //不带头结点我们用头指针的地址来保存单链表
	int i,n;
	printf("（头插法）请输入不带头结点的链表结点个数："); 
	scanf("%d",&n);                   //输入不带头结点单链表的结点个数
	for(i=1;i<=n;i++){      
		PNode Pnew=(PNode)malloc(sizeof(Node));    //创建一个新的结点 
		Pnew->next=NULL;                         //指针域指向空
		printf("第%d个结点的元素为：",n+1-i); 
	    scanf("%d",&Pnew->data);
		if(*head==NULL){              //判断头指针是否指向空
			*head=Pnew;               //如果是则让头指针指向第一个有效结点
		}else{                        //当头指针指向非空时
			Pnew->next=*head;         //将新的结点插入到头指针所指结点的前面
			*head=Pnew;               //头指针指向新插入的结点
		}                             
	}                     //例如你输入  1 2 3 
}                        //实际上链表是 3 2 1  这是因为你是在前面插入了新的结点

3.1.2 尾插法

尾插法呢就比较好理解了，每次都在链表的最后插入一个新的结点就好了，这个是按顺序的，输入什么最后就输出什么。例如输入1，2，3。输出将是1，2，3。


void Creat_2_Node(PNode *head){
	PNode Last;           //尾插法的话，我们要有一个时刻指向尾结点的指针
	int i,n;
	printf("（尾插法）请输入不带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));
		Pnew->next=NULL;
		printf("第%d个结点的元素为：",i); 
		scanf("%d",&Pnew->data);
		if(*head==NULL){        //判断头指针是否指向空，这是必要的
			*head=Pnew;         //头指针指向第一个有效结点
			Last=Pnew;          //因为此时只有一个结点，所以Last指向这个结点就好
		}else{                  //当头指针指向不是空的时候
			Last->next=Pnew;    //尾结点指针域指向新插入的结点
			Last=Pnew;          //将新结点赋给尾结点（插入的结点变成新的尾结点）
		}
	}
}

3.2 创建带头结点的单链表

3.2.1 头插法

带头结点的单链表使用头插法创建时，一定要注意 Pnew->next=p->next 和 p->next=Pnew 两行代码不能颠倒！Pnew->next=p->next 的意思是将p后面的所有结点都接到了要插入的新结点的后面，p->next=Pnew 的意思是将新结点接到p（头结点）的后面。如果将两行代码颠倒了，那么头结点后面的所有结点将丢失，这样无论你创建多大的链表，其实最后都只有两个结点（一个是头结点，没什么用，还有一个就是你输入的最后一个数据），其他的结点都丢失了


void Creat_3_Node(PNode head){
	PNode p=head;          //将head赋给p，p是头结点，不保存数据，为无效结点
	int i,n;
	printf("（头插法）请输入带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));  //创建新的结点
		Pnew->next=NULL;                         //指针域指向空
		printf("第%d个结点的元素为：",n+1-i); 
		scanf("%d",&Pnew->data);                
		Pnew->next=p->next;       //这里注意一定要先把p后面的所有结点接到Pnew后面
		p->next=Pnew;             //再执行把Pnew连接到p后面
	}
}

3.2.2 尾插法

尾插法就不需要担心数据丢失的问题了，因为是在尾结点后面插入（尾结点后面没有其他结点）


void Creat_4_Node(PNode head){
	PNode p=head;
	PNode Last;          //需要一个时刻指向尾结点的指针
	Last=p;
	int i,n;
	printf("（尾插法）请输入带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));
		Pnew->next=NULL;
		printf("第%d个结点的元素为：",i); 
		scanf("%d",&Pnew->data);
		Last->next=Pnew;      //尾结点指针域指向要插入的结点
		Last=Pnew;            //新插入的结点成为新的尾结点
	}	
}

四、单链表的打印

这里分为不带头结点和带头结点两种情况，需要分别打印

4.1 打印不带头结点的单链表


void Print_1_Node(PNode head){
	PNode p=head;            //不带头结点，p就是第一个有效元素
	printf("新的链表为：");
	while(p!=NULL){           //采用循环挨个打印
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

4.2 打印带头结点的单链表


void Print_2_Node(PNode head){
	PNode p=head->next;       //带头结点，p应该为第一个有效结点
	printf("新的链表为：");
	while(p!=NULL){
		printf("%d ",p->data);    //打印
		p=p->next;
	}
	printf("\n");
}

五、代码实现

5.1 完整代码


#include<stdio.h>
#include<malloc.h>
typedef struct Node{
	int data;
	struct Node * next;
}Node,*PNode;
PNode Init_1_Node(){
	PNode head;
	head=NULL;
	return head;
}
PNode Init_2_Node(){
	PNode head;
	head=(PNode)malloc(sizeof(Node));
	head->next=NULL;
	return head;
}
void Creat_1_Node(PNode *head){
	int i,n;
	printf("（头插法）请输入不带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));
		Pnew->next=NULL;
		printf("第%d个结点的元素为：",n+1-i); 
	    scanf("%d",&Pnew->data);
		if(*head==NULL){
			*head=Pnew;
		}else{
			Pnew->next=*head;
			*head=Pnew;
		}
	}
}
void Creat_2_Node(PNode *head){
	PNode Last;
	int i,n;
	printf("（尾插法）请输入不带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));
		Pnew->next=NULL;
		printf("第%d个结点的元素为：",i); 
		scanf("%d",&Pnew->data);
		if(*head==NULL){
			*head=Pnew;
			Last=Pnew;
		}else{
			Last->next=Pnew;
			Last=Pnew;
		}
	}
}
void Creat_3_Node(PNode head){
	PNode p=head;
	int i,n;
	printf("（头插法）请输入带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));
		Pnew->next=NULL;
		printf("第%d个结点的元素为：",n+1-i); 
		scanf("%d",&Pnew->data);
		Pnew->next=p->next;
		p->next=Pnew;
	}
}
void Creat_4_Node(PNode head){
	PNode p=head;
	PNode Last;
	Last=p;
	int i,n;
	printf("（尾插法）请输入带头节点的链表结点个数：");
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		PNode Pnew=(PNode)malloc(sizeof(Node));
		Pnew->next=NULL;
		printf("第%d个结点的元素为：",i); 
		scanf("%d",&Pnew->data);
		Last->next=Pnew;
		Last=Pnew;
	}	
}
void Print_1_Node(PNode head){
	PNode p=head;
	printf("新的链表为：");
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
void Print_2_Node(PNode head){
	PNode p=head->next;
	printf("新的链表为：");
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
int main(){
	PNode H1,H2,H3,H4;
	H1=Init_1_Node();
	Creat_1_Node(&H1);
	Print_1_Node(H1);
	H2=Init_1_Node();
	Creat_2_Node(&H2);
	Print_1_Node(H2);
	H3=Init_2_Node();
	Creat_3_Node(H3);
	Print_2_Node(H3);
	H4=Init_2_Node();
	Creat_4_Node(H4);
	Print_2_Node(H4);
    return 0;
}

5.2 运行结果

六、总结

综上所述，我们一共有四种创建单链表的方法，其实头插法基本不用，我们用的最多的是尾插法创建带头结点的单链表。

在创建单链表的时候，要注意几个问题：

1.一定要初始化单链表，不管是带头结点还是不带头结点的单链表，不然会出现输入一半程序终结的情况（暂时不知道是什么情况）

2.创建不带头结点的单链表，要用到指针的指针，否则没法保存地址。

3.创建不带头结点的单链表，一定要先判断头指针是否指向空

附：系列文章

序号	文章目录	直达链接
1	顺序表的十个基本操作（全）	https://want595.blog.csdn.net/article/details/127139051
2	单链表的十三个基本操作（全）	https://want595.blog.csdn.net/article/details/127139598
3	四种创建单链表的方法	https://want595.blog.csdn.net/article/details/127017405
4	删除重复元素（顺序表、单链表）	https://want595.blog.csdn.net/article/details/127023468
5	两个有序表的合并（三种方法）	https://want595.blog.csdn.net/article/details/127104602
6	一元多项式相加问题（两种方法）	https://want595.blog.csdn.net/article/details/127131351
7	约瑟夫环问题（三种方法）	https://want595.blog.csdn.net/article/details/127019472
8	顺序栈与链栈	https://want595.blog.csdn.net/article/details/127035609
9	顺序循环队列与链队列	https://want595.blog.csdn.net/article/details/127040115
10	后缀表达式的转换（栈的运用）	https://want595.blog.csdn.net/article/details/127088466
11	简单表达式的计算（两种方法）	https://want595.blog.csdn.net/article/details/127121720
12	next数组（详细求法）	https://want595.blog.csdn.net/article/details/127217629
13	BF算法（具体应用）	https://want595.blog.csdn.net/article/details/127138894
14	串的模式匹配相关问题（BF算法、KMP算法）	https://want595.blog.csdn.net/article/details/127182721
15	二叉树的遍历（七种方法）	https://want595.blog.csdn.net/article/details/127472445

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/470561