当前位置:   article > 正文

从图开始,理解单链表---完整c语言实现()_为节点s插入指针域赋值

为节点s插入指针域赋值

参考:大话数据结构
参考:创建单链表的头插法与尾插法详解
https://blog.csdn.net/NINIYUANJ123/article/details/89847543
个人理解链表的实质为多个结构体变量之间通过指针的连接。刚学数据结构,可能会存在错误。

单链表结构之头指针和头节点

首先,我们先区分一下头指针和头节点的区别:
在这里插入图片描述
图3-6-7是不带头节点的链表,可看到,头指针指向第一个节点的数据域。
在这里插入图片描述
图3-6-8/9是带头节点的链表,可看到头指针指向这个头节点的数据域,这个数据域里面可以不存任何信息,添加这个头节点的目的是方便对链表进行操作。
一般称图中a1所在的节点为首节点。
在这里插入图片描述

创建链表中的节点

typedef struct student{    //创建链表中的每个节点,包括数据域和指针域;
    int score;//数据域;
    struct student *next;//指针域;
}Linklist;
  • 1
  • 2
  • 3
  • 4

这里需要注意的意思typedef关键字,typedef作用是为已有的数据类型定义一个新的类型名称,其语法格式为:typedef 已有类型名 新类型名表;
前面提过结构体也是一种数据类型,相比于我们熟悉的int等等基本类型,结构体类型是一种构造类型,因此可以用typedef为其重新起一个名字。在链表这里,这样做的目的是,之后就可以用新类型名Linklist去定义结构体变量了
看严蔚敏的书时,发现里面时这样写:
在这里插入图片描述
当时对这种写法纠结了很久,后来看了这两篇博客:对链表结构体定义LNode,*LinkList的理解烂烂三三才理解的。
总的来说,这两种一个时是对结构体类型起别名,一个是对结构体指针类型起别名。相当于:typedef struct Lnode Lnodetypedef struct Lnode* LinkList,当我们声明指向该结构体的指针变量时, 使用Lnode * pLinkList L 二者等价的。
在这里插入图片描述
书上的目的是,为了区分头节点和其他节点,让LinkList L特意指向头节点,其他普通节点用Lnode * p,后面在讲链表相关的操作时容易理解。
本篇笔记的代码没用这个。

遍历链表

先介绍简单的遍历链表的代码,后面的相关操作都会或多或少的包含这个遍历操作,只不过在循环条件那加了一点判断语句。下面这段代码应该是很好理解的。

void link_print(Linklist *list){
	Linklist *p = list; //定义一个临时指针p,刚开始时与头指针一样,都指向的是头节点;
	while(p!=NULL){
		printf("%d\n",p->score);
		p = p->next;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

在有头节点和无头结点时,这里遍历操作会存在一点不同,具体可看:
单链表创建且遍历之带头结点与不带头结点

单链表插入节点。

首先说一下我对书中几个概念的理解。

  • 如下图所示, 节点p以及节点p->next以及节点s实际上指的是指向该节点数据域的一个指针,一些书中称呼该节点时就把指针名当作该节点的名字。刚开始学链表的时候,这一块还是特别绕口的,后来通过画图,逐渐理解并记住了单链表的一些操作。
  • 说一下我关于指针"指向"相对应赋值号“=”理解,即表达式从左往右看,即为左边的指针指向右边的地址。其实也就是相当于把右边的地址值赋给左边的指针变量。那么画箭头的时候,就顺便可以把代码写出来了。
  • 关于指向p节点的指针和p节点中的指针,两者不是同一个概念,前者代表p,后者代表p->next。
  • 理解:因为每个节点都分为数据域和指针域,其中指针域里存放的是下一个节点的地址,故在下图(1)中,为s->next = p->next;

在这里插入图片描述
我们要把s节点插入到p节点和p->next节点之间。先进行第1步,把s节点中的指针(也就是s->next)指向p->next节点。对应语句就是 s->next = p->next。再进行第二步,再把p节点中的指针指向s节点,对应语句是 p->next = s
即关于插值的操作,为两句话:

s->next = p->next;
p->next = s;
  • 1
  • 2

注意,这两句的顺序不能反过来。假如先是p->next = s,这里p->next已经是指向了s节点,再进行 s->next = p->next时,相当于变成了 s->next=s,这样子是矛盾的。故切记这个顺序不能反,然后,就可以通过自己画图推理出这个插入的过程了,而不必反复地去看书了。
在链表中插入节点的代码:

void insert(Linklist *list,int n){
	Linklist *p = list;
	Linklist *s;
	int i = 0;
	while(i<n-1&&p->next){
		p=p->next;
		i++;
	}
	s = (Linklist*)malloc(sizeof(Linklist));
	printf("请输入插入的新节点的数据值:");
	scanf("%d",&s->score);
	s->next = p->next;
	p->next = s;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

单链表的创建过程-----头插法与尾插法

联系第二小节,一个单链表的创建过程实际上就是多个链表插入节点的过程,有点不同之处在于不断在头部插入节点和在不断在尾部插入节点。后面介绍头插法与尾插法时,均以带头节点的单链表为例,可以通过头插法的例子来理解一下加入头节点的好处。

头插法

加入头节点后,其实就和第一部分插入节点类似,只不过每次是在头节点和首节点之间插值,已插入的节点依次后移。
在这里插入图片描述
理解了第一部分的插入节点,这里也就好理解了。
关于头插法的代码:

#include<stdio.h>
#include<malloc.h>
typedef struct student{    //创建链表中的每个节点,包括数据域和指针域;
    int score;//数据域;
    struct student *next;//指针域;
}Linklist;

Linklist *creat(int n)//创建链表  ,为指针函数,返回的是一个指针
{
	Linklist *head,*node; //定义两个结构体指针
	head=(Linklist*)malloc(sizeof(Linklist));//为头节点开辟内存空间
	for(int i=0;i<n;i++)
	{
    	node=(Linklist*)malloc(sizeof(Linklist));//为每次新插入的节点分配内存空间;
    	scanf("%d",&node->score); //新节点数据域进行赋值
    	node->next=head->next;     //头插法:新节点中的指针指向head->next节点;
    	head->next=node;           //头插法:head中的指针指向新节点;
	}
	return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
尾插法:

即类似排队,每次新插入的节点都排在后面。这里需要定义一个尾指针r,如图所示。
在这里插入图片描述
这个看图也应该容易理解了。
尾插法代码:

Linklist *creat(int n)//创建链表  ,为指针函数,返回的是一个指针
{
	Linklist *head,*node,*end; //定义三个结构体指针
	head=(Linklist*)malloc(sizeof(Linklist));//为头节点开辟内存空间
	end=head; //刚开始时头节点同时也是尾节点
	for(int i=0;i<n;i++)
	{
    	node=(Linklist*)malloc(sizeof(Linklist));//为每次新插入的节点分配内存空间;
    	scanf("%d",&node->score); //新节点数据域进行赋值
    	end->next=node;     //尾插法:尾节点中的指针指向新插入的node
    	end=node;           //尾插法:尾指针挪到新插入的节点上来
	}
	end->next=NULL;         //循环结束后,尾节点中的指针指向空
	return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

单链表删除元素

如下图所示
在这里插入图片描述
删除数据ai所在的节点,只需要把 a i a_i ai所在的节点中的指针指向 a i + 1 a{_{i+1}} ai+1所在节点的数据域,用表达式描述即:p->next = p->next->next,两个箭头的符号在c程序中不存在定义,用q来代替这个p->next,即上式变为:

q = p->next; p->next = q->next;
删除链表中第i个位置节点的代码:
思路是1.从首节点开始,先找(遍历)到第i个节点;2.删除该节点

void delet(Linklist *list, int n){
	Linklist *p = list;
	Linklist *q;
	int i=1;
	while(i<n && p->next){ //  
	 p = p->next;
	 i++;
	}
	if(p->next == NULL){
		printf("待删除位置超出表长,不合理\n");	
	}
	else{
		q=p->next; //用q来代替;
		p->next = q->next; //p中的指针指向q中的指针
		free(q); //释放内存
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

还有一些操作就不放上来了,理解了上面的思想单链表应该就没问题了。总的代码如下:

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct student{
    	int score;//数据域;
    	struct student *next;//指针域;
    	}Linklist;
  
Linklist *creat(int n)//创建链表  ,为指针函数,返回的是一个指针
{
	Linklist *head,*node,*end; //定义三个结构体指针
	head=(Linklist*)malloc(sizeof(Linklist));//为头节点开辟内存空间
	end=head; //刚开始时头节点同时也是尾节点
	for(int i=0;i<n;i++)
	{
    	node=(Linklist*)malloc(sizeof(Linklist));//为每次新插入的节点分配内存空间;
    	scanf("%d",&node->score); //新节点数据域进行赋值
    	end->next=node;     //尾插法:尾节点中的指针指向新插入的node
    	end=node;           //尾插法:尾指针挪到新插入的节点上来
	}
	end->next=NULL;         //循环结束后,尾节点中的指针指向空
	return head;
}
	
void delet(Linklist *list, int n){
	Linklist *p = list;
	Linklist *q;
	int i=1;
	while(i<n && p->next){ //  
	 p = p->next;
	 i++;
	}
	if(p->next == NULL){
		printf("待删除位置超出表长,不合理\n");	
	}
	else{
		q=p->next; //用q来代替;
		p->next = q->next; //p中的指针指向q中的指针
		free(q); //释放内存
	}

}

void link_print(Linklist *list){
	Linklist *p = list; //定义一个临时指针p,刚开始时与头指针一样,都指向的是头节点;
	while(p->next != NULL){
		p = p->next;
		printf("%d\n",p->score);
	}
}

void insert(Linklist *list,int n){
	Linklist *p = list;
	Linklist *s;
	int i = 0;
	while(i<n-1&&p->next){
		p=p->next;
		i++;
	}
	s = (Linklist*)malloc(sizeof(Linklist));
	printf("请输入插入的新节点的数据值:");
	scanf("%d",&s->score);
	s->next = p->next;
	p->next = s;
}

int main(){
	Linklist *head;
        int n,i;
	i=2;//插入和删除的节点位置
	printf("请输入初始创建链表的长度:");
	scanf("%d\n",&n);
	head = creat(n);
	insert(head,i);
	link_print(head);
	printf("///\n");
	delet(head,i);
	link_print(head);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/802939
推荐阅读
相关标签
  

闽ICP备14008679号