头插法创建链表
最编程
2024-06-11 12:21:02
...
要使用链表,就要先创建一个链表,这里只说单链表。先介绍一下头插法创建单链表链表。假如我们现在要在链表中插入一些数据:1、2、3、4、5,并从键盘输入这些数据,
最后数据存入到链表中是反过来的,即{5,4,3,2,1},因为头插法每次都是在头部插入数据的,先插入1,此时表中数据为{1};接着在头部插入2,此时表中数据数据为{2,1};
再在头部插入3,此时表中数据数据为{3,2,1};以此类推,最后,表中数据的顺序和你输入的顺序是相反的。
为了弄明白头插法的原理,我在网上找了一张图来帮助理解头插法,看图
所谓头插法,就是每次新加入的节点,都插入在表头结点的后面,插在表中第一个结点的前面,图中obj结点就插在了a0结点的前面,以此类推。最后你会发现表中数据的顺序与
你输入的数据顺序是相反的。
而头插法创建链表又分为两种情况,一种是已知节点个数,还有一种是未知节点个数,下面用代码来展示一下。先说一下未知结点个数的情况,即不确定输入的结点个数,看代码
1 #include<stdio.h> 2 #include<stdlib.h> 3 typedef struct LNode 4 { 5 int data; 6 struct LNode *next; 7 }LNode,*LinkList; 8 9 LinkList create_LinkList() 10 { 11 LinkList head; //声明头指针 12 int e; 13 char ch; 14 LNode * p=NULL; 15 head=(LinkList)malloc(sizeof(LNode)); //头插法创建链表需要创建表头 16 head->next=NULL;
do{
scanf("%d",&e); 20 p=(LinkList)malloc(sizeof(LNode)); 21 p->data=e; 22 p->next=head->next; //插入在头部,让当前节点的next指向下一个结点 23 head->next=p; //表头指针指向当前结点 24 p=p->next; //p也指向下一个节点
}while((ch=getchar())!='\n'); 27 return head; //返回头指针 28 } 29 int main() 30 { 31 LinkList p; 32 p=create_LinkList(); 33 p=p->next; //链表有头节点,让p跳过头结点,指向链表中的第一个结点 34 while(p!=NULL) 35 { 36 printf("%d ",p->data); 37 p=p->next ; 38 } 39 printf("\n"); 40 return 0; 41 }
结果如下:
还有在已知结点个数的情况下,用代码展示一下
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define N 10 //结点个数 4 typedef struct LNode 5 { 6 int data; 7 struct LNode *next; 8 }LNode,*LinkList; 9 10 LinkList create_LinkList() 11 { 12 LinkList head; //声明头指针 13 LNode * p=NULL; 14 head=(LinkList)malloc(sizeof(LNode)); //需要创建表头结点 15 head->next=NULL; 16 for(int i=1;i<=N;i++) 17 { 18 p=(LinkList)malloc(sizeof(LNode)); 19 scanf("%d",&p->data); 20 p->next=head->next; 21 head->next=p; 22 p=p->next; 23 } 24 return head; 25 } 26 int main() 27 { 28 LinkList p; 29 p=create_LinkList(); 30 p=p->next; 31 while(p!=NULL) 32 { 33 printf("%d ",p->data); 34 p=p->next ; 35 } 36 printf("\n"); 37 return 0; 38 }
结果如下:
通过观察两次的结果,可以看出用头插法创建链表时都会产生这种情况:即插入的数据与插入的顺序相反。
上一篇: 单个链表的反转(表头插入和就地反转)
下一篇: 插入 golang 链接表头
推荐阅读
-
头插法
-
头插法
-
头插法和尾插法
-
使用头部插值和尾部插值方法创建、删除和遍历单个链表
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
头插法
-
头插法详细图解
-
头插法创建链表
-
数据结构 - 头插值逆转单链表 - 空间复杂度为 O(1)
-
HashMap 链表插入方式 → 头插为何改成尾插 ?